Skip to content

Exact Quantum Polynomial Time

The class of decision problems solved by a uniform quantum computation in worst-case polynomial time with exactly zero probability of error.

Version
v1 · 2026-09-28 · History
Domain-specific #
9341
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Quantum Complexity Theory, Computational Complexity → Computer Science & Software Engineering
Aliases
EQP, Exact quantum P, Quantum polynomial time with zero error

Core Idea

EQP captures exact efficient quantum decision. A valid computation uses polynomial worst-case resources and produces the correct Boolean answer with probability one, rather than merely high probability.

Exactness makes model details unusually important. Uniformity, gate set, and admissible amplitudes must be controlled because approximate compilation arguments that preserve bounded-error classes do not automatically preserve exact acceptance.

Structural Signature

Sig role-phrases:

  • Decision language — Defines yes and no instances. It is problem object. Counterfactual: A sampling or search task belongs to a different class definition.
  • Uniform quantum computation — Provides an input-indexed machine or circuit family. It is computation model. Counterfactual: Nonuniform advice can change the class.
  • Polynomial worst-case bound — Limits runtime or circuit size on every input. It is resource bound. Counterfactual: Expected polynomial time alone does not meet the guarantee.
  • Exact acceptance — Requires acceptance probability one on yes instances and zero on no instances. It is error criterion. Counterfactual: Any nonzero error belongs to a bounded- or unbounded-error model instead.
  • Gate and amplitude convention — Specifies exactly available transformations and number representations. It is model precision. Counterfactual: Arbitrary exact amplitudes can encode unintended computational power.
  • Measurement and output — Converts the final quantum state into the decision bit with certainty. It is verdict interface. Counterfactual: A state close to correct is not exact acceptance.

What It Is Not

  • It is not BQP.
  • Exponentially small error is still not zero error.
  • It is not a claim about physical noise-free hardware.
  • Gate-set conventions cannot be omitted from exact complexity claims.
  • Closest near-miss. BQP permits a bounded probability of error that can be amplified but not made identically zero in general; EQP requires exact correctness on every run.

Scope of Application

  • Quantum complexity. Classifies exact polynomial-time decision.
  • Algorithm design. Separates exact interference algorithms from bounded-error ones.
  • Complexity comparison. Relates quantum exact computation to P and other classes.
  • Foundations. Examines sensitivity to amplitudes and gate sets.

Clarity

State machine or circuit model, uniformity, gate and amplitude set, input encoding, time or size bound, halting convention, and exact acceptance probabilities. Keep ideal complexity separate from hardware realization.

Manages Complexity

The class abstracts quantum evolution into a strict resource-and-error contract while exposing precision assumptions hidden by approximate universality.

Abstract Reasoning

  1. Formulate the task as a decision language.
  2. Choose a uniform quantum model and exact gates.
  3. Construct a polynomial-resource computation.
  4. Prove amplitude cancellation yields deterministic acceptance or rejection.
  5. Check the proof under the stated number and gate conventions.

Knowledge Transfer

Algorithm membership transfers between quantum models only under exact simulations that preserve zero error and polynomial overhead.

Examples

Canonical

A uniform polynomial-size quantum circuit family over the declared exact gate set maps every yes input to an accepting measurement outcome with probability one and every no input to rejection with probability one.

Mapped back: problem → decision; uniform → yes; time → polynomial; acceptance → exact; gates → declared.

Applied / In Practice

A polynomial-time quantum algorithm correct with probability 0.99 is a bounded-error computation, not an EQP witness, even if repetition makes error extremely small.

Mapped back: time → polynomial; error → nonzero; verdict → not exact.

Structural Tensions

T1 — Exactness versus Robust Implementability. The class demands mathematical zero error while physical gates and numerical synthesis are approximate.

Diagnostic: Is the statement about an ideal formal model or experimental execution?

T2 — Gate-Set Restriction versus Model Invariance. Approximate universality often preserves BQP but may not preserve exact languages.

Diagnostic: Which exact gates and amplitudes are allowed?

Structural–Framed Character

Exact Quantum Polynomial Time is strongly structural as a resource-bounded zero-error computation class.

Structural Core vs. Domain Accent

The skeleton is language, uniform machine, resource bound, and exact verdict. Quantum theory supplies amplitudes, unitary gates, interference, and measurement.

This entry is a kind of Complexity Class.

  • Approved root. No reviewed parent entails this exact quantum class.

  • Related — P, BQP, quantum circuit, and exact algorithm. They provide classical analogue, bounded-error contrast, model, and witness.

Relationships to Other Abstractions

Local relationship map for Exact Quantum Polynomial TimeParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Exact QuantumPolynomial TimeDOMAINDomain-specific abstraction: Complexity Class — is a kind ofComplexity ClassDOMAIN

Current abstraction Exact Quantum Polynomial Time Domain-specific

Parents (1) — more general patterns this builds on

  • Exact Quantum Polynomial Time is a kind of Complexity Class Domain-specific

    Exact Quantum Polynomial Time is a Complexity Class containing decision problems solved uniformly in quantum polynomial time with zero error.

Hierarchy paths (6) — routes to 5 parentless roots

Neighborhood in Abstraction Space

Exact Quantum Polynomial Time sits in a crowded region of the domain-specific corpus (24th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Quantum States & Computational Models (12 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • BQP. Tell: Allows bounded error.
  • ZQP. Tell: Usually permits zero-error output with expected-polynomial or success-probability conventions.
  • Exact exponential time. Tell: Drops the polynomial resource bound.
  • Quantum supremacy. Tell: Concerns sampling or performance demonstrations, not this decision class.

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Exact_quantum_polynomial_time (revision 1141428076).

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.