Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion
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 bin...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/23/6/3156 |
| _version_ | 1797609073269538816 |
|---|---|
| author | Kyungbae Jang Wonwoong Kim Sejin Lim Yeajun Kang Yujin Yang Hwajeong Seo |
| author_facet | Kyungbae Jang Wonwoong Kim Sejin Lim Yeajun Kang Yujin Yang Hwajeong Seo |
| author_sort | Kyungbae Jang |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="double-struck">F</mi><mo>(</mo><msup><mi>x</mi><mn>8</mn></msup><mo>+</mo><msup><mi>x</mi><mn>4</mn></msup><mo>+</mo><msup><mi>x</mi><mn>3</mn></msup><mo>+</mo><mi>x</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></inline-formula>. |
| first_indexed | 2024-03-11T05:56:23Z |
| format | Article |
| id | doaj.art-98821a5a33fc40ed9e20c9522af39b9b |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-11T05:56:23Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-98821a5a33fc40ed9e20c9522af39b9b2023-11-17T13:46:45ZengMDPI AGSensors1424-82202023-03-01236315610.3390/s23063156Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum InversionKyungbae Jang0Wonwoong Kim1Sejin Lim2Yeajun Kang3Yujin Yang4Hwajeong Seo5Division of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of KoreaDivision of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of KoreaDivision of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of KoreaDivision of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of KoreaDivision of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of KoreaDivision of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of KoreaThe 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="double-struck">F</mi><mo>(</mo><msup><mi>x</mi><mn>8</mn></msup><mo>+</mo><msup><mi>x</mi><mn>4</mn></msup><mo>+</mo><msup><mi>x</mi><mn>3</mn></msup><mo>+</mo><mi>x</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></inline-formula>.https://www.mdpi.com/1424-8220/23/6/3156binary fieldquantum multiplicationToffoli depthquantum inversion |
| spellingShingle | Kyungbae Jang Wonwoong Kim Sejin Lim Yeajun Kang Yujin Yang Hwajeong Seo Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion Sensors binary field quantum multiplication Toffoli depth quantum inversion |
| title | Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion |
| title_full | Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion |
| title_fullStr | Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion |
| title_full_unstemmed | Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion |
| title_short | Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion |
| title_sort | quantum binary field multiplication with optimized toffoli depth and extension to quantum inversion |
| topic | binary field quantum multiplication Toffoli depth quantum inversion |
| url | https://www.mdpi.com/1424-8220/23/6/3156 |
| work_keys_str_mv | AT kyungbaejang quantumbinaryfieldmultiplicationwithoptimizedtoffolidepthandextensiontoquantuminversion AT wonwoongkim quantumbinaryfieldmultiplicationwithoptimizedtoffolidepthandextensiontoquantuminversion AT sejinlim quantumbinaryfieldmultiplicationwithoptimizedtoffolidepthandextensiontoquantuminversion AT yeajunkang quantumbinaryfieldmultiplicationwithoptimizedtoffolidepthandextensiontoquantuminversion AT yujinyang quantumbinaryfieldmultiplicationwithoptimizedtoffolidepthandextensiontoquantuminversion AT hwajeongseo quantumbinaryfieldmultiplicationwithoptimizedtoffolidepthandextensiontoquantuminversion |