Skip to main content
Glossary

Quantum glossary

Oracle

Also: black box, marking oracle, phase oracle

A subroutine that encodes the problem, often by flipping the phase of the states that are solutions.

Query complexity counts calls to the oracle. In real applications the oracle must be built out of gates, and its cost can swamp the speedup — a detail textbook treatments often skip.

See it for yourself

Related terms

  • Grover's algorithm — A quantum algorithm that finds a marked item among N in about √N queries, where classical search needs about N.
  • Phase kickback — When a controlled operation acts on a target in an eigenstate, the eigenvalue’s phase appears on the control qubit instead.