5 ms·

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

by kondro 16y ago

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)
    - sukuriant 16y ago
      Ah! That clears things up quite a bit. I'm surprised they're not able to work at the NP-C set. Is it because the probability of a right answer is so small?

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

by 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)
  - sukuriant 16y ago
    Ah! That clears things up quite a bit. I'm surprised they're not able to work at the NP-C set. Is it because the probability of a right answer is so small?