Technical Summary: Reducing T Gates with Unitary Synthesis (trasyn)

1. Problem Statement

Fault-tolerant quantum computing (FTQC) relies heavily on non-Clifford gates, specifically the $T$ gate, which are significantly more expensive than Clifford gates due to the requirement of magic state distillation. This process consumes substantial physical qubits and time, making the $T$ gate count a primary bottleneck for resource estimation and execution time.

Current fault-tolerant compilation workflows typically decompose arbitrary single-qubit unitaries ($U_3$) into a sequence of three $R_z$ rotations (as per the $Z$-$Y$-$Z$ or similar decomposition). Existing state-of-the-art synthesis tools, such as gridsynth, are optimized for synthesizing $R_z$ rotations using number-theoretic methods. However, synthesizing a general $U_3$ gate via this indirect approach requires three separate $R_z$ synthesis steps. This results in a theoretical threefold increase in the $T$ gate count compared to directly synthesizing the $U_3$ gate. Furthermore, existing methods for direct arbitrary unitary synthesis (e.g., Solovay-Kitaev, exhaustive enumeration, or simulated annealing approaches like Synthetiq) often suffer from poor solution quality, exponential runtime, or a lack of scalability to practical error thresholds.

The core challenge addressed by this work is the lack of an efficient, scalable method to directly synthesize arbitrary single-qubit unitaries ($U_3$) into Clifford+$T$ gate sequences that minimizes the $T$ count without incurring prohibitive computational costs.

2. Methodology: TensoR-based Arbitrary unitary SYNthesis (trasyn)

The authors propose trasyn, a novel synthesis algorithm that leverages tensor networks to navigate the exponentially large search space of gate sequences. Instead of treating the synthesis as a brute-force enumeration or a sequential optimization problem, trasyn encodes the solution space as a compact tensor network.

Core Components:

1. Tensor Network Representation (MPS):

   • The method constructs a Matrix Product State (MPS) where the physical indices represent gate sequences.
   • Step 0 (Precomputation): Unique single-qubit matrices and their shortest gate sequences are enumerated up to a fixed $T$-gate budget (e.g., 15 $T$ gates). These are stored as 3D tensors.
   • Step 1 (MPS Construction): To scale beyond the precomputation limit (e.g., >15 $T$ gates), multiple precomputed tensors are linked along their matrix dimensions to form an MPS. This implicitly represents the exponentially large space of possible gate sequences.
   • Implicit Trace Operation: The target unitary $U$ is attached to the MPS. Through sequential contractions and Singular Value Decompositions (SVDs), the algorithm shifts the target's dimensions to align with the MPS, effectively contracting the network to capture the trace values $\text{Tr}(U^\dagger V)$ for all candidate sequences $V$ without explicitly forming the full tensor.

2. Error-Aware Sampling:

   • The trace values are interpreted as a joint probability distribution over the gate sequences.
   • Step 2 (Sampling): Using the chain rule, the algorithm samples high-quality gate sequences from this distribution. By sampling indices sequentially, it prioritizes sequences that minimize the distance to the target unitary. This allows for "error-aware" sampling where the cost of evaluating the distance is amortized across the tensor contraction.

3. Post-Processing:

   • Step 3: The sampled sequence is post-processed to identify and replace suboptimal subsequences with shorter equivalents using a lookup table generated during Step 0.

Key Technical Distinctions:

• Native $U_3$ Synthesis: Unlike gridsynth, which synthesizes $R_z$ gates, trasyn synthesizes the full $U_3$ unitary directly, avoiding the overhead of decomposing into three separate rotations.
• Scalability: By using MPS and precomputation, trasyn scales to higher $T$ counts (e.g., 30+ $T$ gates) where exhaustive enumeration becomes infeasible.
• Hardware Acceleration: The implementation utilizes GPU acceleration (via CuPy) for tensor contractions, significantly reducing compilation time compared to CPU-based analytical methods.

3. Key Contributions

• Algorithmic Innovation: Introduction of trasyn, a generic, efficient single-qubit unitary synthesis algorithm that uses tensor networks to guide the search for optimal Clifford+$T$ sequences.
• Intermediate Representation (IR) Shift: Demonstration that using a $U_3$-based intermediate representation, rather than the standard $R_z$-based approach, significantly reduces the number of rotations and the corresponding $T$ gate count.
• Error-Resource Trade-off Analysis: Identification of an optimal synthesis error threshold relative to logical error rates. The authors show that for early fault-tolerant (EFT) systems with logical error rates around $10^{-5}$ to $10^{-7}$, a slightly higher synthesis error (fewer $T$ gates) can actually improve overall circuit fidelity by reducing the accumulation of logical errors.
• Open-Source Implementation: A GPU-accelerated Python implementation of trasyn is made available.

4. Experimental Results

The authors evaluated trasyn against state-of-the-art baselines (gridsynth, Synthetiq, BQSKit, PyZX) across 1,000 random single-qubit unitaries and 187 representative application benchmarks (including quantum chemistry, material simulations, and QAOA).

• Single-Qubit Synthesis (RQ1):

  • Compared to gridsynth (applied to decomposed $R_z$ rotations), trasyn reduces the $T$ count by a geometric mean of 3.74× and the Clifford count by 5.73× at an error threshold of 0.001.
  • Compared to Synthetiq, trasyn is significantly more reliable and faster. Synthetiq failed to find solutions within a 10-minute time limit for the vast majority of instances at strict error thresholds, whereas trasyn completed them in seconds.
  • At similar error levels, trasyn achieves synthesis errors two orders of magnitude better than gridsynth for the same $T$ count.

• Application Benchmarks (RQ3):

  • Across 187 benchmarks, trasyn achieved a geometric mean reduction in $T$ count of 1.38× and up to 3.5× in specific cases.
  • Clifford gate counts were reduced by up to 7×.
  • Circuits with diverse rotation types (e.g., quantum Hamiltonians with $R_x, R_y, R_z$) benefited more than those with only $R_z$ rotations, as $U_3$ synthesis allows for more aggressive rotation merging.

• Fidelity and Error Trade-offs (RQ2 & RQ4):

  • The authors modeled the trade-off between synthesis error and logical errors. They found that for logical error rates of $10^{-6}$ to $10^{-7}$, an optimal synthesis error threshold exists (around 0.001).
  • By reducing the $T$ count (even with slightly higher synthesis error), the overall circuit infidelity improved by up to 4× compared to gridsynth-based workflows when accounting for realistic logical error rates.

• Post-Synthesis Optimization (RQ5):

  • Applying PyZX (a $T$-count optimizer) to the synthesized circuits did not reclaim the $T$-count advantage of trasyn. The improvements from trasyn were robust against post-synthesis optimization, confirming that the gains are intrinsic to the synthesis method rather than the initial circuit structure.

5. Significance and Claims

The paper claims that trasyn represents a critical step toward practical fault-tolerant quantum computing by addressing the primary resource bottleneck: the $T$ gate.

• Efficiency: By enabling native $U_3$ synthesis, trasyn eliminates the threefold overhead inherent in current $R_z$-based workflows.
• Scalability: The tensor-network approach allows the method to scale to error thresholds and $T$ counts that are impractical for existing enumeration or heuristic methods.
• Holistic Optimization: The work highlights that minimizing $T$ count is not just about synthesis precision but about balancing synthesis error against logical error accumulation. For early fault-tolerant systems, prioritizing $T$-count efficiency over infinitesimal synthesis error yields better overall operational fidelity.
• Practicality: The authors assert that their method is suitable for early fault-tolerant (EFT) demonstrations, where physical qubit constraints limit the availability of magic states, making the reduction of $T$ gates via efficient compilation essential.

The paper concludes that while multi-qubit synthesis remains a challenge due to the exponential growth of the solution space, the single-qubit synthesis improvements provided by trasyn are foundational and complementary to existing circuit optimization techniques, offering immediate benefits for near-term fault-tolerant quantum algorithms.