EQP (complexity)

In computational complexity theory, EQP (sometimes called QP), which stands for exact quantum polynomial time, is the class of decision problems solvable by a quantum computer which outputs the correct answer with probability 1 and runs in polynomial time. It is the quantum analogue of the complexity class P.

In other words, there is an algorithm for a quantum computer (a quantum algorithm) that solves the decision problem exactly and is guaranteed to run in polynomial time.

References

• Complexity Zoo: EQP

Quantum information science General Quantum computer Qubit Quantum information Quantum programming Timeline of quantum computing Quantum communication Quantum capacity Classical capacity Entanglement-assisted classical capacity Quantum channel Quantum network Quantum cryptography Quantum key distribution Quantum energy teleportation Quantum teleportation Superdense coding LOCC Entanglement distillation Quantum algorithms Universal quantum simulator Deutsch–Jozsa algorithm Grover's algorithm Quantum Fourier transform Shor's algorithm Simon's problem Quantum phase estimation algorithm Quantum annealing Algorithmic cooling Quantum complexity theory Quantum Turing machine EQP BQP QMA PostBQP Quantum computing models Quantum circuit Quantum gate One-way quantum computer cluster state Adiabatic quantum computation Topological quantum computer Decoherence prevention Quantum error correction Stabilizer codes Entanglement-Assisted Quantum Error Correction Quantum convolutional codes Physical implementations Quantum optics Cavity QED Circuit QED Linear optical quantum computing Ultracold atoms Trapped ion quantum computer Optical lattice Spin-based Nuclear magnetic resonance QC Kane QC Loss–DiVincenzo QC Nitrogen-vacancy center Superconducting quantum computing Charge qubit Flux qubit Phase qubit