6 ms·

A 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 pha

A 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=IrbJYsep45E https://www.youtube.com/watch?v=wUwZZaI5u0c 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 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.

wyager 9y ago
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.
- goatlover 9y ago
  > 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?
  - drdeca 9y ago
    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.
  - pdpi 9y ago
    "Solve problem x in polynomial time". AIUI, BQP is thought to be a superset of P and to include some stuff from outside NP. Specific problems that are part of BQP but that we expect are not in P is the interesting response here. An example of such a problem is integer factorisation (see: Shor's Algorithm), which means that RSA and similar schemes might become vulnerable once suitably large quantum computers are available.
  - btilly 9y ago
    The fundamental observation behind quantum computing is that an irreversible bit flip releases a minimum amount of heat, while a reversible one releases none. See https://en.wikipedia.org/wiki/Landauer%27s_principle https://en.wikipedia.org/wiki/Landauer%27s_principle for the theoretical limits to classical computing based on this. But there are, to the best of our current knowledge, no theoretical limits to how much computation can happen reversibly. However the requirement that the operations all be completely reversible is very strict. For example logic operations like "and" and "or" are off the table. BUT when physicists like Richard Feynman looked into, what DOES happen is that your computation can progress in a quantum superposition of states. And there is no upper limit to how many states are in the quantum superposition. So in essence what you get should be a very hard to program but unbelievably parallel computer with no upper limit on computational speed. The first demonstration that this could be useful for problems that people care about was https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm for factoring integers. The fact that we do not know how to factor integers quickly is an underpinning of public key cryptography algorithms like RSA. However we know how to solve that if we had a quantum computer. And this is just engineering, right? Everyone recognizes that it is a very hard engineering problem. But the minority opinion laid out in this article is that the engineering problem is not just a practical problem, but the physics makes it intrinsically hard in a way that cannot ever be worked around. No matter how well a quantum computer works in theory, it is physically impossible for us to build and operate one that does better than the classical computers that we already know how to build.
ohazi 9y ago
https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3
codekilla 9y ago
I'm not sure it's useful anymore to point to quantum computers and say: 'Hey! You're not getting all your function evaluations back....so they're weak'. I feel this leads to misconceptions about quantum computing as well. You have to remember, the tensor product of N qubits is an exponentially expanding space...and the functions DO get evaluated in that space, the trick being you have to extract a JOINT property of the function evaluations, rather than the result of each one individually. Let's be clear, even with this caveat, the potential of quantum computing is enormous. I've personally read Kalai's papers and in my opinion, his objections boil down to 'it's just too good to be true'....but hey...we'll see :)
- stcredzero 9y ago
  the trick being you have to extract a JOINT property of the function evaluations, rather than the result of each one individually. This is an even more succinct way of saying it. This is the key point that people need to know, which separates someone from understanding the real potential of quantum computers from "quantum woo." Let's be clear, even with this caveat, the potential of quantum computing is enormous. No question. But to think clearly about it, one has to know this caveat. Likewise, to understand the potential of conventional computers, one needs to actually be able to think about computation within its realistic limits, not treat them as magic boxes.
fossuser 9y ago
There was a nice morning paper last week that gave some good examples of this with interesting links. https://blog.acolyer.org/2018/02/02/polynomial-time-algorithms-for-prime-factorization-and-discrete-logarithms-on-a-quantum-computer/ https://blog.acolyer.org/2018/02/02/polynomial-time-algorith...

wyager 9y ago

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.

goatlover 9y ago
> 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?
- drdeca 9y ago
  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.
- pdpi 9y ago
  "Solve problem x in polynomial time". AIUI, BQP is thought to be a superset of P and to include some stuff from outside NP. Specific problems that are part of BQP but that we expect are not in P is the interesting response here. An example of such a problem is integer factorisation (see: Shor's Algorithm), which means that RSA and similar schemes might become vulnerable once suitably large quantum computers are available.
- btilly 9y ago
  The fundamental observation behind quantum computing is that an irreversible bit flip releases a minimum amount of heat, while a reversible one releases none. See https://en.wikipedia.org/wiki/Landauer%27s_principle https://en.wikipedia.org/wiki/Landauer%27s_principle for the theoretical limits to classical computing based on this. But there are, to the best of our current knowledge, no theoretical limits to how much computation can happen reversibly. However the requirement that the operations all be completely reversible is very strict. For example logic operations like "and" and "or" are off the table. BUT when physicists like Richard Feynman looked into, what DOES happen is that your computation can progress in a quantum superposition of states. And there is no upper limit to how many states are in the quantum superposition. So in essence what you get should be a very hard to program but unbelievably parallel computer with no upper limit on computational speed. The first demonstration that this could be useful for problems that people care about was https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm for factoring integers. The fact that we do not know how to factor integers quickly is an underpinning of public key cryptography algorithms like RSA. However we know how to solve that if we had a quantum computer. And this is just engineering, right? Everyone recognizes that it is a very hard engineering problem. But the minority opinion laid out in this article is that the engineering problem is not just a practical problem, but the physics makes it intrinsically hard in a way that cannot ever be worked around. No matter how well a quantum computer works in theory, it is physically impossible for us to build and operate one that does better than the classical computers that we already know how to build.

ohazi 9y ago

https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3

codekilla 9y ago

I'm not sure it's useful anymore to point to quantum computers and say: 'Hey! You're not getting all your function evaluations back....so they're weak'. I feel this leads to misconceptions about quantum computing as well. You have to remember, the tensor product of N qubits is an exponentially expanding space...and the functions DO get evaluated in that space, the trick being you have to extract a JOINT property of the function evaluations, rather than the result of each one individually. Let's be clear, even with this caveat, the potential of quantum computing is enormous. I've personally read Kalai's papers and in my opinion, his objections boil down to 'it's just too good to be true'....but hey...we'll see :)

stcredzero 9y ago
the trick being you have to extract a JOINT property of the function evaluations, rather than the result of each one individually. This is an even more succinct way of saying it. This is the key point that people need to know, which separates someone from understanding the real potential of quantum computers from "quantum woo." Let's be clear, even with this caveat, the potential of quantum computing is enormous. No question. But to think clearly about it, one has to know this caveat. Likewise, to understand the potential of conventional computers, one needs to actually be able to think about computation within its realistic limits, not treat them as magic boxes.

fossuser 9y ago

There was a nice morning paper last week that gave some good examples of this with interesting links. https://blog.acolyer.org/2018/02/02/polynomial-time-algorithms-for-prime-factorization-and-discrete-logarithms-on-a-quantum-computer/ https://blog.acolyer.org/2018/02/02/polynomial-time-algorith...