Introduction

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.

Map the Speedup

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">Quantum computers don't speed up everything equally. Click a problem to place it on the map by the <b>best known</b> quantum speedup. Then pick a size <b>n</b> to see how many steps each approach needs.</p>
<div class="problems" id="problems"></div>
<div class="controls">
  <label>Problem size n = <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>Exponential win</h4><div class="slot" id="slot-exp"></div></div>
  <div class="col" data-band="quad"><h4>Quadratic (Grover)</h4><div class="slot" id="slot-quad"></div></div>
  <div class="col" data-band="none"><h4>No known win</h4><div class="slot" id="slot-none"></div></div>
</div>
<div class="status" id="status">Click a problem above to map it.</div>
<div class="btns"><button id="reset" type="button" class="ghost">Reset map</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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// BQP is the class of problems a quantum computer solves efficiently. The map below
// sorts problems by their BEST KNOWN quantum speedup over classical brute force:
//  - exp : exponential win from hidden structure (Shor 1994) -> in BQP, likely outside P
//  - quad: only a square-root win from Grover's search (1996) -> still exponential time
//  - none: no known quantum advantage at all
// Classical cost ~ 2^n for the hard problems; quantum cost depends on the band.
const PROBLEMS = [
  { id:'factoring', name:'Factoring (RSA)', band:'exp',
    algo:'Shor 1994', why:'Periodicity is hidden structure a quantum Fourier transform exposes.' },
  { id:'dlog', name:'Discrete log', band:'exp',
    algo:'Shor 1994', why:'Same hidden-subgroup trick as factoring.' },
  { id:'sim', name:'Quantum simulation', band:'exp',
    algo:'Feynman 1982', why:'A quantum system natively simulates another quantum system.' },
  { id:'search', name:'Unstructured search', band:'quad',
    algo:'Grover 1996', why:'No structure to exploit; amplitude amplification gives only sqrt.' },
  { id:'sat', name:'SAT (NP-complete)', band:'none',
    algo:'(none known)', why:'No quantum algorithm beats brute force; NP is not believed inside BQP.' },
  { id:'tsp', name:'Traveling salesman', band:'none',
    algo:'(none known)', why:'NP-hard; only generic search speedup at best, not a real win.' },
];
const SLOT = { exp:'slot-exp', quad:'slot-quad', none:'slot-none' };
const placed = new Set();

// Steps for size n. Classical hard problems ~ 2^n. Quantum band changes the exponent.
function steps(band, n){
  if(band==='exp')  return n;          // polynomial: ~ n^3, we report the exponent shrinks to poly
  if(band==='quad') return Math.pow(2, n/2); // sqrt of 2^n
  return Math.pow(2, n);               // no win: still 2^n
}
function fmt(x){
  if(x < 1e6) return Math.round(x).toLocaleString();
  const e = Math.floor(Math.log10(x));
  return '≈10^' + e;
}
function classical(n){ return Math.pow(2, n); }

function render(){
  const wrap = document.getElementById('problems'); wrap.innerHTML='';
  PROBLEMS.forEach(p=>{
    const c = document.createElement('button');
    c.className = 'chip' + (placed.has(p.id)?' placed':'');
    c.textContent = p.name;
    c.addEventListener('click', ()=> place(p));
    wrap.appendChild(c);
  });
}
function describe(p, n){
  if(p.band==='exp')  return i18nFmt('classical ≈2^%n% → quantum polynomial (a few thousand steps). Exponential win.', { n: n });
  if(p.band==='quad') return i18nFmt('classical ≈2^%n% = %fmt% → quantum ≈2^%v% = %fmt2%. Square-root only.', { n: n, fmt: fmt(classical(n)), v: n/2, fmt2: fmt(steps('quad',n)) });
  return i18nFmt('classical ≈2^%n% = %fmt% → quantum ≈2^%n%. No known win.', { n: n, fmt: fmt(classical(n)) });
}
function place(p){
  if(placed.has(p.id)) return;
  placed.add(p.id);
  const n = +document.getElementById('n').value;
  const slot = document.getElementById(SLOT[p.band]);
  const it = document.createElement('div'); it.className='item'; it.dataset.id=p.id;
  it.innerHTML = '<b>'+p.name+'</b><small>'+p.algo+' — '+describe(p,n)+'</small>';
  slot.appendChild(it);
  render();
  const msg = { exp:'Exponential speedup — this is what puts a problem firmly inside BQP yet likely outside P.',
                quad:'Only a quadratic speedup. 2^n becomes 2^(n/2): still exponential, so not “efficient”.',
                none:'No known quantum advantage. NP-complete problems are not believed to be in BQP.' }[p.band];
  document.getElementById('status').textContent = p.name + ': ' + msg;
  console.log(p.id, 'band='+p.band, describe(p,n));
}
function refresh(){
  const n = +document.getElementById('n').value;
  document.getElementById('nval').textContent = n;
  PROBLEMS.forEach(p=>{
    if(!placed.has(p.id)) return;
    const it = document.querySelector('.item[data-id="'+p.id+'"]');
    if(it) it.querySelector('small').textContent = p.algo + ' — ' + describe(p,n);
  });
}
document.getElementById('n').addEventListener('input', refresh);
document.getElementById('reset').addEventListener('click', ()=>{
  placed.clear();
  ['slot-exp','slot-quad','slot-none'].forEach(id=> document.getElementById(id).innerHTML='');
  document.getElementById('status').textContent='Click a problem above to map it.';
  render();
});
render(); refresh();
Result
Console

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.

The Real Complexity

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 2n2^{n} search into 2n/22^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bqp/Content licensed under CC BY-NC 4.0.