5 ms·

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 kno

by 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.
  - deepnotderp 9y ago
    Okay, first of all, we are no where near Landauer's Limit right now, and will likely never reach that point because we'll run into thermal noise "danger zones" far before then. Second of all, there are plenty of (and probably the primary ) forms of non-quantum reversible logic. In the slightly less exotic category there is also adiabatic computing which can actually be done in standard CMOS in most flavors.
jcranmer 9y ago
> 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. Quantum computers don't have any space advantage, I thought?
- codekilla 9y ago
  Imagine you have a classical bit string 0101, there are 2^4 possible different configurations of this string, and the classical computer will always exist in ONE of them. A quantum computer, with a qubit register 0101, can be put into a superposition state between all 4 qubits, where the state of the qubit register is ALL 2^4 different configurations simultaneously....now scale that up to 50-100-1000 qubits and you get the idea. The quantum computer has a ridiculous advantage in terms of holding state spaces.
  - jcranmer 9y ago
    That argument is patently wrong: it's the quantum bullshit fallacy. The point of the space argument I was making was that, if you need N bits of space to represent the input/output in classical computers, you should still need (I'm not sure if it's the case, but I don't see why it's not) Ω(N) qubits to do the same representation in a quantum computer. The quantum bullshit fallacy is that, since an entangled N-qubit is represented as a 2^N-dimension vector with complex arguments, it's really a computation on 2^N elements in O(1) time. The first sign that this is fallacious is that the basis here isn't of size 2^N but of size 2^N - 1. We're still only capable of reading N bits of information out of an N-qubit register; the fact that classical simulation requires a much larger state space to compute the probability doesn't mean that there's an inherent ability to freely vary through all of those states to represent the entire state space.
    - codekilla 9y ago
      Honestly, I don't understand the point you are making. If you can explain to me how the Deutsch-Joza algorithm works without making reference to the fact that a function evaluation happens on a qubit in superposition(and thus an expanded state-space, as the simplest example), sure. I sincerely don't understand your points about classical simulation, or input/output in classical computers.

by wyager 9y ago

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.
- deepnotderp 9y ago
  Okay, first of all, we are no where near Landauer's Limit right now, and will likely never reach that point because we'll run into thermal noise "danger zones" far before then. Second of all, there are plenty of (and probably the primary ) forms of non-quantum reversible logic. In the slightly less exotic category there is also adiabatic computing which can actually be done in standard CMOS in most flavors.

jcranmer 9y ago

> 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. Quantum computers don't have any space advantage, I thought?

codekilla 9y ago
Imagine you have a classical bit string 0101, there are 2^4 possible different configurations of this string, and the classical computer will always exist in ONE of them. A quantum computer, with a qubit register 0101, can be put into a superposition state between all 4 qubits, where the state of the qubit register is ALL 2^4 different configurations simultaneously....now scale that up to 50-100-1000 qubits and you get the idea. The quantum computer has a ridiculous advantage in terms of holding state spaces.
- jcranmer 9y ago
  That argument is patently wrong: it's the quantum bullshit fallacy. The point of the space argument I was making was that, if you need N bits of space to represent the input/output in classical computers, you should still need (I'm not sure if it's the case, but I don't see why it's not) Ω(N) qubits to do the same representation in a quantum computer. The quantum bullshit fallacy is that, since an entangled N-qubit is represented as a 2^N-dimension vector with complex arguments, it's really a computation on 2^N elements in O(1) time. The first sign that this is fallacious is that the basis here isn't of size 2^N but of size 2^N - 1. We're still only capable of reading N bits of information out of an N-qubit register; the fact that classical simulation requires a much larger state space to compute the probability doesn't mean that there's an inherent ability to freely vary through all of those states to represent the entire state space.
  - codekilla 9y ago
    Honestly, I don't understand the point you are making. If you can explain to me how the Deutsch-Joza algorithm works without making reference to the fact that a function evaluation happens on a qubit in superposition(and thus an expanded state-space, as the simplest example), sure. I sincerely don't understand your points about classical simulation, or input/output in classical computers.