Resource analysis and modifications of quantum computing with noisy qubits for elliptic curve discrete logarithms

Area of Science:

• Quantum Computing
• Cryptography
• Computer Science

Background:

• Quantum algorithms pose a threat to current cryptographic standards like RSA and elliptic curve cryptography.
• Estimating the resource requirements for implementing quantum algorithms is crucial for assessing these threats.

Purpose of the Study:

• To estimate the physical qubit count and execution time for Shor's algorithm applied to elliptic curve discrete logarithms.
• To compare novel quantum circuits with existing ones for this task.
• To evaluate the impact of logical qubit usage on physical qubit requirements.

Main Methods:

• Decomposition of Shor's algorithm for elliptic curve discrete logarithms into universal gate units.
• Utilizing surface codes and assuming logical qubits with all-to-all connectivity.
• Expressing resource estimates (physical qubits, execution time) as functions of bit length, error rates, and failure probability.

Main Results:

• Demonstrated that increased logical qubits do not necessarily equate to increased physical qubits.
• Provided resource estimations for elliptic curve discrete logarithm implementation using modified quantum circuits.
• Compared resource requirements with Shor's factoring algorithm to assess cryptographic risks.

Conclusions:

• The study offers a refined understanding of quantum resource estimation for cryptographic applications.
• Findings are vital for evaluating the quantum computing threat landscape to RSA and elliptic curve cryptography.
• Optimized quantum circuit designs can potentially reduce the physical resources needed for cryptographically relevant quantum algorithms.