BQP

Quantum computers have a reputation for "trying every answer at once." That story sells headlines, but it is wrong. The honest question is sharper: exactly which problems can a quantum computer solve efficiently? The class that answers this is called BQP — Bounded-error Quantum Polynomial time.

A problem sits in BQP if a quantum computer can solve it in a polynomial number of steps while getting the right answer with probability at least, say, 2/3. Run it a few times, take the majority vote, and the error shrinks to nothing.

The surprise is what BQP contains — and what it almost certainly does not. It holds factoring, a problem we believe is too hard for ordinary computers. But it is not believed to contain all of NP. Quantum computers are not magic shortcut machines; they are sharp tools for a special shape of problem.

Not all problems get the same boost from a quantum computer. Some get an exponential speedup (the famous wins), some get only a modest square-root speedup, and many get essentially none. Click each problem below to place it on the map and see what kind of speedup it gets — and why.

<p class="hint">{{hint}}</p>
<div class="problems" id="problems"></div>
<div class="controls">
  <label>{{size_label}} <span id="nval">20</span></label>
  <input id="n" type="range" min="10" max="50" value="20">
</div>
<div class="map">
  <div class="col" data-band="exp"><h4>{{col_exp}}</h4><div class="slot" id="slot-exp"></div></div>
  <div class="col" data-band="quad"><h4>{{col_quad}}</h4><div class="slot" id="slot-quad"></div></div>
  <div class="col" data-band="none"><h4>{{col_none}}</h4><div class="slot" id="slot-none"></div></div>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns"><button id="reset" type="button" class="ghost">{{btn_reset}}</button></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.problems { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0 .8rem; }
.chip { font: 600 13px system-ui, sans-serif; padding: .45rem .8rem; border: 1px solid #1d3557;
        background: #fff; color: #1d3557; border-radius: 20px; cursor: pointer; transition: all .12s; }
.chip:hover { background: #eef2f7; }
.chip.placed { opacity: .35; cursor: default; pointer-events: none; }
.controls { margin: .3rem 0 .8rem; font-size: .9rem; }
.controls input { width: 100%; }
.map { display: grid; grid-template-columns: repeat(3, 1fr); gap: .5rem; }
.col { border: 1px solid #cdd9e3; border-radius: 10px; padding: .5rem; min-height: 120px; background: #f7fafc; }
.col h4 { margin: 0 0 .5rem; font-size: .8rem; text-align: center; color: #1d3557; }
.col[data-band="exp"] { border-color: #0a7d33; }
.col[data-band="quad"] { border-color: #d9920a; }
.col[data-band="none"] { border-color: #c92f3c; }
.item { background: #fff; border: 1px solid #cdd9e3; border-radius: 8px; padding: .4rem .5rem;
        margin-bottom: .4rem; font-size: .82rem; }
.item b { display: block; }
.item small { color: #555; }
.status { font-size: .95rem; font-weight: 600; margin: .7rem 0 .4rem; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }

// Code not found

Notice the pattern. The big exponential wins, like factoring, exploit deep hidden structure (periodicity). Unstructured search gets only a quadratic nudge from Grover's algorithm. And NP-complete problems? No known quantum algorithm cracks them — most experts believe BQP does not contain NP. The quantum advantage is real, but it is selective.

So where does BQP actually sit on the map of complexity classes?

• It contains P. Anything a classical computer does efficiently, a quantum computer can do too. So BQP ⊇ P — quantum never loses.
• It contains problems likely outside P. In 1994 Peter Shor gave a quantum algorithm that factors integers in polynomial time. Factoring is in BQP but is widely believed to be outside P — the gap that threatens RSA encryption.
• It is contained in PSPACE. A quantum computer can be simulated with polynomial memory (just not polynomial time), so BQP ⊆ PSPACE. It is not a boundless oracle.
• It is NOT believed to contain NP. There is no known quantum algorithm for NP-complete problems like SAT. The best general tool, Grover's search (1996), only gives a quadratic speedup — turning a $2^{n}$ search into $2^{n/2}$, still exponential. Most researchers conjecture NP ⊄ BQP.

The honest status is open: we have not proven BQP ≠ P, nor BQP ⊇ NP or its negation. What we know is that BQP carves out its own region — overlapping P, reaching past it to factoring, but probably stopping short of the full NP frontier.

BQP is not an abstraction for theorists alone — it draws the line for the entire quantum industry:

• Breaking cryptography: because factoring and discrete logarithms are in BQP, a large quantum computer would break RSA and elliptic-curve crypto. This is why post-quantum cryptography is being deployed now, before such machines exist.
• Quantum simulation: simulating molecules and materials is a natural BQP problem — arguably the original motivation (Feynman, 1982). This drives drug discovery and battery research.
• Sober expectations: knowing NP is probably outside BQP keeps the field honest. Quantum computers will not magically solve scheduling, routing, or every optimization problem — see P vs NP.
• Speedup hunting: the whole research game is finding more problems with structure a quantum algorithm can exploit, beyond the square-root limit of brute-force search.

Understanding BQP is understanding exactly where the quantum revolution will land — and where it won't.

BQP is the most honest answer we have to "what can quantum computers do?" It is strictly more than the hype-free version of classical computing in some respects — it holds factoring, which feels impossible for ordinary machines — yet it is almost certainly not the all-conquering class of every hard problem. It probably does not contain NP.

So the future of quantum computing is bright but bounded. Where a problem hides exploitable structure, BQP delivers a dramatic win. Where it does not — the vast unstructured world of SAT and NP-complete puzzles — even a perfect quantum computer offers, at best, a square-root nudge. Quantum is not a miracle. It is a beautifully shaped, and still partly mysterious, special power.