Circuits

Abstract: Quantum access to arbitrary classical data encoded in unitary black-box oracles underlies interesting data-intensive quantum algorithms, such as machine learning or electronic structure simulation. The feasibility of these applications depends crucially on gate-efficient implementations of these oracles, which are commonly some reversible versions of the boolean circuit for a classical lookup table. We present a general parameterized architecture for quantum circuits implementing a lookup table that encompasses all prior work in realizing a continuum of optimal tradeoffs between qubits, non-Clifford gates, and error resilience, up to logarithmic factors. Our architecture assumes only local 2D connectivity, yet recovers results, with the appropriate parameters, poly-logarithmic error scaling. We also identify novel regimes, such as simultaneous sublinear scaling in all parameters. These results enable tailoring implementations of the commonly used lookup table primitive to any given quantum device with constrained resources.

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.