Benjamin Rodatz

A key challenge in fault-tolerant quantum computing is synthesising and optimising circuits in a noisy environment, as traditional techniques often fail to account for the effect of noise on circuits. In this work, we propose a framework for designing fault-tolerant quantum circuits that are correct by construction. The framework starts with idealised specifications of fault-tolerant gadgets and refines them using provably sound basic transformations. To reason about manipulating circuits while preserving their error correction properties, we define fault equivalence; two circuits are considered fault-equivalent if all undetectable faults on one circuit have a corresponding fault on the other. This guarantees that the effect of undetectable faults on both circuits is the same. We argue that fault equivalence is a concept that is already implicitly present in the literature. Many problems, such as state preparation and syndrome extraction, can be naturally expressed as finding an implementable circuit that is fault-equivalent to an idealised specification. To utilise fault equivalence in a computationally tractable manner, we adapt the ZX calculus, a diagrammatic language for quantum computing. We restrict its rewrite system to not only preserve the underlying linear map but also fault equivalence, i.e. the circuit's behaviour under noise. We show that this rewriting system is complete, meaning that two circuits are fault-equivalent if and only if one can be transformed into the other using fault-equivalent ZX rewrites. Enabled by our framework, we verify, optimise and synthesise new and efficient circuits for syndrome extraction and cat state preparation. We anticipate that fault equivalence can capture and unify different approaches in fault-tolerant quantum computing, paving the way for an end-to-end circuit compilation framework.

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.