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

arXiv:2006.03845

Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks

Thomas Häner, Mathias Soeken

Published Jun 6, 2020• 4 citations
arXivHTMLPDF

Abstract

The multiplicative depth of a logic network over the gate basis $\{\land, \oplus, \neg\}$ is the largest number of $\land$ gates on any path from a primary input to a primary output in the network. We describe a dynamic programming based logic synthesis algorithm to reduce the multiplicative depth in logic networks. It makes use of cut enumeration, tree balancing, and exclusive sum-of-products (ESOP) representations. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower $T$-depth of the corresponding quantum circuit. Our experimental results show improvements in $T$-depth over state-of-the-art methods and over several hand-optimized quantum circuits for instances of AES, SHA, and floating-point arithmetic.

DOI
10.48550/arxiv.2006.03845

Related papers

Lowering the T-depth of Quantum Circuits via Logic Network Optimization

Thomas Häner, Mathias Soeken

The multiplicative depth of a logic network over the gate basis {∧ , ⊕ , ¬} is the largest number of ∧ gates on any path from a primary input to a primary output in the network. We describe a dynamic programming based logic synthesis algorithm to reduce the multiplicative depth of logic networks. It makes use of cut enumeration, tree balancing, and exclusive sum-of-products (ESOP) representations. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower T -depth of the corresponding quantum circuit. Our experimental results show improvements in T -depth over state-of-the-art methods and over several hand-optimized quantum circuits, for instance, of AES, SHA, and floating-point arithmetic.

ACM Transactions on Quantum Computing•Mar 4, 2022•7 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

Scaling-up ESOP Synthesis for Quantum Compilation

Bruno de O. Schmitt, Mathias Soeken, Giovanni De Micheli +1 more

Today's rapid advances in quantum computing hardware call for scalable synthesis methods to map combinational logic represented as multi-level Boolean networks (e.g., an and-inverter graph, AIG) to quantum circuits. Such synthesis process must yield reversible logic function since quantum circuits are reversible. Thus, logic representations using exclusive sum-of-products (ESOP) are advantageous because of their natural relation to Toffoli gates, one of the primitives in reversible logic. This motivates developing effective methods to collapse AIG logic networks into ESOPs. In this work, we present two state-of-the-art methods to collapse an AIG into an ESOP expression, describe their shortcomings and introduce a new approach based on the divide-and-conquer paradigm. We demonstrate the effectiveness of our method in collapsing IEEE-compliant half precision floating point networks. Results show that our method can collapse designs-which were previously not solvable within a week-in less than 5 minutes. We also describe a technique capable of taking advantage of this new method to generate quantum circuits with up to 50% fewer T gates compared to state-of-the-art methods.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2019•8 citations

Optimization of Reversible Logic Networks with Gate Sharing

Yung‐Chih Chen, Feng-Jie Chao

Logic synthesis for quantum computing aims to transform a Boolean logic network into a quantum circuit. A conventional two-stage flow first synthesizes the given Boolean logic network into a reversible logic network composed of reversible logic gates. Then, it maps each reversible logic gate into quantum gates to generate a quantum circuit. The state-of-the-art method for the first stage takes advantage of the lookup-table (LUT) mapping technology for FPGAs to decompose the given Boolean logic network into sub-networks, and then maps the sub-networks into reversible logic networks. Although every sub-network is well synthesized, we observe that the reversible logic networks could be further optimized by sharing the reversible logic gates belonging to different sub-networks. Thus, in this paper, we propose a new optimization method for the reversible logic networks by sharing gates. We translate the problem of extracting shareable gates to the exclusive-sums-of-product term optimization problem. The experimental results show that the proposed method successfully optimizes the reversible logic networks generated by the LUT-based method. It is able to reduce an average of approximately 4% of quantum gate cost without increasing the number of ancilla lines for a set of IWLS 2005 benchmarks.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 16, 2023•2 citations

Quantum circuit designs of efficient squaring

Seong-Min Cho, Changyeol Lee, Seung-Hyun Seo

Quantum squaring circuits have been used as helpful arithmetic modules in various quantum algorithms for calculating series expansions or distances of vectors, etc. Quantum multipliers can replace quantum squaring circuits, but squaring with quantum multipliers is inefficient because it involves using quantum gates for unnecessary bitwise multiplication. In this paper, we propose a depth-optimized quantum circuit dedicated to squaring by eliminating these unnecessary quantum gates and implementing quantum gates in parallel. We also discuss the optimal distribution of the partial products to reduce further the gate cost of the quantum adder used for the sum of the partial products. The proposed partial product distribution method lowers the quantum adder’s number of gates and depth by half. Our quantum squaring circuit is the most efficient, with an average improvement of 68% and 79.7% in T-count and T-depth, respectively, compared to existing quantum squaring circuits. Despite the increased qubit counts caused by the depth optimization, we demonstrate that the proposed circuit has the smallest $$\hbox {KQ}_\textrm{T}$$ .

Quantum Information Processing•Jan 24, 2025•2 citations

Quantum algorithm for ESOP minimization

Hrithik Ketineni, Marek A. Perkowski

The Exclusive-OR Sum-of-Product (ESOP) minimization problem has long been of interest to the research community because of its importance in classical logic design (including low-power design and design for test), reversible logic synthesis, and knowledge discovery, among other applications. However, no exact minimal minimization method has been presented for more than seven variables on arbitrary functions. This paper presents a novel quantum-classical hybrid algorithm for the exact minimal ESOP minimization of incompletely specified Boolean functions. This algorithm constructs oracles from sets of constraints and leverages the quantum speedup offered by Grover's algorithm to find solutions to these oracles, thereby improving over classical algorithms. Improved encoding of ESOP expressions results in substantially fewer decision variables compared to many existing algorithms for many classes of Boolean functions. This paper also extends the idea of exact minimal ESOP minimization to additionally minimize the cost of realizing an ESOP expression as a quantum circuit. To the extent of the authors' knowledge, such a method has never been published. This algorithm was tested on completely and incompletely specified Boolean functions via quantum simulation.

Quantum Information and Computation•Jan 29, 2023•2 citations
The multiplicative depth of a logic network over the gate basis {∧,⊕,¬}\{\land, \oplus, \neg\}{∧,⊕,¬} is the largest number of ∧\land∧ gates on any path from a primary input to a primary output in the network. We describe a dynamic programming based logic synthesis algorithm to reduce the multiplicative depth in logic networks. It makes use of cut enumeration, tree balancing, and exclusive sum-of-products (ESOP) representations. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower TTT-depth of the corresponding quantum circuit. Our experimental results show improvements in TTT-depth over state-of-the-art methods and over several hand-optimized quantum circuits for instances of AES, SHA, and floating-point arithmetic.
The multiplicative depth of a logic network over the gate basis {∧ , ⊕ , ¬} is the largest number of ∧ gates on any path from a primary input to a primary output in the network. We describe a dynamic programming based logic synthesis algorithm to reduce the multiplicative depth of logic networks. It makes use of cut enumeration, tree balancing, and exclusive sum-of-products (ESOP) representations. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower T -depth of the corresponding quantum circuit. Our experimental results show improvements in T -depth over state-of-the-art methods and over several hand-optimized quantum circuits, for instance, of AES, SHA, and floating-point arithmetic.
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.
Today's rapid advances in quantum computing hardware call for scalable synthesis methods to map combinational logic represented as multi-level Boolean networks (e.g., an and-inverter graph, AIG) to quantum circuits. Such synthesis process must yield reversible logic function since quantum circuits are reversible. Thus, logic representations using exclusive sum-of-products (ESOP) are advantageous because of their natural relation to Toffoli gates, one of the primitives in reversible logic. This motivates developing effective methods to collapse AIG logic networks into ESOPs. In this work, we present two state-of-the-art methods to collapse an AIG into an ESOP expression, describe their shortcomings and introduce a new approach based on the divide-and-conquer paradigm. We demonstrate the effectiveness of our method in collapsing IEEE-compliant half precision floating point networks. Results show that our method can collapse designs-which were previously not solvable within a week-in less than 5 minutes. We also describe a technique capable of taking advantage of this new method to generate quantum circuits with up to 50% fewer T gates compared to state-of-the-art methods.
Logic synthesis for quantum computing aims to transform a Boolean logic network into a quantum circuit. A conventional two-stage flow first synthesizes the given Boolean logic network into a reversible logic network composed of reversible logic gates. Then, it maps each reversible logic gate into quantum gates to generate a quantum circuit. The state-of-the-art method for the first stage takes advantage of the lookup-table (LUT) mapping technology for FPGAs to decompose the given Boolean logic network into sub-networks, and then maps the sub-networks into reversible logic networks. Although every sub-network is well synthesized, we observe that the reversible logic networks could be further optimized by sharing the reversible logic gates belonging to different sub-networks. Thus, in this paper, we propose a new optimization method for the reversible logic networks by sharing gates. We translate the problem of extracting shareable gates to the exclusive-sums-of-product term optimization problem. The experimental results show that the proposed method successfully optimizes the reversible logic networks generated by the LUT-based method. It is able to reduce an average of approximately 4% of quantum gate cost without increasing the number of ancilla lines for a set of IWLS 2005 benchmarks.
Quantum squaring circuits have been used as helpful arithmetic modules in various quantum algorithms for calculating series expansions or distances of vectors, etc. Quantum multipliers can replace quantum squaring circuits, but squaring with quantum multipliers is inefficient because it involves using quantum gates for unnecessary bitwise multiplication. In this paper, we propose a depth-optimized quantum circuit dedicated to squaring by eliminating these unnecessary quantum gates and implementing quantum gates in parallel. We also discuss the optimal distribution of the partial products to reduce further the gate cost of the quantum adder used for the sum of the partial products. The proposed partial product distribution method lowers the quantum adder’s number of gates and depth by half. Our quantum squaring circuit is the most efficient, with an average improvement of 68% and 79.7% in T-count and T-depth, respectively, compared to existing quantum squaring circuits. Despite the increased qubit counts caused by the depth optimization, we demonstrate that the proposed circuit has the smallest KQT\hbox {KQ}_\textrm{T}KQT​ .
The Exclusive-OR Sum-of-Product (ESOP) minimization problem has long been of interest to the research community because of its importance in classical logic design (including low-power design and design for test), reversible logic synthesis, and knowledge discovery, among other applications. However, no exact minimal minimization method has been presented for more than seven variables on arbitrary functions. This paper presents a novel quantum-classical hybrid algorithm for the exact minimal ESOP minimization of incompletely specified Boolean functions. This algorithm constructs oracles from sets of constraints and leverages the quantum speedup offered by Grover's algorithm to find solutions to these oracles, thereby improving over classical algorithms. Improved encoding of ESOP expressions results in substantially fewer decision variables compared to many existing algorithms for many classes of Boolean functions. This paper also extends the idea of exact minimal ESOP minimization to additionally minimize the cost of realizing an ESOP expression as a quantum circuit. To the extent of the authors' knowledge, such a method has never been published. This algorithm was tested on completely and incompletely specified Boolean functions via quantum simulation.