Quantum Information

In this talk (based on arXiv:1001.0354) we give a quantum statistical interpretation for the Kauffmann bracket polynomial state sum <K> for the Jones polynomial. We use this quantum mechanical interpretation to give a new quantum algorithm for computing the Jones polynomial. This algorithm is useful for its conceptual simplicity, and it applies to all values of the polynomial variable that lie on the unit circle in the complex plane. Letting C(K) denote the Hilbert space for this model, there is a natural unitary transformation U from C(K) to itself such that <K> = <F|U|F> where |F> is a sum over basis states for C(K). The quantum algorithm arises directly from this formula via the Hadamard Test. We then show that the framework for our quantum model for the bracket polynomial is a natural setting for Khovanov homology. The Hilbert space C(K) of our model has basis in one-to-one correspondence with the enhanced states of the bracket state summmation and is isomorphic with the chain complex for Khovanov homology with coefficients in the complex numbers. We show that for the Khovanov boundary operator d defined on C(K) we have the relationship dU + Ud = 0. Consequently, the unitary operator U acts on the Khovanov homology, and we therefore obtain a direct relationship between Khovanov homology and this quantum algorithm for the Jones polynomial. The formula for the Jones polynomial as a graded Euler characteristic is now expressed in terms of the eigenvalues of U and the Euler characteristics of the eigenspaces of U in the homology. The quantum algorithm given here is inefficient, and so it remains an open problem to determine better quantum algorithms that involve both the Jones polynomial and the Khovanov homology.

Multipartite quantum states constitute a (if not the) key resource for quantum computations and protocols. However obtaining a generic, structural understanding of entanglement in N-qubit systems is still largely an open problem. Here we show that multipartite quantum entanglement admits a compositional structure. The two SLOCC-classes of genuinely entangled 3-qubit states, the GHZ-class and the W-class, exactly correspond with the two kinds of commutative Frobenius algebras on C^2, namely `special' ones and `anti-special' ones. Within the graphical language of symmetric monoidal categories, the distinction between `special' and `anti-special' is purely topological, in terms of `connected' vs.~`disconnected'. These GHZ and W Frobenius algebras form the primitives of a graphical calculus which is expressive enough to generate and reason about representatives of arbitrary N-qubit states. This calculus induces a generalised graph state paradigm for measurement-based quantum computing, and refines the graphical calculus of complementary observables due to Duncan and one of the authors [ICALP'08], which has already shown itself to have many applications and admit automation. References: Bob Coecke and Aleks Kissinger, http://arxiv.org/abs/1002.2540

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.