QuantumComputinglib learn · inspect · formalize
Checked on this commit 4,524 public declarations commit 4e2c5b2c0be5 Build record

Quantum Scientific Computing / Polynomial Signals

Polynomial Signals

Exercise PLAN-519

basic · proof · test_public

primary source nl only. Current content-bound mathematical second pass accepted. No new Lean verification is claimed for this NL view.

Assumptions and conventions

  • The bit oracle adds f(x) into the answer qubit modulo two
  • The minus state is (|0> - |1>)/sqrt(2)
  • Query cost is counted in oracle calls; the reusable ancilla is prepared once

Question

The marking information for search is first given as a bit oracle that adds the function value into an answer qubit modulo two. Prove that running this bit oracle with the answer qubit prepared in the minus state converts it into a phase oracle that multiplies each input basis state by minus one exactly when it is marked, leaving the answer qubit unchanged. Make explicit why this is a clean conversion (the answer qubit factorizes out and can be reused), and explain the resource consequence: that one phase-oracle reflection costs one bit-oracle query plus state preparation of the answer qubit, with no measurement or amplification required.

Hint: mathematical route

Running the bit oracle on an answer qubit in the minus state imprints the sign (minus one) to the f(x) on the input and returns the answer qubit unchanged, so one phase reflection costs one bit-oracle query plus a one-time reusable minus-state preparation with no measurement.

  1. Prepare the answer qubit in the minus state.
  2. The bit oracle sends x tensored with minus state to (minus one) to the f(x) times the same.
  3. For both values of f(x) the answer qubit returns unchanged.
  4. The answer qubit factorizes out unentangled and is reusable.
  5. One phase reflection costs one bit-oracle query plus a one-time minus-state preparation.
  6. No measurement or amplification is needed since phase kickback is a coherent unitary effect.
Reference solution

Prepare the answer qubit in the minus state, the equal superposition of zero and one with a relative minus sign, normalized by one over the square root of two. The bit oracle maps an input string x with answer bit y to the same x with answer bit y exclusive-or f(x). Apply it to x tensored with the minus state: by linearity it sends the minus state's two components, (x,0) with plus sign and (x,1) with minus sign, to (x, f(x)) with plus sign and (x, 1 exclusive-or f(x)) with minus sign. If f(x) = 0 this is (x,0) plus sign and (x,1) minus sign, i.e. x tensored with the minus state unchanged. If f(x) = 1 this is (x,1) with plus sign and (x,0) with minus sign, i.e. x tensored with (minus the minus state) = (minus one) times x tensored with the minus state. In both cases the result is (minus one) to the f(x) times x tensored with the minus state. Hence the overall action is x tensored with minus state mapping to (minus one) to the f(x) times the same, which is exactly a phase oracle applying the sign (minus one) to the f(x) on the input register while the answer qubit is returned unchanged in the minus state. The conversion is clean because the answer qubit comes out in the identical minus state regardless of x, so it factorizes completely out of the input register and is left unentangled; therefore it can be prepared once and reused across every application of the phase oracle (including both the marked-state reflection and, by the same device, the diffusion reflection). Resource consequence: one application of the phase-oracle reflection costs exactly one query to the bit oracle plus the one-time preparation of the answer qubit in the minus state (a single-qubit state preparation), and crucially it requires no measurement and no amplification, because phase kickback is a unitary, deterministic effect; the sign is imprinted coherently rather than read out. Thus converting bit access to phase access is free up to a reusable ancilla, and the search's query accounting can be stated directly in phase-oracle reflections.

Assessment rubric
  1. Computes the bit oracle on x tensored with the minus state and obtains (minus one) to the f(x) times the same state (1 weight)
  2. Shows the answer qubit returns unchanged in the minus state for both f(x) = 0 and f(x) = 1 (1 weight)
  3. Explains the answer qubit factorizes out unentangled and can be prepared once and reused (1 weight)
  4. States the resource consequence: one phase reflection = one bit-oracle query plus one-time minus-state preparation, with no measurement or amplification (1 weight)

Graph-grounded prerequisites

These are support/source anchors, not an automatically extracted theorem-dependency proof.

  • Operator and semigroup theory (frozen curriculum anchor; see graph registry)
  • Block Encoding (frozen curriculum anchor; see graph registry)

Download the shared core registry

Lean view and evidence boundary

No aligned Lean view has been admitted for this native core in this textbook checkpoint. This is not a claim that the underlying mathematics lacks a formal proof. Contributions must preserve this exact target contract and split.

Read the Lean track and existing diagnostic warmups

Sources and provenance

Contract: 79b4f7fdf66d25ba3607bd6e15d7c862922a03e8f0d7565c6039b3d271f6d9bb

Item digest: afb80c476b2ea2e3b90eb6c6150ac9bab08f06123950b5cbfebb94a581d1d088

Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

Authored support steps: 6. This is not measured graph distance or model difficulty.