3 ms·

It's not a question of possibility, but rather speedup. The three "flagship" algos are for unstructured search[1] (not clear if really useful), factoring[2] (us

by ivan_ah 10y ago

It's not a question of possibility, but rather speedup. The three "flagship" algos are for unstructured search[1] (not clear if really useful), factoring[2] (useful to crack public key crypto), and more recently there is a result that shows that random instances of general linear problems can be solved faster[3]. Another class of algorithms use quantum computers as simulators (e.g. for chemical simulations). You can also encode certain optimization problems as "constraints" in a quantum system and hope that quantum dynamics will find good solutions to the optim. problem faster. [1] https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm [3] https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_s...

mathgenius 10y ago
> It's not a question of possibility Yeah it really is. Quantum states just do not even fit in classical memory. Like, exponentially so. The parent was specifically asking about "possibility" not speedup.
- Ar-Curunir 10y ago
  That's just a matter of speed no? It's not an impossibility result like Turing's; classical computers can compute whatever quantum computers can. That's the Church-Turing hypothesis.
  - moefh 10y ago
    It's just a matter of speed, but there's no need to invoke the Church-Turing hypothesis. One of the first things proven[1] about BQP is that it's contained in P^#P, which is contained in PSPACE. That means a Turing machine can simulate any quantum computer with only polynomial space (but possibly very slowly). [1] http://epubs.siam.org/doi/abs/10.1137/S0097539796300921 http://epubs.siam.org/doi/abs/10.1137/S0097539796300921
    - Ar-Curunir 10y ago
      I think I was using the argument that Quantum computation is Turing complete, which is why they can only compute what classical computers can.
nightcracker 10y ago
Grover's algorithm is also (theoretically) used for breaking symmetric crypto, by halving the exponent needed in brute force search. It's the main reason to move from 128-bit ciphers to 256 bit.

by ivan_ah 10y ago

mathgenius 10y ago

> It's not a question of possibility Yeah it really is. Quantum states just do not even fit in classical memory. Like, exponentially so. The parent was specifically asking about "possibility" not speedup.

Ar-Curunir 10y ago
That's just a matter of speed no? It's not an impossibility result like Turing's; classical computers can compute whatever quantum computers can. That's the Church-Turing hypothesis.
- moefh 10y ago
  It's just a matter of speed, but there's no need to invoke the Church-Turing hypothesis. One of the first things proven[1] about BQP is that it's contained in P^#P, which is contained in PSPACE. That means a Turing machine can simulate any quantum computer with only polynomial space (but possibly very slowly). [1] http://epubs.siam.org/doi/abs/10.1137/S0097539796300921 http://epubs.siam.org/doi/abs/10.1137/S0097539796300921
  - Ar-Curunir 10y ago
    I think I was using the argument that Quantum computation is Turing complete, which is why they can only compute what classical computers can.

nightcracker 10y ago

Grover's algorithm is also (theoretically) used for breaking symmetric crypto, by halving the exponent needed in brute force search. It's the main reason to move from 128-bit ciphers to 256 bit.