Abstracts
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.
