Andrey Boris Khesin

Random classical linear codes are widely believed to be hard to decode, exponentially so at constant coding rate. If the rate vanishes asymptotically sufficiently rapidly, slightly sub-exponential decoding algorithms are known. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate—the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any coding rate, would immediately imply a breakthrough in cryptography. More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. Our work also demonstrates several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding—all of which are classically identical—to have distinct or non-trivially equivalent complexity.

The ability to fault-tolerantly prepare cat states, also known as multi-qubit GHZ states, is an important primitive for quantum error correction. It is required for Shor-style syndrome extraction, and can also be used as a subroutine for doing fault-tolerant state preparation of CSS codewords. Existing approaches to fault-tolerant cat state preparations have been found using computationally expensive heuristics involving SAT solving, reinforcement learning or exhaustive analysis. In this paper we constructively find optimal circuits for cat states in a scalable way. In particular, we derive formal lower bounds on the number of CNOT gates required for circuits implementing n-qubit cat-states that do not spread errors of weight at most t for values t = 1, ..., 5. We do this by using fault-equivalent rewrites of ZX-diagrams to reduce it to a problem of characterising certain 3-regular simple graphs. We provide explicit constructions for circuits that match this lower bound for all n and t <= 5. Furthermore, we use SAT solvers to construct circuits for all n <= 50 and t <= 7. We additionally show how to trade CNOT count against depth, in particular allowing us to construct constant-depth fault-tolerant implementations using O(n) ancilla and O(n) CNOT gates.