Francisca Vasconcelos

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.

Implicit neural representations (INRs) have achieved impressive results for scene reconstruction and computer graphics, where their performance has primarily been assessed on reconstruction accuracy. As INRs make their way into other domains, where model predictions inform high-stakes decision-making, uncertainty quantification of INR inference is becoming critical. To that end, we study a Bayesian reformulation of INRs, UncertaINR, in the context of computed tomography, and evaluate several Bayesian deep learning implementations in terms of accuracy and calibration. We find that they achieve well-calibrated uncertainty, while retaining accuracy competitive with other classical, INR-based, and CNN-based reconstruction techniques. Contrary to common intuition in the Bayesian deep learning literature, we find that INRs obtain the best calibration with computationally efficient Monte Carlo dropout, outperforming Hamiltonian Monte Carlo and deep ensembles. Moreover, in contrast to the best-performing prior approaches, UncertaINR does not require a large training dataset, but only a handful of validation images.