Quantum Circuit Optimization for Solving Discrete Logarithm of Binary Elliptic Curves Obeying the Nearest-Neighbor...

Area of Science:

• Quantum Computing
• Cryptography
• Computational Mathematics

Background:

• Discrete logarithm problem on binary elliptic curves is crucial for cryptography.
• Quantum circuits for elliptic curve cryptography require significant resources.
• Optimizing quantum operations is key to practical quantum cryptographic implementations.

Purpose of the Study:

• To optimize quantum circuits for binary elliptic curve discrete logarithms.
• To reduce resource expenditure, specifically CNOT gate count.
• To improve the design of quantum operations for elliptic curve point addition.

Main Methods:

• Utilized space-efficient quantum Karatsuba multiplication.
• Applied Steiner tree problem reduction for circuit optimization.
• Analyzed the relationship between CNOT count and connected graph minimum degree.

Main Results:

• Reduced the number of CNOTs in quantum circuits for inversion and division.
• Demonstrated optimization under constrained connectivity.
• Established a link between optimized CNOT count and graph properties.

Conclusions:

• The proposed optimization techniques effectively reduce resource requirements for quantum discrete logarithm computations on binary elliptic curves.
• The study provides a pathway for more efficient quantum cryptographic implementations.
• Further research can explore these methods for other complex quantum algorithms.