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