Francisca Vasconcelos

Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(\log \log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of \emphconstant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit \textttTOFFOLI gates, (b) many-qubit \textttFANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit \textttTOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class \QAC^0. Finally, our results suggest a new approach towards proving that \textttPARITY is not computable in \QAC^0, a long-standing question in quantum complexity theory.

Block encodings are a fundamental primitive in quantum algorithms, but can often have large ancilla overhead. In this work, we introduce novel techniques for reducing this overhead in two distinct ways. In Part I, we prove the existence of a "space-time tradeoff" by deriving an algorithm that, for any block encoding, approximately uncomputes all but one of its ancilla (freeing up those ancillae for reuse in later parts of a quantum algorithm). In Part II, we evaluate the minimum number of ancillae required to perform coherent multiplication of block encodings. We prove that logarithmic ancillae is optimal for exact multiplication of block encodings. However, in certain block encoding regimes, we show that approximate multiplication of block encodings can be achieved to high-precision with just one ancilla.

We present the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, we provide a quasi-polynomial time and sample complexity algorithm for learning unknown QAC0 circuits – constant-depth circuits with arbitrary single-qubit gates and polynomially many CZ gates of unbounded width – up to inverse-polynomially small error. Furthermore, we show that the learned unitary can be efficiently synthesized in poly-logarithmic depth. This work expands the family of efficiently learnable quantum circuits, notably since in finite-dimensional circuit geometries, QAC0 circuits require polynomial depth to implement.

Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ε²) iterations to ε-Nash equilibria in the 4^d-dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ε) iterations to ε-Nash equilibria. This quadratic speed-up relative to Jain and Watrous’ original algorithm sets a new benchmark for computing ε-Nash equilibria in quantum zero-sum games.

The circuit class QAC⁰ was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC⁰ cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC⁰ circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC⁰ circuits. We conjecture that the Pauli spectrum of \mathsfQAC^0 circuits satisfies low-degree concentration, in analogy to the famous Linial, Nisan, Mansour theorem on the low-degree Fourier concentration of AC⁰ circuits. If true, this conjecture immediately implies that polynomial-size QAC⁰ circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC⁰ circuits with at most n^O(1/d) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute: (1) the n-bit parity function on more than (1/2 + 2^(-Ω(n^1/d)))-fraction of inputs, and (2) the n-bit majority function on more than (1 - 1/poly(n))-fraction of inputs. Additionally we show that this class of QAC⁰ circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC⁰ circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.