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?
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/
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.
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.
> 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?