4 ms·

This disentangling continues to entangle the most salient aspect of this -- the definition of a qubit itself. Claiming a device with hundreds of qubits exists

This disentangling continues to entangle the most salient aspect of this -- the definition of a qubit itself. Claiming a device with hundreds of qubits exists is a stretch because we have modified the target. Current generation of QC's are targeting NISQ (Noisy Intermediate-Scale Quantum) architectures. They are not general-purpose computers; they are instead attempting to address the central problem of quantum computing and "quantum supremacy" -- namely, whether there exist computational problems for which classical computers demonstrate exponential growth in time complexity, but quantum computers show sub-exponential growth. It remains unclear whether even this is possible, much less whether it is possible to build error-correction systems that will allow for the creation of a general-purpose programmable quantum computer. The oft-cited examples of quantum computers factoring small numbers with Shor's algorithm demonstrate that the principles are correct, but do not actually factor the numbers; instead they basically assign probabilities; effectively (not literally) saying that there is a non-zero probability that 11 is a factor of 21. At this point it does not appear that any of the solutions (photonics, NMR) for these toy problems can scale at all -- I would love to see more pre-registration for attempts to factor larger numbers to get a better idea of why they are failing, we have precious few examples of the breakdown. When we compare where we are compared to digital computers, we are still in the pre-vacuum-tube era; maybe even the pre-differential era if we look at mechanical computers. Predicting timelines for this is a fools errand at this point -- it could be tomorrow with a crazy breakthrough; it could be 100 years; it could (and this is my view) not even be possible.

Georgelemental 4y ago
> whether there exist computational problems for which classical computers demonstrate exponential growth in time complexity, but quantum computers show sub-exponential growth. > It remains unclear whether even this is possible "Quantum supremacy" by this definition has already been experimentally demonstrated, and it's not a high bar to meet. Like saying that if I let go of a feather in a windy area and measure how long it takes to fall to the ground with a stopwatch, that is "feather drop timing supremacy" because I have solved the problem of determining how long the feather takes to fall easily, while a classical computer would need to do complex physics simulations to get the same result. What is hard and interesting is to find a useful computational problem for which quantum computers are much better than classical ones.
- krastanov 4y ago
  I think you are having a relatively common misunderstanding. Indeed, just having some analog process run itself is a boring example of "supremacy". https://www.smbc-comics.com/comic/2013-07-19 https://www.smbc-comics.com/comic/2013-07-19 A "useful" computation is indeed the important final proof of supremacy. But intermediary results of "programmable" but useless computation is a pretty amazing achievement on its own, and it is not just "an analog process running itself". The distinction is described quite well here and it really matters to computational complexity theory https://scottaaronson.blog/?p=5460 https://scottaaronson.blog/?p=5460
- andrewla 4y ago
  I agree that this is the problem that we are effectively trying to solve. The problem with the feather analogy is that there's an initial condition problem that is basically unresolvable. Replicating them in such a way that the result of physically dropping the feather is identical between runs of this computer is far beyond intractable, much less representing them in such a way that you can compare the output of a classical computer in this regard. The NMR results from factoring 15 [1] are incredibly fascinating. Here the quantum computer is just a molecule, and using NMR we can get a precise view of the initial conditions and the time evolution. We're just asking the molecule to molecule itself and measuring the outcome. This unfortunately does not appear to scale, so it's impossible to say if we are demonstrating quantum supremacy, but the experimental design blows my mind. [1] https://cryptome.org/shor-nature.pdf https://cryptome.org/shor-nature.pdf
qualudeheart 4y ago
AGI incorporating a Scott Aaronson brain emulation will solve quantum computing within 20 years.
panda-giddiness 4y ago
> The oft-cited examples of quantum computers factoring small numbers with Shor's algorithm demonstrate that the principles are correct, but do not actually factor the numbers; instead they basically assign probabilities; effectively (not literally) saying that there is a non-zero probability that 11 is a factor of 21. I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. It's a feature of the calculation, not a bug. At any rate, it's not really a problem if the factorization is sometimes incorrect. If you doubt the result, just multiply the numbers together on a classical computer. If the numbers don't match, repeat the process. Even if your quantum computer only yields the correct result 50% of the time, you'd still be better off using a quantum computer than brute forcing for large enough numbers. (Of course, and I suppose this is your point, quantum computers with a sufficient numbers of qubits to prove supremacy in factorization do not yet exist.)
- ithkuil 4y ago
  > I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. The substrate of physical digital computers is analog and probabilistic too. We just put a threshold above which a logic signal is considered 1 and we give enough time for a state transition to be considered done. We also throw in the mix a large number of electrons so that it's very likely that the aggregate effect produces a definite answer. This is not all that unlike what we have to do with quantum computers. You just have to find a suitable threshold after which your desired answer is sufficiently likely to come out.
  - tromp 4y ago
    But even under these conditions no team has been able to demonstrate a working implementation of Shor's algorithm that can factor arbitrary 6-bit prime products. Quoting from [1]: > In 2019 an attempt was made to factor the number {\displaystyle 35}{\displaystyle 35} using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.[13] Though larger numbers have been factored by quantum computers using other algorithms,[14] these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms. [1] https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also

Georgelemental 4y ago

> whether there exist computational problems for which classical computers demonstrate exponential growth in time complexity, but quantum computers show sub-exponential growth. > It remains unclear whether even this is possible "Quantum supremacy" by this definition has already been experimentally demonstrated, and it's not a high bar to meet. Like saying that if I let go of a feather in a windy area and measure how long it takes to fall to the ground with a stopwatch, that is "feather drop timing supremacy" because I have solved the problem of determining how long the feather takes to fall easily, while a classical computer would need to do complex physics simulations to get the same result. What is hard and interesting is to find a useful computational problem for which quantum computers are much better than classical ones.

krastanov 4y ago
I think you are having a relatively common misunderstanding. Indeed, just having some analog process run itself is a boring example of "supremacy". https://www.smbc-comics.com/comic/2013-07-19 https://www.smbc-comics.com/comic/2013-07-19 A "useful" computation is indeed the important final proof of supremacy. But intermediary results of "programmable" but useless computation is a pretty amazing achievement on its own, and it is not just "an analog process running itself". The distinction is described quite well here and it really matters to computational complexity theory https://scottaaronson.blog/?p=5460 https://scottaaronson.blog/?p=5460
andrewla 4y ago
I agree that this is the problem that we are effectively trying to solve. The problem with the feather analogy is that there's an initial condition problem that is basically unresolvable. Replicating them in such a way that the result of physically dropping the feather is identical between runs of this computer is far beyond intractable, much less representing them in such a way that you can compare the output of a classical computer in this regard. The NMR results from factoring 15 [1] are incredibly fascinating. Here the quantum computer is just a molecule, and using NMR we can get a precise view of the initial conditions and the time evolution. We're just asking the molecule to molecule itself and measuring the outcome. This unfortunately does not appear to scale, so it's impossible to say if we are demonstrating quantum supremacy, but the experimental design blows my mind. [1] https://cryptome.org/shor-nature.pdf https://cryptome.org/shor-nature.pdf

qualudeheart 4y ago

AGI incorporating a Scott Aaronson brain emulation will solve quantum computing within 20 years.

panda-giddiness 4y ago

> The oft-cited examples of quantum computers factoring small numbers with Shor's algorithm demonstrate that the principles are correct, but do not actually factor the numbers; instead they basically assign probabilities; effectively (not literally) saying that there is a non-zero probability that 11 is a factor of 21. I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. It's a feature of the calculation, not a bug. At any rate, it's not really a problem if the factorization is sometimes incorrect. If you doubt the result, just multiply the numbers together on a classical computer. If the numbers don't match, repeat the process. Even if your quantum computer only yields the correct result 50% of the time, you'd still be better off using a quantum computer than brute forcing for large enough numbers. (Of course, and I suppose this is your point, quantum computers with a sufficient numbers of qubits to prove supremacy in factorization do not yet exist.)

ithkuil 4y ago
> I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. The substrate of physical digital computers is analog and probabilistic too. We just put a threshold above which a logic signal is considered 1 and we give enough time for a state transition to be considered done. We also throw in the mix a large number of electrons so that it's very likely that the aggregate effect produces a definite answer. This is not all that unlike what we have to do with quantum computers. You just have to find a suitable threshold after which your desired answer is sufficiently likely to come out.
- tromp 4y ago
  But even under these conditions no team has been able to demonstrate a working implementation of Shor's algorithm that can factor arbitrary 6-bit prime products. Quoting from [1]: > In 2019 an attempt was made to factor the number {\displaystyle 35}{\displaystyle 35} using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.[13] Though larger numbers have been factored by quantum computers using other algorithms,[14] these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms. [1] https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also