Scott Aaronson still has his $100 000 wager available for an actual refutation of scalable QC. The impetus for the bet was actually from arguing with Gil Kalai in the comments on a blog.
An Argument Against Quantum Computers
11–20 of 67 posts
Re: An Argument Against Quantum Computers
#12Gil Kalai can have his contrarian opinion on quantum computers. But we can have a much simpler argument against quantum computers. That they will remain infeasible for a long enough time for traditional computers to catch up to it.
What I mean by traditional computers catching up with it is that we will see innovations in traditional algorithms that either make quantum computers extremely pricey for a very long time in respect to traditional computers or that we find innovations that will bypass the things that they are good at without violating any of the current theories we have.
Currently, we have an enormous effort invested in our silicon architecture. We seem to be hitting limitations to silicon and they seem to be making a large bet on Quantum computers to eventually allow them to proceed. But, if quantum algorithms take a long time to have useful implementations then we have a local maxima where quantum computers aren't close enough to implement without investing a massive amount of money and that silicon just becomes cheaper and cheaper. When Intel finally reaches the limit of traditional computing that doesn't mean that it won't stop being cheaper.
Intel, IBM, Microsoft, DWave, Google and other companies have small bets on quantum computer engineering strategies that may or may not pay off. Also there seems to be a bunch of researchers publishing more and more papers on the theory of quantum algorithms. There are cross collaborations with academia on quantum computation (and they are basically what the research institutions work with the quantum engineering departments in those companies).
If we find that quantum computers can only speed up computations in the limited set of algorithms then they will probably end up as accelerator cards attached to traditional computers. I expect a order of magnitude of inefficiency to translate problems or do work on quantum computers. Either due to interconnecting or the way that we will figure out to operate them. So we will see these systems relegated to supercomputer workloads.
On the algorithms side, funding the research of quantum algorithms will probably dry up in the way that string theory research has.
Hopefully we will see a large breakthrough that will make quantum computers feasible. From my reading of the research it seems like Topological Quantum Computers have the best chance.
Re: An Argument Against Quantum Computers
#13A note for the savvy: A quantum computer is not a magic bit-string that mysteriously flips to the correct answer. A n-qubit quantum computer is not like 2^n phantom computers running at the same time in some quantum superposition phantom-zone. That's the popular misconception, but it's effectively ignorant techno-woo.
Here's what really happens. If you have a string of n-qubits, when you measure them, they might end up randomly in of of the 2^n possible configurations. However, if you apply some operations to your string of n-qubits using quantum gates, you can usefully bias their wave equations, such that the probabilities of certain configurations are much more likely to appear. (You can't have too many of these operations, however, as that runs the risk of decoherence.) Hopefully, you can do this in such a way, that the biased configurations are the answer to a problem you want to solve.
So then, if you have a quantum computer in such a setup, you can run it a bunch of times, and if everything goes well after enough iterations, you will be able to notice a bias towards certain configurations of the string of bits. If you can do this often enough to get statistical significance, then you can be pretty confident you've found your answers.
https://www.youtube.com/watch?v=IrbJYsep45E
https://www.youtube.com/watch?v=wUwZZaI5u0c
EDIT: I rather like Issac Arthur, but unfortunately, his Quantum Computing episode is an example of exactly this kind of popular misconception. I've called him out on it in comments.
https://www.youtube.com/watch?v=wgCuKTN8sX0
EDIT: I can't find my comment anymore, and I've also discovered that I'm now banned from the public Facebook group! Hmmm.
EDIT: It seems that Issac did correct his video, kind of. He still seems to advocate the 2^n parallelism, but then explains why that can't work around 18 minutes in.
Re: An Argument Against Quantum Computers
#14A note for the savvy: A quantum computer is not a magic bit-string that mysteriously flips to the correct answer. A n-qubit quantum computer is not like 2^n phantom computers running at the same time in some quantum superposition phantom-zone. That's the popular misconception, but it's effectively ignorant techno-woo. Here's what really happens. If you have a string of n-qubits, when you measure them, they might end…
Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer.
The answer: we don’t know. We don’t even know if BQP is actually any bigger than P.
However, we’ve figured out how to do some things quickly on quantum computers that we haven’t ever figured out how to do quickly on classical computers, like certain mathematically useful operations on abelian groups.
One specific example is that you can do Fourier transforms in O(log(n)log(log(n))) rather than O(n log(n)), which is pretty cool. If your vector space is too big to even represent in classical memory, you might still be able to work with it on a quantum computer.
Re: An Argument Against Quantum Computers
#15Gil Kalai can have his contrarian opinion on quantum computers. But we can have a much simpler argument against quantum computers. That they will remain infeasible for a long enough time for traditional computers to catch up to it. What I mean by traditional computers catching up with it is that we will see innovations in traditional algorithms that either make quantum computers extremely pricey for a very long time…
> That they will remain infeasible for a long enough time for traditional computers to catch up to it.
Doesn't work for things we know are exponentially faster on quantum computers. Eventually, with enough (but not an absurd number) of bits, a decent quantum computer can solve problems that wouldn't be possible on a classical computer the size of the universe operating for billions of years.
Improvements in algorithms cuts both ways, too. And for some classes of problems, it's possible to prove (given P != NP, etc) that any classical algorithm is much worse than quantum.
Re: An Argument Against Quantum Computers
#16The flip side of this argument is that if a quantum computer can never show "quantum supremacy" over a classical computer, then perhaps there are much better ways of simulating quantum phenomenon with classical computers than we've yet discovered.
It's important to remember that the motivation for quantum computing came from the realization that it's intractable to simulate quantum phenomenon on classical computers. So any claim that classical computers can do just as good as quantum needs to butt up against this realization at some point (IMHO).
Re: An Argument Against Quantum Computers
#17Gil Kalai can have his contrarian opinion on quantum computers. But we can have a much simpler argument against quantum computers. That they will remain infeasible for a long enough time for traditional computers to catch up to it. What I mean by traditional computers catching up with it is that we will see innovations in traditional algorithms that either make quantum computers extremely pricey for a very long time…
> That they will remain infeasible for a long enough time for traditional computers to catch up to it. Doesn't work for things we know are exponentially faster on quantum computers. Eventually, with enough (but not an absurd number) of bits, a decent quantum computer can solve problems that wouldn't be possible on a classical computer the size of the universe operating for billions of years. Improvements in algorithm…
We don't know of any such thing. There is nothing proven to be NP-hard that can be done in polynomial time with a quantum algorithm. Factorization isn't proven to be NP-hard.
Re: An Argument Against Quantum Computers
#18A note for the savvy: A quantum computer is not a magic bit-string that mysteriously flips to the correct answer. A n-qubit quantum computer is not like 2^n phantom computers running at the same time in some quantum superposition phantom-zone. That's the popular misconception, but it's effectively ignorant techno-woo. Here's what really happens. If you have a string of n-qubits, when you measure them, they might end…
Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer. The answer: we don’t know. We don’t even know if BQP is actually any bigger than P. However, we’ve figured out how to do some things quickly on quantum computers that we haven’t ever figured out how to do quickly on classical computers, like certain mathematically useful operations on abelian groups. One…
> Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer.
Why would there be anything you could compute on a quantum computer that you can't compute on a classical one (provided the classical one is powerful enough or given enough time for certain algorithms quantum computers are more efficient at).
Is there speculation that a quantum computer could be used for hypercomputing?
Re: An Argument Against Quantum Computers
#19Earlier quoted context omitted.
> That they will remain infeasible for a long enough time for traditional computers to catch up to it. Doesn't work for things we know are exponentially faster on quantum computers. Eventually, with enough (but not an absurd number) of bits, a decent quantum computer can solve problems that wouldn't be possible on a classical computer the size of the universe operating for billions of years. Improvements in algorithm…
We don't know of any such thing. There is nothing proven to be NP-hard that can be done in polynomial time with a quantum algorithm. Factorization isn't proven to be NP-hard.
[deleted]
Re: An Argument Against Quantum Computers
#20Earlier quoted context omitted.
Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer. The answer: we don’t know. We don’t even know if BQP is actually any bigger than P. However, we’ve figured out how to do some things quickly on quantum computers that we haven’t ever figured out how to do quickly on classical computers, like certain mathematically useful operations on abelian groups. One…
> Your answer doesn’t actually explain what we can do on a quantum computer that we can’t on a traditional computer. Why would there be anything you could compute on a quantum computer that you can't compute on a classical one (provided the classical one is powerful enough or given enough time for certain algorithms quantum computers are more efficient at). Is there speculation that a quantum computer could be used f…
They meant due to practical limitations on the speed of the computer and/or the amount of time you can afford to wait for the answer.
They were not saying that there may be computations that can be done with finite space and finite time on a quantum computer that cannot be done in any finite space and finite time on a classical computer.
They were talking about computational complexity, not computability.