Algorithm guide · oracle
Deutsch's algorithm
A black-box function takes one bit and returns one bit. Is it constant or balanced?
Circuit size: 1 input qubit + 1 ancilla
H and X gates · Amplitudes versus probabilities · XOR (addition modulo two)
Review quantum fundamentals →Notation used in this lesson
- |ψ⟩ and ⟨ψ|
- A state vector (ket) and its conjugate transpose (bra). ⟨a|b⟩ is their inner product.
- α, β and i
- α and β are complex amplitudes; i²=−1. A probability is the squared magnitude |α|².
- XOR, · and ⊗
- XOR adds bits modulo two. In s·x, multiply corresponding bits and XOR them. ⊗ combines registers or operations on different wires.
- U†, Σ and Tr
- U† is the adjoint (inverse for a unitary). Σ sums terms. Tr is the matrix trace, the sum of diagonal entries.
- Probability, shots and angles
- Ideal probabilities describe the model; measured shot frequencies fluctuate. Angles inside trigonometric expressions are in radians unless explicitly labeled turns.
1. The problem
A black box computes a one-bit function f. Either its two outputs agree (constant) or they differ (balanced). Decide which, without needing to learn both outputs. A deterministic classical solution must inspect f(0) and f(1).
2. How it works
Prepare a helper qubit in |−⟩. Flipping this helper multiplies its state by −1. The oracle can therefore write function values as signs on the input amplitudes. A final H makes equal signs add into 0 and opposite signs add into 1.
Prepare
Put the input in |+⟩ and the helper in |−⟩ using X and H.
Query once
Apply U_f: |x,y⟩ → |x,y XOR f(x)⟩. The helper returns to |−⟩ while the input acquires a sign.
Interfere and measure
Apply H to the input. Measure its answer bit; the helper is not the answer.
3. The mathematics, one idea at a time
This is phase kickback: the oracle’s conditional X becomes a sign.
Each branch gets its own sign. This is a coherent state, not two readable function values.
Equal signs give probability one; opposite signs cancel to zero. The other outcome has the remaining probability.
Work this through by hand
4. The smallest case: f(x) = x
Two physical qubits: one input and one helper. This is the smallest supported Deutsch circuit.
Choose Balanced, so f(0)=0 and f(1)=1.
| Stage | Calculation or state | What it means |
|---|---|---|
| Input preparation | (|0⟩ + |1⟩)/√2 | Both branches start with amplitude +1/√2. |
| Oracle | (|0⟩ − |1⟩)/√2 = |−⟩ | Only the branch x=1 changes sign. |
| Final H | H|−⟩ = |1⟩ | The signs become a certain answer bit. |
Expected outcomes for this example
These are ideal predictions for the stated configuration, not a result already measured by your browser. Rows describing alternative modes or combined events are labeled explicitly.
| Outcome or event | Ideal probability | Interpretation |
|---|---|---|
| 1 | 100% ideal | Balanced function. |
| 0 | 0% ideal | Would indicate constant in an ideal unedited circuit. |
5. Load the worked example in Composer
The worked example can use smaller or simpler inputs than the gallery defaults. The button below loads the exact circuit used in this lesson.
- Oracle setup
- Define function
- Oracle
- Balanced
- Save any current circuit you want to keep, then open the worked example. Loading it does not execute a paid hardware job.
- Trace the preparation, main operations and measurements against the worked table. Check the gate editor for controls, targets and angles.
- Start with an ideal noiseless simulator compatible with the circuit. Mid-circuit measurement, reset and feed-forward require support from the chosen backend.
- Inspect the live preview. For a recorded experiment, open Execute, set the available backend options and shots, and Run. Sign in when prompted to retain it in My Jobs.
- Read the output as described below before changing one setting and repeating. The guide describes the original example; edits can change the answer.
6. Read the output correctly
Read c0 in Classical bits. Do not interpret the helper’s random computational-basis outcome as the answer.
With ideal gates, all sampled answers are 1. Change the oracle to Constant, f ≡ 0; the answer switches to 0.
A bit label is a register value; its bar height is a probability or count. For S shots and observed count k, the sampled frequency is k/S. A typical sampling scale for probability p is √[p(1−p)/S]; this is not a strict error bound. Finite samples do not have to match the ideal percentages exactly.
7. Common mistakes & limits
- One query does not reveal f(0) and f(1) separately. It reveals their parity.
- Constant f ≡ 1 differs from f ≡ 0 only by a global sign in this procedure; both produce answer 0.
8. Check your understanding
What happens for f(x)=1−x?
Reveal the reasoning
It is balanced too. The input becomes −|−⟩; the global minus does not change the answer 1.
9. Further study
The lesson’s register mappings, supported inputs and loadable example follow Quantket’s implemented circuit. A reference may use different wire names, bit order or resource conventions.
Gallery reference: defaults, definitions & implementation notes
- constant
- f(0) = f(1)
- balanced
- f(0) ≠ f(1)
Inputs & default settings
Set f(0) and f(1), or let the function be picked at random. One run in Composer tells constant from balanced.
These are the gallery defaults. The worked example above may override them. Configure the card to change the inputs before loading its editable circuit.
- Oracle setup
- Default: define · Choices for the current settings: Define function; Random oracle.
- Oracle
- Default: balanced · Choices for the current settings: Constant, f ≡ 0 (Never flips the ancilla.); Constant, f ≡ 1 (Flips the ancilla unconditionally.); Balanced (Ancilla picks up the parity of the input.); Balanced, complemented (Parity, then flipped.). Shown only for the relevant configuration.
Implementation notes
f is evaluated once on 0 and 1 together. A balanced f flips a phase, and the final Hadamard turns it into a bit: 0 means constant, 1 means balanced.
Default example: predictions & circuit facts
These values describe the unedited default setup. They are predictions and circuit properties, not measured results from your saved execution.
- Oracle queries
- 1
- Classical queries
- 2
Read your saved result
Check the submitted circuit, measured register and execution settings in Run details. Exact results give computed probabilities; sampled results show frequencies from the recorded shots. Edited circuits and noise can change the expected outcome. The algorithm label records the circuit's origin; it does not certify an edited circuit or a measured result.