4 ms·
> 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 specifi
by 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 agoThat'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 agoIt'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 agoI think I was using the argument that Quantum computation is Turing complete, which is why they can only compute what classical computers can.