Quantum mechanics

Algorithm

Prime time

Quantum computer

Discrete mathematics

Factorization

Quantum error correction

Supersymmetric quantum mechanics

Quantum circuit

Embedded system

Prime (order theory)

Theoretical computer science

Gate count

Telecommunications

Computer science

Mathematical optimization

Hamiltonian (control theory)

The Imaginary

Physics

Imaginary time

Quantum statistical mechanics

Psychology

Mathematics

Psychotherapist

Prime number

Quantum

Combinatorics

Qubit

Scientific Reports

The road to computing on quantum devices has been accelerated by the promises that come from using Shor’s algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as $$O(n^{5}d)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>5</mml:mn> </mml:msup> <mml:mi>d</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where n is the bit-length of the number to be factorized and d is the depth of the circuit. We use a single layer of entangling gates to factorize 36 numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method’s performance by implementing it on the IBMQ Lima hardware to factorize 55, 65, 77 and 91 which are greater than the largest number (21) to have been factorized on IBMQ hardware.

Prime factorization using quantum variational imaginary time evolution