Magic state preparation is often among the most expensive operations in a fault tolerant quantum computation. One obstacle to coming up with better magic state preparation circuits lies in verifying their fault tolerance properties, as it is difficult to verify either by hand or in software that a very large number of combinations of faults do not give rise to high-weight or logical errors, especially in a non-Clifford circuit. In this work, we propose the use of the CNOT + T gate set to fault-tolerantly prepare a large class of magic states. We consider the propagation of Pauli faults within CNOT + T circuits and derive properties similar to those of Pauli faults within Clifford circuits, with a view to verifying fault tolerance as efficiently as possible. We present Comb, a library that can verify the fault tolerance of CNOT + T magic state preparation circuits, and demonstrate its use in verifying the fault tolerance of distance three and distance five magic state preparation circuits in minutes on a laptop. We present a distance five magic state preparation circuit that was discovered using Comb. As an independent confirmation of Comb's correctness we compare its findings to circuit-level noisy simulations for several magic state preparation circuits.
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 more 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
1≤t≤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 then provide families of such optimal graphs for infinitely many values of
n and
t≤5. By encoding the construction of optimal graphs as a constraint satisfaction problem we find explicit constructions for circuits that match this lower bound on CNOT count for all
n≤50 and
t≤5 and for nearly all pairs
(n,t) with
n≤100 and
t≤5 or
n≤50 and
t≤7, significantly extending the regimes that were achievable by previous methods and improving the resource counts for existing constructions. We additionally show how to trade CNOT count against depth, allowing us to construct constant-depth fault-tolerant implementations using
O(n) ancilla and
O(n) CNOT gates.
The well-known 3-bit Hermitian gate (a Toffoli gate) has been implemented using Clifford + T circuits. Compared with the Peres gate, its implementation circuit requires more controlled-NOT (CNOT) gates. However, the Peres gate is not Hermitian. This paper reports four 3-bit Hermitian gates named LI gates. Whose realized circuits have the same T-count, T-depth, and CNOT-count as the Peres gate. Furthermore, two decomposition methods of a multiple control Toffoli (MCT) gate are proposed for different primary optimization goals. Then, we design the equality, less-than, and full comparators with the minimum circuit width using proposed Hermitian gates and optimized MCT gates. A fault-tolerant circuit is required for robust quantum computing. Clifford+T circuits are accepted solutions for fault-tolerant implementation. Considering T-count, T-depth, CNOT-count, and circuit width as the primary optimization goals, we design the optimized Clifford + T circuits of three comparators using LI gates and optimized MCT gates. Comparison and analysis show that the proposed comparators have better overall performances for T-count, T-depth, CNOT-count, and circuit width than the best-known comparators without quantum measurements.