Quantum Information

The original motivation to build a quantum computer came from Feynman who envisaged a machine capable of simulating generic quantum mechanical systems, a task that is intractable for classical computers. Such a machine would have tremendous applications in all physical sciences, including condensed matter physics, chemistry, and high energy physics. Part of Feynman's challenge was met by Lloyd who showed how to approximately decompose the time-evolution operator of interacting quantum particles into a short sequence of elementary gates, suitable for operation on a quantum computer. However, this left open the more fundamental problem of how to simulate the equilibrium and static properties of quantum systems. This requires the preparation of ground and Gibb's states on a quantum computer. For classical systems, this problem is solved by the ubiquitous Metropolis algorithm, a method that basically acquired a monopoly for the simulation of interacting particles. In this talk, I will demonstrate that the corresponding quantum problem can be solved by a quantum Metropolis algorithm. This validates the quantum computer as a universal simulator, and proves that the so-called sign problem occurring in quantum Monte Carlo methods can be resolved with a quantum computer.

In quantum information, entanglement has often been viewed as a resource. But in this talk, I will look at (pure bipartite) entanglement through the lens of superselection rules. The idea is that it requires quantum communication not only to create entanglement, but also to destroy it in a way that doesn't leak information to the environment. As a result, when communication is scarce, superpositions of different numbers of EPR pairs can be difficult to obtain. This constraint is not a strict superselection rule, but rather an approximate version that gives rigorous bounds on achievable fidelities. After describing the general phenomenon, I will show how it relates to communication complexity, information theory and fairy tales about princesses. This talk is based on 0803.3066, 0909.1557, 0912.5537 and other unpublished work.

I'll discuss some work-in-progress about the computational complexity of simulating the extremely "simple" quantum systems that arise in linear optics experiments. I'll show that *either* one can describe an experiment, vastly easier than building a universal quantum computer, that would test whether Nature is performing nontrivial quantum computation, or else one can give surprising new algorithms for approximating the permanent. Audience feedback as to which of these possibilities is the right one is sought. Joint work with Alex Arkhipov.

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.