2 ms·

> In practical terms, Shor's algorithm requires O(n lg n) qubits Wait, is that 'n' the number being factor or the number of bits? If it is the number being fa

> In practical terms, Shor's algorithm requires O(n lg n) qubits Wait, is that 'n' the number being factor or the number of bits? If it is the number being factored, then quantum computing will effectively never be a threat; since you would need 200 million bits in order to factor a 32-bit number. If it is the number of bits then why haven't we seen any new results? The current record is held by factoring 21, a 5 bit number. There are numerous claims that people have built quantum computers in the 49-qubit range. Why aren't we seeing successful factorings of 17-bit numbers as a matter of course? I don't count here the extension of the 21 result to larger numbers that yield the same period-finding problem, but rather direct approaches using the quantum computers that exist now.

jcranmer 8y ago
> Wait, is that 'n' the number being factor or the number of bits? Number of bits.
abdullahkhalids 8y ago
You have to implement quantum error correction on these 49 physical qubits to avoid errors, which leaves you with a lot fewer logical qubits. Also you have to take into account the constants.
- andrewla 8y ago
  So how many "effective" qbits are there in these systems that I see hyped up? Intel's press release for its 49-bit system [1] does not mention anything about "logical qubits". IBM's 50-qubit system [2] similarly does not hedge here. I see a question on stack overflow [3] that has some information, and actually claims an O(n) bound on the number of qubits, which is much tighter than the O(nlogn) number, but that just makes my question about why the record for Shor's algorithm has not yet been broken. I mean, forget about "quantum supremacy" -- where quantum anything? [1] https://newsroom.intel.com/news/intel-advances-quantum-neuromorphic-computing-research/ https://newsroom.intel.com/news/intel-advances-quantum-neuro... [2] https://www.technologyreview.com/s/609451/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/ https://www.technologyreview.com/s/609451/ibm-raises-the-bar... [3] https://stackoverflow.com/questions/41397576/how-many-qubits-do-i-need-to-factor-15-using-shors-algorithm https://stackoverflow.com/questions/41397576/how-many-qubits...

jcranmer 8y ago

> Wait, is that 'n' the number being factor or the number of bits? Number of bits.

abdullahkhalids 8y ago

You have to implement quantum error correction on these 49 physical qubits to avoid errors, which leaves you with a lot fewer logical qubits. Also you have to take into account the constants.

andrewla 8y ago
So how many "effective" qbits are there in these systems that I see hyped up? Intel's press release for its 49-bit system [1] does not mention anything about "logical qubits". IBM's 50-qubit system [2] similarly does not hedge here. I see a question on stack overflow [3] that has some information, and actually claims an O(n) bound on the number of qubits, which is much tighter than the O(nlogn) number, but that just makes my question about why the record for Shor's algorithm has not yet been broken. I mean, forget about "quantum supremacy" -- where quantum anything? [1] https://newsroom.intel.com/news/intel-advances-quantum-neuromorphic-computing-research/ https://newsroom.intel.com/news/intel-advances-quantum-neuro... [2] https://www.technologyreview.com/s/609451/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/ https://www.technologyreview.com/s/609451/ibm-raises-the-bar... [3] https://stackoverflow.com/questions/41397576/how-many-qubits-do-i-need-to-factor-15-using-shors-algorithm https://stackoverflow.com/questions/41397576/how-many-qubits...