QuICS seminar

How powerful are quantum computers? Despite the prevailing belief that quantum computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's algorithm, for instance, gives an example of a problem (factoring), which can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring however, is unlikely to be NP-hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered.

In this talk I will talk about the power of quantum proofs in the framework of quantum query complexity. Specifically, I will discuss the trade-off between the number of queries to an input string and the number of qubits of a quantum proof needed to verify whether the input string possesses a property of interest, and how this trade-off is affected if we only require the algorithm to output the correct answer on a fraction of the inputs.

The Shannon and von Neumann entropies quantify the uncertainty in a system. They are operationally motivated by natural information processing tasks such as compression, channel coding or randomness extraction. In addition to characterizing the fundamental rates at which such tasks can be performed, their additivity properties make them a very valuable tool in applications ranging from complexity theory to many-body systems.

We propose a family of exactly solvable toy models for the AdS/CFT correspondence based on a novel construction of quantum error-correcting codes with a tensor network structure. Our building block is a special type of tensor with maximal entanglement along any bipartition, which gives rise to an exact isometry from bulk operators to boundary operators. The entire tensor network is a quantum error-correcting code, where the bulk and boundary degrees of freedom may be identified as logical and physical degrees of freedom respectively.

We study (d−1)-dimensional excitations in the d-dimensional color code that are created by transversal application of the R_d phase operators on connected subregions of qubits. We find that such excitations are superpositions of electric charges and can be characterized by fixed-point wavefunctions of (d−1) dimensional bosonic SPT phases with (Z_2)^(\otimes d) symmetry.

Quantum field theory provides the framework for the Standard Model of particle physics and plays a key role in physics. However, calculations are generally computationally complex and limited to weak interaction strengths. I'll describe polynomial-time quantum algorithms for computing relativistic scattering amplitudes in both scalar and fermionic quantum field theories. The algorithms achieve exponential speedup over known classical methods. One of the motivations for this work comes from computational complexity theory.

In this talk I’ll present recent results relating the time of preparation of thermal states by quantum Gibbs samplers, the analogue of classical metropolis sampling. In particular I will connect the efficiency of quantum Gibbs samplers to the static properties of the thermal state, in particular whether it has a finite correlation length.

In recent years, deep learning has achieved great success in many areas of artificial intelligence, such as computer vision, speech recognition, natural language processing, etc. Its central idea is to build a hierarchy of successively more abstract representations of data (e.g. image, audio, text) by using a neural network with many layers. Training such a deep neural network, however, can be very time-consuming. In this talk, we will investigate whether quantum computing can make this process more efficient.

One of the best known problem that a quantum computer is expected to solve more efficiently than a classical one is the simulation of quantum systems. While significant work has considered the case of discrete, finite dimensional quantum systems, the study of fast quantum simulation methods for continuous-variable systems has only received little attention. In this talk, I will present quantum methods to simulate the time evolution of two quantum systems, namely the quantum harmonic oscillator and the quantum particle in a quartic potential.

We propose a quantum voting system in the spirit of quantum games such as the quantum Prisoner’s Dilemma. Our scheme violates a quantum analogue of Arrow’s Impossibility Theorem, which states that every (classical) constitution endowed with three innocuous-seeming properties is a dictatorship. Superpositions, interference, and entanglement of votes feature in voting tactics available to quantum voters but not to classical. (This work was conducted with Ning Bao. Reference: arXiv:1501.00458v1.)