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

Quantum Information Processing

Toffoli gate count optimized space-efficient quantum circuit for binary field multiplication

Sunyeop Kim, Insung Kim, Seonggyeom Kim, Seokhie Hong

Published Sep 30, 2024• 5 citations
Publisher
DOI
10.1007/s11128-024-04536-1

Related papers

Optimized Implementation of Quantum Binary Field Multiplication with Toffoli Depth One

Kyungbae Jang, Wonwoong Kim, Sejin Lim +3 more

Lecture notes in computer science•Jan 1, 2023•11 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

Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count

Iggy van Hoof

Multiplication is an essential step in a lot of calculations. In this paper we look at multiplication of 2 binary polynomials of degree at most $n-1$, modulo an irreducible polynomial of degree $n$ with $2n$ input and $n$ output qubits, without ancillary qubits, assuming no errors. With straightforward schoolbook methods this would result in a quadratic number of Toffoli gates and a linear number of CNOT gates. This paper introduces a new algorithm that uses the same space, but by utilizing space-efficient variants of Karatsuba multiplication methods it requires only $O(n^{\log_2(3)})$ Toffoli gates at the cost of a higher CNOT gate count: theoretically up to $O(n^2)$ but in examples the CNOT gate count looks a lot better.

arXiv:1910.02849•Oct 7, 2019•2 citations

Efficient Toffoli Gate in Circuit Quantum Electrodynamics

Matthew Reed, L. DiCarlo, Luyan Sun +2 more

Bulletin of the American Physical Society•Mar 21, 2011•0 citations

Optimization of Quantum Boolean Circuits by Relative-Phase Toffoli Gates

Shohei Kuroda, Shigeru Yamashita

Lecture notes in computer science•Jan 1, 2022•4 citations

Space-efficient quantum multiplication polynomials for binary finite fields with sub-quadratoc Toffoli gate count

Iggy van Hoof

Multiplication is an essential step in a lot of calculations. In this paper we look at multiplication of 2 binary polynomials of degree at most n-1, modulo an irreducible polynomial of degree n with 2n input and n output qubits, without ancillary qubits, assuming no errors. With straightforward schoolbook methods this would result in a quadratic number of Toffoli gates and a linear number of CNOT gates. This paper introduces a new algorithm that uses the same space, but by utilizing space-efficient variants of Karatsuba multiplication methods it requires only O(n^{\log_2(3)}) Toffoli gates at the cost of a higher CNOT gate count: theoretically up to O(n^2) but in examples the CNOT gate count looks a lot better.

Quantum Information and Computation•Aug 1, 2020•26 citations
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.
Multiplication is an essential step in a lot of calculations. In this paper we look at multiplication of 2 binary polynomials of degree at most n−1n-1n−1, modulo an irreducible polynomial of degree nnn with 2n2n2n input and nnn output qubits, without ancillary qubits, assuming no errors. With straightforward schoolbook methods this would result in a quadratic number of Toffoli gates and a linear number of CNOT gates. This paper introduces a new algorithm that uses the same space, but by utilizing space-efficient variants of Karatsuba multiplication methods it requires only O(nlog⁡2(3))O(n^{\log_2(3)})O(nlog2​(3)) Toffoli gates at the cost of a higher CNOT gate count: theoretically up to O(n2)O(n^2)O(n2) but in examples the CNOT gate count looks a lot better.
Multiplication is an essential step in a lot of calculations. In this paper we look at multiplication of 2 binary polynomials of degree at most n-1, modulo an irreducible polynomial of degree n with 2n input and n output qubits, without ancillary qubits, assuming no errors. With straightforward schoolbook methods this would result in a quadratic number of Toffoli gates and a linear number of CNOT gates. This paper introduces a new algorithm that uses the same space, but by utilizing space-efficient variants of Karatsuba multiplication methods it requires only O(n^{\log_2(3)}) Toffoli gates at the cost of a higher CNOT gate count: theoretically up to O(n^2) but in examples the CNOT gate count looks a lot better.