05 / Algorithms · LESSON 11 / 27 · 18 MIN
Deutsch’s algorithm and phase kickback.
Understand how an oracle can encode a property into phase.
|0⟩ ─ H ─ U_f ─ H ─ M |1⟩ ─ H ─ U_f ─────────
Specify the oracle
A reversible Boolean oracle acts as U_f|x,y⟩ = |x,y⊕f(x)⟩. With target |−⟩, flipping that target contributes a minus sign: U_f|x,−⟩ = (−1)ᶠ⁽ˣ⁾|x,−⟩. This is phase kickback, not a free readout of f.
Ask a global question
For one input bit, f is constant if f(0)=f(1), balanced otherwise. Prepare |+⟩|−⟩, apply the oracle once, and apply H to the input. The input becomes |0⟩ for constant f or |1⟩ for balanced f.
Count oracle queries honestly
The ideal algorithm uses one quantum query versus two deterministic classical queries. Preparing and implementing the oracle costs resources too. The advantage here concerns queries under a specific oracle model, not every real-world task.
CHECK YOUR UNDERSTANDING
Lesson quiz
Answer all 2 questions correctly. Unlimited retries.
0/2 answered
Checking your account…
