What Does It Take to Run Shor's Algorithm on a Quantum Computer?

https://www.quantum-machines.co/blog/what-does-it-take-for-a-control-system-to-run-shors-algorithm-on-an-error-corrected-quantum-machine/

by GavCo • 2 years ago

23 9 2 years ago

quantum-machines.co

tromp2• 2 years ago

I hoped this article would explain how many logical qubits are required to run the fully general Shor's algorithm (without precompilation cheats and such) to factor e.g. the product of two 6-bit primes, but it seems more geared to advertising a quantum circuit controller that this company makes:

Controlling 1015 qubits requires thousands of synchronized analog control channels attached to a powerful orchestration brain able to handle thousands of simultaneous operations. Adopting a modular approach, QM has tackled this challenge by creating OPX1000, the most advanced and highest-scale quantum controller in industry.

The article suggests that only 5 logical qubits are needed to factor the product of two 3-bit primes, but how does one arrive at that number? Shor's algorithm requires performing a multiplication of two k-bit numbers, which would seem to require more than 2k-1 bits. So what do these 5 qubits correspond to exactly in Shor's algorithm?

swernli• 2 years ago

The Azure Quantum website has some good resources for learning about what’s required for performing error corrected runs of Shor’s algorithm in order to defeat current cryptographic schemes: https://quantum.microsoft.com/en-us/tools/quantum-cryptograp...

You can also try a small scale simulation of Shor’s algorithm and a resource estimation sample in the interactive playground available via VS Code for Web: https://vscode.dev/quantum/playground/

abdullahkhalids• 2 years ago

To factor a number of n bits or smaller, you need n + t qubits. The larger the t the less time you take to find a solution, and if I remember correctly t has to be O(n).

I assume in the article, they are giving estimates with tricks.

coolThingsFirst• 2 years ago

A quantum computer?

randomdata• 2 years ago

First, you need to give birth to the entire universe.

fragmede2• 2 years ago

That’s just to factorize the number 21.

Reading between the lines, we're many many many years away from being able to factor large primes.

tromp2• 2 years ago

The factorization of large prime p is simply p.

fragmede2• 2 years ago

haha, fair! Too late to edit my post to say "factor the product of two large primes" now tho.

tetha• 2 years ago

Truth.

At the same time, phasing out and introducing crypto primitives takes 10 - 20 years across the industry due to inertia from unmaintained systems, legacy code, compatibility, fear and such. So the growing interest to move to quantum secure encryption is right, even if the first RSA breaking quantum computer goes live after I retire.

What Does It Take to Run Shor's Algorithm on a Quantum Computer?

Related Stories