# Prime Factorization Using Quantum Variational Imaginary Time Evolution

arXiv: https://arxiv.org/abs/2107.10196 · HTML: https://mlsanity.com/paper/2107.10196/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2021.

## Built on by (most cited first, 2 of 2)

- [Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries](https://mlsanity.com/paper/2409.15645/) (2024)
- [Estimating the Effect of Crosstalk Error on Circuit Fidelity Using Noisy Intermediate-Scale Quantum Devices](https://mlsanity.com/paper/2402.06952/) (2024)

## Abstract (arXiv)

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(n5d), 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 several numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method's performance by implementing it on the IBMQ Lima hardware.