Quantum Security Threats from the NISQ Era and Beyond

It is widely believed that quantum computers won’t be able to inflict any serious harm on our security systems for at least 15 years. That is when full scale, fault-tolerant quantum computers are expected to be available and able to run Shor’s algorithm to crack RSA in a reasonable amount of time. Well, the reality is much dimmer: real quantum security threats are much more immediate, most likely within five years.

You might be asking, “Really? How so?”

These near-term security threats will be from heuristic algorithms running on error-prone quantum devices from the NISQ era we are already in today.

Using Shor’s algorithm, factoring a 2048-bit RSA number requires 100,000 fault-tolerant qubits running for 10 days, or 20M NISQ qubits for 8 hours. Since we won’t have such large-scale quantum computers for at least a decade, we might feel that we have a lot of time on hand to get prepared.

But using today’s NISQ devices, we at Zapata Computing have come up with a heuristic algorithm called Variational Quantum Factoring (VQF, patented), which we estimate can factor a 2048-bit RSA number with roughly 6,000 NISQ qubits within one hour. Based on published product roadmaps from leading quantum computer companies, NISQ quantum computers at this scale are expected to be available within five years.

Think about it. The quantum security threat is much more immediate than what most realize.

Well, you might be wondering, “What is a heuristic algorithm, and why in this case, is it so much more powerful than Shor’s algorithm when it comes to breaking an RSA number?”

The computing complexity pioneer and Turing award winner, Stephen Cook, defines it well:

“A heuristic algorithm is one that is designed to solve a problem in a faster and more efficient fashion than traditional methods by sacrificing optimality, accuracy, precision, or completeness for speed.”

In other words, a heuristic algorithm is not mathematically complete or proven in theory, but it works in practice. A well-known example of a heuristic algorithm is neural networks, which have proven to be extremely effective in applications such as facial recognition, despite there being no mathematical proof that it should work. Moreover, it’s getting more accurate and more powerful as better convolutional neural networks are designed.

Our VQF algorithm is another example. Unlike Shor’s algorithm, it is a hybrid algorithm using both quantum computers and classical computers. Specifically, it maps the factoring problem into a combinatorial optimization problem, uses classical computers for pre-processing, and employs the well-known quantum approximate optimization algorithm (QAOA). This approach has significantly reduced the number of qubits required to factor a large number.

The NISQ Threat Is a Lot Nearer-term than the PQC Threat

While most efforts across academia, standard bodies, and security firms are focused on mitigating security threats from the Post-Quantum Cryptography (PQC) era a decade or more down the road with expected threats from Shor’s algorithms running on full scale, fault-tolerant quantum computers, the VQF algorithm has exposed the feasibility of near-term security threats from heuristic algorithms running on quantum computers in the NISQ era we are already in today.

We have been looking closely at this issue and speaking to large enterprises, governments and organizations. This is the kind of quantum cybersecurity threat that they are most concerned about.

With our deep bench of quantum scientists and our Orquestra® software platform running on quantum computers, we have developed a set of tools and services to help you get better prepared for security threats from the NISQ era and beyond, including research, assessment, testing, rating and verification.

Let’s get started today.

Jay Liu, VP of Product at Zapata Computing