Quantum Information

Some years ago Valiant introduced a notion of \'matchgate\' and \'holographic algorithm\', based on properties of counting perfect matchings in graphs. This provided some new poly-time classical algorithms and embedded in this formalism, he recognised a remarkable class of quantum circuits (arising when matchgates happen to be unitary) that can be classically efficiently simulated. Subsequently various workers (including Knill, Terhal and DiVincenzo, Bravyi) showed that these results can be naturally interpreted in terms of the formalism of fermionic quantum computation. In this talk I will outline how unitary matchgates and their simulability arise from considering a Clifford algebra of anticommuting symbols, and then I\'ll discuss some avenues for further generalisation and interesting properties of matchgate circuits. In collaboration with Akimasa Miyake, University of Innsbruck.

We give an overview of several connections between topics in quantum information theory, graph theory, and statistical mechanics. The central concepts are mappings from statistical mechanical models defined on graphs, to entangled states of multi-party quantum systems. We present a selection of such mappings, and illustrate how they can be used to obtain a cross-fertilization between different research areas. For example, we show how width parameters in graph theory such as \'tree-width\' and \'rank-width\', which may be used to assess the computational hardness of evaluating partition functions, are intimately related with the entanglement measure \'entanglement width\', which is used to asses to computational power of resource states in quantum information. Furthermore, using our mappings we provide simple techniques to relate different statistical mechanical models with each other via basic graph transformations. These techniques can be used to prove that that there exist models which are \'complete\' in the sense that every other model can be viewed as a special instance of such a complete model via a polynomial reduction. Examples of such complete models include the 2D Ising model in an external field, as well as the zero-field 3D Ising model. Joint work with W. Duer, G. de las Cuevas, R. Huebener and H. Briegel

The idea of pseudo-randomness is to use little or no randomness to simulate a random object such as a random number, permutation, graph, quantum state, etc... The simulation should then have some superficial resemblance to a truly random object; for example, the first few moments of a random variable should be nearly the same. This concept has been enormously useful in classical computer science. In my talk, I\'ll review some quantum analogues of pseudo-randomness: unitary k-designs, quantum expanders (and their new cousin, quantum tensor product expanders), extractors. I\'ll talk about relations between them, efficient constructions, and possible applications. Some of the material is joint work with Matt Hastings and Richard Low.

Certain structures arising in Physics (mub\'s and sic-povm\'s) can be viewed as sets of lines in complex space that are as large as possible, given some simple constraints on the angles between distinct lines. The analogous problems in real space have long been of interest in Combinatorics, because of their relation to classical combinatorial structures. In the complex case there seems no reason for any combinatorial connection to exist. will discuss some of the history of the real problems, and describe some recent work that relates the complex problems to some very interesting classes of graphs.

The talk concerns a generalization of the concept of a minimum uncertainty state to the finite dimensional case. Instead of considering the product of the variances of two complementary observables we consider an uncertainty relation involving the quadratic Renyi entropies summed over a full set of mutually unbiased bases (MUBs). States which achieve the lower bound set by this inequality were introduced by Wootters and Sussman, who proved existence for every prime power dimension, and by Appleby, Dang and Fuchs who showed that in prime dimension the fiducial vector for a for a symmetric informationally complete positive operator valued measure (SIC-POVM) covariant under the Weyl-Heisenberg group is a state of this kind. Subsequently Sussman proved existence for a class of odd prime power dimensions. The purpose of this talk is to complete the existence proof by showing that minimum uncertainty states exist in every prime power dimension, without exception. Along the way we establish a number of properties of the Clifford group, and Galois extension fields, which might be of some independent interest.

Coin flipping by telephone (Blum \'81) is one of the most basic cryptographic tasks of two-party secure computation. In a quantum setting, it is possible to realize (weak) coin flipping with information theoretic security. Quantum coin flipping has been a longstanding open problem, and its solution uses an innovative formalism developed by Alexei Kitaev for mapping quantum games into convex optimization problems. The optimizations are carried out over duals to the cone of operator monotone functions, though the mapped problem can also be described in a very simple language that involves moving points in the plane. Time permitting, I will discuss both Kitaev\'s formalism, and the solution that leads to quantum weak coin flipping with arbitrarily small bias.

Decoherence attempts to explain the emergent classical behaviour of a quantum system interacting with its quantum environment. In order to formalize this mechanism we introduce the idea that the information preserved in an open quantum evolution (or channel) can be characterized in terms of observables of the initial system. We use this approach to show that information which is broadcast into many parts of the environment can be encoded in a single observable. This supports a model of decoherence where the pointer observable can be an arbitrary positive operator-valued measure (POVM). This generalization makes it possible to characterize the emergence of a realistic classical phase-space. In addition, this model clarifies the relations among the information preserved in the system, the information flowing from the system to the environment (measurement), and the establishment of correlations between the system and the environment.

I should like to show how particular mathematical properties can limit our metaphysical choices, by discussing old and new theorems within the statistical-model framework of Mielnik, Foulis & Randall, and Holevo, and what these theorems have to say about possible metaphysical models of quantum mechanics. Time permitting, I should also like to show how metaphysical assumptions lead to particular mathematical choices, by discussing how the assumption of space as a relational concept leads to a not widely known frame-invariant formulation of classical point-particle mechanics by Föppl and Zanstra, and related research topics in continuum mechanics and general relativity.

The \\\"frequency comb\\\" defined by the eigenmodes of an optical resonator is a naturally large set of exquisitely well defined quantum systems, such as in the broadband mode-locked lasers which have redefined time/frequency metrology and ultra precise measurements in recent years. High coherence can therefore be expected in the quantum version of the frequency comb, in which nonlinear interactions couple different cavity modes, as can be modeled by different forms of graph states. We show that is possible to thereby generate states of interest to quantum metrology and computing, such as multipartite entangled cluster and Greenberger-Horne-Zeilinger states.

The Achilles\\\' heel of quantum information processors is the fragility of quantum states and processes. Without a method to control imperfection and imprecision of quantum devices, the probability that a quantum computation succeed will decrease exponentially in the number of gates it requires. In the last ten years, building on the discovery of quantum error correction, accuracy threshold theorems were proved showing that error can be controlled using a reasonable amount of resources as long as the error rate is smaller than a certain threshold. We thus have a scalable theory describing how to control quantum systems. I will briefly review some of the assumptions of the accuracy threshold theorems and comment on experiments that have been done and should be done to turn quantum error correction into an experimental reality.

We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of 10-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process, requiring only initial product state preparation. Both the quantum circuit and its input are encoded in an initial canonical basis state of the qudit chain. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time greater than a polynomial in the size of the quantum circuit has passed, the result of the computation can be obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless BPP=BQP). This is joint work with Daniel Nagaj.

The renormalization group (RG) is one of the conceptual pillars of statistical mechanics and quantum field theory, and a key theoretical element in the modern formulation of critical phenomena and phase transitions. RG transformations are also the basis of numerical approaches to the study of low energy properties and emergent phenomena in quantum many-body systems. In this colloquium I will introduce the notion of \\\"entanglement renormalization\\\" and use it to define a coarse-graining transformation for quantum systems on a lattice [G.Vidal, Phys. Rev. Lett. 99, 220405 (2007)]. The resulting real-space RG approach is able to numerically address 1D and 2D lattice systems with thousands of quantum spins using only very modest computational resources. From the theoretical point of view, entanglement renormalization sheds new light into the structure of correlations in the ground state of extended quantum systems. I will discuss how it leads to a novel, efficient representation for the ground state of a system at a quantum critical point or with topological order.