Prime factorization using quantum variational imaginary time evolution.

Area of Science:

• Quantum Computing
• Computational Mathematics
• Quantum Algorithms

Background:

• Shor's algorithm offers theoretical speedups for prime factorization but is hindered by noisy qubits and lack of error correction.
• Current quantum hardware limitations restrict the practical application of complex quantum algorithms like Shor's.

Purpose of the Study:

• To explore an alternative quantum method for prime factorization using variational imaginary time evolution.
• To demonstrate a viable approach for prime factorization on current quantum devices despite hardware imperfections.

Main Methods:

• Constructing a Hamiltonian whose ground state encodes the prime factors of a given number.
• Employing variational techniques to iteratively evolve a quantum state towards the solution.
• Utilizing a single layer of entangling gates for factorization.

Main Results:

• The number of circuits evaluated per iteration scales as O(2^(n/2) * d), where n is bit-length and d is circuit depth.
• Successfully factorized 36 numbers using 7, 8, and 9-qubit Hamiltonians.
• Factored 55, 65, 77, and 91 on IBMQ hardware, exceeding previous records for numbers factorized on such platforms.

Conclusions:

• Variational imaginary time evolution presents a promising alternative for quantum prime factorization on near-term devices.
• The method demonstrates scalability and practical feasibility, surpassing limitations of existing quantum factorization approaches.
• This work advances the potential for practical quantum advantage in number theory problems.