Richie Yeung

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.

Randomness extractors are an essential component in numerous applications, for example, for privacy amplification in quantum key distribution and randomness extraction in random number generation. Despite their importance, selecting, optimising and implementing the appropriate extractor and parameters requires significant expertise and time investment. We present Cryptomite, a publicly available software library that provides a variety of two-source, seeded, and deterministic randomness extractor implementations with state-of-the-art performance. The software is efficient, numerically precise and capable of handling input sizes up to $10^{12}$, allowing for use even in resource intensive protocols, e.g. device-independent ones. Alongside the software, we provide theoretical contributions that include improvements and generalisations to existing extractors, new extractor constructions and parameter calculation in a variety of useful security models. To showcase the library, we empirically compare the properties of the output of several random number generators and the effect of different randomness extraction methods on it, using intense statistical testing.