Clifford circuit optimization is an important step in the quantum compilation pipeline. Major compilers employ heuristic approaches. While they are fast, their results are often suboptimal. Minimization of noisy gates, like 2-qubit CNOT gates, is crucial for practical computing. Exact approaches have been proposed to fill the gap left by heuristic approaches. Among these are SAT based approaches that optimize gate count or depth, but they suffer from scalability issues. Further, they do not guarantee optimality on more important metrics like CNOT count or CNOT depth. A recent work proposed an exhaustive search only on Clifford circuits in a certain normal form to guarantee CNOT count optimality. But an exhaustive approach cannot scale beyond 6 qubits. In this paper, we incorporate search restricted to Clifford normal forms in a SAT encoding to guarantee CNOT count optimality. By allowing parallel plans, we propose a second SAT encoding that optimizes CNOT depth. By taking advantage of flexibility in SAT based approaches, we also handle connectivity restrictions in hardware platforms, and allow for qubit relabeling. We have implemented the above encodings and variations in our open source tool Q-Synth. In experiments, our encodings significantly outperform existing SAT approaches on random Clifford circuits. We consider practical VQE and Feynman benchmarks to compare with TKET and Qiskit compilers. In all-to-all connectivity, we observe reductions up to 32.1% in CNOT count and 48.1% in CNOT depth. Overall, we observe better results than TKET in the CNOT count and depth. We also experiment with connectivity restrictions of major quantum platforms. Compared to Qiskit, we observe up to 30.3% CNOT count and 35.9% CNOT depth further reduction.
The conventional circuit paradigm, utilizing a small set of gates to construct arbitrary quantum circuits, is hindered by significant noise. In the quantum Fourier transform, for instance, the standard gate paradigm employs two CNOT gates for the partial CPhase. In contrast, some quantum computers can directly implement such operations using their native interaction, resulting in less noisy gates. Unfortunately, coherent errors degrade the performance of these gates. In Clifford gates such as the CNOT, these errors can be addressed through randomized compiling (RC). However, RC does not apply to the non-Clifford multi-qubit native implementations described above. The present work introduces and experimentally demonstrates a technique called ‘Pseudo Twirling’ (PST) to address coherent errors. We demonstrate experimentally that integrating PST with the ‘Adaptive KIK’ quantum error mitigation method enables the simultaneous mitigation of noise and coherent errors in multi-qubit non-Clifford gates.
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.