Format results
-
-
-
-
-
Purity Without Probability
Giulio Chiribella University of Hong Kong (HKU)
-
Interactive Quantum Information Theory
Dave Touchette University of Sherbrooke
-
Classifying Hamiltonians in terms of computational complexity
Barbara Terhal Delft University of Technology
-
-
Quantum information geometric foundations: an overview
Ryszard Kostecki University of Gdansk
-
-
-
-
Completeness Results for Graphical Quantum Process Languages
From Feynman diagrams via Penrose graphical notation to quantum circuits, graphical languages are widely used in quantum theory and other areas of theoretical physics. The category-theoretical approach to quantum mechanics yields a new set of graphical languages, which allow rigorous pictorial reasoning about quantum systems and processes. One such language is the ZX-calculus, which is built up of elements corresponding to maps in the computational and the Hadamard basis. This calculus is universal for pure state qubit quantum mechanics, meaning any pure state, unitary operation, and post-selected pure projective measurement can be represented. It is also sound, meaning any graphical rewrite corresponds to a valid equality when translated into matrices.
While the calculus is not complete for general quantum mechanics, I show that it is complete for stabilizer quantum mechanics and for the single-qubit Clifford+T group. This means that within those subtheories, any equality that can be derived using matrices can also be derived graphically.
The ZX-calculus can thus be applied to a wide range of problems in quantum information and quantum foundations, from the analysis of quantum non-locality to the verification of measurement-based quantum computation and error-correcting codes. I also show how to construct a ZX-like graphical calculus for Spekkens' toy bit theory and give its associated completeness proof.
-
Different Strategies for Quantum Adiabatic Optimization, and the Computational Power of Simulated Quantum Annealing
Quantum Adiabatic Optimization proposes to solve discrete optimization problems by mapping them onto quantum spin systems in such a way that the optimal solution corresponds to the ground state of the quantum system. The standard method of preparing these ground states is using the adiabatic theorem, which tells us that quantum systems tend to remain in the ground state of a time-dependent Hamiltonian which transforms sufficiently slowly. In this talk I'll show that alternative strategies using non-adiabatic effects can in some cases be dramatically faster for instances which are hard for the traditional adiabatic method.
I will also discuss Simulated Quantum Annealing (SQA), which is a classical simulation of adiabatic optimization at non-zero temperature based on Path-Integral Quantum Monte Carlo. SQA is widely used in practice to study adiabatic optimization, but relatively little is known about the rate of convergence of the markov chain that underlies the algorithm. By focusing on a family of instances which adiabatic optimization solves in polynomial time, but require exponential time to solve using classical (thermal) simulated annealing, I will present numerical evidence as well as a work-in-progress proof that SQA can be exponentially faster than classical simulated annealing.
-
Implications of computer science principles for quantum physics
The Church-Turing thesis is one of the pillars of computer science; it postulates that every classical system has equivalent computability power to the so-called Turing machine. While this thesis is crucial for our understanding of computing devices, its implications in other scientific fields have hardly been explored. What if we consider the Church-Turing thesis as a law of nature? In this talk I will present our first results in connection with quantum information theory [1] by showing that computer science laws have profound implications for some of the most fundamental results of quantum theory. First I will show how they question our knowledge on what a mixed quantum state is, as we identified situations in which ensembles of quantum states defining the same mixed state, indistinguishable according to the quantum postulates, do become distinguishable when prepared by a computer (or any classical system). Then I will introduce a new loophole for Bell-like experiments: if some of the parties in a Bell-like experiment use a computer to decide which measurements to make, then the computational resources of an eavesdropper have to be limited in order to have a proper observation of non-locality.
-
Ground state connectivity of local Hamiltonians
The study of ground spaces of local Hamiltonians is a fundamental task in condensed matter physics. In terms of computational complexity theory, a common focus in this area has been to estimate a given Hamiltonian’s ground state energy. However, from a physics perspective, it is sometimes more relevant to understand the structure of the ground space itself. In this talk, we pursue the latter direction by introducing the notion of “ground state connectivity” of local Hamiltonians. In particular, we show that determining how “connected” the ground space of a local Hamiltonian is can range from QCMA-complete to NEXP-complete. (Here, QCMA is the same as QMA, but with a classical witness.) As a result, we obtain a natural QCMA-complete problem, a task which has generally proven difficult since the conception of QCMA over a decade ago.
-
Purity Without Probability
Giulio Chiribella University of Hong Kong (HKU)
Pure states and pure transformations play a crucial role in most of the recent reconstructions of quantum theory. In the frameworks of general probabilistic theories, purity is defined in terms of probabilistic mixtures and bears an intuitive interpretation of ``maximal knowledge" of the state of the system or of the evolution undergone by it. On the other hand, many quantum features do not need the probabilistic structure of the theory. For example, Schumacher and Westmoreland formulated a toy theory that only specifies which events are possible (without quantifying they probability) and still reproduces a large number of quantum features. In this talk I will provide a probability-free definition of pure states and pure transformations, which can expressed in the categorical framework of process theories developed by Abramsky and Coecke and coincides with the usual notion under standard assumptions. Building on this definition, I will present a probability-free version of the purification principle, which allows one to retrieve a large number of quantum features even in the lack of probabilistic structure. This work is part of a larger programme that aims at drawing the line between those aspects of quantum theory that can be defined solely in terms of operations in a circuit and those that rely on the subjective expectations of an agent.
Related works:
-GC, Distinguishability and copiability of programs in general process theories, arXiv:1411.3035;
-Categorical purification, http://www.cs.ox.ac.uk/CQM2014/programme/Giulio.pdf
-GC, G. M. D'Ariano, and P. Perinotti, Probabilistic theories with purification, Phys. Rev. A 81, 062348 (2010) -
Interactive Quantum Information Theory
Dave Touchette University of Sherbrooke
In unidirectional communication theory, two of the most prominent problems are those of compressing a source of information and of transmitting data noiselessly over a noisy channel. In 1948, Shannon introduced information theory as a tool to address both of these problems. Since then, information theory has flourished into an important field of its own. It has also been successfully extended to the quantum setting, where it has also served to address questions about quantum source compression and transmission of classical and quantum data over noisy quantum channels.
However, in interactive communication theory, more specifically communication complexity, it is much more recently that tools from information theory have been successfully applied. Indeed, the interactive nature of communication protocols in this setting imposes new constraints and tools specific to this setting need to be developed, both for the interactive analogue of source compression and that of coding for noisy channels. The exciting field of classical interactive information theory has been very active in recent years.
We discuss recent works for its quantum counterpart. In particular, we discuss joint work showing that a constant factor overhead is sufficient for robustly implementing interactive quantum communication over noisy channels [1]. We also discuss work introducing a new notion of quantum information complexity that exactly captures the amortized cost per copy for implementing many copies of a communication task in parallel, such that compressing to this information complexity leads to a bounded-round direct sum theorem [2].
For both of these, we further discuss many interesting potential research directions that follow.
[1] joint work with Gilles Brassard, Ashwin Nayak, Alain Tapp, Falk Unger, QIP’14, FOCS’14 [2] Merge of arXiv:1404.3733 and arXiv:1409.4391, to appear at QIP’15
-
Classifying Hamiltonians in terms of computational complexity
Barbara Terhal Delft University of Technology
Quantum many-body systems ranging from a many-electron atom to a solid material are described by effective Hamiltonians which are obtained from more accurate Hamiltonians by neglecting or treating weak interactions perturbatively. Quantum complexity theory asks about the quantum computational power of such quantum many-body models for both practical as well as fundamental purposes. Three distinct computational classes have emerged within this framework: namely (1) classical Hamiltonians such as the Ising model, (2) sign-free or stoquastic Hamiltonians such as the transverse field Ising model, and (3) fully quantum Hamiltonians such as the Heisenberg model. Each class can be characterized by certain prototype universal Hamiltonians which can encode the physics of any other Hamiltonian in that class. We will show how this encoding is established through the use of perturbation theory via perturbative gadgets. We will discuss the technical expression of this classification in terms of the complexity classes NP, Stoquastic MA and QMA and the power of these Hamiltonians for performing quantum adiabatic computation.
-
From locality and operationalism to classical and quantum theory?
We present a first principles approach to a probabilistic description of nature based on two guiding principles: spacetime locality and operationalism. No notion of time or metric is assumed, neither any specific physical model. Remarkably, the emerging framework converges with the recently proposed positive formalism of quantum theory, obtained constructively from known quantum physics. However, it also seems to embrace classical physics.
-
Quantum information geometric foundations: an overview
Ryszard Kostecki University of Gdansk
I will present a new approach to information-theoretic foundations of quantum theory, that does not rely on probability theory, spectral theory, or Hilbert spaces. The direct nonlinear generalisations of quantum kinematics and dynamics are constructed using quantum information geometric structures over algebraic states of W*-algebras (quantum relative entropies and Poisson structure). In particular, unitary evolutions are generalised to nonlinear hamiltonian flows, while Lueders? rules are generalised to constrained relative entropy maximisations. Orthodox probability theory and quantum mechanics are special cases of this framework. I will also discuss the epistemic interpretation associated with this approach (rendering quantum theory as a framework for ontically noncommittal causal inference), as well as the possibility of deriving emergent space-times directly from quantum models.
-
Quantum theory and spacetime: a different perspective
Quantum information theory has taught us that quantum theory is just one possible probabilistic theory among many others. In the talk, I will argue that this "bird's-eye" perspective does not only allow us to derive the quantum formalism from simple physical principles, but also reveals surprising connections between the structures of spacetime and probability which can be phrased as mathematical theorems about information-theoretic scenarios.
-
Equivalence of wave-particle duality to entropic uncertaintyEquivalence of wave-particle duality to entropic uncertainty
Patrick Coles Carnegie Mellon University
Interferometers capture a basic mystery of quantum mechanics: a single particle can exhibit wave behavior, yet that wave behavior disappears when one tries to determine the particle's path inside the interferometer. This idea has been formulated quantitatively as an inequality, e.g., by Englert and Jaeger, Shimony, and Vaidman, which upper bounds the sum of the interference visibility and the path distinguishability. Such wave-particle duality relations (WPDRs) are often thought to be conceptually inequivalent to Heisenberg's uncertainty principle, although this has been debated. Here we show that WPDRs correspond precisely to a modern formulation of the uncertainty principle in terms of entropies, namely the min- and max-entropies. This observation unifies two fundamental concepts in quantum mechanics. Furthermore, it leads to a robust framework for deriving novel WPDRs by applying entropic uncertainty relations to interferometric models (arXiv reference: 1403.4687).
-
Decoherence tests without quantum theory
In quantum theory, people have thought for some while about the problem of how to estimate the decoherence of a quantum channel from classical data gained in measurements. Applications of these developments include security criteria for quantum key distribution and tests of decoherence models. In this talk, I will present some ideas for how to interpret the same classical data to make statements about decoherence in cases where nature is not necessarily described by quantum theory. This is work in progress in collaboration with many people.