5 ms·

Quantum computing device hints at powerful future

paulnelligan 16y ago
Does anyone have any info as to how the art of programming might change with quantum technology ?
- Devilboy 16y ago
  I'm no expert on the topic but I guess the real nuts and bolts will be abstracted away from the developers. One example is a new LIKE implementation in your SQL database that uses a quantum algorithm for approximate search hits (from a DWave paper iirc)
- sunkencity 16y ago
  One of the major changes is that you cannot inspect the process of computation until it's done, because looking at the cubits collapses them into bits.. So no debuggers/stepping I assume :)
- Estragon 16y ago
  That's getting a bit ahead of where they're at. To the best of my knowledge, the fundamental assumption behind the QC paradigm, the Copenhagen Interpretation, has never really been tested.[1] It is possible that a device like this will constitute the definitive test. The question will be whether such a system can actually perform a calculation across a superposition of states. In the systems I am aware of where such a calculation has been claimed, what actually happened was that a large number of atoms were manipulated simultaneously, and the "superposition" was potentially across the specific states in those individual atoms. My own opinion is that the QC scenario is a reductio ad absurdum for the Copenhagen Interpretation, and that when a true QC calculation is set up, it will fail. This is actually an optimistic view, because the Copenhagen Interpretation is a fundamentally pessimistic assumption: that because we don't know what's behind a certain observed random distribution, we can't. See the following link for more details. (But IAMAP, and I'm not really keeping up with this area.) [1] For more on how the Copenhagen Interpretation evolved, and just how little empirical basis there is for it, see http://books.google.com/books?id=tTN4HuUNXjgC&lpg=PP1&pg=PA328#v=onepage&q&f=false http://books.google.com/books?id=tTN4HuUNXjgC&lpg=PP1&#3...
  - gjm11 16y ago
    Quantum computation does not in any way depend on the Copenhagen interpretation.
    - Estragon 16y ago
      The QC scenario relies on the superposition of states which collapse probabilistically when the system is observed. It is precisely this superposition which enables the massive parallelism the QC scenario promises. This superposition and probabilistic collapse is a central component of the Copenhagen Interpretation, as I understand it.
      - Jach 16y ago
        Superposition isn't part of the Copenhagen interpretation, nor is decoherence. Copenhagen is the addition to standard QM (which QC is based on) and states that the other possibilities we don't observe, also stop existing, making there only be "one true world". But it's not predicted by standard QM which predicts MWI: http://arxiv.org/pdf/0905.1283v1 http://arxiv.org/pdf/0905.1283v1 http://www.hpl.hp.com/breweb/quiprocone/Protected/Lecture_2.htm http://www.hpl.hp.com/breweb/quiprocone/Protected/Lecture_2....
        Estragon 16y ago
        This might be a matter of semantics. When I say "superposition," I mean the view that all we could possibly know about a system is represented in its wave function. This implies an ontological superposition of states until the wave function is collapsed, as is famously embodied in Schroedinger's cat. It is this ontological superposition of states which the QC scenario depends on for massive parallelism: If Schroedinger's cat was the input to your QC function, you would get to run the function with an alive-cat and a dead-cat input at the same time. Of course, you only get to see the output for the state the cat's in when the wave function is collapsed, and a key aspect of search algorithms like Shor's QC factorization scheme is to make sure that all the other states cancel out. (Shor's algorithm basically tries all possible divisors of the target number at the same time, through a superposition scheme.) But if the probabilistic component of the QM wave function instead merely represents our degree of ignorance about the entire system, rather than some such magical superposition, then the QC system is actually only in one of the many states on which the computation is supposed to be run simultaneously, and the promised massive parallelism is just a fantasy. (Yes, I think a hidden-variables explanation is more likely than the Copenhagen interpretation. Yes, I know about the EPR experiment.)
- rayboyd 16y ago
  Some info at Quantiki: http://www.quantiki.org/ http://www.quantiki.org/ http://www.quantiki.org/search/google?query=programming http://www.quantiki.org/search/google?query=programming
- gjm11 16y ago
  Here's one concrete proposal: http://arxiv.org/PS_cache/cs/pdf/0103/0103009v3.pdf http://arxiv.org/PS_cache/cs/pdf/0103/0103009v3.pdf I strongly suspect, though, that the answer is: The quantum magic will be packaged up into small black boxes that perform a modest range of tasks faster than they could be done classically, and programming will continue to consist mostly of writing classical code; it's just that there will be superfast implementations of a few useful things. That might change if the number of qubits we can put into a quantum computer ever gets comparable to the number of ordinary bits we can put into a classical computer. That'll take a while. (My suspicions and guesses are merely suspicions and guesses. I am not a quantum computing expert.)
  - deleted 16y ago
    [deleted]
- Panoramix 16y ago
  Very valid question, just keep in mind that quantum computers are not meant to and will not likely replace CMOS. Quantum computers will probably suck at the tasks where your laptop excels and vice versa.
kondro 16y ago
Yay, probabilistic computing. You have a 99.5% chance that your PayPal transaction has succeeded. A bit like using a NoSQL database.
- wladimir 16y ago
  A bit like any hardware/software combo. Nothing in life is 100% reliable. If you make the probability of failure small enough, and are able to detect and fix errors (very important), it will be good enough.
- sukuriant 16y ago
  It's more useful for problems in the NP-Complete set, where you can write an algorithm that should take a very long time to perform, but takes very little time to check. Take the 3-sat problem, for example. It takes a very long time for conventional algorithms to produce a correct answer; but, given a potential solution, it takes very little time to check for correctness. It's this area that quantum computers could shine in. Get a potential answer from the machine and check its accuracy very quickly. If wrong, try again. [edit: if I misunderstand quantum computers, forgive me. This is just what I thought their allure was]
  - gjm11 16y ago
    Quantum computers are not known to be able to solve NP-complete problems in polynomial time. (Assuming for the sake of argument that we can actually build them.) There are problems -- factorization, as others have already said, is the commonest example -- that (1) are not known to be solvable classically in a reasonable amount of time and (2) are known to be solvable by a quantum computer in a reasonable amount of time. But they aren't NP-complete problems.
    - vmind 16y ago
      Quantum Computers are able to solve problems of complexity BQP in polynomial time. BQP is suspected to cover all problems in P, some in NP (but not NP-complete), and some outside of NP but in PSPACE. (http://en.wikipedia.org/wiki/BQP http://en.wikipedia.org/wiki/BQP)
exit 16y ago
this article doesn't get into what kind of future quantum computing will enable. can anyone describe a program which cannot be written (efficiently) today, which might run on quantum computers eventually?
- wlievens 16y ago
  Shor's algorithm is the classic (pun intended) example: http://en.wikipedia.org/wiki/Shors_algorithm http://en.wikipedia.org/wiki/Shors_algorithm
  - Jach 16y ago
    I think this is a better writeup: http://www.scottaaronson.com/blog/?p=208 http://www.scottaaronson.com/blog/?p=208
- retube 16y ago
  Factorisation is the common example. You'll be able to factor gigantic numbers like an RSA public key pretty much instantaneously, as thanks to a qubit's super-position of states you can operate on all possible states at once. But in general it's all about parallelisation - being able to perform an operation on all states (ie numbers) at once. Due to the probabilistic/uncertain nature of measurements of a quantum system though I believe operations have to be performed a number of times in order to build statistics around the "right" answer.
- trotsky 16y ago
  While the other answer about factorization hit the nail on the head, let me say it again in more direct terms. There is a strong belief among those who pay serious attention to encryption (NSA, etc.) that quantum computing would/will render all traditional encryption (minus things like one time pads) obsolete. An actor with a sufficiently advanced quantum computer would be able to break everyone else's comms.
  - maggit 16y ago
    I understand how quantum computers can break RSA; by factoring numbers quickly. That's exploiting a known "weakness" in RSA. I'm curious as to how quantum computers would break other encryption algorithms like AES or ElGamal. Do you have any details?

Does anyone have any info as to how the art of programming might change with quantum technology ?

Devilboy 16y ago
I'm no expert on the topic but I guess the real nuts and bolts will be abstracted away from the developers. One example is a new LIKE implementation in your SQL database that uses a quantum algorithm for approximate search hits (from a DWave paper iirc)
sunkencity 16y ago
One of the major changes is that you cannot inspect the process of computation until it's done, because looking at the cubits collapses them into bits.. So no debuggers/stepping I assume :)
Estragon 16y ago
That's getting a bit ahead of where they're at. To the best of my knowledge, the fundamental assumption behind the QC paradigm, the Copenhagen Interpretation, has never really been tested.[1] It is possible that a device like this will constitute the definitive test. The question will be whether such a system can actually perform a calculation across a superposition of states. In the systems I am aware of where such a calculation has been claimed, what actually happened was that a large number of atoms were manipulated simultaneously, and the "superposition" was potentially across the specific states in those individual atoms. My own opinion is that the QC scenario is a reductio ad absurdum for the Copenhagen Interpretation, and that when a true QC calculation is set up, it will fail. This is actually an optimistic view, because the Copenhagen Interpretation is a fundamentally pessimistic assumption: that because we don't know what's behind a certain observed random distribution, we can't. See the following link for more details. (But IAMAP, and I'm not really keeping up with this area.) [1] For more on how the Copenhagen Interpretation evolved, and just how little empirical basis there is for it, see http://books.google.com/books?id=tTN4HuUNXjgC&lpg=PP1&pg=PA328#v=onepage&q&f=false http://books.google.com/books?id=tTN4HuUNXjgC&lpg=PP1&#3...
- gjm11 16y ago
  Quantum computation does not in any way depend on the Copenhagen interpretation.
  - Estragon 16y ago
    The QC scenario relies on the superposition of states which collapse probabilistically when the system is observed. It is precisely this superposition which enables the massive parallelism the QC scenario promises. This superposition and probabilistic collapse is a central component of the Copenhagen Interpretation, as I understand it.
    - Jach 16y ago
      Superposition isn't part of the Copenhagen interpretation, nor is decoherence. Copenhagen is the addition to standard QM (which QC is based on) and states that the other possibilities we don't observe, also stop existing, making there only be "one true world". But it's not predicted by standard QM which predicts MWI: http://arxiv.org/pdf/0905.1283v1 http://arxiv.org/pdf/0905.1283v1 http://www.hpl.hp.com/breweb/quiprocone/Protected/Lecture_2.htm http://www.hpl.hp.com/breweb/quiprocone/Protected/Lecture_2....
      - Estragon 16y ago
        This might be a matter of semantics. When I say "superposition," I mean the view that all we could possibly know about a system is represented in its wave function. This implies an ontological superposition of states until the wave function is collapsed, as is famously embodied in Schroedinger's cat. It is this ontological superposition of states which the QC scenario depends on for massive parallelism: If Schroedinger's cat was the input to your QC function, you would get to run the function with an alive-cat and a dead-cat input at the same time. Of course, you only get to see the output for the state the cat's in when the wave function is collapsed, and a key aspect of search algorithms like Shor's QC factorization scheme is to make sure that all the other states cancel out. (Shor's algorithm basically tries all possible divisors of the target number at the same time, through a superposition scheme.) But if the probabilistic component of the QM wave function instead merely represents our degree of ignorance about the entire system, rather than some such magical superposition, then the QC system is actually only in one of the many states on which the computation is supposed to be run simultaneously, and the promised massive parallelism is just a fantasy. (Yes, I think a hidden-variables explanation is more likely than the Copenhagen interpretation. Yes, I know about the EPR experiment.)
rayboyd 16y ago
Some info at Quantiki: http://www.quantiki.org/ http://www.quantiki.org/ http://www.quantiki.org/search/google?query=programming http://www.quantiki.org/search/google?query=programming
gjm11 16y ago
Here's one concrete proposal: http://arxiv.org/PS_cache/cs/pdf/0103/0103009v3.pdf http://arxiv.org/PS_cache/cs/pdf/0103/0103009v3.pdf I strongly suspect, though, that the answer is: The quantum magic will be packaged up into small black boxes that perform a modest range of tasks faster than they could be done classically, and programming will continue to consist mostly of writing classical code; it's just that there will be superfast implementations of a few useful things. That might change if the number of qubits we can put into a quantum computer ever gets comparable to the number of ordinary bits we can put into a classical computer. That'll take a while. (My suspicions and guesses are merely suspicions and guesses. I am not a quantum computing expert.)
- deleted 16y ago
  [deleted]
Panoramix 16y ago
Very valid question, just keep in mind that quantum computers are not meant to and will not likely replace CMOS. Quantum computers will probably suck at the tasks where your laptop excels and vice versa.

Yay, probabilistic computing. You have a 99.5% chance that your PayPal transaction has succeeded. A bit like using a NoSQL database.

wladimir 16y ago
A bit like any hardware/software combo. Nothing in life is 100% reliable. If you make the probability of failure small enough, and are able to detect and fix errors (very important), it will be good enough.
sukuriant 16y ago
It's more useful for problems in the NP-Complete set, where you can write an algorithm that should take a very long time to perform, but takes very little time to check. Take the 3-sat problem, for example. It takes a very long time for conventional algorithms to produce a correct answer; but, given a potential solution, it takes very little time to check for correctness. It's this area that quantum computers could shine in. Get a potential answer from the machine and check its accuracy very quickly. If wrong, try again. [edit: if I misunderstand quantum computers, forgive me. This is just what I thought their allure was]
- gjm11 16y ago
  Quantum computers are not known to be able to solve NP-complete problems in polynomial time. (Assuming for the sake of argument that we can actually build them.) There are problems -- factorization, as others have already said, is the commonest example -- that (1) are not known to be solvable classically in a reasonable amount of time and (2) are known to be solvable by a quantum computer in a reasonable amount of time. But they aren't NP-complete problems.
  - vmind 16y ago
    Quantum Computers are able to solve problems of complexity BQP in polynomial time. BQP is suspected to cover all problems in P, some in NP (but not NP-complete), and some outside of NP but in PSPACE. (http://en.wikipedia.org/wiki/BQP http://en.wikipedia.org/wiki/BQP)

exit 16y ago

this article doesn't get into what kind of future quantum computing will enable. can anyone describe a program which cannot be written (efficiently) today, which might run on quantum computers eventually?

wlievens 16y ago
Shor's algorithm is the classic (pun intended) example: http://en.wikipedia.org/wiki/Shors_algorithm http://en.wikipedia.org/wiki/Shors_algorithm
- Jach 16y ago
  I think this is a better writeup: http://www.scottaaronson.com/blog/?p=208 http://www.scottaaronson.com/blog/?p=208
retube 16y ago
Factorisation is the common example. You'll be able to factor gigantic numbers like an RSA public key pretty much instantaneously, as thanks to a qubit's super-position of states you can operate on all possible states at once. But in general it's all about parallelisation - being able to perform an operation on all states (ie numbers) at once. Due to the probabilistic/uncertain nature of measurements of a quantum system though I believe operations have to be performed a number of times in order to build statistics around the "right" answer.
trotsky 16y ago
While the other answer about factorization hit the nail on the head, let me say it again in more direct terms. There is a strong belief among those who pay serious attention to encryption (NSA, etc.) that quantum computing would/will render all traditional encryption (minus things like one time pads) obsolete. An actor with a sufficiently advanced quantum computer would be able to break everyone else's comms.
- maggit 16y ago
  I understand how quantum computers can break RSA; by factoring numbers quickly. That's exploiting a known "weakness" in RSA. I'm curious as to how quantum computers would break other encryption algorithms like AES or ElGamal. Do you have any details?