Fernando G. S. L. Brandão

We present a protocol for fault-tolerantly implementing the logical quantum random access memory (QRAM) operation, given access to a specialized, noisy QRAM device. For coherently accessing classical memories of size 2^n, our protocol consumes only poly(n) fault-tolerant quantum resources (logical gates, logical qubits, quantum error correction cycles, etc.), avoiding the need to perform active error correction on all Ω(2^n) components of the QRAM device. This is the first rigorous conceptual demonstration that a specialized, noisy QRAM device could be useful for implementing a fault-tolerant quantum algorithm. In fact, the fidelity of the device can be as low as 1/poly(n). The protocol queries the noisy QRAM device poly(n) times to prepare a sequence of n-qubit QRAM resource states, which are moved to a general-purpose poly(n)-size processor to be encoded into a QEC code, distilled, and fault-tolerantly teleported into the computation. To aid this protocol, we develop a new gate-efficient streaming version of quantum purity amplification that matches the optimal sample complexity in a wide range of parameters and is therefore of independent interest. The exponential reduction in fault-tolerant quantum resources comes at the expense of an exponential quantity of purely classical complexity---each of the n iterations of the protocol requires adaptively updating the 2^n-size classical dataset and providing the noisy QRAM device with access to the updated dataset at the next iteration. We show that this classical operation can be parallelized to poly(n) classical circuit depth, but only in a model where classical sparse matrix-vector multiplication for 2^n-dimensional vectors can be as well. While our protocol demonstrates that QRAM is more compatible with fault-tolerant quantum computation than previously thought, the need for significant classical computational complexity exposes potentially fundamental limitations to realizing a truly poly(n)-cost fault-tolerant QRAM.

Understanding how fast physical systems can resemble Haar-random unitaries is a fundamental question in physics. Many experiments of interest in quantum gravity and many-body physics, including the butterfly effect in quantum information scrambling and the Hayden-Preskill thought experiment, involve queries to a random unitary~$U$ alongside its inverse~$U^\dagger$, conjugate~$U^*$, and transpose~$U^T$. However, conventional notions of approximate unitary designs and pseudorandom unitaries (PRUs) fail to capture these experiments. In this work, we introduce and construct strong unitary designs and strong PRUs that remain robust under all such queries. Our constructions achieve the optimal circuit depth of $\mathcal{O}(\log n)$ for systems of $n$ qubits. We further show that strong unitary designs can form in circuit depth $\mathcal{O}(\log^2 n)$ in circuits composed of independent two-qubit Haar-random gates, and that strong PRUs can form in circuit depth $\poly(\log n)$ in circuits with no ancilla qubits. Our results provide an operational proof of the fast scrambling conjecture from black hole physics: every observable feature of the fastest scrambling quantum systems reproduces Haar-random behavior at logarithmic times.

Haar-random unitaries are fundamental mathematical tools for understanding quantum many-body dynamics, yet they fail to obey basic physical constraints imposed by Hamiltonians. In this work, we explore how to reconcile random unitary models with physical constraints imposed by Hamiltonians, addressing the central question: Can we efficiently generate random unitaries while obeying Hamiltonian constraints? First, we consider the role of energy conservation in the setting where the Hamiltonian $H$ is completely known. There, we show that energy-conserving pseudorandom unitaries (PRUs) exist for random local commuting Hamiltonians, assuming quantum-secure one-way functions exist. However, we also prove that energy-conserving PRUs do not exist for some local translation-invariant Hamiltonians, even in one-dimensional systems. Furthermore, we show that determining whether energy-conserving PRUs exist for a family of Hamiltonians is undecidable. Second, we consider Hamiltonian time dynamics itself when there is incomplete knowledge of $H$. In this setting, we prove that random unitaries $e^{-iHt}$ generated from any ensemble of constant-local Hamiltonians $H$ cannot form approximate unitary designs or PRUs. This barrier vanishes when we relax locality: we construct an ensemble of polylog-local Hamiltonians $H$ that generates short-time dynamics which form both a unitary design and a PRU. Our results reveal fundamental computational barriers emerging from energy conservation constraints, highlighting the tension between common models of ergodicity and the structure of physical dynamics.

We address a question of leveraging the noise bias to simplify quantum error correction (QEC) protocols and improve their performance. We focus on the previously unexplored bias between the amplitude damping and dephasing errors that is fundamental to many quantum technologies. We propose a simple scheme to convert amplitude damping errors into erasure errors. Despite its simplicity, our scheme significantly improves the performance of QEC protocols and can be extended to handle leakage errors. Importantly, we provide two concrete realizations with superconducting circuits, analyzing their performance both from the analytical and numerical perspective. Our results provide a breakthrough shift in the current architecture paradigm. Namely, they suggest that engineering efforts should focus on improving the dephasing and the quality of quantum coherent control, as they effectively limit the performance of fault-tolerant protocols.

Abstract Random quantum circuits are commonly viewed as hard to simulate classically. In some regimes this has been formally conjectured, and there had been no evidence against the more general possibility that for circuits with uniformly random gates, approximate simulation of typical instances is almost as hard as exact simulation. We prove that this is not the case by exhibiting a shallow circuit family with uniformly random gates that cannot be efficiently classically simulated near-exactly under standard hardness assumptions, but can be simulated approximately for all but a superpolynomially small fraction of circuit instances in time linear in the number of qubits and gates. We furthermore conjecture that sufficiently shallow random circuits are efficiently simulable more generally. To this end, we propose and analyze two simulation algorithms. Implementing one of our algorithms numerically, we give strong evidence that it is efficient both asymptotically and, in some cases, in practice. To argue analytically for efficiency, we reduce the simulation of 2D shallow random circuits to the simulation of a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements -- a type of process that has generally been observed to undergo a phase transition from an efficient-to-simulate regime to an inefficient-to-simulate regime as measurement strength is varied. Using a mapping from quantum circuits to statistical mechanical models, we give evidence that a similar computational phase transition occurs for our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied.

Abstract We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes. Understanding the conditions for anti-concentration is important for determining which quantum circuits are difficult to simulate classically, as anti-concentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation. Our definition of anti-concentration is that the expected collision probability, that is, the probability that two independently drawn outcomes will agree, is only a constant factor larger than if the distribution were uniform. We show that when the 2-local gates are each drawn from the Haar measure (or any two-design), at least O(n log(n)) gates (and thus O(log(n)) circuit depth) are needed for this condition to be met on an n qudit circuit. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show O(n log(n)) gates are also sufficient, and we precisely compute the optimal constant prefactor for the n log(n). The technique we employ relies upon a mapping from the expected collision probability to the partition function of an Ising-like classical statistical mechanical model, which we manage to bound using stochastic and combinatorial techniques.

The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a short-cut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary k-designs, ensembles which capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. The class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into constant factor approximations of the original quadratic optimization problem.

We give a strengthening as well as a generalization of an inequality for the quantum conditional mutual information of a tripartite quantum state recently proved by Fawzi and Renner, connecting it with the ability to reconstruct the state from its bipartite reductions. We provide three alternative and simplified proofs ranging from quantum state redistribution via duality of semidefinite programming to elementary properties of pinching maps and the operator logarithm.