Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Journal on Emerging Technologies in Computing Systems

Compact Quantum Circuits for Autosymmetric and Dimension Reducible Functions

Anna Bernasconi, Valentina Ciriani, Gianmarco Cuciniello, Nicolas Manini, Asma Taheri Monfared

Published Sep 15, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1145/3845812

Related papers

Compact Quantum Circuits for Dimension Reducible Functions

Anna Bernasconi, Valentina Ciriani, Asma Taheri Monfared +1 more

The classical synthesis method for quantum oracles generally requires a reversible logic synthesis and a quantum compilation step. In the reversible logic synthesis it is important to obtain a compact reversible circuit in order to minimize the quantum cost of the final quantum circuit. In this paper, we exploit function regularities for enabling efficient reversible syn-thesis. In particular, we propose and implement a new method for the quantum synthesis of Dimension reducible Boolean functions. The experimental results validate the proposed approach showing relevant gains in area.

Euromicro Conference on Digital System Design (DSD)•Sep 6, 2023•1 citation

Oracle Synthesis Based on X-Map Decision Diagrams

Xin Hong, Kezhen Zhang, Aochu Dai +3 more

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.

quant-pharXiv:2609.20854•Aug 27, 2026•0 citations

XOR-AND-XOR Logic Forms for Autosymmetric Functions and Applications to Quantum Computing

Anna Bernasconi, Alessandro Berti, Valentina Ciriani +2 more

We propose a new three-level XOR-AND-XOR form for autosymmetric functions, called XORAX expression. In general, a Boolean function f over n variables is k-autosymmetric if it can be projected onto a smaller function fk, which depends on n-k variables only. We show that XORAX expressions can ease the reversible synthesis of autosymmetric functions, producing compact reversible networks, without inserting additional new input lines. Autosymmetry occurs especially for functions that exhibit a regular structure, as for instance arithmetic functions. For this reason, compact reversible networks for autosymmetric functions might be interesting for quantum computing. Experimental results validate the proposed approach.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 10, 2022•8 citations

Back-end-aware Fault-tolerant Quantum Oracle Synthesis

Mingfei Yu, Alessandro Tempia Calvino, Mathias Soeken +1 more

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.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 20, 2025•0 citations

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

Bruno de O. Schmitt, Fereshte Mozafari, Giulia Meuli +2 more

We propose a flow for automated quantum compilation. Our flow takes a Boolean function implemented in Python as input and translates it into a format appropriate for reversible logic synthesis. We focus on two quantum compilation tasks: uniform state preparation and oracle synthesis. To illustrate the use of our flow, we solve IBM's virtual hackathon challenge of 2019, called the Zed city problem, an instance of vertex coloring, by using quantum search algorithms. The expressiveness of Python in combination with automated compilation algorithms allows us to express quantum algorithms at a high level of abstraction, which reduces the effort to implement them, and leads to better and more flexible implementations. We show that our proposed flow generates a lower-cost circuit implementation of the oracle needed to solve IBM's challenge when compared to the winning submission.

Design, Automation, and Test in Europe•Feb 1, 2021•6 citations

Quantum Circuit Synthesis Using an Exact T Library

Hanyu Wang, Mingfei Yu, Xinrui Wu +1 more

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%.

quant-pharXiv:2605.15476•ACM/IEEE Design Automation Conference (DAC)•May 18, 2026•0 citations
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.
The classical synthesis method for quantum oracles generally requires a reversible logic synthesis and a quantum compilation step. In the reversible logic synthesis it is important to obtain a compact reversible circuit in order to minimize the quantum cost of the final quantum circuit. In this paper, we exploit function regularities for enabling efficient reversible syn-thesis. In particular, we propose and implement a new method for the quantum synthesis of Dimension reducible Boolean functions. The experimental results validate the proposed approach showing relevant gains in area.
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 TTT-count and CXCXCX-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 TTT-count and CXCXCX-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.
We propose a new three-level XOR-AND-XOR form for autosymmetric functions, called XORAX expression. In general, a Boolean function f over n variables is k-autosymmetric if it can be projected onto a smaller function fk, which depends on n-k variables only. We show that XORAX expressions can ease the reversible synthesis of autosymmetric functions, producing compact reversible networks, without inserting additional new input lines. Autosymmetry occurs especially for functions that exhibit a regular structure, as for instance arithmetic functions. For this reason, compact reversible networks for autosymmetric functions might be interesting for quantum computing. Experimental results validate the proposed approach.
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.
We propose a flow for automated quantum compilation. Our flow takes a Boolean function implemented in Python as input and translates it into a format appropriate for reversible logic synthesis. We focus on two quantum compilation tasks: uniform state preparation and oracle synthesis. To illustrate the use of our flow, we solve IBM's virtual hackathon challenge of 2019, called the Zed city problem, an instance of vertex coloring, by using quantum search algorithms. The expressiveness of Python in combination with automated compilation algorithms allows us to express quantum algorithms at a high level of abstraction, which reduces the effort to implement them, and leads to better and more flexible implementations. We show that our proposed flow generates a lower-cost circuit implementation of the oracle needed to solve IBM's challenge when compared to the winning submission.
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%.