Quantum oracle synthesis involves compiling arbitrary Boolean functions into quantum circuits using specific quantum gates supported by the target quantum computer. The Clifford+T gate library is particularly common in fault-tolerant quantum computing systems. Utilizing XOR-AND-inverter graphs (XAGs) as the logic representation for the target Boolean functions has received extensive attention due to the observed direct correlation between the number of AND nodes in an XAG and the T count and the helper qubit count of the quantum oracle optimally compiled from it. However, to be deployed onto fault-tolerant quantum hardware, quantum gates must be further re-expressed by logical quantum error correction (QEC) code operations, a process known as back-end compilation. This paper enhances the current XAG-based oracle synthesis techniques by establishing a link between the properties of XAGs and quality measures of back-end-compiled quantum oracles. This link unlocks more optimization opportunities---experimental results demonstrate average reductions of 4.49% in T count, 7.00% in logical time steps, and 14.89% in helper qubit count, respectively, on benchmarks optimized by the proposed back-end-aware XAG optimization approaches.
Quantum oracle synthesis involves compiling arbitrary Boolean functions into quantum circuits using specific quantum gates supported by the target quantum computer. The Clifford+T gate library is particularly common in fault-tolerant quantum computing systems. Utilizing XOR-AND-inverter graphs (XAGs) as the logic representation for the target Boolean functions has received extensive attention due to the observed direct correlation between the number of AND nodes in an XAG and the T count and the helper qubit count of the quantum oracle optimally compiled from it. However, to be deployed onto fault-tolerant quantum hardware, quantum gates must be further re-expressed by logical quantum error correction (QEC) code operations, a process known as back-end compilation. This paper enhances the current XAG-based oracle synthesis techniques by establishing a link between the properties of XAGs and quality measures of back-end-compiled quantum oracles. This link unlocks more optimization opportunities---experimental results demonstrate average reductions of 4.49% in T count, 7.00% in logical time steps, and 14.89% in helper qubit count, respectively, on benchmarks optimized by the proposed back-end-aware XAG optimization approaches.
Abstract Quantum compilation is the task of translating a high-level description of a quantum algorithm into a sequence of low-level quantum operations. We propose and motivate the use of Xor-And-Inverter Graphs (XAG) to specify Boolean functions for quantum compilation. We present three different XAG-based compilation algorithms to synthesize quantum circuits in the Clifford + T library, hence targeting fault-tolerant quantum computing. The algorithms are designed to minimize relevant cost functions, such as the number of qubits, the T-count, and the T-depth, while allowing the flexibility of exploring different solutions. We present novel resource estimation results for relevant cryptographic and arithmetic benchmarks. The achieved results show a significant reduction in both T-count and T-depth when compared with the state-of-the-art.
Scalable quantum computation is expected to rely on fault-tolerant quantum computation (FTQC), in which quantum error correction (QEC) suppresses physical errors sufficiently to support reliable logical operations. This requires quantum compilation to move beyond general-purpose circuit optimization toward encoding-aware and protocol-structured compilation across the full stack of fault-tolerant quantum computers. Beyond circuit synthesis and hardware mapping, an FTQC compiler must lower algorithm-level operations into the logical gate set supported by the chosen code, coordinate encoded data and ancilla resources, realize logical operations together with repeated syndrome extraction under hardware constraints, and provide the resulting measurement stream to real-time decoding.
This survey presents a full-stack view of compiler design for QEC-protected quantum computation. We organize existing work into three interacting layers: logical-level QEC compilation, physical-level QEC realization, and decoder runtime integration. At the logical level, we review surface-code lattice-surgery compilers, beyond-surface-code code-surgery frameworks including emerging qLDPC approaches, and compilation support for non-Clifford operations such as magic-state distillation and code switching. At the physical level, we survey hardware-aware QEC realization on superconducting, trapped-ion, and neutral-atom platforms. We further examine decoder models, real-time decoding systems, and frame-management mechanisms that close the feedback loop during fault-tolerant execution. Finally, we identify open challenges in cross-layer optimization, qLDPC compilation, compiler-decoder co-design, runtime adaptivity, and the development of integrated and benchmarkable FTQC compilation stacks. An actively maintained paper list is available at: github.com/chenghongz/QEC-compiler-design.
A quantum oracle is a reversible quantum subroutine that implements a classical Boolean function within a quantum algorithm. Classical synthesis methods for quantum oracles typically involve two steps: reversible logic synthesis and quantum compilation. In the reversible logic synthesis phase, producing a compact reversible circuit is crucial to minimizing the quantum cost of the final quantum circuit. In this paper, we investigate Boolean functions that simultaneously exhibit two distinct XOR-based regularities: autosymmetry and D-reducibility. These regularities can be effectively utilized for efficient reversible circuit synthesis of Boolean functions. In particular, we propose and implement a new method for the quantum synthesis of autosymmetric and D-reducible Boolean functions. The experimental results demonstrate the effectiveness of our approach on the considered benchmarks, showing reductions in T-count and CNOT-count after Clifford+T quantum compilation.
Quantum oracles act as reversible black-box operators that encode classical Boolean functions into quantum states, enabling efficient function evaluation in quantum superposition. The resource efficiency of oracle implementation is critical to the performance of numerous quantum algorithms. Most state-of-the-art oracle synthesis approaches rely on compact Boolean function representations such as exclusive-sum-of-products (ESOP), yet still suffer from excessive T-count and CX-count for large-scale functions.
In this paper, we propose a novel compact representation named X-Map decision diagram (XMDD) for Boolean functions, which integrates local invertible maps and complement edges to achieve higher compression efficiency. Based on XMDD, we further develop an optimized quantum oracle synthesis algorithm. Extensive experimental results demonstrate that, for Boolean functions with more than seven input variables, our method outperforms the state-of-the-art ESOP-based approach and Qiskit in nearly all test cases, achieving simultaneous reduction in both T-count and CX-count without an obvious trade-off. Moreover, we show that the performance can be further boosted by employing more optimal variable orderings. The proposed XMDD-based framework provides a scalable and resource-efficient solution for practical oracle synthesis in near-term and fault-tolerant quantum computing.
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%.
Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce T-count
Compiling quantum circuits into Clifford+T gates is a central task for fault-tolerant quantum computing using stabilizer codes. In the near term, T gates will dominate the cost of fault tolerant implementations, and any reduction in the number of such expensive gates could mean the difference between being able to run a circuit or not. While exact synthesis is exponentially hard in the number of qubits, local synthesis approaches are commonly used to compile large circuits by decomposing them into substructures. However, composing local methods leads to suboptimal compilations in key metrics such as T-count or circuit depth, and their performance strongly depends on circuit representation. In this work, we address this challenge by proposing \textsc{Q-PreSyn}, a strategy that, given a set of local edits preserving circuit equivalence, uses a RL agent to identify effective sequences of such actions and thereby obtain circuit representations that yield a reduced T-count upon synthesis. Experimental results of our proposed strategy, applied on top of well-known synthesis algorithms, show up to a 20% reduction in T-count on circuits with up to 25 qubits, without introducing any additional approximation error prior to synthesis.