News for hackers. Stuff that matters.
Re:What Does It Take to Run Shor's Algorithm on a Quantum Co... by tromp on Friday September 13, 2024 @03:56AM (#41529003)
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.

Re:What Does It Take to Run Shor's Algorithm on a Quantum Co... by swernli on Friday September 13, 2024 @10:29AM (#41531582)
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/

Re:What Does It Take to Run Shor's Algorithm on a Quantum Co... by abdullahkhalids on Friday September 13, 2024 @11:44PM (#41537319)
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.