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.

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. Inclusion test: Give a uniform quantum machine or circuit model, admissible gate set and amplitudes, worst-case polynomial resource bound, and exact acceptance semantics for every input. Exclusion test: Exclude bounded-error BQP algorithms, Las Vegas procedures with variable runtime unless they meet the exact worst-case definition, approximate state preparation, and quantum speedups for non-decision tasks without a class reduction. Nearest boundary: 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. Exit condition: A problem leaves EQP under a model if correctness relies on approximation error, success probability below one, or superpolynomial worst-case resources. Common misclassifications: 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. Nearest named distinctions: BQP: Allows bounded error. ZQP: Usually permits zero-error output with expected-polynomial or success-probability conventions. Exact exponential time: Drops the polynomial resource bound. Quantum supremacy: Concerns sampling or performance demonstrations, not this decision class.

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.

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