Steven Flammia

Abstract Random quantum circuits have played a central role in establishing the computational advantages of near-term quantum computers over their conventional counterparts. Here, we use ensembles of low-depth random circuits with local connectivity in D spatial dimensions to generate quantum error-correcting codes. For random stabilizer codes and the erasure channel, we find strong evidence that a depth O(logN) random circuit is necessary and sufficient to converge (with high probability) to zero failure probability for any finite amount below the channel capacity for any D. Previous results on random circuits have only shown that O(N^1/D) depth suffices or that O(log^3 N) depth suffices for all-to-all connectivity. We then study the critical behavior of the erasure threshold in the so-called moderate deviation limit, where both the failure probability and the distance to the channel capacity converge to zero with N. We find that the requisite depth scales like O(log N) only for dimensions D=2, and that random circuits require O(N^1/2) depth for D=1. Finally, we introduce an "expurgation" algorithm that uses quantum measurements to remove logical operators that cause the code to fail by turning them into either additional stabilizers or into gauge operators in a subsystem code. With such targeted measurements, we can achieve sub-logarithmic depth in D=2 spatial dimensions below capacity without increasing the maximum weight of the check operators. We find that for any rate beneath the capacity, high-performing codes with thousands of logical qubits are achievable with depth 4-8 expurgated random circuits in D=2 dimensions. These results indicate that finite-rate quantum codes are practically relevant for near-term devices and may significantly reduce the resource requirements to achieve fault tolerance for near-term applications.

Abstract Exactly solvable models are essential in physics. For many-body spin-1/2 systems, an important class of such models consists of those that can be mapped to free fermions hopping on a graph. We provide a complete characterization of models which can be solved this way. Specifically, we reduce the problem of recognizing such spin models to the graph-theoretic problem of recognizing line graphs, which has been solved optimally. A corollary of our result is a complete set of constant-sized commutation structures that constitute the obstructions to a free-fermion solution. We find that symmetries are tightly constrained in these models. Pauli symmetries correspond to either: (i) cycles on the fermion hopping graph, (ii) the fermion parity operator, or (iii) logically encoded qubits. Clifford symmetries within one of these symmetry sectors, with three exceptions, must be symmetries of the free-fermion model itself. We demonstrate how several exact free-fermion solutions from the literature fit into our formalism and give an explicit example of a new model previously unknown to be solvable by free fermions

Abstract We show that a variant of the surface code---the XZZX code---offers remarkable performance for fault-tolerant quantum computation. The error threshold of this code matches what can be achieved with random codes (hashing) for \emph{every} single-qubit Pauli noise channel; it is the first explicit code shown to have this universal property. We present numerical evidence that the threshold even exceeds this hashing bound for an experimentally relevant range of noise parameters. Focusing on the common situation where qubit dephasing is the dominant noise, we show that this code has a practical, high-performance decoder and surpasses all previously known thresholds in the realistic setting where syndrome measurements are unreliable. We go on to demonstrate the favorable sub-threshold resource scaling that can be obtained by specializing a code to exploit structure in the noise. We show that it is possible to maintain all of these advantages when we perform fault-tolerant quantum computation. We finally suggest some small-scale experiments that could exploit noise bias to reduce qubit overhead in two-dimensional architectures. The complete version of this paper can be found at https://arxiv.org/abs/2009.07851.

Estimating quantum time-series such as the Loschmidt echo $f(t)=\langle\psi|\mathrm{e}^{-\mathrm{i}Ht}|\psi\rangle$ is central to spectroscopy and Hamiltonian analysis. Direct estimation via the Hadamard test requires controlled implementations of $\mathrm{e}^{-\mathrm{i}Ht}$, and the depth of these controlled circuits grows with $t$, making long-time estimation challenging on near-term hardware. Inspired by the classical Phaselift approach to phase retrieval, we introduce Quantum Phaselift, a lifting-based framework that estimates the rank-one matrix $Z = f f^\dagger$ sampled at discrete times instead of $f$ directly. We propose quantum circuits for estimating the entries of $Z$ and prove that measuring only a narrow band of this matrix around the diagonal provides sufficient data for unique signal reconstruction. This reformulation reduces the depth of required controlled circuits to scale with the width of the measured band, rather than with the total evolution time. We then show that generic signals can be recovered from a band of width $O(1)$, providing a substantial savings in controlled operations compared to naïve algorithms. We develop three robust estimators to recover the signal from the noisy measurements of the entries on this narrow band: a block-by-block algebraic estimator, a block-by-block eigenvector estimator, and a least-squares estimator. We rigorously prove exact recovery for all three estimators in the noiseless setting and establish stability guarantees and sample complexity bounds for the block-by-block algebraic estimator in the presence of measurement noise. Finally, we numerically demonstrate that high-quality signal recovery is possible for the 2D Fermi-Hubbard and 2D transverse-field Ising model time-series with more than 100 points using only a few million samples and reasonable post-processing time, making our recovery techniques efficient and effective for near-term implementations.

Modern quantum devices require high-precision Hamiltonian dynamics, but environmental noise can cause calibrated Hamiltonian parameters to drift over time, necessitating expensive recalibration. Detecting when recalibration is needed is challenging, especially since the very gates required for sophisticated verification protocols may themselves be miscalibrated. While cloud quantum computing services implement heuristic routines for triggering recalibration, the fundamental limits of optimal recalibration have yet to be illuminated. Here we study the recalibration problem by developing efficient Hamiltonian certification and \changepoint{} detection protocols in the \emph{autonomous} setting. In this setting we use only single-qubit gates and measurements and do not use any ancilla qubits, making the protocols robust to the calibration issues for multi-qubit operations they aim to detect. For an unknown $n$-qubit $M$-sparse Hamiltonian $H$, our certification protocol distinguishes whether $\|H - H_0\|_F \geq \epsilon$ or $\|H - H_0\|_F \leq O(\epsilon/\sqrt{n})$ with sample complexity $\mathcal{O}(nM^2\ln(1/\delta)/\epsilon^2)$ and total evolution time $\mathcal{O}(nM\ln(1/\delta)/\epsilon^2)$, where $H_0$ is the target Hamiltonian and $\delta$ bounds the failure probability. The protocol achieves this by evolving random stabilizer product states and performing adaptive single-qubit measurements based on a classically simulable hypothesis state. Extending this to continuous monitoring, we develop an online \changepoint{} detection algorithm using the CUSUM procedure that achieves a detection delay bound of $\mathcal{O}(nM\ln(M\falsealarm{T})/\epsilon^2)$, matching the known asymptotically optimal scaling with respect to false alarm run length $\falsealarm{T}$. Our approach enables quantum devices to autonomously monitor their own calibration status without requiring ancillary systems, entangling operations, or a trusted reference device, and provides maximum-likelihood estimates of \changepoint{} locations to identify and rerun affected computations, offering a practical solution for robust quantum computing with contemporary noisy devices.