Hot answers tagged

2

I think your hierarchy collapses, or at least would never get beyond $P$, following the top-line results of Bravyi and Gosset. Bravyi and Gosset's paper gives an algorithm to classically simulate a quantum circuit on $n$ qubits comprising $O(\mathrm{poly\:}n)$ Clifford gates and a constant number of $T$ gates - that is, polynomial in $n$ (although ...


2

Boaz Barak has a lovely essay on various hypothetical worlds with quantum computers. In particular, he calls your world where NP$\subseteq$BQP "popscitopia", and provides: ...in popscitopia quantum computers can be built, and NP $\subseteq$ BQP. This is the world that is described by some popular accounts of quantum computers as being able to “...


Only top voted, non community-wiki answers of a minimum length are eligible