Quantum Cambridge-Oxford-Warwick Colloquium: Talk abstracts

Complexity theoretic and physics view on shallow quantum circuits (Anurag Anshu)

Shallow quantum circuits—quantum circuits of low depth—occupy a central role in both quantum many-body physics and quantum computer science. They naturally arise in attempts to probe and simulate quantum many-body systems and mark a meaningful boundary between weakly entangled states and highly correlated states. Considerable recent effort has focused on understanding the capability of such circuits to approximate ground states and low-energy states of families of local Hamiltonians.

This tutorial will survey rigorous schemes for approximating ground energies with shallow circuits, along with lower-bound techniques that clarify why many physically and computationally interesting Hamiltonians resist such approximations. We will also examine the limitations of current lower-bound methods and highlight compelling open problems. In addition, the tutorial will discuss what is known about the learnability of shallow circuits and outline several open directions in this emerging area.

Unconditional pseudorandomness against shallow quantum circuits (Sathya Subramanian)

Most recent progress on quantum pseudorandomness targets powerful adversaries and relies on cryptographic assumptions. In this talk, we take a different perspective: what pseudorandomness can be achieved unconditionally when the adversary is restricted?

We will see that for adversaries that are constant-depth, bounded-fan-in quantum circuits (QNC⁰, allowing arbitrary ancillae), even with additional AC⁰ post-processing, any quantum state 2-design already suffices for unconditional pseudorandomness. Using random phased subspace states then provides explicit constructions of pseudoentangled states against these shallow adversaries. Similarly, unitary 2-designs naturally give rise to parallel-query pseudorandom unitaries that are secure against geometrically local QNC⁰ circuits.

The main theme of the talk will be how the severe locality constraints of shallow circuits allow the usual two-copy statistical guarantees of 2-designs to be promoted to computational indistinguishability under polynomially many queries. Throughout, we will highlight connections to existing approaches to pseudorandomness, contrast them with the shallow-adversary viewpoint, and outline open directions for further inquiry into this aspect of the complexity of shallow quantum circuits.

Pauli spectrum analysis toolkit for quantum learning and quantum pseudorandomness (Mina Doosti)

I will introduce Pauli Spectrum Analysis as a powerful toolkit for quantum learning theory, with a focus on learning quantum channels. I will present some results obtained through this technique, including applications to shallow quantum circuits in both black-box and statistical query learning models. I will also discuss the implications of these results for quantum pseudorandomness.

Random unitaries from random quantum circuits (Jonas Haferkamp)

We review recent results on the convergence of random quantum circuits to random unitaries. In particular, we show that random circuits on any geometry, including a 1D line, can form approximate unitary designs over n qubits in log n depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in polylog n depth. In both cases, the n dependence is optimal and improves exponentially over known results. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.

Quantum Advantage from Sampling Shallow Circuits (Daniel Grier)

How can we prove that quantum computers are unconditionally better than classical computers? One answer that has emerged over the last decade is to compare the depths of quantum and classical circuits for the same task. After surveying this area, I will describe some recent work that attempts to give the simplest and most basic form of this kind of quantum-classical separation. Namely, I will describe a *single* distribution (for each number of qubits) that can be sampled by a simple constant-depth quantum circuit that cannot be sampled in constant depth by a classical circuit.

Constant-depth quantum circuits with large gates (Greg Rosenthal)

We will survey the landscape of constant-depth quantum circuit classes with gates that may act on an unbounded number of qubits. The high-level takeaways are that i) many such classes are now known to be equivalent, and ii) there are formal barriers to proving strong lower bounds for these equivalent classes. Despite this, there are several interesting open problems in the area which we will discuss as well.

General techniques in constructing constant-depth circuits for Boolean functions and beyond (João Doriguello)

In this talk, we review and summarise several known techniques for constructing Boolean functions and related unitaries in constant depth using special gates like the Fan-Out or the Global Tunable gate, most of these techniques being based on different Fourier decompositions. Special care is given to important gates like AND, OR, THRESHOLD, QRAM, and QRAG.

QAC^0 and the Quest to Compute Parity (Francisca Vasconcelos)

In the NISQ era, where noise limits device coherence times, we are fundamentally constrained to shallow quantum computation. This talk will explore the power and limitations of the QAC^0 circuit class--i.e. the family of polynomial-sized, constant-depth quantum circuits composed of arbitrary single-qubit gates and unbounded CZ/Toffoli gates. I will center the discussion around a long-standing open problem in quantum circuit complexity: is Parity computable in QAC^0? This question is central to our understanding of the power of QAC^0 and its relationship to classical AC^0. I will survey the growing literature of upper- and lower-bounds for this problem, highlighting how the techniques behind these results have led to a range of exciting applications such as efficient learnability of and pseudorandomness in QAC^0. The talk is based on joint work with Ben Foxman, Hsin-Yuan Huang, Malvika Joshi, Shivam Nadimpalli, Natalie Parham, Avishay Tal, John Wright, and Henry Yuen, as well as results by several others in the field.