Zapata Develops Potential Alternative to Shor’s Factoring Algorithm for NISQ Quantum Computers



Anyone who looks at quantum computing is quickly aware of Shor’s algorithm which can potentially factor large semiprime numbers in a reasonable period of time.  What this means is that some future quantum computer running Shor’s algorithm will be able to factor a large 2048 bit number in perhaps a few hours versus the billions of years it would take using the best known classical algorithm.  This could jeopardizes the security of the RSA public key cryptography algorithm which is dependent upon the difficulty of factoring such a large number.

The drawback to Shor’s algorithm is that to factor the 2048 number typically used with RSA it would requires a quantum computer with about 4100 logical (or error-free) qubits.  However, because of the fragility of quantum qubits, massive error correction would be needed. The 4100 logical qubits could require roughly 40 million or more physical qubits in order to implement the error correction needed.  Machines of this large size are still a long ways off.

So it is with great interest that we have just seen a new algorithm published by Zapata called Variational Quantum Factoring.  This new algorithm converts the factor problem to a binary optimization problem of finding the ground state of an Ising Hamiltonian.  These types of problems can use a hybrid classical/quantum approach call the Quantum Approximate Optimization Algorithm (QAOA), which is starting to become popular in various computational chemistry and other optimization applications.

The advantage of this new approach is that it is much less sensitive to error and does not require massive error correction and consume far fewer resources than would be needed with Shor’s algorithm.  As such it may be more amenable for use with the current NISQ (Noisy Intermediate Scale Quantum) computers that will be available in the near and medium term.

The research is still very new and it is not yet known how viable the algorithm would be for use with larger numbers.  Even in their paper Zapata noted that the algorithm does struggle with certain factoring instances.   They will be performing more research on this new algorithm and so far the largest number they have explored with this approach is 291311 which is the product of 523 and 557.  That number is a little larger than 18 binary bits and to attack RSA one would have to factor a 2048 bit number. But if this algorithm does work out, it would be a significant development and could replace Shor’s algorithm as the preferred method for factoring large numbers on a quantum computer.

For more details, you can read the paper that Zapata published on arXiv here.