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.
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.
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(nlog2(3)) Toffoli gates at the cost of a higher CNOT gate count: theoretically up to O(n2) but in examples the CNOT gate count looks a lot better.
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). In this paper, we present an algorithm for constructing quantum circuits that perform multiplication over GF(2n) with O(nlog2(3)) Toffoli gates. We propose a variant of our construction that achieves linear depth by using 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(nlog2(3)) gates.
Asymptotic yet practical optimization of quantum circuits implementing GF(2m) multiplication and division operations
We present optimized quantum circuits for GF(2m) multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of O(mlog23), an improvement over the previous best bound of O(m2). This was achieved by developing an efficient O(m) circuit for multiplication by the constant polynomial 1+x⌈m/2⌉, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters m of practical importance. For the GF division, we reduce gate count complexity from O(m2log(m)) to O(m2loglog(m)/log(m)) by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of m, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.
This paper examines the asymptotic performance of multiplication and the cost of quantum implementation for the Naive schoolbook, Karatsuba, and Toom-Cook methods in the classical and quantum cases and provides insights into multiplication roles in the post-quantum cryptography (PQC) era. Further, considering that the lattice-based PQC algorithm is based on polynomial multiplication algorithms, including the Toom-Cook 4-way multiplier as its fundamental building block, we propose a higher-degree multiplier, the Toom-Cook 8-way multiplier, which has the lowest asymptotic performance and implementation cost. Additionally, the designed multiplication will include additional sub-operations to complete the multiplication of large integers in order to prevent side-channel attacks. To design our Toom-Cook 8-way in detail, we employ detailed step computations such as splitting, evaluation, point-wise multiplication, interpolation, and recomposition, as well as several strategies to reduce space and time requirements. Existing asymptotic performance and quantum implementation cost multipliers are compared with our 2-way, 4-way, and 8-way Toom-Cook multiplier designs. Our Toom-Cook 8-way quantum multiplier has the lowest asymptotic performance analysis or qubit count in terms of space efficiency, withn( 15/8 )log 15 /(2 log 15–log 8) log8nor asymptoticallyO(n1.245). The design has the lowest logical Toffoli counts bound at 112nlog815– 128nand Toffoli depth ofn( 15/8 )1– log 15 /(2 log 15–log 8) log8n, asymptotically close toO(n1.0569), which corresponds to a space- and time-efficient multiplication.
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 a method for constructing quantum circuits for schoolbook multiplication using controlled add-subtract circuits, asymptotically halving the Toffoli count compared to traditional controlled-adder-based constructions. Controlled n-qubit add-subtract circuits, which perform an addition when the control qubit is one and a subtraction when it is zero, require only n-1 Toffoli gates, instead of the 2n-1 needed for controlled adders. Despite the existence of multiplication circuits with better asymptotic scaling, schoolbook multiplication yields the lowest Toffoli counts for small register sizes, making it advantageous in practical applications. For example, the presented approach reduces the Toffoli count by up to around 30% in circuits for breaking 256-bit elliptic curve keys compared to circuits with standard schoolbook multipliers.