QuICS seminar

We present a new algorithm for classical simulation of quantum circuits over the Clifford+T gate set. The runtime of the algorithm is polynomial in the number of qubits and the number of Clifford gates in the circuit but exponential in the number of T gates. The exponential scaling is sufficiently mild that the algorithm can be used in practice to simulate medium-sized quantum circuits dominated by Clifford gates.

Encryption of classical data is ubiquitous in everyday life. As quantum computation and communication gains wider use, encryption of quantum data is likely to become important as well. Until recently, the theory of quantum encryption was fairly limited, consisting primarily of the quantum analogue of the one-time pad. In this talk, I will discuss how to place quantum encryption on the same foundations as classical encryption, and how to translate many of the great achievements of classical encryption theory to the quantum setting.

The study of equivalence relations on mathematical structures is a vast theory embracing combinatorics, optimization, algebra, and mathematical logic. In this context, graph isomorphism and its hierarchy of relaxations constitute a central topic, not only for its elusive complexity, but also for its mathematical richness.  We develop a framework which succeeds in capturing salient aspects of the relaxations of graph isomorphism with tools furnished by nonlocal games. This framework allows us to introduce quantum and non-signalling isomorphism.

Hamiltonian simulation is a very promising area of quantum algorithms where quantum computers can provide a dramatic speedup over classical computers. Until recently, all algorithms had poor scaling in the allowable error. New algorithms allow for complexity scaling logarithmically in the allowable error. One is based on implementing a Taylor series, and another is based on a superposition of different numbers of steps of a quantum walk.

In complexity theory and cryptography, parallel repetition is a natural operation to reduce the error of a game or protocol without increasing the number of rounds. Raz's parallel repetition theorem is a cornerstone result in complexity theory showing that the value of two-player one round game, when repeated in parallel, decreases exponentially fast with the number of repetitions. Although the statement is intuitive, its analysis requires sophisticated techniques in information theory.

To give a reference point for the talk, I shall briefly summarize existing results regarding quantum computing for and from quantum field theory. I'll then describe some solved or open technical problems arising in this context, mentioning possible solutions of the latter. As will be apparent from this discussion, there exist various connections with topics in quantum optics and AMO physics.

Monogamy of entanglement limits the distribution of quantum correlations in a many-body system. The no-cloning theorem states that quantum information cannot be copied. From quantum cryptography to quantum chemistry simulations, these principles govern our approach to quantum information processing and distinguish it from classical information processing. For the most part, mathematical investigations of the monogamy of entanglement and "no-cloning" have been independent.

A very fundamental problem in quantum statistical mechanics involves whether--and how--an isolated quantum system will thermalize at long times. In quantum systems that do thermalize, the long-time expectation value of any "reasonable" operator will match its predicted value in the canonical ensemble. The Eigenstate Thermalization Hypothesis (ETH) posits that this thermalization occurs at the level of each individual energy eigenstate; in fact, any single eigenstate in a microcanonical energy window will predict the expectation values of such operators exactly.

The momentum-space entanglement properties of several quantum spin chains are investigated. More specifically, we study the entanglement spectra, i.e. the set of eigenvalues of the reduced density matrix, between left-and right-moving particles in bosonic and fermionic formulations of quantum spin chains. We elaborate on how momentum-space entanglement spectra may support the numerical study of phase transitions and classify certain critical systems.

For partial boolean functions, whose domain can be a subset of {0,1}^n, exponential separations are known between the number of queries a classical deterministic algorithm needs to compute a function and the number of queries a quantum algorithm needs. For a total boolean function f, whose domain is all of {0,1}^n, the situation is quite different: the quantum Q(f) and deterministic D(f) query complexities are always polynomially related, in fact D(f) = O(Q(f)^6).