Simulation of Quantum Circuits

Abstract: Certain families of quantum mechanical models can be described and solved efficiently on a classical computer, including qubit or qudit Clifford circuits and stabilizer codes, free-boson or free-fermion models, and certain rotor and GKP codes. We show that all of these families can be described as instances of the same algebraic structure, namely quadratic functions over abelian groups, or more generally over (super) Hopf algebras. Different kinds of degrees of freedom correspond to different "elementary" abelian groups or Hopf algebras: $\mathbb Z_2$ for qubits, $\mathbb Z_d$ for qudits, $\mathbb R$ for continuous variables, both $\mathbb Z$ and $\mathbb R/\mathbb Z$ for rotors, and a super Hopf algebra $\mathcal F$ for fermionic modes. Objects such as states, operators, superoperators, or projection-operator valued measures, etc, are tensors. For the solvable models above, these tensors are quadratic tensors based on quadratic functions. Quadratic tensors with $n$ degrees of freedom are fully specified by only $O(n^2)$ coefficients. Tensor networks of quadratic tensors can be contracted efficiently on the level of these coefficients, using an operation reminiscent of the Schur complement. Our formalism naturally includes models with mixed degrees of freedom, such as qudits of different dimensions. We also use quadratic functions to define generalized stabilizer codes and Clifford gates for arbitrary abelian groups. Finally, we give a generalization from quadratic (or 2nd order) to $i$th order tensors, which are specified by $O(n^i)$ coefficients but cannot be contracted efficiently in general.

Abstract: The classical simulation of noisy-intermediate scale quantum (NISQ) circuits has been a topic of intense study over the past few years. The majority of results on efficient simulation assume that the circuits undergo some variant of unital noise. For example, it has been shown that the output distributions of random quantum circuits and arbitrary IQP circuits undergoing depolarizing noise can be simulated in polynomial time with low error. However, it is currently unknown if such results can be extended to circuits undergoing non-unital noise. In this work, we answer this question partially by providing a classical algorithm to simulate the output distributions of arbitrary IQP circuits of depth d = Ω(log(n)) undergoing amplitude damping noise with a runtime O(dpoly(n/ϵ)).

Abstract: It has been known for almost 30 years that quantum circuits with interspersed depolarizing noise converge to the uniform distribution at 𝜔(log n) depth, where n is the number of qubits, making them classically simulable. We show that under the realistic constraint of geometric locality, this bound is loose: these circuits become classically simulable at even shallower depths. While prior work in this regime considered quantum circuits with random gates/inputs or circuits with high levels of noise, we consider sampling from any quantum circuit and noise of any constant strength. First, we prove that the output distributions of noisy geometrically local quantum circuits can be approximately sampled from in quasipolynomial time, when their depth exceeds a fixed Θ(log n) critical threshold which depends on the noise strength. This scaling in n matches classical simulability results that were previously only known for noisy random quantum circuits (Aharonov et al., STOC 2023). We further conjecture that our bound is still loose and that a Θ(1)-depth threshold suffices for simulability due to a percolation effect. To support this, we provide analytical evidence together with a candidate efficient algorithm. Our results rely on new information-theoretic properties of the output states of noisy shallow quantum circuits, which may be of broad interest. On a fundamental level, we demonstrate that unitary quantum processes in constant dimensions are more fragile to noise than previously understood.