Hot answers tagged

2 votes

How powerful are boundedly many $T$-gates?

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 ...
user avatar
  • 7,042
2 votes

Consequences of SAT ∈ BQP

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 ...
user avatar
  • 7,042

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