IQC-QuICS Math-CS Seminar

In quantum optics, the Hilbert space of a mode of light corresponds to functions on a plane called the phase space (so called because it reminded Boltzmann of oscillators in 2-d real space.)  This correspondence offers three important features:  it can autonomously handle quantum theoretical calculations, it allows for the infinite-dimensional Hilbert space to be easily visualized, and it is intimately related to a basic experimental measurement (the so-called heterodyne detection).  Continuous phase space correspondences exist naturally for many types of Hilbert space

The stabilizer rank of a quantum state ψ is the minimal integer r such that ψ can be written as a linear combination of r stabilizer states. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n-th tensor power of single-qubit magic states. In this talk we'll present a recent improved lower bound of Ω(n) on the stabilizer rank of such states, and an Ω(sqrt{n}/log n) lower bound on the rank of any state which approximates them to a high enough accuracy.

Quantifying quantum states’ complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. We prove a prominent conjecture by Brown and Susskind about how random quantum circuits’ complexity increases. Consider constructing a unitary from Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitary’s exact circuit complexity.

We study quantum error correcting codes generated by local random circuits and consider the circuit depth required to achieve high-performance against local error models. Notably, we find that random circuits in D spatial dimensions generate high-performing codes at depth at most O(log N) independent of D. Our approach to quantum code design is rooted in arguments from statistical physics and establishes several deep connections between random quantum coding and critical phenomena in phase transitions.

Fault-tolerant error correction (FTEC), a procedure which suppresses error propagation in a quantum circuit, is one of the most important components for building large-scale quantum computers. One major technique often used in recent works is the flag technique, which uses a few ancillas to detect faults that can lead to errors of high weight and is applicable to various fault-tolerant schemes. In this talk, I will further improve the flag technique by introducing the use of error weight parities in error correction.

Fermionic Linear Optics (FLO) is a restricted model of quantum computation which in its original form is known to be efficiently classically simulable. We show that, when initialized with suitable input states, FLO circuits can be used to demonstrate quantum computational advantage with strong hardness guarantees. Based on this, we propose a quantum advantage scheme which is a fermionic analogue of Boson Sampling: Fermion Sampling with magic input states.

In many natural situations where the input consists of n quantum systems, each associated with a state space C^d, we are interested in problems that are symmetric under the permutation of the n systems as well as the application of the same unitary U to all n systems. Under these circumstances, the optimal algorithm often involves a basis transformation, known as (quantum) Schur transform, which simultaneously block-diagonalizes the said actions of the permutation and the unitary groups.

Differential equations are ubiquitous throughout mathematics, natural and social science, and engineering. There has been extensive previous work on efficient quantum algorithms for linear differential equations. However, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. We give the first quantum algorithm for dissipative nonlinear differential equations that is efficient provided the dissipation is sufficiently strong relative to the nonlinearity and the inhomogeneity.

Recently, works such as the landmark MIP*=RE paper by Ji et. al. have established deep connections between computability theory and the power of nonlocal games with entangled provers. Many of these works start by establishing compression procedures for nonlocal games, which exponentially reduce the verifier's computational task during a game. These compression procedures are then used to construct reductions from uncomputable languages to nonlocal games, by a technique known as iterated compression.