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:2610.41142

Encoded reversible addition in constant Toffoli depth

Aidan Epperly, Isaac H. Kim, Mingyu Lee

quant-phSubmitted Oct 30, 2026• Announced Nov 2, 2026
arXivHTMLPDF

Abstract

We show that reversible in-place quantum addition modulo $2^n-1$ can be implemented in constant Toffoli depth using $O(n)$ space, provided that the variables are encoded in a certain non-standard form. Using measurement-based uncomputation, the Toffoli depth can be reduced to one. We also present space-depth tradeoffs and an application to programmable rotations.

AI Summary

The paper asks whether changing the representation of integers permits exact reversible addition with constant Toffoli depth and linear space. It constructs in-place addition modulo $M=2^n-1$ for registers already stored in a nonstandard encoding, without including conversion costs. The encoding maps $a$ to $(f^a,f^{-a})$, where $f$ generates $\mathrm{GF}(2^n)^\times$. Addition becomes field multiplication, while the inverse components permit cleanup of the old inputs. A length-$\mu(n)$ bilinear decomposition implements multiplication through linear Clifford transformations and parallel Toffoli gates. Known algebraic-geometric constructions provide $\mu(n)=O(n)$ with polynomial-time circuit construction. The fully unitary in-place adder has Toffoli depth $4$ and uses $8\mu(n)$ Toffolis. Measuring bilinear outputs in the $X$ basis and correcting their phases with classically controlled CZ gates reduces this to depth $1$, $2\mu(n)$ Toffolis, and $6n+6\mu(n)$ total qubits. Space–depth tradeoffs include a zero-workspace field multiply-add circuit of depth at most $8\lceil\mu(n)/n\rceil$, obtained by splitting terms into linearly independent groups. Batching and register reuse give further tradeoffs. An application implements programmable rotations with Toffoli depth $L+2$ and count $\mu(n)+2n$, assuming a reusable encoded phase-gradient state and a multiplier of depth $L$. The constant-depth claim concerns Toffoli depth, not total circuit depth. Encoding and decoding require exponentiation and discrete logarithms, respectively. Constants remain large, and the rotation application avoids conversion through classical-table lookup but offers only modest overall improvements in the settings discussed. Extensions to other moduli, including $2^n$, remain open.

Little sign of AI-generated textAI use disclosedStrong assumptions
Claude Opus 5.5 (Anthropic) was used to edit the manuscript, to write the code that generated the plots, and to optimize the constants of our constructions.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
19 pages, 2 figures

Related papers

Toffoli-depth reduction method preserving in-place quantum circuits and its application to SHA3-256

Jongheon Lee, Yousung Kang, You-Seok Lee +2 more

Abstract When implementing a quantum circuit for a desired reversible function, an attempt is made to design an accurate quantum circuit. Then, the quantum circuit is optimized based on a specific cost function, such as design cost, width (the number of qubits), depth, etc. In particular, if an in-place subcircuit itself can be optimized while maintaining its in-place property, it will be a very useful way to increase efficiency without changing the initial architecture of the entire quantum circuit. Furthermore, since its (clean) work qubits can easily be utilized in subsequent subroutines of the quantum circuit, it has an additional important advantage in terms of width. In this paper, for the first time to the best of our knowledge, we present a global Toffoli-depth reduction methodology for an in-place version reversible circuit in the case that the given input circuit is optimized with Toffoli-count. We mainly introduce a process to optimize the $$\chi $$ χ internal function block in SHA3-256 to explain our Toffoli-depth reduction approach preserving the in-place property, and hence, well-balanced five $$\chi $$ χ quantum circuits are induced in terms of its width and T-depth. And then, we apply these five $$\chi $$ χ circuits to design the entire SHA3-256 cryptosystem. One of the proposed SHA3-256 quantum circuits has a width of 1600 and a T-depth of 264, and this shows a result of 50% and 38.9% reduction compared to the previous circuit in terms of width and T-depth, respectively. Other versions of our SHA3-256 circuits just required 10–33 qubits per one T-depth compared to the previous results which require over 1800 qubits per T-depth, and so this means that our SHA3-256 circuits are well-balanced. Finally, we constructed Grover’s algorithm circuit using each version that realized SHA3-256. When output circuits for the presented method were used, quantum volume values of Grover’s algorithm circuits became 33 and 50 $$\%$$ % of the value when the input circuit was used.

Quantum Information Processing•Apr 18, 2024•6 citations

Any Clifford+T circuit can be controlled with constant T-depth overhead

Isaac H. Kim, Tuomas Laakkonen

Since an n-qubit circuit consisting of CNOT gates can have up to $Ω(n^2/\log{n})$ CNOT gates, it is natural to expect that $Ω(n^2/\log{n})$ Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision $ε$ in T-depth exactly 1 using a universal $\lceil\log_2(8/ε)\rceil$-qubit catalyst state.

quant-pharXiv:2512.24982•Jan 1, 2026•0 citations

Novel Optimized Designs of Modulo 2 n +1 Adder for Quantum Computing

Bhaskar Gaur, Himanshu Thapliyal

Quantum modular adders are one of the most fundamental yet versatile quantum computation operations. They help implement the functions of higher complexity, such as subtraction and multiplication, which are used in applications, such as quantum cryptanalysis, quantum image processing, and securing communication. To the best of our knowledge, there is no existing design of quantum modulo ($2^{n}+1$) adder (QMA). In this work, we propose four quantum adders targeted specifically for modulo ($2^{n}+1$) addition. These adders can provide both regular and modulo ($2^{n}+1$) sum concurrently, enhancing their application in residue number system-based arithmetic. Our first design, QMA1, is a novel quantum modulo ($2^{n}+1$) adder. The second proposed adder, QMA2, optimizes the utilization of quantum gates within the QMA1, resulting in 37.5% reduced CNOT gate count, 46.15% reduced CNOT depth, and 26.5% decrease in both Toffoli gates and depth. We propose a third adder QMA3 that uses zero resets, a dynamic circuits-based feature that reuses qubits, leading to 25% savings in qubit count. Our fourth design, QMA4, demonstrates the benefit of incorporating additional zero resets to achieve a purer$|0$$\rangle $state, reducing quantum state preparation errors. Notably, we conducted experiments using 5-qubit configurations of the proposed modulo ($2^{n}+1$) adders on the IBM Washington, a 127-qubit quantum computer based on the Eagle R1 architecture, to demonstrate a 28.8% reduction in QMA1’s error of which do the following: 1) 18.63% error reduction happens due to gate/depth reduction in QMA2; 2) 2.53% drop in error due to qubit reduction in QMA3; and 3) 7.64% error decreased due to application of additional zero resets in QMA4.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Jul 15, 2024•5 citations

Prefix Sums via Kronecker Products

Aleksandros Sobczyk, Anastasios Zouzias

In this work, we revisit prefix sums through the lens of linear algebra. We describe an identity that decomposes triangular all-ones matrices as a sum of two Kronecker products, and apply it to design recursive prefix sum algorithms and circuits. Notably, the proposed family of circuits is the first one that achieves the following three properties simultaneously: (i) zero-deficiency, (ii) constant fan-out per-level, and (iii) depth that is asymptotically strictly smaller than $2\log(n)$ for input length $n$. As an application, we show how to use these circuits to design quantum adders with $1.893\log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits, improving the Toffoli depth and/or Toffoli size of existing constructions.

quant-pharXiv:2512.16309•Dec 19, 2025•0 citations

The PPKN Gate: An Optimal 1-Toffoli Input-Preserving Full Adder for Quantum Arithmetic

G. Papakonstantinou

Efficient arithmetic operations are a prerequisite for practical quantum computing. Optimization efforts focus on two primary metrics: Quantum Cost (QC), determined by the number of non-linear gates, and Logical Depth, which defines the execution speed. Existing literature identifies the HNG gate as the standard for Input-Preserving Reversible Full Adders. HNG gate typically requires a QC of 12 and a logical depth of 5, in the area of classical reversible circuits. This paper proposes the PPKN Gate, a novel design that achieves the same inputpreserving functionality using only one Toffoli gate and five CNOT gates. With a Quantum Cost of 10 and a reduced logical depth of 4, the PPKN gate outperforms the standard HNG gate in both complexity and speed. Furthermore, we present a modular architecture for constructing an n-bit Ripple Carry Adder by cascading PPKN modules.

quant-pharXiv:2512.12073•Dec 16, 2025•0 citations

Measurement-based uncomputation of quantum circuits for modular arithmetic

Alessandro Luongo, Antonio Michele Miti, Varun Narasimhachar +1 more

Measurement-based uncomputation (MBU) is a technique used to perform probabilistic uncomputation of quantum circuits. We formalize this technique for the case of single-qubit registers, and we show applications to modular arithmetic. Using MBU, we reduce Toffoli count and depth by 10% to 15% for modular adders based on the architecture of [1], and by almost 25% for modular adders based on the architecture of [2]. Our results have the potential to improve other circuits for modular arithmetic, such as modular multiplication and modular exponentiation, and can find applications in quantum cryptanalysis.

arXiv:2407.20167•ACM/IEEE Design Automation Conference (DAC)•Jun 22, 2025•7 citations
We show that reversible in-place quantum addition modulo 2n−12^n-12n−1 can be implemented in constant Toffoli depth using O(n)O(n)O(n) space, provided that the variables are encoded in a certain non-standard form. Using measurement-based uncomputation, the Toffoli depth can be reduced to one. We also present space-depth tradeoffs and an application to programmable rotations.
The paper asks whether changing the representation of integers permits exact reversible addition with constant Toffoli depth and linear space. It constructs in-place addition modulo M=2n−1M=2^n-1M=2n−1 for registers already stored in a nonstandard encoding, without including conversion costs.
The encoding maps aaa to (fa,f−a)(f^a,f^{-a})(fa,f−a), where fff generates GF(2n)×\mathrm{GF}(2^n)^\timesGF(2n)×. Addition becomes field multiplication, while the inverse components permit cleanup of the old inputs. A length-μ(n)\mu(n)μ(n) bilinear decomposition implements multiplication through linear Clifford transformations and parallel Toffoli gates. Known algebraic-geometric constructions provide μ(n)=O(n)\mu(n)=O(n)μ(n)=O(n) with polynomial-time circuit construction. The fully unitary in-place adder has Toffoli depth 444 and uses 8μ(n)8\mu(n)8μ(n) Toffolis. Measuring bilinear outputs in the XXX basis and correcting their phases with classically controlled CZ gates reduces this to depth 111, 2μ(n)2\mu(n)2μ(n) Toffolis, and 6n+6μ(n)6n+6\mu(n)6n+6μ(n) total qubits.
Space–depth tradeoffs include a zero-workspace field multiply-add circuit of depth at most 8⌈μ(n)/n⌉8\lceil\mu(n)/n\rceil8⌈μ(n)/n⌉, obtained by splitting terms into linearly independent groups. Batching and register reuse give further tradeoffs. An application implements programmable rotations with Toffoli depth L+2L+2L+2 and count μ(n)+2n\mu(n)+2nμ(n)+2n, assuming a reusable encoded phase-gradient state and a multiplier of depth LLL.
The constant-depth claim concerns Toffoli depth, not total circuit depth. Encoding and decoding require exponentiation and discrete logarithms, respectively. Constants remain large, and the rotation application avoids conversion through classical-table lookup but offers only modest overall improvements in the settings discussed. Extensions to other moduli, including 2n2^n2n, remain open.
Abstract When implementing a quantum circuit for a desired reversible function, an attempt is made to design an accurate quantum circuit. Then, the quantum circuit is optimized based on a specific cost function, such as design cost, width (the number of qubits), depth, etc. In particular, if an in-place subcircuit itself can be optimized while maintaining its in-place property, it will be a very useful way to increase efficiency without changing the initial architecture of the entire quantum circuit. Furthermore, since its (clean) work qubits can easily be utilized in subsequent subroutines of the quantum circuit, it has an additional important advantage in terms of width. In this paper, for the first time to the best of our knowledge, we present a global Toffoli-depth reduction methodology for an in-place version reversible circuit in the case that the given input circuit is optimized with Toffoli-count. We mainly introduce a process to optimize the χ\chi χ χ internal function block in SHA3-256 to explain our Toffoli-depth reduction approach preserving the in-place property, and hence, well-balanced five χ\chi χ χ quantum circuits are induced in terms of its width and T-depth. And then, we apply these five χ\chi χ χ circuits to design the entire SHA3-256 cryptosystem. One of the proposed SHA3-256 quantum circuits has a width of 1600 and a T-depth of 264, and this shows a result of 50% and 38.9% reduction compared to the previous circuit in terms of width and T-depth, respectively. Other versions of our SHA3-256 circuits just required 10–33 qubits per one T-depth compared to the previous results which require over 1800 qubits per T-depth, and so this means that our SHA3-256 circuits are well-balanced. Finally, we constructed Grover’s algorithm circuit using each version that realized SHA3-256. When output circuits for the presented method were used, quantum volume values of Grover’s algorithm circuits became 33 and 50 %\%% % of the value when the input circuit was used.
Since an n-qubit circuit consisting of CNOT gates can have up to Ω(n2/log⁡n)Ω(n^2/\log{n})Ω(n2/logn) CNOT gates, it is natural to expect that Ω(n2/log⁡n)Ω(n^2/\log{n})Ω(n2/logn) Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision εεε in T-depth exactly 1 using a universal ⌈log⁡2(8/ε)⌉\lceil\log_2(8/ε)\rceil⌈log2​(8/ε)⌉-qubit catalyst state.
Quantum modular adders are one of the most fundamental yet versatile quantum computation operations. They help implement the functions of higher complexity, such as subtraction and multiplication, which are used in applications, such as quantum cryptanalysis, quantum image processing, and securing communication. To the best of our knowledge, there is no existing design of quantum modulo (2n+12^{n}+12n+1) adder (QMA). In this work, we propose four quantum adders targeted specifically for modulo (2n+12^{n}+12n+1) addition. These adders can provide both regular and modulo (2n+12^{n}+12n+1) sum concurrently, enhancing their application in residue number system-based arithmetic. Our first design, QMA1, is a novel quantum modulo (2n+12^{n}+12n+1) adder. The second proposed adder, QMA2, optimizes the utilization of quantum gates within the QMA1, resulting in 37.5% reduced CNOT gate count, 46.15% reduced CNOT depth, and 26.5% decrease in both Toffoli gates and depth. We propose a third adder QMA3 that uses zero resets, a dynamic circuits-based feature that reuses qubits, leading to 25% savings in qubit count. Our fourth design, QMA4, demonstrates the benefit of incorporating additional zero resets to achieve a purer∣0|0∣0$\rangle $state, reducing quantum state preparation errors. Notably, we conducted experiments using 5-qubit configurations of the proposed modulo (2n+12^{n}+12n+1) adders on the IBM Washington, a 127-qubit quantum computer based on the Eagle R1 architecture, to demonstrate a 28.8% reduction in QMA1’s error of which do the following: 1) 18.63% error reduction happens due to gate/depth reduction in QMA2; 2) 2.53% drop in error due to qubit reduction in QMA3; and 3) 7.64% error decreased due to application of additional zero resets in QMA4.
In this work, we revisit prefix sums through the lens of linear algebra. We describe an identity that decomposes triangular all-ones matrices as a sum of two Kronecker products, and apply it to design recursive prefix sum algorithms and circuits. Notably, the proposed family of circuits is the first one that achieves the following three properties simultaneously: (i) zero-deficiency, (ii) constant fan-out per-level, and (iii) depth that is asymptotically strictly smaller than 2log⁡(n)2\log(n)2log(n) for input length nnn. As an application, we show how to use these circuits to design quantum adders with 1.893log⁡(n)+O(1)1.893\log(n)+O(1)1.893log(n)+O(1) Toffoli depth, O(n)O(n)O(n) Toffoli gates, and O(n)O(n)O(n) additional qubits, improving the Toffoli depth and/or Toffoli size of existing constructions.
Efficient arithmetic operations are a prerequisite for practical quantum computing. Optimization efforts focus on two primary metrics: Quantum Cost (QC), determined by the number of non-linear gates, and Logical Depth, which defines the execution speed. Existing literature identifies the HNG gate as the standard for Input-Preserving Reversible Full Adders. HNG gate typically requires a QC of 12 and a logical depth of 5, in the area of classical reversible circuits. This paper proposes the PPKN Gate, a novel design that achieves the same inputpreserving functionality using only one Toffoli gate and five CNOT gates. With a Quantum Cost of 10 and a reduced logical depth of 4, the PPKN gate outperforms the standard HNG gate in both complexity and speed. Furthermore, we present a modular architecture for constructing an n-bit Ripple Carry Adder by cascading PPKN modules.
Measurement-based uncomputation (MBU) is a technique used to perform probabilistic uncomputation of quantum circuits. We formalize this technique for the case of single-qubit registers, and we show applications to modular arithmetic. Using MBU, we reduce Toffoli count and depth by 10% to 15% for modular adders based on the architecture of [1], and by almost 25% for modular adders based on the architecture of [2]. Our results have the potential to improve other circuits for modular arithmetic, such as modular multiplication and modular exponentiation, and can find applications in quantum cryptanalysis.