/ quantum courseBack to lab
PATHWAY PROGRESS0/27 passed

05 / Algorithms · LESSON 11 / 27 · 18 MIN

Deutsch’s algorithm and phase kickback.

Understand how an oracle can encode a property into phase.

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

1. Input measurement 1 means f is…
2. Phase kickback uses which target state?

Checking your account…