liveBook · Manning

Oracle query

As explained in Quantum Programming in Depth

A query is one evaluation of a black-box function or oracle on a supplied input.

A query is one evaluation of a black-box function or oracle on a supplied input. In quantum search, the goal is to find an input x₀ such that f(x₀) = 1 using as few queries as possible. section 7.0

Queries support generic search when the function's internal structure is unavailable:

  • The oracle accepts an n-bit input and returns the deterministic value 0 or 1. section 7.0
  • A constraint-satisfaction problem can encode each variable assignment as x, returning 1 when all constraints hold and 0 otherwise. section 7.0
  • Query complexity measures how many function evaluations an algorithm needs while remaining independent of the oracle's internal implementation. section 7.0

How Quantum Programming in Depth covers it

How deep it goes
Defines oracle evaluation and query minimization, but stops short of deriving query complexity or implementing an oracle.
Examples
Uses deterministic Boolean functions, satisfying variable assignments, and generic inputs x with f(x) = 1.
What it assumes
Assumes familiarity with inputs, deterministic Boolean functions, and function evaluation while defining oracle-based search from first principles.
What you can do after
Evaluate an opaque Boolean function through its oracle and reason about algorithms by counting required queries.
How it connects
Connects queries to black-box functions, oracles, search problems, constraint satisfaction, and Grover's search algorithm.
Cover of Quantum Programming in Depth
liveBookmanning.com
Read Quantum Programming in Depth on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Quantum Programming in Depth. The section links point to the parts of the book it draws on.