August 27, 2018

Variational Quantum Factoring

  • Yudong Cao
  • Jonathan Olson

Shor’s famous algorithm from 1994 jumpstarted quantum computing as it demonstrated that quantum computers could pose a security risk for our society’s most common encryption protocols.  Though the hardware required to realize Shor’s algorithm is still a distant future (requiring tens of millions of qubits), in this paper we consider a near-term possibility that could reduce the qubit overhead to around 6,000 for factoring a 2048-bit RSA number. 


Integer factorization has been one of the cornerstone applications of the field of quantum com- puting since the discovery of an efficient algorithm for factoring by Peter Shor. Unfortunately, factoring via Shor’s algorithm is well beyond the capabilities of today’s noisy intermediate-scale quantum (NISQ) devices. In this work, we revisit the problem of factoring, developing an alter- native to Shor’s alyugorithm, which employs established techniques to map the factoring problem to the ground state of an Ising Hamiltonian. The proposed variational quantum factoring (VQF) algorithm starts by simplifying equations over Boolean variables in a preprocessing step to reduce the number of qubits needed for the Hamiltonian. Then, it seeks an approximate ground state of the resulting Ising Hamiltonian by training variational circuits using the quantum approximate op- timization algorithm (QAOA). We benchmark the VQF algorithm on various instances of factoring and present numerical results on its performance.

Yudong Cao
Zapata Author

Yudong Cao , Ph.D.

Chief Technology Officer & Co-Founder
Jonathan Olson
Zapata Author

Jonathan Olson , Ph.D.

Associate Director of Quantum Science IP & Co-Founder