5 ms·

That should not matter. Quantum computers promise to do things that classical computers will never be able to do. A 'proper' QC with on the order of a few thous

That should not matter. Quantum computers promise to do things that classical computers will never be able to do. A 'proper' QC with on the order of a few thousand qubits can perform calculations that even a known-universe-sized classical computer will find intractable. Optimisation quickly becomes irrelevant when you scale these problems just a little bit more.

dvanduzer 11y ago
I do not believe there are any problems known to be solvable by QC, and unsolvable by classical computers. edit: I was trying to be polite, but Scott Aaronson has spilled quite a lot of blog ink denouncing remarks like the parent post as utter nonsense.
- deleted 11y ago
  [deleted]
- letstryagain 11y ago
  You might have misunderstood my comment (or Scott's writings?) Classical computers are limited by what they can compute because the universe has limits. A 10,000 qubit quantum computer can factor fairly large numbers. 10,000 qubits is pretty small, one day hopefully it will fit inside a small room. To factor those same numbers using a classical computer you'd have to make a computer the size of the entire known universe and run that computer until the heat death of the universe. Obviously this is not possible, even in principal. Theoretically any QC computation can be simulated by a classical computer but in our limited universe you quickly run into the wall where the classical computer just becomes too big (bigger than the entire universe) and too slow (slower than the life of the universe).
  - dvanduzer 11y ago
    I definitely reread your comment several times and kept stewing on the word "intractable" since I'd seen it used somewhere else to talk about problems in NP-Complete. I assumed if I was misinterpreting what you were saying, it would hinge on that word. Aside from factoring, what kinds of things do we think will meaningfully change if we get general QC? Cryptographers are already preparing for the post-quantum world. Who else needs to be preparing? Everything I think I understand about QC suggests that a practical breakthrough will not cause any changes in society, other than the abandonment of RSA. Am I missing something?
    - phaas 11y ago
      Imagine simulating a human brain. I'm not sure how massive a computer would need to be today to simulate the neurons, but an efficient implementation can be made to be the size of.. Well.. A brain. I could see this causing massive changes in society. An artificial intelligent simulation of a super-smart human, that can be tuned toward a specific problem area and made much more focused and efficient than a purely biological brain could work...
      - dvanduzer 11y ago
        Is there a specific reason a quantum computer would be better at simulating a human brain than a classical computer?
        drdeca 11y ago
        Well, to simulate the chemistry in the brain, would, I think, involve simulating some quantum mechanical things, which a quantum computer might be better equipped to simulate? Is the argument that I've heard. I don't know how that works when the qubits are being used to deal with other sorts of variables than bits though?
    - nl 11y ago
      It might provide a rapid, general approach to non-convex optimization for neural nets. And that changes everything, probably more than anything since (the iPhone|the internet|computers|penicillin|the industrial revolution|fire) depending on how optimistic you are. It'll change things a lot, anyway. See http://research.microsoft.com/en-us/events/qml/ http://research.microsoft.com/en-us/events/qml/
    - lololomg 11y ago
      Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N^1/2) time and using O(log N) storage space
    - zodiac 11y ago
      Since you seem to already familiar with integer factoring, isn't factoring large integers something that "solvable by QC, and unsolvable by classical computers"?
  - lmm 11y ago
    Not proven. The best currently known algorithms for factoring on a classical computer take asymptotically longer than the best known quantum ones. That doesn't necessarily mean it's a fundamental limit of the universe. More generally we have no proof that BQP =/= P.
- nl 11y ago
  I do not believe there are any problems known to be solvable by QC, and unsolvable by classical computers. The space between unsolvable by classical computers and solvable practically by classical computers is... significant.
- deleted 11y ago
  [deleted]
johncolanduoni 11y ago
> Quantum computers promise to do things that classical computers will never be able to do. A 'proper' QC with on the order of a few thousand qubits can perform calculations that even a known-universe-sized classical computer will find intractable. Your first statement is correct, but Shor's algorithm (the one I suspect you are referring to when you talk about a universe sized computer) is not an example of one. We do not know that there is not a classical factoring algorithm that is as good or better than Shor's, and we have no quantum algorithms as of yet that can give an exponential speedup over any possible (but possible yet unknown) classical algorithm (which is needed for the universe sized computer thing). We have some that give more modest speed ups that are known to be unbeatable by classical algorithms; Grover's search algorithm is such an example, but it is only quadratic. This means you have a quantum computer of size N, you only need a classical computer of size N^2 to match it. > Optimisation quickly becomes irrelevant when you scale these problems just a little bit more. The problem with quantum computers isn't optimization of algorithms, but it's still optimization of strategies for dealing with errors (which sometimes look a lot like algorithms). Building reasonably accurate logic gates was figured out with a lot less effort when we started even thinking of building such things, and their reliability didn't fall off with increasing size very quickly. Our technology for quantum computers, on the other hand, all have crippling flaws as of yet. The most common one (superconducting qubits and ion trap based designs both suffer from this) is that when we try to make the computer bigger, it needs an unscalable amount of error correction an eventually stops working altogether. Some other approaches (linear optical quantum computer for example) can scale up without getting worse per se, but the gates we can build are already so unreliable that we still need too much error correction to scale. So optimizing our error correction strategies is one possible avenue that is being explored.

dvanduzer 11y ago

I do not believe there are any problems known to be solvable by QC, and unsolvable by classical computers. edit: I was trying to be polite, but Scott Aaronson has spilled quite a lot of blog ink denouncing remarks like the parent post as utter nonsense.

deleted 11y ago
[deleted]
letstryagain 11y ago
You might have misunderstood my comment (or Scott's writings?) Classical computers are limited by what they can compute because the universe has limits. A 10,000 qubit quantum computer can factor fairly large numbers. 10,000 qubits is pretty small, one day hopefully it will fit inside a small room. To factor those same numbers using a classical computer you'd have to make a computer the size of the entire known universe and run that computer until the heat death of the universe. Obviously this is not possible, even in principal. Theoretically any QC computation can be simulated by a classical computer but in our limited universe you quickly run into the wall where the classical computer just becomes too big (bigger than the entire universe) and too slow (slower than the life of the universe).
- dvanduzer 11y ago
  I definitely reread your comment several times and kept stewing on the word "intractable" since I'd seen it used somewhere else to talk about problems in NP-Complete. I assumed if I was misinterpreting what you were saying, it would hinge on that word. Aside from factoring, what kinds of things do we think will meaningfully change if we get general QC? Cryptographers are already preparing for the post-quantum world. Who else needs to be preparing? Everything I think I understand about QC suggests that a practical breakthrough will not cause any changes in society, other than the abandonment of RSA. Am I missing something?
  - phaas 11y ago
    Imagine simulating a human brain. I'm not sure how massive a computer would need to be today to simulate the neurons, but an efficient implementation can be made to be the size of.. Well.. A brain. I could see this causing massive changes in society. An artificial intelligent simulation of a super-smart human, that can be tuned toward a specific problem area and made much more focused and efficient than a purely biological brain could work...
    - dvanduzer 11y ago
      Is there a specific reason a quantum computer would be better at simulating a human brain than a classical computer?
      - drdeca 11y ago
        Well, to simulate the chemistry in the brain, would, I think, involve simulating some quantum mechanical things, which a quantum computer might be better equipped to simulate? Is the argument that I've heard. I don't know how that works when the qubits are being used to deal with other sorts of variables than bits though?
  - nl 11y ago
    It might provide a rapid, general approach to non-convex optimization for neural nets. And that changes everything, probably more than anything since (the iPhone|the internet|computers|penicillin|the industrial revolution|fire) depending on how optimistic you are. It'll change things a lot, anyway. See http://research.microsoft.com/en-us/events/qml/ http://research.microsoft.com/en-us/events/qml/
  - lololomg 11y ago
    Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N^1/2) time and using O(log N) storage space
  - zodiac 11y ago
    Since you seem to already familiar with integer factoring, isn't factoring large integers something that "solvable by QC, and unsolvable by classical computers"?
- lmm 11y ago
  Not proven. The best currently known algorithms for factoring on a classical computer take asymptotically longer than the best known quantum ones. That doesn't necessarily mean it's a fundamental limit of the universe. More generally we have no proof that BQP =/= P.
nl 11y ago
I do not believe there are any problems known to be solvable by QC, and unsolvable by classical computers. The space between unsolvable by classical computers and solvable practically by classical computers is... significant.
deleted 11y ago
[deleted]

johncolanduoni 11y ago

> Quantum computers promise to do things that classical computers will never be able to do. A 'proper' QC with on the order of a few thousand qubits can perform calculations that even a known-universe-sized classical computer will find intractable. Your first statement is correct, but Shor's algorithm (the one I suspect you are referring to when you talk about a universe sized computer) is not an example of one. We do not know that there is not a classical factoring algorithm that is as good or better than Shor's, and we have no quantum algorithms as of yet that can give an exponential speedup over any possible (but possible yet unknown) classical algorithm (which is needed for the universe sized computer thing). We have some that give more modest speed ups that are known to be unbeatable by classical algorithms; Grover's search algorithm is such an example, but it is only quadratic. This means you have a quantum computer of size N, you only need a classical computer of size N^2 to match it. > Optimisation quickly becomes irrelevant when you scale these problems just a little bit more. The problem with quantum computers isn't optimization of algorithms, but it's still optimization of strategies for dealing with errors (which sometimes look a lot like algorithms). Building reasonably accurate logic gates was figured out with a lot less effort when we started even thinking of building such things, and their reliability didn't fall off with increasing size very quickly. Our technology for quantum computers, on the other hand, all have crippling flaws as of yet. The most common one (superconducting qubits and ion trap based designs both suffer from this) is that when we try to make the computer bigger, it needs an unscalable amount of error correction an eventually stops working altogether. Some other approaches (linear optical quantum computer for example) can scale up without getting worse per se, but the gates we can build are already so unreliable that we still need too much error correction to scale. So optimizing our error correction strategies is one possible avenue that is being explored.