5 ms·

Quantum annealing can be used for optimization of functions. Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us.

by NhanH 9y ago

Quantum annealing can be used for optimization of functions. Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us. But in general, quantum computer is not strictly a superset of improvement over Turing machine. It’s just different. And while it might reduces your database query time, unless you are already working at that abstraction it might probably be invisible changes for you.

TrinaryWorksToo 9y ago
From what I gathered, it's similar to how a CPU and GPU compare: different complexity classes, different problems it's efficient on.
- asddkk 9y ago
  The CPU-GPU analogy is very good for all sorts of reasons. For some things there's no speedup, for some important things there's a huge speedup, for other things there's some significant speedup, but not game-changing. I tend to think of applications where you might want to brute-force search or simulate over some large set as being where quantum computing will be most significant, but I say that very vaguely and timidly. This gives a number of applications and algorithms; I found some of the references in it really interesting to read: http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/
bsder 9y ago
> Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us. I thought it was still an open question as to whether a quantum computer would actually be able to solve this class of problems or not. In addition, quantum computers have a great deal of noise--so quantum error correction seems to be a thing.
- yorwba 9y ago
  Quantum computing is certainly able to solve integer factorization and related problems (like breaking RSA encryption), just not for practical problem sizes yet. You are probably thinking about NP-hard problems, which may or may not be solvable faster than on classical computers.
- jcoffland 9y ago
  Shor’s algorithm can factorize integers on a quantum computer asymptoticly faster than on a classical computer but the algorithm requires at least a 128 qubit quantum computer to factor a 128 bit number and thereby break something like 128 bit RSA encryption. No one yet has, or is publicly admitting to having, a reliable 128 qubit device. In some cases, error correction can be achieved simply by running the algorithm a few times.
  - Beltiras 9y ago
    Error correction is immaterial for the factoring case. You multiply the factors and if you do not get the original number you know you have to run it again.
    - jcoffland 9y ago
      In Schor's algorithm, the quantum computer finds the period p of B mod N were N is the number you are trying to factor and B is a random number less than N. The quantum computer may find p with imperfect accuracy. Running the algorithm repeatedly can improve the accuracy of p. You can also try other numbers close to p. Both are examples of error correcting a quantum algorithm.

by NhanH 9y ago

TrinaryWorksToo 9y ago

From what I gathered, it's similar to how a CPU and GPU compare: different complexity classes, different problems it's efficient on.

asddkk 9y ago
The CPU-GPU analogy is very good for all sorts of reasons. For some things there's no speedup, for some important things there's a huge speedup, for other things there's some significant speedup, but not game-changing. I tend to think of applications where you might want to brute-force search or simulate over some large set as being where quantum computing will be most significant, but I say that very vaguely and timidly. This gives a number of applications and algorithms; I found some of the references in it really interesting to read: http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/

bsder 9y ago

> Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us. I thought it was still an open question as to whether a quantum computer would actually be able to solve this class of problems or not. In addition, quantum computers have a great deal of noise--so quantum error correction seems to be a thing.

yorwba 9y ago
Quantum computing is certainly able to solve integer factorization and related problems (like breaking RSA encryption), just not for practical problem sizes yet. You are probably thinking about NP-hard problems, which may or may not be solvable faster than on classical computers.
jcoffland 9y ago
Shor’s algorithm can factorize integers on a quantum computer asymptoticly faster than on a classical computer but the algorithm requires at least a 128 qubit quantum computer to factor a 128 bit number and thereby break something like 128 bit RSA encryption. No one yet has, or is publicly admitting to having, a reliable 128 qubit device. In some cases, error correction can be achieved simply by running the algorithm a few times.
- Beltiras 9y ago
  Error correction is immaterial for the factoring case. You multiply the factors and if you do not get the original number you know you have to run it again.
  - jcoffland 9y ago
    In Schor's algorithm, the quantum computer finds the period p of B mod N were N is the number you are trying to factor and B is a random number less than N. The quantum computer may find p with imperfect accuracy. Running the algorithm repeatedly can improve the accuracy of p. You can also try other numbers close to p. Both are examples of error correcting a quantum algorithm.