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

IEICE Transactions on Information and Systems

Leveraging Different Boolean Function Decompositions to Reduce T-Count in LUT-Based Quantum Circuit Synthesis

David Clarino, Naoya ASADA, Atsushi Matsuo, Shigeru Yamashita

Published Oct 29, 2024• 0 citations
Publisher

Abstract

Lookup Table (LUT) based synthesis methods have recently been proposed as a way to synthesize quantum Boolean circuits in a qubit-constrained environment. Other recent research papers have demonstrated the possibility of using relative phase quantum circuits when compute/uncompute logic is used in tandem, reducing T-count in quantum Boolean circuits in the fault-tolerant quantum computing paradigm. Because LUT-based synthesis methods use compute/uncompute pairs on ancilla qubits, this suggests that implementing the arbitrary Boolean logic that make up the individual Boolean logic network nodes in a relative phase manner could reduce the T-count. To generate such arbitrary Boolean functions, we utilize Shannon’s decomposition, Davio expansions, as well as alternating balanced and unbalanced relative phase circuits. Experimental results demonstrate that our method can reduce the T-count to an average of 24% of the existing method.

DOI
10.1587/transinf.2024edp7194

Related papers

Optimizing LUT-Based Quantum Circuit Synthesis Using Relative Phase Boolean Operations

David Clarino, Naoya Asada, Shigeru Yamashita

LUT-based synthesis methods have recently been proposed as a way to synthesize quantum Boolean circuits in a qubit constrained environment. Other results have also shown that allowing a relative phase when implementing quantum Boolean circuits yields an advantage in T-count without additional ancilla qubits, which is advantageous in the fault-tolerant quantum computing paradigm. We propose a method that utilizes both LUT-based synthesis and relative phase quantum Boolean circuits which minimize the T-count while minimizing the ancilla required to implement them. We leverage recent results regarding relative phase versions of Boolean functions and Shannon's decomposition to propose a novel method to synthesize arbitrary Boolean functions up to a relative phase. We then utilize this method to synthesize Boolean logic inside each LUT as a relative phase quantum Boolean circuit and show that the resulting quantum circuit has a clear advantage in T-count over more naive methods.

•Oct 28, 2023•1 citation

Synthesis Techniques for Fault-tolerant Quantum Circuit Implementation using Clifford+ Z N -group

Laxmidhar Biswal, Debjyoti Bhattacharjee, Amlan Chakrabarti +1 more

Decoherence jeopardizes the entanglement of fragile quantum states, and is among the foremost challenges towards engineering scalable quantum computers. Realizing quantum circuit implementation with small qubit count and shallow circuit depth is necessary due to the linear scaling of decoherence rate with qubit count and circuit depth. Conversely, reasonable correction of small unitary errors can be achieved by using surface codes along with a transversal gate set to protect quantum information from decoherence. In this paper, we analyze and report the upper bound of non-Clifford phase-depth for different mapping schemes and synthesis approaches. We introduce a synthesis methodology based on lookup-table (LUT) networks, wherein the Boolean logic translates into fault-tolerant quantum logic using Clifford+ Z N group with zero ancillary cost. We also present fault-tolerant synthesis techniques for k -LUT network using additional ancillary lines with exponential phase-count and unit phase-depth.

ACM Transactions on Quantum Computing•Jun 14, 2024•1 citation

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

Optimizing Quantum Circuit Synthesis with Dominator Analysis

Giacomo Lancellotti, Giovanni Agosta, Alessandro Barenghi +1 more

Quantum circuit synthesis translates a classical Boolean function into an equivalent quantum circuit. The syn-thesis is solvable by playing the reversible pebble game on the logic network of the function. However, optimal solutions are im-practical for large networks, affecting the number of qubits and gates of the final quantum circuit. In this work, we improve the solution of the reversible pebble game by leveraging dominance relations on the directed acyclic graph of the classical function, reducing qubits needed for syntheses. The proposed algorithm exposes a tunable tradeoff between the available number of qubits and the circuit size expressed as T-count and T-depth. We experimentally validate our methodology on cryptographic and arithmetic benchmarks, reporting reductions between 37% and 83 % in qubit number with respect to Bennet syntheses algorithms and complete the majority of our syntheses in less than a second, improving on the current running times of state of the art approaches.

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)•Nov 18, 2024•1 citation

Reducing T-Count in Quantum Circuits Using Alternate Forms of the Relative Phase Toffoli Gate

David Clarino, Shohei KURODA, Shigeru Yamashita

Toffoli gates are an important primitive in reversible Boolean logic. In quantum computation, these Toffoli gates are composed using other elementary gates, most notably the Clifford+T basis. However, in fault-tolerant implementations of quantum circuits, the T-gate incurs extra cost relative to Clifford gates like the S-gate and CNOT gate. Relative-phase Toffoli Gates (RTOFs) have been proposed as a way to reduce this T-count at the cost of incurring a relative phase that could skew the final quantum states. In this paper, we utilize an observation that the relative phase which RTOFs introduce can be canceled by the appropriate application of less expensive S-gates instead of T-gates. It leverages alternate forms of the RTOF including incorporating S-gates into it or moving around its input bits in order to simplify the logic to erase the relative phase. We find experimentally that our method has a clear advantage in most cases, and identify several types of circuits that it could be synergistic with.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jul 15, 2024•1 citation

Compact Quantum Circuits for Autosymmetric and Dimension Reducible Functions

Anna Bernasconi, Valentina Ciriani, Gianmarco Cuciniello +2 more

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.

ACM Journal on Emerging Technologies in Computing Systems•Sep 15, 2026•0 citations
Lookup Table (LUT) based synthesis methods have recently been proposed as a way to synthesize quantum Boolean circuits in a qubit-constrained environment. Other recent research papers have demonstrated the possibility of using relative phase quantum circuits when compute/uncompute logic is used in tandem, reducing T-count in quantum Boolean circuits in the fault-tolerant quantum computing paradigm. Because LUT-based synthesis methods use compute/uncompute pairs on ancilla qubits, this suggests that implementing the arbitrary Boolean logic that make up the individual Boolean logic network nodes in a relative phase manner could reduce the T-count. To generate such arbitrary Boolean functions, we utilize Shannon’s decomposition, Davio expansions, as well as alternating balanced and unbalanced relative phase circuits. Experimental results demonstrate that our method can reduce the T-count to an average of 24% of the existing method.
LUT-based synthesis methods have recently been proposed as a way to synthesize quantum Boolean circuits in a qubit constrained environment. Other results have also shown that allowing a relative phase when implementing quantum Boolean circuits yields an advantage in T-count without additional ancilla qubits, which is advantageous in the fault-tolerant quantum computing paradigm. We propose a method that utilizes both LUT-based synthesis and relative phase quantum Boolean circuits which minimize the T-count while minimizing the ancilla required to implement them. We leverage recent results regarding relative phase versions of Boolean functions and Shannon's decomposition to propose a novel method to synthesize arbitrary Boolean functions up to a relative phase. We then utilize this method to synthesize Boolean logic inside each LUT as a relative phase quantum Boolean circuit and show that the resulting quantum circuit has a clear advantage in T-count over more naive methods.
Decoherence jeopardizes the entanglement of fragile quantum states, and is among the foremost challenges towards engineering scalable quantum computers. Realizing quantum circuit implementation with small qubit count and shallow circuit depth is necessary due to the linear scaling of decoherence rate with qubit count and circuit depth. Conversely, reasonable correction of small unitary errors can be achieved by using surface codes along with a transversal gate set to protect quantum information from decoherence. In this paper, we analyze and report the upper bound of non-Clifford phase-depth for different mapping schemes and synthesis approaches. We introduce a synthesis methodology based on lookup-table (LUT) networks, wherein the Boolean logic translates into fault-tolerant quantum logic using Clifford+ Z N group with zero ancillary cost. We also present fault-tolerant synthesis techniques for k -LUT network using additional ancillary lines with exponential phase-count and unit phase-depth.
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 synthesis translates a classical Boolean function into an equivalent quantum circuit. The syn-thesis is solvable by playing the reversible pebble game on the logic network of the function. However, optimal solutions are im-practical for large networks, affecting the number of qubits and gates of the final quantum circuit. In this work, we improve the solution of the reversible pebble game by leveraging dominance relations on the directed acyclic graph of the classical function, reducing qubits needed for syntheses. The proposed algorithm exposes a tunable tradeoff between the available number of qubits and the circuit size expressed as T-count and T-depth. We experimentally validate our methodology on cryptographic and arithmetic benchmarks, reporting reductions between 37% and 83 % in qubit number with respect to Bennet syntheses algorithms and complete the majority of our syntheses in less than a second, improving on the current running times of state of the art approaches.
Toffoli gates are an important primitive in reversible Boolean logic. In quantum computation, these Toffoli gates are composed using other elementary gates, most notably the Clifford+T basis. However, in fault-tolerant implementations of quantum circuits, the T-gate incurs extra cost relative to Clifford gates like the S-gate and CNOT gate. Relative-phase Toffoli Gates (RTOFs) have been proposed as a way to reduce this T-count at the cost of incurring a relative phase that could skew the final quantum states. In this paper, we utilize an observation that the relative phase which RTOFs introduce can be canceled by the appropriate application of less expensive S-gates instead of T-gates. It leverages alternate forms of the RTOF including incorporating S-gates into it or moving around its input bits in order to simplify the logic to erase the relative phase. We find experimentally that our method has a clear advantage in most cases, and identify several types of circuits that it could be synergistic with.
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.