BQP and the limits of complexity-class inference
Research context
postgraduate concept · established · As of 2026-10-10
BQP consists of decision problems with uniform polynomial-size quantum circuits and bounded error, using a specified finite gate model and classical input/output.
Key knowledge
BQP consists of decision problems with uniform polynomial-size quantum circuits and bounded error, using a specified finite gate model and classical input/output. Standard amplification changes constant error without exponential resources. BPP is contained in BQP, and BQP is contained in PP and hence PSPACE. These inclusions do not assert strict separations, and a query-oracle separation does not settle an ordinary unrelativized class relationship.
Conditions and scope
- Uniformity excludes hiding arbitrary answers in nonuniform circuits; precision and promise-problem conventions are explicit.
- Complexity is asymptotic in input length and differs from current hardware capability on one problem size.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: §IV BQP/resource/oracle model, §V QMA promises and 2-local Hamiltonian Theorem 8; historical survey; Introduction, Theorems 1.1–1.2 and formal oracle/list-recovery construction; unrelativized boundary. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-bqp-uniform-circuit-model
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference