Technical Summary: High-Performance Exact Synthesis of Two-Qubit Quantum Circuits

Problem Statement

Exact quantum circuit synthesis aims to completely characterize a well-defined region of circuit space to identify which unitaries are reachable and to determine their optimal circuits under a specific cost metric. While heuristic optimization produces "good enough" circuits quickly, it lacks the unconditional optimality and canonical structure required for rigorous verification and the creation of reusable building blocks.

The general problem of exact synthesis for Clifford+T circuits is computationally intractable (NP-hard and co-NQP-hard), particularly when minimizing T-count (the number of non-Clifford T gates, which dominate resource costs in fault-tolerant architectures). Consequently, exact methods have historically been limited to small, carefully scoped regimes. This paper addresses the challenge of making exact synthesis practical for two-qubit Clifford+T circuits by focusing on a "pay once, query forever" strategy: exhaustively enumerating a bounded search space offline to create a database of optimal representatives that can be reused across compilation tasks.

Methodology

The authors propose a synthesis framework that combines exhaustive breadth-first enumeration with meet-in-the-middle (MITM) search, underpinned by a high-performance algebraic backbone. The approach relies on three core pillars:

1. Algebraic Representation and Equivalence

To manage the complexity of the search space, the authors map two-qubit Clifford+T circuits into the special orthogonal group $SO(6)$ via a two-to-one cover $\Phi: SU(4) \to SO(6)$.

• Gate Set: Instead of standard generators, they utilize a generating set $G = \{G_{i,j}\}$ derived from Clifford conjugates of $T \otimes I$. These generators are chosen to facilitate efficient enumeration by T-count.
• Equivalence Classes: The framework defines an equivalence relation where two circuits are equivalent if they differ by global phase and left/right multiplication by Clifford operations ($C_2$). This allows the system to store only one optimal representative per equivalence class rather than all possible circuits.
• Involutive Generators: The authors demonstrate that representatives can be generated using a set of involutions, simplifying the search structure and enabling efficient pruning.

2. Algorithmic Structure

The synthesis engine operates in two modes:

• Lookup Table (LUT) Generation: A breadth-first search (Algorithm 1) enumerates circuits layer by layer (by T-count). It uses a canonicalization procedure to filter out redundant representatives, ensuring exactly one representative per equivalence class is stored for each T-distance.
• Meet-in-the-Middle (MITM) Search: To synthesize a specific target unitary, the algorithm performs a bidirectional search (Algorithm 2). It expands layers from the identity and the target simultaneously until an intersection is found. The algorithm employs provable pruning rules based on the parity of T-count (Theorem 4.2), ensuring that the search does not revisit layers of the same parity and that the first intersection found corresponds to a minimal T-count solution.

3. High-Performance Implementation

The paper emphasizes that the algorithm's theoretical simplicity is deceptive; practical feasibility relies on replacing general-purpose linear algebra with gate-set-aware arithmetic.

• Specialized Kernels: Instead of generic $6 \times 6$ matrix multiplication, T-steps are implemented as specialized linear maps acting on specific rows. This reduces operations to constant-time integer arithmetic and bit manipulations.
• Packed Arithmetic: Elements of the ring $\mathbb{Z}[1/\sqrt{2}]$ are stored in a fixed-width packed format (numerator coefficients and exponent), avoiding heap allocations and floating-point overhead.
• Canonicalization Pipeline: The system uses a "cheap signature first" approach, where compact hashes are computed to filter candidates before expensive canonical form comparisons are performed.
• Parallelization: The frontier expansion is parallelized using concurrent hash sets, with "best-effort" stopping predicates for MITM searches to handle early termination in multi-threaded environments.

Key Contributions

1. Exact Synthesis Engine: A procedure for two-qubit Clifford+T synthesis that guarantees provably minimal T-count within the enumerated domain.
2. Canonicalization and Pruning: Formal proofs for correctness, including equivalence relations that reduce the search space and pruning rules that prevent redundant exploration without sacrificing optimality.
3. High-Performance Implementation: A software architecture that achieves orders-of-magnitude speedups by replacing dense matrix operations with specialized, cache-resident integer kernels and packed arithmetic.
4. Empirical Scaling: Benchmarks demonstrating the ability to generate lookup tables and perform exact synthesis at T-counts that were previously considered impractical for exact methods on comparable hardware.

Results

The authors report experimental results on a workstation with an AMD Ryzen 9 7900X CPU:

• Lookup Table Generation: The system successfully generated lookup tables for T-counts up to 12 for identity-rooted searches and up to 8 for random-rooted searches. The number of representatives grows exponentially (e.g., ~67 million representatives at T-count 12 for the identity root), but the per-iteration time remains manageable due to the optimized inner loop.
• MITM Performance: The meet-in-the-middle search outperforms baseline implementations significantly. The authors compare their method against existing depth-optimized approaches (which do not guarantee T-count optimality) and note that their T-count optimal synthesis is feasible at depths where previous exact methods would fail.
• Scalability: The random-rooted searches scale rapidly, approaching an asymptotic growth rate of roughly $14^k$, while identity-rooted searches initially grow slower due to higher equivalence rates before catching up.

Significance and Claims

The paper positions its work not as a replacement for heuristic compilers for large-scale circuits, nor as a solution to the general NP-hard problem of exact synthesis at arbitrary scales. Instead, the significance lies in providing reusable, exact infrastructure for structured two-qubit regimes.

• Practicality of Exact Synthesis: The authors demonstrate that by combining strong equivalence reduction with gate-set-aware arithmetic, offline exact enumeration becomes a viable resource for compilers.
• Ground Truth: The generated databases provide "ground-truth" instances for evaluating and improving heuristic compilers.
• Modular Backend: The engine is designed to be embedded as a backend in larger compilation pipelines (e.g., for sliding-window or peephole optimization), offering provably optimal sub-circuits.
• Generalizability: While instantiated for Clifford+T, the authors argue the approach is generalizable to other discrete gate sets and resource counts, provided exact representations and efficient equivalence testing can be defined.

The work concludes that while worst-case hardness results limit asymptotic scalability, scoped, structure-driven approaches offer a practical path to unconditional optimality for the small sub-circuits and canonical blocks that frequently appear in fault-tolerant compilation.