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

Sensors

Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion

Kyungbae Jang, Wonwoong Kim, Sejin Lim, Yeajun Kang, Yujin Yang, Hwajeong Seo

Published Mar 15, 2023• 7 citations
Publisher

Abstract

The Shor's algorithm can find solutions to the discrete logarithm problem on binary elliptic curves in polynomial time. A major challenge in implementing Shor's algorithm is the overhead of representing and performing arithmetic on binary elliptic curves using quantum circuits. Multiplication of binary fields is one of the critical operations in the context of elliptic curve arithmetic, and it is especially costly in the quantum setting. Our goal in this paper is to optimize quantum multiplication in the binary field. In the past, efforts to optimize quantum multiplication have centred on reducing the Toffoli gate count or qubits required. However, despite the fact that circuit depth is an important metric for indicating the performance of a quantum circuit, previous studies have lacked sufficient consideration for reducing circuit depth. Our approach to optimizing quantum multiplication differs from previous work in that we aim at reducing the Toffoli depth and full depth. To optimize quantum multiplication, we adopt the Karatsuba multiplication method which is based on the divide-and-conquer approach. In summary, we present an optimized quantum multiplication that has a Toffoli depth of one. Additionally, the full depth of the quantum circuit is also reduced thanks to our Toffoli depth optimization strategy. To demonstrate the effectiveness of our proposed method, we evaluate its performance using various metrics such as the qubit count, quantum gates, and circuit depth, as well as the qubits-depth product. These metrics provide insight into the resource requirements and complexity of the method. Our work achieves the lowest Toffoli depth, full depth, and the best trade-off performance for quantum multiplication. Further, our multiplication is more effective when not used in stand-alone cases. We show this effectiveness by using our multiplication to the Itoh-Tsujii algorithm-based inversion of F(x8+x4+x3+x+1).

DOI
10.3390/s23063156

Related papers

Depth-Optimization of Quantum Cryptanalysis on Binary Elliptic Curves

Dedy Septono Catur Putranto, Rini Wisnu Wardhani, Harashta Tatimma Larasati +2 more

This paper presents quantum cryptanalysis for binary elliptic curves from a time-efficient implementation perspective (i.e., reducing the circuit depth), complementing the previous research that focuses on the space-efficiency perspective (i.e., reducing the circuit width). To achieve depth optimization, we propose an improvement to the existing circuit implementation of the Karatsuba multiplier and FLT-based inversion, then construct and analyze the resource in the Qiskit quantum computer simulator. The proposed multiplier architecture, which improves the quantum Karatsuba multiplier from the previous study, reduces the depth and yields a lower number of CNOT gates that bound to$O(n^{log_{2}(3)})$while maintaining a similar number of Toffoli gates and qubits. Furthermore, our improved FLT-based inversion reduces CNOT count and overall depth, with a tradeoff of higher qubit size. Finally, we employ the proposed multiplier and FLT-based inversion for performing quantum cryptanalysis of binary point addition as well as the complete Shor’s algorithm for the elliptic curve discrete logarithm problem (ECDLP). As a result, apart from depth reduction, we are also able to reduce up to 90% of the Toffoli gates required in a single-step point addition compared to prior work, leading to significant improvements and giving new insights on quantum cryptanalysis for a depth-optimized implementation.

IEEE Access•Jan 1, 2023•18 citations

Depth Optimization of FLT-Based Quantum Inversion Circuit

Harashta Tatimma Larasati, Dedy Septono Catur Putranto, Rini Wisnu Wardhani +2 more

Works on quantum computing and cryptanalysis have increased significantly in the past few years. Various constructions of quantum arithmetic circuits as one of the primary elements in the field have also been proposed. However, there have only been a few studies on finite field inversion despite its essential use in realizing quantum algorithms, such as in Shor’s algorithm for Elliptic Curve Discrete Logarithm Problem (ECDLP). In this study, we propose to reduce the depth of the existing quantum Fermat’s Little Theorem (FLT)-based inversion circuit for the binary finite field. In particular, we propose to follow a complete waterfall approach to translate the Itoh-Tsujii’s variant of FLT to the corresponding quantum circuit and remove the inverse squaring operations employed in the previous work by Banegas et al., lowering the number of CNOT gates (i.e., CNOT count) as well as slightly reducing the$T$depth, which contributes to a reduced overall depth and gate count. Furthermore, we concretely verify our method and compare it with the previous work in Qiskit, a quantum computer simulation environment, by constructing both our method and the previous work from scratch and performing the resource analysis. Additionally, we propose employing the relative-phase Toffoli gate by Gidney as opposed to the standard Toffoli implementation, which yields a significantly lower$T$depth while further reducing the overall depth. Our approach can serve as an alternative for a time-efficient implementation.

IEEE Access•Jan 1, 2023•6 citations

A Highly Efficient ECPM Quantum Circuit for Binary Elliptic Curve Cryptanalysis

Rini Wisnu Wardhani, Dedy Septono Catur Putranto, Jaehan Cho +1 more

This paper provides a detailed analysis and estimation of the quantum resources required for depth-optimized elliptic curve point multiplication (ECPM), with a focus on qubits, Toffoli gates, CNOT gates, and circuit depth. The proposed ECPM quantum circuit, which is tailored for binary elliptic curve cryptanalysis using Shor’s algorithm, incorporates improved arithmetic operations into optimized point addition (PA) and point doubling (PD) processes. The quantum resources required for single-step and full-step ECPM implementations (comprising$2n$PD +2 PA) were systematically evaluated to enable in-depth cryptanalysis of binary elliptic curve cryptography using Shor’s algorithm. The proposed approach offers a significant improvement in resource efficiency compared to circuits that rely solely on the existing PA, which typically require ($2n+2$)PA operations. The execution of a full iteration of quantum cryptanalysis using the Shor circuit was estimated to require$2n^{3}+ 2n(\log 3 + 1) + 32n^{2}\log n + 8n^{2} + O (n^{(\log 3 + 1)})$Toffoli gates, approximately$2n + 7n\log _{6} n + 7$qubits, and a circuit depth of approximately$7+n\log _{3}{9}$. Comparisons with leading Toffoli gate-level analysis results validate our findings, which demonstrate reduced quantum resource usage. In addition, key findings related to techniques for solving discrete logarithm problems are summarized, drawing from influential previous studies and current advancements.

IEEE Access•Jan 1, 2024•5 citations

Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost

Vivien Vandaele

Multiplication over binary fields is a crucial operation in quantum algorithms designed to solve the discrete logarithm problem for elliptic curve defined over $GF(2^n)$. In this paper, we present an algorithm for constructing quantum circuits that perform multiplication over $GF(2^n)$ with $\mathcal{O}(n^{\log_2(3)})$ Toffoli gates. We propose a variant of our construction that achieves linear depth by using $\mathcal{O}(n\log_2(n))$ ancillary qubits. This approach provides the best known space-time trade-off for binary field multiplication with a subquadratic number of Toffoli gates. Additionally, we demonstrate that for some particular families of primitive polynomials, such as trinomials, the multiplication can be done in logarithmic depth and with $\mathcal{O}(n^{\log_2(3)})$ gates.

arXiv:2501.16136•Jan 27, 2025•1 citation

Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

André Schrottenloher

Shor's algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its costs, either at the logical level (assuming a fault-tolerant architecture), or at the physical level (taking into account the constraints of envisioned hardware). In particular, recent works by Chevignard et al. (CRYPTO 2024) and Gidney (arXiv 2025) used improved arithmetic to significantly reduce the qubit cost of factoring RSA public keys. Even more recently, Babbush et al. (arXiv 2026) improved the cost of computing elliptic curve discrete logarithms, with a reduction of a factor 2 to 3 in gate count and qubit count compared to a previous work by Litinski (arXiv 2023). Their result relies on optimized point addition circuits on elliptic curves over prime fields. However they did not reveal their logical quantum circuits, relying instead on a zero-knowledge proof. In this paper, we detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field.

quant-pharXiv:2606.02235•Jun 2, 2026•0 citations

Concrete quantum cryptanalysis of binary elliptic curves

Gustavo Banegas, Daniel J. Bernstein, Iggy van Hoof +1 more

This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.

IACR Transactions on Cryptographic Hardware and Embedded Systems•Dec 3, 2020•47 citations
The Shor's algorithm can find solutions to the discrete logarithm problem on binary elliptic curves in polynomial time. A major challenge in implementing Shor's algorithm is the overhead of representing and performing arithmetic on binary elliptic curves using quantum circuits. Multiplication of binary fields is one of the critical operations in the context of elliptic curve arithmetic, and it is especially costly in the quantum setting. Our goal in this paper is to optimize quantum multiplication in the binary field. In the past, efforts to optimize quantum multiplication have centred on reducing the Toffoli gate count or qubits required. However, despite the fact that circuit depth is an important metric for indicating the performance of a quantum circuit, previous studies have lacked sufficient consideration for reducing circuit depth. Our approach to optimizing quantum multiplication differs from previous work in that we aim at reducing the Toffoli depth and full depth. To optimize quantum multiplication, we adopt the Karatsuba multiplication method which is based on the divide-and-conquer approach. In summary, we present an optimized quantum multiplication that has a Toffoli depth of one. Additionally, the full depth of the quantum circuit is also reduced thanks to our Toffoli depth optimization strategy. To demonstrate the effectiveness of our proposed method, we evaluate its performance using various metrics such as the qubit count, quantum gates, and circuit depth, as well as the qubits-depth product. These metrics provide insight into the resource requirements and complexity of the method. Our work achieves the lowest Toffoli depth, full depth, and the best trade-off performance for quantum multiplication. Further, our multiplication is more effective when not used in stand-alone cases. We show this effectiveness by using our multiplication to the Itoh-Tsujii algorithm-based inversion of F(x8+x4+x3+x+1).
This paper presents quantum cryptanalysis for binary elliptic curves from a time-efficient implementation perspective (i.e., reducing the circuit depth), complementing the previous research that focuses on the space-efficiency perspective (i.e., reducing the circuit width). To achieve depth optimization, we propose an improvement to the existing circuit implementation of the Karatsuba multiplier and FLT-based inversion, then construct and analyze the resource in the Qiskit quantum computer simulator. The proposed multiplier architecture, which improves the quantum Karatsuba multiplier from the previous study, reduces the depth and yields a lower number of CNOT gates that bound toO(nlog2(3))O(n^{log_{2}(3)})O(nlog2​(3))while maintaining a similar number of Toffoli gates and qubits. Furthermore, our improved FLT-based inversion reduces CNOT count and overall depth, with a tradeoff of higher qubit size. Finally, we employ the proposed multiplier and FLT-based inversion for performing quantum cryptanalysis of binary point addition as well as the complete Shor’s algorithm for the elliptic curve discrete logarithm problem (ECDLP). As a result, apart from depth reduction, we are also able to reduce up to 90% of the Toffoli gates required in a single-step point addition compared to prior work, leading to significant improvements and giving new insights on quantum cryptanalysis for a depth-optimized implementation.
Works on quantum computing and cryptanalysis have increased significantly in the past few years. Various constructions of quantum arithmetic circuits as one of the primary elements in the field have also been proposed. However, there have only been a few studies on finite field inversion despite its essential use in realizing quantum algorithms, such as in Shor’s algorithm for Elliptic Curve Discrete Logarithm Problem (ECDLP). In this study, we propose to reduce the depth of the existing quantum Fermat’s Little Theorem (FLT)-based inversion circuit for the binary finite field. In particular, we propose to follow a complete waterfall approach to translate the Itoh-Tsujii’s variant of FLT to the corresponding quantum circuit and remove the inverse squaring operations employed in the previous work by Banegas et al., lowering the number of CNOT gates (i.e., CNOT count) as well as slightly reducing theTTTdepth, which contributes to a reduced overall depth and gate count. Furthermore, we concretely verify our method and compare it with the previous work in Qiskit, a quantum computer simulation environment, by constructing both our method and the previous work from scratch and performing the resource analysis. Additionally, we propose employing the relative-phase Toffoli gate by Gidney as opposed to the standard Toffoli implementation, which yields a significantly lowerTTTdepth while further reducing the overall depth. Our approach can serve as an alternative for a time-efficient implementation.
This paper provides a detailed analysis and estimation of the quantum resources required for depth-optimized elliptic curve point multiplication (ECPM), with a focus on qubits, Toffoli gates, CNOT gates, and circuit depth. The proposed ECPM quantum circuit, which is tailored for binary elliptic curve cryptanalysis using Shor’s algorithm, incorporates improved arithmetic operations into optimized point addition (PA) and point doubling (PD) processes. The quantum resources required for single-step and full-step ECPM implementations (comprising2n2n2nPD +2 PA) were systematically evaluated to enable in-depth cryptanalysis of binary elliptic curve cryptography using Shor’s algorithm. The proposed approach offers a significant improvement in resource efficiency compared to circuits that rely solely on the existing PA, which typically require (2n+22n+22n+2)PA operations. The execution of a full iteration of quantum cryptanalysis using the Shor circuit was estimated to require2n3+2n(log⁡3+1)+32n2log⁡n+8n2+O(n(log⁡3+1))2n^{3}+ 2n(\log 3 + 1) + 32n^{2}\log n + 8n^{2} + O (n^{(\log 3 + 1)})2n3+2n(log3+1)+32n2logn+8n2+O(n(log3+1))Toffoli gates, approximately2n+7nlog⁡6n+72n + 7n\log _{6} n + 72n+7nlog6​n+7qubits, and a circuit depth of approximately7+nlog⁡397+n\log _{3}{9}7+nlog3​9. Comparisons with leading Toffoli gate-level analysis results validate our findings, which demonstrate reduced quantum resource usage. In addition, key findings related to techniques for solving discrete logarithm problems are summarized, drawing from influential previous studies and current advancements.
Multiplication over binary fields is a crucial operation in quantum algorithms designed to solve the discrete logarithm problem for elliptic curve defined over GF(2n)GF(2^n)GF(2n). In this paper, we present an algorithm for constructing quantum circuits that perform multiplication over GF(2n)GF(2^n)GF(2n) with O(nlog⁡2(3))\mathcal{O}(n^{\log_2(3)})O(nlog2​(3)) Toffoli gates. We propose a variant of our construction that achieves linear depth by using O(nlog⁡2(n))\mathcal{O}(n\log_2(n))O(nlog2​(n)) ancillary qubits. This approach provides the best known space-time trade-off for binary field multiplication with a subquadratic number of Toffoli gates. Additionally, we demonstrate that for some particular families of primitive polynomials, such as trinomials, the multiplication can be done in logarithmic depth and with O(nlog⁡2(3))\mathcal{O}(n^{\log_2(3)})O(nlog2​(3)) gates.
Shor's algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its costs, either at the logical level (assuming a fault-tolerant architecture), or at the physical level (taking into account the constraints of envisioned hardware). In particular, recent works by Chevignard et al. (CRYPTO 2024) and Gidney (arXiv 2025) used improved arithmetic to significantly reduce the qubit cost of factoring RSA public keys. Even more recently, Babbush et al. (arXiv 2026) improved the cost of computing elliptic curve discrete logarithms, with a reduction of a factor 2 to 3 in gate count and qubit count compared to a previous work by Litinski (arXiv 2023). Their result relies on optimized point addition circuits on elliptic curves over prime fields. However they did not reveal their logical quantum circuits, relying instead on a zero-knowledge proof. In this paper, we detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field.
This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.