Division of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of Korea.
Sensors (Basel). 2023 Mar 15;23(6):3156. doi: 10.3390/s23063156.
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).
肖尔算法可以在多项式时间内找到二进制椭圆曲线离散对数问题的解。在实现肖尔算法时，一个主要的挑战是使用量子电路表示和执行二进制椭圆曲线的算术，这需要大量的开销。在椭圆曲线算术的上下文中，二进制字段的乘法是关键操作之一，在量子设置中尤其昂贵。我们的目标是优化二进制字段中的量子乘法。在过去，优化量子乘法的努力集中在减少 Toffoli 门数量或所需的量子比特上。然而，尽管电路深度是表示量子电路性能的重要指标，但以前的研究对减少电路深度缺乏足够的考虑。我们优化量子乘法的方法与以前的工作不同，我们的目标是减少 Toffoli 深度和全深度。为了优化量子乘法，我们采用了基于分治思想的 Karatsuba 乘法方法。总之，我们提出了一种优化的量子乘法，其 Toffoli 深度为 1。此外，由于我们的 Toffoli 深度优化策略，量子电路的全深度也得到了降低。为了证明我们提出的方法的有效性，我们使用各种度量标准，如量子比特数、量子门和电路深度以及量子比特深度乘积，来评估其性能。这些度量标准提供了对方法资源需求和复杂性的深入了解。我们的工作实现了量子乘法的最低 Toffoli 深度、全深度和最佳折衷性能。此外，我们的乘法在不是独立使用的情况下更为有效。我们通过使用我们的乘法来进行基于 Itoh-Tsujii 算法的 F(x8+x4+x3+x+1)的逆运算，展示了这种有效性。
