Quantum Circuit Synthesis Using an Exact T Library
Hanyu Wang, Mingfei Yu, Xinrui Wu, Jason Cong · 2026
Read Quantum Circuit Synthesis Using an Exact T Library by Hanyu Wang, Mingfei Yu, Xinrui Wu, Jason Cong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15476.txt.
Introduction
Hanyu Wang, Mingfei Yu, Xinrui Wu, and Jason Cong attack the cost of fault-tolerant quantum circuits, where T gates supplied as magic states dominate expense. Standard flows minimize a proxy count that ignores phase cancellation, so the team formulates exact T synthesis, groups Boolean functions under Clifford equivalence, and precomputes optimal implementations up to seven variables. Their mapper cuts T counts by up to 14.3 percent on standard benchmarks and by up to 40 percent on several cryptographic modules.
Catalog record
| CREATOR | Hanyu Wang, Mingfei Yu, Xinrui Wu, Jason Cong |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36839 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.15476
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Circuit Synthesis Using an Exact T Library Thanks: This work is supported by the NSF Challenge Institute for Quantum Computation (CIQC, Grant No. 2016245), the National Quantum Virtual Laboratory (NQVL, Grant No. 2410716), NSF Grant No. CCF-2313083, and a gift from Google LLC. J.C. has a financial interest in Google. Hanyu Wang, Mingfei Yu, Xinrui Wu, Jason Cong Abstract . In fault-tolerant quantum circuit synthesis, T gates supplied via magic states dominate space–time cost, while Clifford gates incur negligible overhead. Conventional flows minimize AND count in an {XOR, AND, NOT} basis as a proxy for T, which neglects phase cancellation and can be far from T-optimal. We instead formulate an exact T synthesis problem and canonicalize Boolean functions under Clifford equivalence. By precomputing T-optimal implementations up to seven variables and developing a customized mapper, we reduce the T count by up to 14.3% on EPFL benchmarks and improve the T counts of several cryptographic modules by up to 40%. obeypunctuation=true] University of California, Los Angeles , , Los Angeles , , USA obeypunctuation=true] École Polytechnique Fédérale de Lausanne , , Lausanne , , Switzerland obeypunctuation=true] University of California, Los Angeles , , Los Angeles , , USA obeypunctuation=true] University of California, Los Angeles , , Los Angeles , , USA 1. Introduction Fault-tolerant quantum computing (FTQC) is becoming practical as systems reach scales where quantum error correction (QEC) sustains long-lived logical qubits. Growth in physical qubits, coherence, and control fidelity is pushing code distances to the regime needed for nontrivial algorithms, moving FTQC from aspiration to engineering ( 15 ; 16 ; 32 ) . In these architectures, T gates are the bottleneck resource and hinder us from running practical applications fault-tolerantly. This is because Clifford gates can be executed transversally (e.g., color codes), while non-Clifford gates such as T require magic-state distillation and injection with a 3D code ( 4 ; 14 ; 42 ) . The magic state factory’s throughput and layout dominate the cost, despite the latest progress on state cultivation ( 22 ; 12 ; 33 ; 7 ) . Therefore, minimizing T count is critical. Two example circuits with identical AND count but different T cost. Figure 1. Example of the same AND count results in different T costs. Although both functions A and B contain two ANDs, the two Ts in A can be merged, while a Hadamard blocks those in B. Two example circuits with identical AND count but different T cost. When implementing modules, existing methods map Boolean functions onto the {XOR, AND, NOT} basis ( 17 ) and decrease the number of AND gates, as they require Ts. Riener et al. ( 30 ) introduces a SAT-based method that guarantees the minimum number of minterms in a two-level XOR-AND expression. Meuli et al. ( 26 ) evaluates the gap between terms and AND count, and develops a weighted objective. Testa et al. ( 35 ) proposes affine-equivalence and minimizes the AND count in multi-level XOR-AND graphs (XAG). Meuli et al. ( 28 ) extends the library to k -LUT mapping. Although the AND count reflects the T cost, classical and quantum flows measure “nonlinearity” differently. AND count is only a proxy; it often fails to predict non-Clifford cancellations and phase simplification and can be far from T-optimal. For instance, functions A and B in Figure 1 have the exact same AND count, but Ts in function A can be optimized by canceling two adjacent Ts highlighted, while function B cannot due to the Hadamard (see caption). Indeed, once XAG mapping is fixed, subsequent quantum circuit optimizations cannot easily recover missed structural opportunities due to the inserted Hadamard gates and allocated ancilla qubits. As a result, T optimizations, e.g., AlphaTensor ( 31 ) and Fast TODD ( 37 ) , cannot further improve these circuits. Therefore, assuming each AND uniformly transforms to a fixed number of Ts is not only inaccurate but also leads to an irreversible loss in optimality. In this work, we refine the formulation on XAG to directly use the exact T count to drive optimizations and mapping. By canonicalizing Boolean functions under Clifford equivalence, we precompute a library of T-optimal implementations for functions with up to seven variables and customize a mapping algorithm for circuit optimization. Our approach combines the strengths of existing works: we keep the graph topology of the XOR-AND graph (XAG) to preserve structural information for technology mapping, and we introduce a quantum-aware cost model that reads the exact T count via phase polynomial representation. Compared to XAG mapping driven by exact AND count, our method produces higher-quality Clifford+T circuits; next to standalone T optimizations applied after mapping, ours offers better scalability and circuit quality by exploiting the underlying logic network. On the EPFL arithmetic benchmarks, our mapper achieves up to 14.3\% T count reduction compared to prior works on XAG. After integrating into the circuit synthesis flow, we lower the best known T count for running important cryptography applications by up to 40%, demonstrating that preserving XAG structure while reasoning with exact T cost yields tangible improvements. 2. Classical and Quantum Nonlinearity As mentioned, all existing works use the AND count, i.e., multiplicative complexity (MC), as the proxy for T count optimization. This is because they measure nonlinearity in classical and quantum logic, respectively. In order to illustrate their differences in Section 3 , we introduce their connections as background in this section. 2.1. Multiplicative Complexity of Classical Functions The nonlinearity of a Boolean function f:\{0,1\}^{n}\to\{0,1\}^{m} is captured by its MC: the minimum number of AND gates in any XOR-AND graph (XAG), in which XOR is linear (treated as free) and AND measures nonlinearity. The MC of a Boolean function can be canonically upper-bounded by its algebraic normal form (ANF). ANF counts nonlinear monomials S with the corresponding coefficients a_{S} : f(x_{1},\dots,x_{n})=\bigoplus_{S\subseteq[n]}a_{S}\prod_{i\in S}x_{i}, whose naïve realization builds each monomial of degree |S|\geq 2 with a tree using |S|-1 ANDs and XORs the results, giving \text{MC}_{\text{ANF}}(f)=\sum_{\begin{subarray}{c}S\subseteq[n],\,a_{S}=1\end{subarray}}\bigl(|S|-1\bigr). For example, Figure 3 (a) contains an XAG with inputs a,b,c,d and outputs f and g . Nodes in the XAG are ANDs (purple) and XORs (green), and edges are wires or inverters (dashed). We derive the ANF of f=\neg(a\wedge(\neg b)) using the property \neg x=1\oplus x : (1) f=1\oplus a(1\oplus b)=1\oplus a\oplus ab, from where we read the AND cost 0\!+\!0\!+\!1\!=\!1 . This bound is often loose: sharing, negation, and affine rewriting can reduce ANDs. For example, h=ab\oplus abc requires 2 instead of 1\!+\!2\!=\!3 ANDs because the term ab can be shared. Therefore, prior work canonicalizes functions up to affine equivalence (e.g., via Walsh-Hadamard spectra) ( 27 ) and synthesizes exact MC libraries available up to about 5-6 inputs ( 35 ) . However, these works still fail to consider sharing between outputs. For instance, although f and g in Figure 3 require one and three ANDs, respectively, ab can be shared. This dual-output function requires at most 3 , instead of 1\!+\!3\!=\!4 ANDs. Circuit with two T gates and corresponding phase polynomial and vector representations. Figure 2. A circuit with two Ts ( T_{1} , T_{2} ) and two representations of the phase shift on \ket{x_1x_2x_3} : (a) phase polynomial and its (b) vector form. Circuit