Quantum Algorithms for Prime Number Search and Verification

[ThiriYaminHsu]

Project Overview

This project aims to implement quantum algorithms for efficiently identifying prime numbers by leveraging Grover's search and quantum order-finding techniques. The implementation is inspired by recent research on quantum computation of prime number functions and primality testing, including:

1. "Quantum Computation of Prime Number Functions" (Latorre & Sierra) – arXiv:1302.6245
2. "A Quantum Primality Test with Order Finding" (Donis-Vela & García-Escartín) – arXiv:1711.02616
3. "Using Quantum Computers to Identify Prime Numbers via Entanglement Dynamics" (dos Santos & Maziero) – arXiv:2403.14703

The goal is to explore quantum-enhanced methods for prime number search and verification while comparing their performance with classical approaches.

Scientific Background

Prime number identification is crucial in cryptography, number theory, and computational complexity. Classical methods, such as the AKS primality test or Miller-Rabin test, are efficient but can still be improved for large numbers.

Quantum computing introduces speedups through algorithms like:

• Grover’s Algorithm for Unstructured Search – Can be used to amplify the probability of finding primes in a given range.
• Quantum Order Finding (Shor's Algorithm Variant) – Helps in identifying primes by checking modular properties of numbers.
• Quantum Counting Algorithms (Amplitude Estimation) – Estimates the distribution of prime numbers in a given range.

By implementing these quantum methods, we can explore their computational advantages over classical algorithms.

Implementation Scope

Core Algorithm Implementations

• Quantum Prime Number Search using Grover's search.
• Quantum Primality Testing leveraging order-finding techniques.
• Quantum-enhanced Prime Counting of using amplitude estimation.

Quantum Circuit Components

• Oracle functions for prime number verification.
• Quantum register initialization and measurement mechanisms.
• Entanglement-based techniques for prime identification.

Performance Analysis & Comparison

• Simulating algorithm performance using Qiskit and the Classiq SDK.
• Benchmarking against classical methods such as AKS and Miller-Rabin tests.
• Optimizing scalability for practical applications.

Expected Outcomes

• Fully functional quantum circuits for prime number search and testing.
• Comparative analysis of quantum vs. classical methods.
• Open-source contribution to the Classiq Library, with detailed documentation.

Why This Project Matters

• Advancing Quantum Computing Applications – Prime searching is fundamental in cryptography and number theory.
• Exploring Quantum Speedups – Investigates potential advantages of quantum algorithms over classical counterparts.
• Contributing to Open Quantum Research – Provides a foundation for quantum-secure cryptographic applications.

[TomerGoldfriend]

Sounds interesting @ThiriYaminHsu !

Please note that we accept high-quality implementations to our repository and will be glad to accept a contribution that meets our standards.
Feel free to reach out to the community for any questions!

Good luck!