4 ms·
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 fa
by tromp 2y 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 2y agoThe 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-cryptography 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/ https://vscode.dev/quantum/playground/
- abdullahkhalids 2y agoTo 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.