Steven GellerQuantum Computing, End to End

Book contents

Type at least two characters.

    Current section

    Part IV. Protocols and Algorithms

    1. Bell Tests and Nonclassical Correlations
    2. Superdense Coding
    3. Teleportation
    4. Quantum Key Distribution
    5. Oracles and Query Complexity
    6. Deutsch, Deutsch-Jozsa, and Bernstein-Vazirani
    7. Simon and Hidden Structure
    8. Grover and Amplitude Amplification
    9. Quantum Fourier Transform
    10. Phase Estimation
    11. Shor as Period Finding
    12. Hamiltonian Simulation
    13. Variational Algorithms and Their Limits
    All chaptersGlossaryLabsSourcesAbout

    Part IV. Protocols and Algorithms · Chapter 27

    Oracles and Query Complexity

    Most famous quantum speedups are proven in a world where a black box answers structured questions and nobody itemizes its bill. This chapter teaches you to read that world honestly: count the queries, then price the box.

    Steven Geller
    Lab
    In this chapter 8 sections

    Reader question. What does a quantum query-complexity result count, and which costs does the oracle abstraction hide?

    It counts uses of a specified black-box unitary under an input promise; it can expose a genuine information advantage while hiding oracle construction, data loading, gate decomposition, verification, and classical work, all of which must be restored before making a runtime claim.

    Scope and non-goals.
    • Query complexity is treated as a bounded cost model rather than a hardware-performance claim.
    • Quantum and classical comparisons must use the same declared oracle contract.
    One oracle call in the standard model One oracle call: data in, answer encoded |x> |y> U_foracle |x> passes through unchanged |y xor f(x)> carries the answer Query complexity counts calls to this box. The box's own gate depth is a separate bill.
    Figure 27.1. Notice that the diagram hides the interesting number: you pay per call, but nothing in the picture says what one call costs to build. With the target prepared as ∣−⟩\lvert-\rangle, the answer comes back as a phase instead of a bit flip; the kickback trick this chapter develops.

    The black-box contract

    Define domain, range, unitary action, and input promise.

    An oracle is an abstract operation that answers a structured question about the input: given xx, it makes f(x)f ( x ) available to the algorithm in one step. Query complexity counts how many times the algorithm calls it. That counting discipline is what lets theorists prove clean separations; quantum needs one call where classical needs many; without committing to any hardware.

    The discipline has five parts, and a speedup claim missing any of them is incomplete:

    1. State the oracle. What exactly does one call compute?
    2. State the input promise. What structure is guaranteed; a hidden string, a balanced function, a single marked item?
    3. Count oracle calls. Quantum and classical, under the same access model.
    4. State non-oracle costs. State preparation, gates between calls, measurement, post-processing.
    5. Compare against the best classical baseline given the same oracle access, not against a strawman that reads the input one bit at a time.

    Run this checklist on a celebrated result and it holds up beautifully. Run it on a product pitch and you will often find the promise doing all the work.

    Evidence boundary. Quantum query complexity studies the number of oracle calls required under a defined black-box model. [Ethan Bernstein] [John Watrous]

    Two oracle encodings that are not interchangeable

    Compare bit and phase oracles.

    The standard bit oracle acts on two registers:

    Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩U_f\lvert x\rangle\lvert y\rangle=\lvert x\rangle\lvert y\oplus f(x)\rangle(27.1)

    The input register passes through untouched; the answer lands on the target. Now prepare the target in the minus state, ∣−⟩=(∣0⟩−∣1⟩)/2\lvert-\rangle=(\lvert0\rangle-\lvert1\rangle)/\sqrt2. Because flipping ∣−⟩\lvert-\rangle only multiplies it by −1, the function value comes back as a phase on the input branch:

    Uf∣x⟩∣−⟩=(−1)f(x)∣x⟩∣−⟩U_f\lvert x\rangle\lvert-\rangle=(-1)^{f(x)}\lvert x\rangle\lvert-\rangle(27.2)

    The target register is left exactly as it started; the information has "kicked back" onto the input. A phase is invisible to a direct measurement; but a later basis change can turn a phase pattern into interference, and interference into a measurable answer. The oracle never prints anything. It reshapes the state, and the rest of the circuit decides what that reshaping reveals.

    Evidence boundary. A reversible bit oracle can induce a phase oracle through phase kickback. [Michael A. Nielsen] [John Preskill]

    Kickback moves a value into phase

    Derive the |-> target calculation.

    Prepare the oracle target as |->=(|0>-|1>)/sqrt(2). Because X|->=-|->, mapping y to y xor f(x) multiplies the x branch by (-1)^f(x) while returning the target unchanged. This phase oracle equivalence costs one bit-oracle query plus explicit local state preparation. It does not reveal f(x) as a classical output.

    Evidence boundary. Query complexity does not by itself include circuit synthesis, data access, or end-to-end runtime. [Ethan Bernstein] [National Academies of Sciences]

    OracleUf∣x,y>=∣x,y⊕f(x)>;phaseoracleOf∣x>=(−1)f(x)∣x>;QqueriesseparatedfromGgates.Oracle U_f|x,y>=|x,y⊕f(x)>; phase oracle O_f|x>=(-1)^{f(x)}|x>; Q queries separated from G gates.(27.3)

    Notation contract: Oracle U_f|x,y>=|x,y⊕f(x)>; phase oracle O_f|x>=(-1)^{f(x)}|x>; Q queries separated from G gates.

    What a query bound proves

    Separate information access from implementation time.

    An oracle is an interface with an unusually strong contract: the implementation is hidden, the call is atomic, and the promise is guaranteed. Production systems hide nothing forever, so the bridge from textbook to feasibility runs through six questions:

    • What does the oracle actually compute?
    • How is the input represented, and who loads it?
    • What promise is assumed, and does the real workload keep it?
    • What does one call cost in gates, depth, and ancillas?
    • Can the computation be made reversible, as unitarity demands?
    • What classical algorithm receives the same access; and how well does it do?

    These questions are not pedantry. They are the difference between an algorithm and an application.

    Restore the hidden cost ledger

    Price construction, invocation, data, and verification.

    Record oracle queries, oracle implementation gates, non-oracle gates, depth after connectivity mapping, state preparation, measurements or shots, classical post-processing, and verification as separate rows. A query lower bound speaks only to the first row under the black-box promise. End-to-end advantage needs every remaining row and a relevant classical implementation under comparable input access.

    Oracle contract and cost-ledger schema

    Acceptance contract for Oracle contract and cost-ledger schema
    FieldReader-visible record
    FormatReference bit/phase oracle circuits plus machine-readable cost model
    VerificationTests unitary action on every small input, verifies kickback equivalence, and rejects ledgers with unpriced construction or verification.
    AvailabilitySource-embedded acceptance record; no separate download is claimed
    {
  "artifact": "Oracle contract and cost-ledger schema",
  "format": "Reference bit/phase oracle circuits plus machine-readable cost model",
  "acceptance_test": "Tests unitary action on every small input, verifies kickback equivalence, and rejects ledgers with unpriced construction or verification.",
  "publication_state": "source-embedded contract and worked fixture"
}

    Executable reference fixture

    Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.

    class Oracle:
    def __init__(self, fn): self.fn, self.queries = fn, 0
    def __call__(self, x):
        self.queries += 1
        return self.fn(x)
def linear_search(size, target):
    if type(size) is not int or size < 1 or target not in range(size):
        raise ValueError("target must index a nonempty domain")
    oracle = Oracle(lambda x: x == target)
    answer = next(x for x in range(size) if oracle(x))
    return {"answer": answer, "queries": oracle.queries, "domain": size}

middle = linear_search(16, 7)
boundary = linear_search(16, 0)
rejected = False
try:
    linear_search(16, 16)
except ValueError:
    rejected = True
assert middle == {"answer": 7, "queries": 8, "domain": 16}
assert boundary["answer"] == 0 and boundary["queries"] == 1
assert rejected and middle["queries"] > boundary["queries"]
print(f"PASS: 27 oracle ledger middle_queries={middle['queries']} boundary_queries={boundary['queries']} invalid_target={rejected}")

    Scope boundary

    • Query complexity is treated as a bounded cost model rather than a hardware-performance claim.
    • Quantum and classical comparisons must use the same declared oracle contract.

    Depth commitment. One contract, two implementations, one equivalence proof, and one cost schema.

    Practice problem

    For a two-bit Boolean function, construct bit and phase oracles, prove kickback equivalence, and assign separate query and gate costs.

    Deliverable
    Two unitary matrices/circuits, one state trace, and a completed cost ledger.
    Pass condition
    Fixtures exhaust all inputs, compare induced phases, and recalculate costs from gate lists.

    Verification record

    Expected solution form. Algebraic equivalence proof plus exhaustive circuit and ledger tests.

    Model answer. The bit oracle maps |x,y> to |x,y xor f(x)>; with y=|->, it returns (-1)^f(x)|x>|->, which is the phase oracle action on x. Each use counts as one query; gates used to prepare |-> or change basis remain separate local circuit cost.

    Model result and check. CI verifies unitarity, truth-table behavior, phase action, and ledger arithmetic.

    Acceptance test. Fixtures exhaust all inputs, compare induced phases, and recalculate costs from gate lists.

    Companion work

    Artifacts for this chapter

    These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.

    1. Reproduce or test

      python3 tools/validate_briefs.py --briefs data/editorial_briefs_00_35.json --from 0 --through 35 --check-rewritten-sources --execute-artifacts

    Provenance

    Sources and review

    1. Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing. 1997primary paper
    2. John Watrous. The Theory of Quantum Information. Cambridge University Press / University of Waterloo. 2018textbook
    3. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press. 2010textbook
    4. John Preskill. Lecture Notes for Physics 219: Quantum Computation. California Institute of Technology. 2018graduate lecture notes
    5. National Academies of Sciences, Engineering, and Medicine. Quantum Computing: Progress and Prospects. National Academies Press. 2019consensus study report

    The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.

    External review: Open.

    How review worksRevision historyReport or inspect errata

    Dependency graph

    Prerequisites for this chapter

    1. Controlled Gates and Reversible Classical ComputationPart III. Circuit Model · Chapter 18
    2. Circuit Cost: Depth, Width, Gate Set, ConnectivityPart III. Circuit Model · Chapter 22

    Continue the thread

    1. Quantum Algorithms and SpeedupsOrientation guide
    2. Deutsch, Deutsch-Jozsa, and Bernstein-VaziraniPart IV. Protocols and Algorithms · Chapter 28
    3. Grover and Amplitude AmplificationPart IV. Protocols and Algorithms · Chapter 30

    Cite this chapter