Itai Arad, Zeph Landau and Umesh Vazirani.
An improved area law for 1D frustration-free systems

Abstract: We present a new proof for the 1D area law for frustration-free systems with a constant gap, which exponentially improves the entropy bound in Hastings' 1D proof. For particles of dimension d, a spectral gap \eps>0 and interaction strength of at most J, our entropy bound is S <= O(1)X^3 log^8 X where X=(J log d)/ \eps, versus the e^{O(X)} in Hastings' proof. Our proof is completely combinatorial. It follows the simple proof of the commuting case, combining the detectability lemma with basic tools from approximation theory. In higher dimensions, we manage to slightly improve the bound, showing that the entanglement entropy between a region L and its surrounding is bounded by S <= O(1) |\partial L|^2 log^8|\partial L|, which in 2D is very close to the (trivial) volume-law.

Salman Beigi and Amin Gohari.
Information Causality is a Special Point in the Dual of the Gray-Wyner Region

Abstract: Information Causality puts restrictions on the amount of information learned by a party (Bob) in a one-way communication problem. Bob receives an index b, and after a one-way communication from the other party (Alice), tries to recover a part of Alice's input. Because of the possibility of cloning, this game in its completely classical form is equivalent to one in which there are several Bobs indexed by b, who are interested in recovering different parts of Alice's input string, after receiving a public message from her. Adding a private message from Alice to each Bob, and assuming that the game is played many times, we obtain the Gray-Wyner problem for which a complete characterization of the achievable region is known. In this paper, we first argue that in the classical case Information Causality is only a single point in the dual of the Gray-Wyner region. Next, we show that despite the fact that cloning is impossible in a general physical theory, the result from classical world carries over to any physical theory provided that it satisfies a new property. This new property of the physical theory is called the Accessibility of Mutual Information and holds in the quantum theory. It implies that the Gray-Wyner region completely characterizes all the inequalities corresponding to the game of Information Causality. In other words, we provide infinitely many inequalities that Information Causality is only one of them.

In the second part of the paper we prove that Information Causality leads to a non-trivial lower bound on the communication cost of simulating a given non-local box when the parties are allowed to share entanglement. We also consider the same problem when the parties are provided with preshared randomness. Our non-technical contribution is to comment that information theorists who have been interested in the area of control have independently studied the same problem in a different context from an information theoretic perspective, rather than a communication complexity one. Connecting these two lines of research, we report a formula that, rather surprisingly, gives an exact computable expression for the optimal amount of communication needed for sampling from a non-local distribution given infinite preshared randomness.

Salman Beigi and Robert Koenig.
Simplified instantaneous non-local quantum computation with applications to position-based cryptography

Abstract: Motivated by concerns that non-local measurements may violate causality, Vaidman has shown that any non-local operation can be implemented using local operations and a single round of simultaneously passed classical communication only. His protocols are based on a highly non-trivial recursive use of teleportation. Here we give a simple proof of this fact, reducing the amount of entanglement required from a doubly exponential to an exponential amount. We also prove a linear lower bound on the amount of entanglement consumed for the implementation of a certain non-local measurement.
These results have implications for position-based cryptography: any scheme becomes insecure if the adversaries share an amount of entanglement scaling exponentially in the number of communicated qubits. Furthermore, certain schemes are secure under the assumption that the adversaries have at most a linear amount of entanglement and are required to communicate classically.

Aleksandrs Belovs.
Span Programs for Functions with Constant-Sized 1-certificates

Abstract: Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph.

We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit.

We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity O(n^{35/27}) that is better than O(n^{13/10}) of the best previously known algorithm by Magniez et al.

Dominic Berry, Richard Cleve and Sevag Gharibian.
Discrete simulations of continuous-time query algorithms that are efficient with respect to queries, gates and space

Abstract: We show that any continuous-time quantum query algorithm whose total query time is T and whose driving Hamiltonian is implementable with G gates can be simulated by a discrete-query quantum algorithm using the following resources: * O(T log T / loglog T) queries * O(T G polylog T) 1- and 2-qubit gates * O(polylog T) qubits of space. This extends previous results where the query cost is the same or better, but where the orders of the second and third resource costs are at least T^2 polylog T and T polylog T respectively. These new bounds are useful in circumstances where abstract black-box query algorithms are translated into concrete algorithms with subroutines substituted for the black-box queries. In these circumstances, what matters most is the total gate complexity, which can be large if the cost of the operations performed between the queries is large (even if the number of queries is small). Our bound implies that if the implementation cost of the driving Hamiltonian is small, the total gate complexity is not much more than the query complexity.

Robin Blume-Kohout.
Paranoid tomography: Confidence regions for quantum hardware

Abstract: Many ``paranoid'' quantum information processing protocols, such as fault tolerance and cryptography, require rigorously validated quantum hardware. We use tomography to characterize and calibrate such devices. But point estimates of the state or gate implemented by a device -- which are the end result of all current tomographic protocols -- can never provide the rigorously reliable validation required for fault tolerance or QKD. We need region estimators. Here, I introduce likelihood-ratio confidence region estimators, and show that (unlike ad hoc techniques such as the bootstrap) they are absolutely reliable and near-optimally powerful, as well as convenient and simple to implement.

Fernando Brandao, Aram Harrow and Michal Horodecki.
Local random quantum circuits are approximate polynomial-designs

Abstract: We prove that local random quantum circuits acting on n qubits composed of polynomially many nearest neighbor two-qubit gates form an approximate unitary poly(n)-design. Previously it was unknown whether random quantum circuits were a t-design for any t > 3.

The proof is based on an interplay of techniques from quantum many-body theory, representation theory, and the theory of Markov chains. In particular we employ a result of Nachtergaele for lower bounding the spectral gap of frustration-free quantum local Hamiltonians; a quasi-orthogonality property of permutation matrices; and a result of Oliveira which extends to the unitary group the path-coupling method for bounding the mixing time of random walks.

We also consider pseudo-randomness properties of local random quantum circuits of small depth and prove they constitute a quantum poly(n)-copy tensor product expander. The proof also rests on techniques from quantum many-body theory, in particular on the detectability lemma of Aharonov, Arad, Landau, and Vazirani.

We give two applications of the results. Firstly we show the following pseudo- randomness property of efficiently generated quantum states: almost every state of n qubits generated by circuits of size n.k cannot be distinguished from the maximally mixed state by circuits of size n^((k+4)/6); this provides a data-hiding scheme against computationally bounded adversaries. Secondly, we reconsider a recent argument of Masanes, Roncaglia, and Acin concerning local equilibration of time-envolving quantum systems, and strengthen the connection between fast equilibration of small subsystems and the circuit complexity of the unitary which diagonalizes the Hamiltonian.

Gilles Brassard, Peter Høyer, Kassem Kalach, Marc Kaplan, Sophie Laplante and Louis Salvail.
Merkle Puzzles in a Quantum World

Abstract: In 1974, Ralph Merkle proposed the first unclassified scheme for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break into their communication without spending a time proportional to N^2, which is quadratically more than the legitimate effort. We showed in an earlier paper that Merkle's schemes are completely insecure against a quantum adversary, but that their security can be partially restored if the legitimate parties are also allowed to use quantum computation: the eavesdropper needed to spend a time proportional to N^{3/2} to break our earlier quantum scheme. Furthermore, all previous classical schemes could be broken completely by the onslaught of a quantum eavesdropper and we conjectured that this is unavoidable. We give two novel key establishment schemes in the spirit of Merkle's. The first one can be broken by a quantum adversary that makes an effort proportional to N^{5/3} to implement a quantum random walk in a Johnson graph reminiscent of Andris Ambainis' quantum algorithm for the element distinctness problem. This attack is optimal up to logarithmic factors. Our second scheme is purely classical, yet it cannot be broken by a quantum eavesdropper who is only willing to expend effort proportional to that of the legitimate parties.

Sergey Bravyi.
Topological qubits: stability against thermal noise

Abstract: A big open question in the quantum information theory concerns feasibility of a self-correcting quantum memory. A user of such memory would need quantum computing capability only to write and read information. The storage itself requires no action from the user, as long as the memory is put in contact with a cold enough thermal bath.

In this talk I will review toy models of a quantum memory based on stabilizer code Hamiltonians with the topological order. These models describe quantum spin lattices with short-range interactions and a quantum code degenerate ground state. I will show how to derive a lower bound on the memory time for stabilizer Hamiltonians that have no string-like logical operators, such as the recently discovered 3D Cubic Code. This bound applies when the interaction between the spin lattice and the thermal bath can be described by a Markovian master equation. Our results demonstrate that the 3D Cubic Code is a marginally self-correcting memory: for a fixed temperature T the maximum memory time that can be achieved by increasing the lattice size grows exponentially with 1/T^2, whereas the optimal lattice size grows exponentially with 1/T.

We also compute the memory time of the 3D Cubic Code numerically using a novel error correction algorithm to simulate the readout step. The numerics suggests that our lower bound on the memory time is tight.

A unique feature of the studied stabilizer Hamiltonians responsible for the self-correction is the energy landscape that penalizes any sequence of local errors resulting in a logical error. The energy barrier that must be overcome to implement a bit-flip or phase-flip on the encoded qubit grows logarithmically with the lattice size. Such energy landscape also renders diffusion of topological defects over large distances energetically unfavorable.

This is a joint work with Jeongwan Haah (Caltech)

Sergey Bravyi and Robert Koenig.
Disorder-assisted error correction in Majorana chains

Abstract: It was recently realized that quenched disorder may enhance the reliability of topological qubits by reducing the mobility of anyons at zero temperature. Here we compute storage times with and without disorder for quantum chains with unpaired Majorana fermions - the simplest toy model of a quantum memory. Disorder takes the form of a random site-dependent chemical potential. The corresponding one-particle problem is a one-dimensional Anderson model with disorder in the hopping amplitudes. We focus on the zero-temperature storage of a qubit encoded in the ground state of the Majorana chain. Storage and retrieval are modeled by a unitary evolution under the memory Hamiltonian with an unknown weak perturbation followed by an error-correction step. Assuming dynamical localization of the one-particle problem, we show that the storage time grows exponentially with the system size. We give supporting evidence for the required localization property by estimating Lyapunov exponents of the one-particle eigenfunctions. We also simulate the storage process for chains with a few hundred sites. Our numerical results indicate that in the absence of disorder, the storage time grows only as a logarithm of the system size. We provide numerical evidence for the beneficial effect of disorder on storage times and show that suitably chosen pseudorandom potentials can outperform random ones.

Jop Briet and Thomas Vidick.
Explicit lower and upper bounds on the entangled value of multiplayer XOR games

Abstract: XOR games are the simplest model in which the nonlocal properties of entanglement manifest themselves. When there are two players, it is well known that the bias --- the maximum advantage over random play --- of entangled players is at most a constant times greater than that of classical players. Using tools from operator space theory, Perez-Garcia et al. [Comm. Math. Phys. 279 (2), 2008] showed that no such bound holds when there are three or more players: in that case the ratio of the entangled and classical biases can become unbounded and scale with the size of the game.

We give a new, simple and explicit (though still probabilistic) construction of a family of three-player XOR games for which entangled players have a large advantage over classical players. Our game has N^2 questions per player and entangled players have a factor of order sqrt(N) (up to log factors) advantage over classical players. Moreover, the entangled players only need to share a state of local dimension N and measure observables defined by tensor products of the Pauli matrices.

Additionally, we give the first upper bounds on the maximal violation in terms of the number of questions per player, showing that our construction is only quadratically off in that respect. Our results rely on probabilistic estimates on the norm of random matrices and higher-order tensors. Our results rely on probabilistic estimates on the norm of random matrices and higher-order tensors.

Harry Buhrman, Serge Fehr, Christian Schaffner and Florian Speelman.
The Garden-Hose Game and Application to Position-Based Quantum Cryptography

Abstract: We study position-based cryptography in the quantum setting. We examine a class of protocols that only require the communication of a single qubit and 2n bits of classical information. To this end, we define a new model of communication complexity, the garden-hose model, which enables us to prove upper bounds on the number of EPR pairs needed to attack such schemes. This model furthermore opens up a way to link the security of quantum position-based cryptography to traditional complexity theory.

Josh Cadney, Noah Linden and Andreas Winter.
Infinitely many constrained inequalities for the von Neumann entropy

Abstract: We exhibit infinitely many new, constrained inequalities for the von Neumann entropy, and show that they are independent of each other and the known inequalities obeyed by the von Neumann entropy (basically strong subadditivity). The new inequalities were proved originally by Makarychev et al. [Commun. Inf. Syst., 2(2):147-166, 2002] for the Shannon entropy, using properties of probability distributions. Our approach extends the proof of the inequalities to the quantum domain, and includes their independence for the quantum and also the classical cases.

André Chailloux and Iordanis Kerenidis.
Optimal Bounds for Quantum Bit Commitment

Abstract: Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4[Amb01]. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2}[Kit03] (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important and open question.

In this paper, we provide the optimal bound for quantum bit commitment. We first show a lower bound of approximately 0.739, improving Kitaev's lower bound. We then present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to 0.739. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + \eps in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(\eps). We then use the optimal quantum weak coin flipping protocol described by Mochon[Moc07]. To stress the fact that our protocol uses quantum effects beyond the weak coin flip, we show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.

André Chailloux and Or Sattath.
The Complexity of the Separable Hamiltonian Problem

Abstract: In this paper, we study variants of the canonical local hamiltonian problem where we have the additional promise that the witness is separable. We define two variants of the local problem. In the separable sparse hamiltonian problem, the hamiltonians are not necessarily local, but rather sparse. We show that this problem is QMA(2) complete. On the other hand, we consider another problem, the separable local hamiltonian problem and show that it is QMA complete. This should be compared to the local hamiltonian problem, and to the sparse hamiltonian problem which are both QMA complete. This is the first study of separable Hamiltonian problems which leads to new complete problems for both QMA and QMA(2) and might give some new ways of comparing these two classes.

Eric Chitambar, Wei Cui and Hoi-Kwong Lo.
Increasing Entanglement by Separable Operations and New Monotones for W-type Entanglement

Abstract: In this talk, we seek to better understand the structure of local operations and classical communication (LOCC) and its relationship to separable operations (SEP). To this end, we compare the abilities of LOCC and SEP for distilling EPR entanglement from one copy of an N-qubit W-class state (i.e. that of the form sqrt{x_0}|00...0> + sqrt{x_1}|10...0> +...+ sqrt{x_n}|00...1>). In terms of transformation success probability, we are able to quantify a gap as large as 37% between the two classes. Our work involves constructing new analytic entanglement monotones for W-class states which can increase on average by separable operations. Additionally, we are able to show that the set of LOCC operations, considered as a subset of the most general quantum measurements, is not closed. Extended Version: arXiv:1106.1208

Matthias Christandl and Renato Renner.
Reliable Quantum State Tomography

Abstract: Quantum state tomography is the task of inferring the state of a quantum system by appropriate measurements. Since the frequency distributions of the outcomes obtained from any finite number of measurements will generally deviate from their asymptotic limits, the estimation of the state can never be perfectly accurate, thus requiring the specification of error bounds. Furthermore, the individual reconstruction of matrix elements of the density operator representation of a state may lead to inconsistent results (e.g., operators with negative eigenvalues). Here we introduce a framework for quantum state tomography that enables the computation of accurate and consistent estimates and reliable error bars from a finite set of data and show that these have a well-defined and universal operational significance. The method does not require any prior assumptions about the distribution of the possible states or a specific parametrization of the state space. The resulting error bars are tight, corresponding to the fundamental limits that quantum theory imposes on the precision of measurements. At the same time, the technique is practical and particularly well suited for tomography on systems consisting of a small number of qubits, which are currently in the focus of interest in experimental quantum information science.

Toby Cubitt, Martin Schwarz, Frank Verstraete, Or Sattath and Itai Arad.
Three Proofs of a Constructive Commuting Quantum Lovasz Local Lemma

Abstract: The recently proven Quantum Lovasz Local Lemma generalises the well-known Lovasz Local Lemma. It states that, if a collection of subspace constraints are "weakly dependent", there necessarily exists a state satisfying all constraints. It implies e.g. that certain instances of the quantum kQSAT satisfiability problem are necessarily satisfiable, or that many-body systems with "not too many" interactions are never frustrated. However, the QLLL only asserts existence; it says nothing about how to find the state. Inspired by Moser's breakthrough classical results, we present a constructive version of the QLLL in the setting of commuting constraints, proving that a simple quantum algorithm converges efficiently to the required state. In fact, we provide three different proofs, all of which are independent of the original QLLL proof. So these results also provide independent, constructive proofs of the commuting QLLL itself, but strengthen it significantly by giving an efficient algorithm for finding the state whose existence is asserted by the QLLL.

Marcus P. Da Silva, Steven T. Flammia, Olivier Landon-Cardinal, Yi-Kai Liu and David Poulin.
Practical characterization of quantum devices without tomography

Abstract: Quantum tomography is the main method used to assess the quality of quantum information processing devices, but its complexity presents a major obstacle for the characterization of even moderately large systems. However, tomography generates much more information than is often sought. Taking a more targeted approach, we develop schemes that enable (i) estimating the fidelity of an experiment to a theoretical ideal description, (ii) learning which description within a reduced subset best matches the experimental data. Both these approaches yield a significant reduction in resources compared to tomography. In particular, we show how to estimate the fidelity between a predicted pure state and an arbitrary experimental state using only a constant number of Pauli expectation values selected at random according to an importance-weighting rule. In addition, we propose methods for certifying quantum circuits and learning continuous-time quantum dynamics that are described by local Hamiltonians or Lindbladians. This extended abstract is a synthesis of arXiv:1104.3835 and arXiv:1104.4695, which the reader can consult for complete details on the results, methods and proofs.

Nilanjana Datta, Min-Hsiu Hsieh and Mark Wilde.
Quantum rate distortion, reverse Shannon theorems, and source-channel separation

Abstract: We derive quantum counterparts of two key theorems of classical information theory, namely, the rate distortion theorem and the source-channel separation theorem. The rate-distortion theorem gives the ultimate limits on lossy data compression, and the source-channel separation theorem implies that a two-stage protocol consisting of compression and channel coding is optimal for transmitting a memoryless source over a memoryless channel. In spite of their importance in the classical domain, there has been surprisingly little work in these areas for quantum information theory. In the present work, we prove that the quantum rate distortion function is given in terms of the regularized entanglement of purification. Although this formula is regularized, at the very least it demonstrates that Barnum's conjecture on the achievability of the coherent information for quantum rate distortion is generally false. We also determine single-letter expressions for entanglement-assisted quantum rate distortion. Moreover, we prove several quantum source channel separation theorems. The strongest of these are in the entanglement-assisted setting, in which we establish a necessary and sufficient condition for transmitting a memoryless source over a memoryless quantum channel up to a given distortion.

Thomas Decker, Gábor Ivanyos, Miklos Santha and Pawel Wocjan.
Hidden Symmetry Subgroup Problems

Abstract: We advocate a new approach of addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the Hidden Symmetry Subgroup Problem (HSSP), which is a generalization of the well-studied Hidden Subgroup Problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.

Guillaume Duclos-Cianci, Héctor Bombin and David Poulin.
Equivalence of Topological Codes and Fast Decoding Algorithms

Abstract: Two topological phases are equivalent if they are connected by a local unitary transformation. In this sense, classifying topological phases amounts to classifying long-range entanglement patterns. We show that all 2D topological stabilizer codes are equivalent to several copies of one universal phase: Kitaev's topological code. Error correction benefits from the corresponding local mappings.

Omar Fawzi, Patrick Hayden, Ivan Savov, Pranab Sen and Mark Wilde.
Advances in classical communication for network quantum information theory

Abstract: Our group has developed new techniques that have yielded significant advances in network quantum information theory. We have established the existence of a quantum simultaneous decoder for two-sender quantum multiple access channels by using novel methods to deal with the non-commutativity of the many operators involved, and we have also applied this result in various scenarios, included unassisted and assisted classical communication over quantum multiple access channels, quantum broadcast channels, and quantum interference channels. Prior researchers have already considered classical communication over quantum multiple-access and broadcast channels, but our work extends and in some cases improves upon this prior work. Also, we are the first to make progress on the capacity of the quantum interference channel, which is a channel with two senders and two receivers, where one sender is interested in communicating with one receiver and the other sender with the other receiver. The aim of the proposed talk at QIP 2012 is to summarize this recent work and its applications as well as to discuss new avenues for network quantum information theory that may make use of these results.

Rodrigo Gallego, Lars Würflinger, Antonio Acín and Miguel Navascués.
An operational framework for nonlocality

Abstract: Since the advent of the first quantum information protocols, entanglement was recognized as a key ingredient for quantum information purposes, necessary for quantum computation or cryptography. A framework was developed to characterize and quantify entanglement as a resource based on the following operational principle: entanglement among N parties cannot be created by local operations and classical communication, even when N-1 parties collaborate. More recently, nonlocality has been identified as another resource, alternative to entanglement and necessary for device-independent quantum information protocols. We introduce a novel framework for nonlocality based on a similar principle: nonlocality among N parties cannot be created by local operations and shared randomness even when N-1 parties collaborate. We then show that the standard definition of multipartite nonlocality, due to Svetlichny, is inconsistent with this operational approach: according to it, genuine tripartite nonlocality could be created by two collaborating parties. We then discuss alternative definitions for which consistency is recovered.

Rodrigo Gallego, Lars Erik Würflinger, Antonio Acín and Miguel Navascués.
Quantum correlations require multipartite information principles

Abstract: Identifying which correlations among distant observers are possible within our current description of Nature, based on quantum mechanics, is a fundamental problem in Physics. Recently, information concepts have been proposed as the key ingredient to characterize the set of quantum correlations. Novel information principles, such as, information causality or non-trivial communication complexity, have been introduced in this context and successfully applied to some concrete scenarios. We show in this work a fundamental limitation of this approach: no principle based on bipartite information concepts is able to single out the set of quantum correlations for an arbitrary number of parties. Our results reflect the intricate structure of quantum correlations and imply that new and intrinsically multipartite information concepts are needed for their full understanding.

Sevag Gharibian and Julia Kempe.
Hardness of approximation for quantum problems

Abstract: The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact strongly hard to approximate. Our results thus yield the first known hardness of approximation results for a quantum complexity class. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999].

Gus Gutoski and Xiaodi Wu.
Parallel approximation of min-max problems with applications to classical and quantum zero-sum games

Abstract: This paper presents an efficient parallel algorithm for a new class of min-max problems based on the matrix multiplicative weight (MMW) update method. Our algorithm can be used to find near-optimal strategies for competitive two-player classical or quantum games in which a referee exchanges any number of messages with one player followed by any number of additional messages with the other. This algorithm considerably extends the class of games which admit parallel solutions and demonstrates for the first time the existence of a parallel algorithm for any game (classical or quantum) in which one player reacts adaptively to the other.

As a direct consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a new class of semidefinite programs whose feasible region consists of n-tuples of semidefinite matrices that satisfy a .transcript-like. consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP = PSPACE. It is noteworthy that our algorithm establishes a new way, called the min-max approach, to solve SDPs in contrast to the primal-dual approach to SDPs used in the original proof of QIP = PSPACE.

Jeongwan Haah.
Local stabilizer codes in three dimensions without string logical operators

Abstract: We suggest concrete models for self-correcting quantum memory by reporting examples of local stabilizer codes in 3D that have no string logical operators. Previously known local stabilizer codes in 3D all have string-like logical operators, which make the codes non-self-correcting. We introduce a notion of "logical string segments" to avoid difficulties in defining one dimensional objects in discrete lattices. We prove that every string-like logical operator of our code can be deformed to a disjoint union of short segments, and each segment is in the stabilizer group.

Esther Haenggi and Marco Tomamichel.
The Link between Uncertainty Relations and Non-Locality

Abstract: Two of the most intriguing features of quantum physics are the uncertainty principle and the occurrence of non-local correlations. The uncertainty principle states that there exist pairs of non-compatible measurements on quantum systems such that their outcomes cannot be simultaneously predicted by any observer. Non-local correlations of measurement outcomes at different locations cannot be explained by classical physics, but appear in quantum mechanics in the presence of entanglement. Here, we show that these two essential properties of quantum mechanics are quantitatively related. Namely, we provide an entropic uncertainty relation that gives a lower bound on the uncertainty of the binary outcomes of two measurements in terms of the maximum Clauser-Horne-Shimony-Holt value that can be achieved using the same measurements. We discuss an application of this uncertainty relation to certify a quantum source using untrusted devices.

Rahul Jain and Nayak Ashwin.
A quantum information cost trade-off for the Augmented Index

Abstract: In this work we establish a trade-off between the amount of (classical and) quantum information the two parties necessarily reveal about their inputs in the process of the computing Augmented Index, a natural variant of the Index function. A surprising feature of this trade-off is that it holds even under a distribution on inputs on which the function value is 'known in advance'. In fact, this is the price paid by any protocol that works correctly on a ``hard'' distribution. We show that quantum protocols that compute the Augmented Index function correctly with constant error on the uniform distribution, either Alice reveals Omega(n/t) information about her n-bit input, or Bob reveals Omega(1/t) information about his (log n)-bit input, where t is the number of messages in the protocol, even when the inputs are drawn from an ``easy'' distribution, the uniform distribution over inputs which evaluate to 0.

The classical version of this result has implications for the space required by streaming algorithms---algorithms that scan the input sequentially only a few times, while processing each input symbol quickly using a small amount of space. It implies that certain context free properties need space Omega(sqrt(n)/T) on inputs of length n, when allowed T unidirectional passes over the input. The quantum version would have similar consequences, provided a certain information inequality holds.

Andrew Landahl, Jonas Anderson and Patrick Rice.
Fault-tolerant quantum computing with color codes

Abstract: We present and analyze protocols for fault-tolerant quantum computing using color codes. To process these codes, no qubit movement is necessary; nearest-neighbor gates in two spatial dimensions suffices. Our focus is on the color codes defined by the 4.8.8 semiregular lattice, as they provide the best error protection per physical qubit among color codes. We present circuit-level schemes for extracting the error syndrome of these codes fault-tolerantly. We further present an integer-program-based decoding algorithm for identifying the most likely error given the (possibly faulty) syndrome. We simulated our syndrome extraction and decoding algorithms against three physically-motivated noise models using Monte Carlo methods, and used the simulations to estimate the corresponding accuracy thresholds for fault-tolerant quantum error correction. We also used a self-avoiding walk analysis to lower-bound the accuracy threshold for two of these noise models. We present two methods for fault-tolerantly computing with these codes. In the first, many of the operations are transversal and therefore spatially local if two-dimensional arrays of qubits are stacked atop each other. In the second, code deformation techniques are used so that all quantum processing is spatially local in just two dimensions. In both cases, the accuracy threshold for computation is comparable to that for error correction. Our analysis demonstrates that color codes perform slightly better than Kitaev's surface codes when circuit details are ignored. When these details are considered, we estimate that color codes achieve a threshold of 0.082(3)%, which is higher than the threshold of 1.3 times 10^{-5} achieved by concatenated coding schemes restricted to nearest-neighbor gates in two dimensions [Spedalieri and Roychowdhury, Quant. Inf. Comp. 9, 666 (2009)] but lower than the threshold of 0.75% to 1.1% reported for the Kitaev codes subject to the same restrictions [Raussendorf and Harrington, Phys. Rev. Lett. 98, 190504 (2007); Wang et al., Phys. Rev. A 83, 020302(R) (2011)]. Finally, because the behavior of our decoder's performance for two of the noise models we consider maps onto an order-disorder phase transition in the three-body random-bond Ising model in 2D and the corresponding random-plaquette gauge model in 3D, our results also answer the Nishimori conjecture for these models in the negative: the statistical-mechanical classical spin systems associated to the 4.8.8 color codes are counterintuitively more ordered at positive temperature than at zero temperature.

Troy Lee, Rajat Mittal, Ben Reichardt, Robert Spalek and Mario Szegedy.
Quantum query complexity for state conversion

Abstract: State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm.

In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem.

Troy Lee and Jérémie Roland.
A strong direct product theorem for quantum query complexity

Abstract: We show that quantum query complexity satisfies a strong direct product theorem. This means that computing k copies of a function with less than k times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in k. For a boolean function f we also show an XOR lemma---computing the parity of k copies of f with less than k times the queries needed for one copy implies that the advantage over random guessing will be exponentially small.

We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, is always at least as large as the additive adversary method, which is known to characterize quantum query complexity.

Francois Le Gall.
Improved Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication

Abstract: We present new quantum algorithms for Boolean Matrix Multiplication in both the time complexity and the query complexity settings. As far as time complexity is concerned, our results show that the product of two n x n Boolean matrices can be computed on a quantum computer in time O(n^{3/2}+nk^{3/4}), where k is the number of non-zero entries in the product, improving over the output-sensitive quantum algorithm by Buhrman and Spalek (SODA'06) that runs in O(n^{3/2}k^{1/2}) time. This is done by constructing a quantum version of a recent classical algorithm by Lingas (ESA'09), using quantum techniques such as quantum counting to exploit the sparsity of the output matrix. As far as query complexity is concerned, our results improve over the quantum algorithm by Vassilevska Williams and Williams (FOCS'10) based on a reduction to the triangle finding problem. One of the main contributions leading to this improvement is the construction of a quantum algorithm for triangle finding tailored especially for the tripartite graphs appearing in the reduction.

Spyridon Michalakis and Justyna Pytel.
Stability of Frustration-Free Hamiltonians

Abstract: We prove stability of the spectral gap for gapped, frustration-free Hamiltonians under general, quasi-local perturbations. We present a necessary and sufficient condition for stability, which we call Local Topological Quantum Order. This result extends previous work by Bravyi et al. on the stability of topological quantum order for Hamiltonians composed of commuting projections with a common zero-energy subspace.

Abel Molina and John Watrous.
Hedging bets with correlated quantum strategies

Abstract: This paper studies correlations among independently administered hypothetical tests of a simple interactive type, and demonstrates that correlations arising in quantum information theoretic variants of these tests can exhibit a striking non-classical behavior. When viewed in a game-theoretic setting, these correlations are suggestive of a perfect form of hedging, where the risk of a loss in one game of chance is perfectly offset by one's actions in a second game. This type of perfect hedging is quantum in nature, it is not possible in classical variants of the tests we consider.

Sandu Popescu.
The smallest possible thermal machines and the foundations of thermodynamics

Abstract: In my talk I raise the question on the fundamental limits to the size of thermal machines - refrigerators, heat pumps and work producing engines - and I will present the smallest possible ones. I will then discuss the issue of a possible complementarity between size and efficiency and show that even the smallest machines could be maximally efficient and I will also present a new point of view over what is work and what do thermal machines actually do. Finally I will present a completely new approach to the foundations of thermodynamics that follows from these results, which in their turn are inspired from quantum information concepts.

Joseph M. Renes, Frederic Dupuis and Renato Renner.
Quantum Polar Coding

Abstract: Polar coding, introduced in 2008 by Arikan, is the first efficiently encodable and decodable coding scheme that provably achieves the Shannon bound for the rate of information transmission over classical discrete memoryless channels (in the asymptotic limit of large block sizes). Here we study the use of polar codes for the efficient coding and decoding of quantum information. Focusing on the case of qubit channels we construct a coding scheme which, using some pre-shared entanglement, asymptotically achieves a net transmission rate equal to the coherent information. Furthermore, for channels with sufficiently low noise level, no pre-shared entanglement is required.

Jérémie Roland.
Quantum rejection sampling

Abstract: Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann (1951) and has many applications in classical computing. We define a quantum analogue of rejection sampling: given a black box producing a coherent superposition of (possibly unknown) quantum states with some amplitudes, the problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. The main result of this paper is a tight characterization of the query complexity of this quantum state generation problem. We exhibit an algorithm, which we call quantum rejection sampling, and analyze its cost using semidefinite programming. Our proof of a matching lower bound is based on the automorphism principle which allows to symmetrize any algorithm over the automorphism group of the problem.

Furthermore, we illustrate how quantum rejection sampling may be used as a primitive in designing quantum algorithms, by providing three different applications. We first show that it was implicitly used in the quantum algorithm for linear systems of equations by Harrow, Hassidim and Lloyd. Secondly, we show that it can be used to speed up the main step in the quantum Metropolis sampling algorithm by Temme et al.. Finally, we derive a new quantum algorithm for the hidden shift problem of an arbitrary Boolean function.

Joint work with Maris Ozols and Martin Roetteler, to appear in ITCS'12

Norbert Schuch.
Complexity of commuting Hamiltonians on a square lattice of qubits

Abstract: We consider the computational complexity of Hamiltonians which are sums of commuting terms acting on plaquettes in a square lattice of qubits, and we show that deciding whether the ground state minimizes the energy of each local term individually is in the complexity class NP. That is, if the ground states has this property, this can be proven using a classical certificate which can be efficiently verified on a classical computer. Different to previous results on commuting Hamiltonians, our certificate proves the existence of such a state without giving instructions on how to prepare it.

Martin Schwarz, Kristan Temme, Frank Verstraete, Toby Cubitt and David Perez-Garcia.
Preparing projected entangled pair states on a quantum computer

Abstract: We present a quantum algorithm to prepare injective PEPS on a quantum computer, a problem raised by Verstraete, Wolf, Perez-Garcia, and Cirac [PRL 96, 220601 (2006)]. To be efficient, our algorithm requires well-conditioned PEPS projectors and, essentially, an inverse-polynomial spectral gap of the PEPS' parent Hamiltonian. Injective PEPS are the unique groundstates of their parent Hamiltonians and capture groundstates of many physically relevant many-body Hamiltonians, such as e.g. the 2D AKLT state. Even more general is the class of G-injective PEPS which have parent Hamiltonians with a ground state space of degeneracy |G|, the order of the discrete symmetry group G. As our second result we show how to prepare G-injective PEPS under similar assumptions as well. The class of G-injective PEPS contains topologically ordered states, such as Kitaev's toric code which our algorithm is thus able to prepare.

Yaoyun Shi and Xiaodi Wu.
Epsilon-net method for optimizations over separable states

Abstract: In this paper we study the algorithms for the linear optimization over separable quantum states, which is a NP-hard problem. Precisely, the objective function is <Q, \rho> for some hermitian Q where \rho is a separable quantum state. Our strategy is to enumerate (via epsilon-nets) more cleverly with the help of certain structure of some interesting Qs. As a result, we obtain efficient algorithms either in time or space for the following cases.

Firstly, we provide a polynomial time (or space) algorithm when Q can be decomposed into the form Q = sum_{i=1}^M Q^1_i tensor Q^2_i with small M. As a direct consequence, we prove a variant of the complexity class QMA(2) where the verifier performs only logarithm number of unit gates acting on both proofs simultaneously is contained in PSPACE. We also initiate the study of the natural extension of the local Hamiltonian problem to the k-partite case. By the same algorithm, we conclude those problems remain to be inside PSPACE.

Secondly, for a positive semidefinite Q we obtain an algorithm with running time exponential in the Frobenius norm of Q , which reproves one of the main results of Brandao, Christandl and Yard [STOC pp.343(2011)]. Note that this result was originally proved by making use of many non-trivial results in quantum information, whereas our algorithm only utilizes fundamental operations of matrices and the Schmidt decomposition of bipartite pure states.

Graeme Smith, John A. Smolin and Jon Yard.
Quantum communication with gaussian channels of zero quantum capacity

Abstract: Superactivation of channel capacity occurs when two channels have zero capacity separately, but can have nonzero capacity when used together. We present a family of simple and natural examples of superactivation of quantum capacity using gaussian channels that can potentially be realized with current technologies. This demonstrates the richness of the set of gaussian channels and the complexity of their capacity-achieving protocols. Superactivation is therefore not merely an oddity confined to unrealistic models but is in fact necessary for a proper characterization of realistic communication settings.

Rolando Somma and Sergio Boixo.
Spectral Gap Amplification

Abstract: Many problems in quantum information reduce to preparing a specific eigenstate of some Hamiltonian H. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of H for that eigenstate and the cost of evolving with H for some fixed time. The goal of spectral gap amplification is therefore to construct a Hamiltonian H' with the same eigenstate as that of H but a bigger spectral gap, requiring that constant-time evolutions with H' and H can be implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when H satisfies a frustration-free property and give H' for this case. This results in quantum speedups for some adiabatic evolutions. Defining a suitable oracle model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stochastic Hamiltonian and the corresponding stochastic matrix is hard in the oracle model, setting strong limits in the power of some classical methods that simulate quantum adiabatic evolutions. Implications of spectral gap amplification for quantum speedups of optimization problems and the preparation of projected entangled pair states (PEPS) are discussed.

Nengkun Yu, Runyao Duan and Quanhua Xu.
Bounds on the distance between a unital quantum channel and the convex hull of unitary channels, with applications to the asymptotic quantum Birkhoff conjecture

Abstract: Motivated by the recent resolution of Asymptotic Quantum Birkhoff Conjecture (AQBC), we attempt to estimate the distance between a given unital quantum channel and the convex hull of unitary channels. We provide two lower bounds on this distance by employing techniques from quantum information and operator algebra, respectively. We then show how to apply these results to construct some explicit counterexamples to AQBC.



PDF file of Programme Booklet:

QIP2012 Poster:

Supported by: