Quantum Physics

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 dynamics of particles moving in a medium defined by its relativistically invariant stochastic properties is investigated. For this aim, the force exerted on the particles by the medium is defined by a stationary random variable as a function of the proper time of the particles. The equations of motion for a single one-dimensional particle are obtained and numerically solved. A conservation law for the drift momentum of the particle during its random motion is shown. Moreover, the conservation of the mean value of the total linear momentum for two particles repelling each other according to the Coulomb interaction also follows. Therefore, the results indicate the realization of a kind of stochastic Noether theorem in the system under study.

Chris Isham in pre-recorded video, with Andreas Doring fielding questions and clarifications. Like watching commentators Scott Hamilton and Katarina Witt analyze Kristi Yamaguchi\'s performance at the World Figure Skating Championships for CBS News, join us for something different in quantum foundations. Chris Isham parries the intricacies of topos theory; Andreas Doring shows us how to see the moves in slow motion. Bring your own popcorn and plenty of questions.

Quantum measure theory describes quantum theory as a generalization of a classical stochastic process, which may be fruitful for quantum gravity. I will describe the approach, and show that, in the context of an EPRB setup with two distant experimenters, two alternative experiments, and two outcomes per experiment, any set of no signaling probabilities can be realized, albeit by violating a `strong positivity\' condition.

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.

It is usually expected that nonrelativistic many-body Schroedinger equations emerge from some QFT models in the limit of infinite masses. For instance, from Yukawa\'s QFT, if the initial state contains 2 fermions, we expect to recover a 2-fermion nonrelativistic Schroedinger equation with 2-body Yukawa potential (in the limit of infinite fermion mass). I will give an easy (but still heuristic) derivation of this, based on the analysis of the corresponding Feynman diagrams and on the behaviour of the complete propagators for large spacetime distances. Then, I may outline another possible derivation based on the Schroedinger picture and dressed particles.

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.

At a very basic level, physics is about what we can say about propositions like \'A has a value in S\' (or \'A is in S\' for short), where A is some physical quantity like energy, position, momentum etc. of a physical system, and S is some subset of the real line. In classical physics, given a state of the system, every proposition of the form \'A is in S\' is either true or false, and thus classical physics is realist in the sense that there is a \'way things are\'. In contrast to that, quantum theory only delivers a probability of \'A is in S\' being true. The usual instrumentalist interpretation of the formalism leading to these probabilities involves an external observer, measurements etc.In a future theory of quantum gravity/cosmology, we will have to treat the whole universe as a quantum system, which renders instrumentalism meaningless, since there is no external observer. Moreover, space-time presumably does not have a smooth continuum structure at small scales, and possibly physical quantities will take their values in some other mathematical structure than the real numbers, which are the \'mathematical continuum\'. In my talk, I will show how the use of topos theory, which is a branch of category theory, may help to formulate physical theories in a way that (a) is neo-realist in the sense that all propositions \'A is in S\' do have truth values and (b) does not depend fundamentally on the continuum in the form of the real numbers. After introducing topoi and their internal logic, I will identify suitable topoi for classical and quantum physics and show which structures within these topoi are of physical significance. This is still very far from a theory of quantum gravity, but it can already shed some light on ordinary quantum theory, since we avoid the usual instrumentalism. Moreover, the formalism is general enough to allow for major generalisations. I will conclude with some more general remarks on related developments.

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.