Quantum Information

Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. Inspired by the success of the statistical study of classical constraint optimization problems, we study random ensembles of the QMA$_1$-complete quantum satisfiability (QSAT) problem introduced by Bravyi. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are product satisfiable, entangled satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for a fixed interaction graph exhibit the same dimension of the satisfying manifold. This establishes the generic QSAT decision problem as equivalent to a purely graph theoretic property and that the hardest typical instances are likely to be localized in a bounded range of clause density. Based on papers: C.R. Laumann, R. Moessner, A. Scardicchio, and S.L. Sondhi. Phase transitions and random quantum satisfiability. QIC 10 (1/2), (2009). arXiv:0903.1904 C.R. Laumann, A.M. Lauchli, R. Moessner, A. Scardicchio, and S.L. Sondhi. On product, generic and random generic quantum satisfiability. arXiv:0910.2058

If a pure quantum state is drawn at random, this state will almost surely be almost maximally entangled. This is a well-known example for the "concentration of measure" phenomenon, which has proved to be tremendously helpful in recent years in quantum information theory. It was also used as a new method to justify some foundational aspects of statistical mechanics. In this talk, I discuss recent work with David Gross and Jens Eisert on concentration in the set of pure quantum states with fixed mean energy: We show typicality in this manifold of quantum states, and give a method to evaluate expectation values explicitly. This involves some interesting mathematics beyond Levy's Lemma, and suggests potential applications such as finding stronger counterexamples to the additivity conjecture.

Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b, find a vector x such that Ax=b. Often, one does not need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse and well-conditioned, with largest dimension N, the best known classical algorithms can find x and estimate x'Mx in O(N * poly(log(N))) time. In this talk I'll describe a quantum algorithm for solving linear sets of equations that runs in poly(log N) time, an exponential improvement over the best classical algorithm. This talk is based on my paper arXiv:0811.3171v2, which was written with Avinatan Hassidim and Seth Lloyd.

In topological quantum computation, a quantum algorithm is performed by braiding and fusion of certain quasi-particles called anyons. Therein, the performed quantum circuit is encoded in the topology of the braid. Thus, small inaccuracies in the world-lines of the braided anyons do not adversely affect the computation. For this reason, topological quantum computation has often been regarded as error-resilient per se, with no need for quantum error-correction. However, newer work [1], [2] shows that even topological computation is plagued with (small) errors. As a consequence, it requires error-correction, too, and in the scaling limit causes a poly-logarithmic overhead similar to systems without topological error-correction. I will discuss Nussinov and Ortiz' recent result [2] that the toric code is not fault-tolerant in a Hamiltonian setting, and outline its potential implications for topological quantum computation in general. [1] Nayak, C., Simon, S. H., Stern, A. et al. Non-Abelian anyons and topological quantum computation. Rev. Mod. Phys. 80, 1083-1159 (2008). [2] Z. Nussinov and G. Ortiz, arXiv:0709.2717 (condmat)

In the closed system setting I will show how to obtain extremely accurate adiabatic QC by proper choice of the interpolation between the initial and final Hamiltonians. Namely, given an analytic interpolation whose first N initial and final time derivatives vanish, the error can be made to be smaller than 1/N^N, with an evolution time which scales as N and the square of the norm of the time-derivative of the Hamiltonian, divided by the cube of the gap (joint work with Ali Rezakhani and Alioscia Hamma). In the open system setting I will describe a method for protecting adiabatic QC by use of a hybrid encoding-dynamical decoupling scheme. This strategy can be used to protect spin-based universal adiabatic QC against arbitrary 1-local noise using only global magnetic fields. By combining error bounds for the closed and open system settings, I will show that in principle the method is scalable to arbitrarily large computations. References: Closed system case: arXiv:0808.2697 Open system case: Phys. Rev. Lett. 100, 160506 (2008)

There are many results showing that the probability of entanglement is high for large dimensions. Recently, Arveson showed that the probability of entanglement is zero when the rank of a bipartite state is no larger than half the dimension of the smaller space. We show that that the probability of entanglement is zero when the rank of a bipartite state is no larger than half the maximum of the rank of its two reduced density matrices. Our approach is quite different from that of Arveson and uses a different measure. But both approaches show that the separable states lie in a lower dimensional manifold given a reasonable parameterization of the separable states. This is joint work with Elisabeth Werner, using on characterizations of the extreme points of qubit channels given by Ruskai, Szarek and Werner and the extreme points of entanglement breaking channels given by M. Horodecki, Shor and Ruskai.

A recent breakthrough in quantum computing has been the realization that quantum computation can proceed solely through single-qubit measurements on an appropriate quantum state - for example, the ground state of an interacting many-body system. It would be unfortunate, however, if the usefulness of a ground state for quantum computation was critically dependent on the details of the system\'s Hamiltonian; a much more powerful result would be the existence of a robust ordered phase which is characterized by the ability to perform measurement-based quantum computation (MBQC). To identify such phases, we propose to use nonlocal correlation functions that quantify the fidelity of quantum gates performed between distant qubits. We investigate a simple spin-lattice system based on the cluster-state model for MBQC, and demonstrate that it possesses a zero temperature phase transition between a disordered phase and an ordered \'cluster phase\' in which it is possible to perform a universal set of quantum gates.

This is a talk in two parts. The first part is on evolution of a system under a Hamiltonian. First, a general method for implementing evolution under a Hamiltonian using entanglement and classical communication is presented. This method improves on previous methods by requiring less entanglement and communication, as well as allowing more general Hamiltonians to be implemented. Next, a method for simulating evolution under a sparse Hamiltonian using a quantum computer is presented. When H acts on n qubits, and has at most a constant number of nonzero entries in each row/column, we may select any positive integer k such that the simulation requires O((log*n)t^(1+1/2k)) accesses to matrix entries of H. The second part of the talk is on adaptive measurements of optical phase. Standard measurement schemes, using each resource independently, lead to a phase uncertainty that scales as 1/sqrt(N). It has long been conjectured that it should be possible to achieve a precision limited only by the Heisenberg uncertainty principle, dramatically improving the scaling to 1/N. I present a Heisenberg-limited phase estimation procedure which has been demonstrated experimentally. We use multiple applications of the phase shift on unentangled single-photon states, and generalize Kitaev\\\'s phase estimation algorithm using adaptive measurement theory to achieve a standard deviation scaling at the Heisenberg limit.

We define a measure of the quantumness of correlations, based on the operative task of local broadcasting of a bipartite state. Such a task is feasible for a state if and only if it corresponds to a joint classical probability distribution, or, in other terms, it is strictly classically correlated. A gap, defined in terms of quantum mutual information, can quantify the degree of failure in fulfilling such a task, therefore providing a measure of how non-classical a given state is. We are led to consider the asymptotic average mutual information of a state, defined as the minimal per-copy mutual information between parties, when they share an infinite amount of broadcast copies of the state. We analyze the properties of such quantity, and find that it satifies many of the properties required for an entanglement measure. We show that it lies between the quantum- and the classical-conditioned versions of squashed entanglement. The non-vanishing of asymptotic average mutual information for entangled states may be interpreted as a signature of monogamy of entanglement.

I will present an efficient quantum algorithm for an additive approximation of the famous Tutte polynomial of any planar graph at any point. The Tutte polynomial captures an extremely wide range of interesting combinatorial properties of graphs, including the partition function of the q-state Potts model. This provides a new class of quantum complete problems. Our methods generalize the recent AJL algorithm for the approximation of the Jones polynomial; instead of using unitary representations, we allow non-unitarity, which seems counter intuitive in the quantum world. Significant contribution of this is a proof that non-unitary operators can be used for universal quantum computation.

Thermodynamics places surprisingly few fundamental constraints on information processing. In fact, most people would argue that it imposes only one, known as Landauer's Principle: a process erasing one bit of information must release an amount kT ln 2 of heat. It is this simple observation that finally led to the exorcism of Maxwell's Demon from statistical mechanics, more than a century after he first appeared. Ignoring the lesson implicit in this early advance, however, quantum information theorists have been surprisingly slow to embrace erasure as a fundamental primitive. Over the past couple of years, however, it has become clear that a detailed understanding of how difficult it is to erase correlations leads to a nearly complete synthesis and simplification of the known results of asymptotic quantum information theory. As it turns out, surprisingly many of the tasks of interest, from distilling high-quality entanglement to sending quantum data through a noisy medium to many receivers, can be understood as variants of erasure. I'll sketch the main ideas behind these discoveries and end with some speculations on what lessons the new picture might have for understanding information loss in real physical systems.