Algorithm guide · oracle
Deutsch–Jozsa
A hidden function takes n bits and returns one bit. Is it constant or balanced?
Circuit size: n = 1..6 input qubits + 1 ancilla
Deutsch’s algorithm · Tensor-product H gates · The promise on an input problem
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
Given f on all n-bit strings, promised to be either constant or balanced (exactly half zero and half one), identify its class. The promise is essential: arbitrary functions need not belong to either class.
2. How it works
The all-zero output amplitude is the average of the oracle’s signs. Constant functions have no sign cancellation. Balanced functions have exactly enough cancellation to remove the all-zero outcome.
Prepare all inputs
Apply H to n input wires and prepare one |−⟩ helper.
Encode f as signs
Use one oracle call to multiply each |x⟩ amplitude by (−1)^f(x).
Read interference
Apply H to every input and measure. All zeros means constant; any nonzero string means balanced, under the promise.
3. The mathematics, one idea at a time
The dot product x·y means the XOR of corresponding bit products. H combines all branches into each output y.
For a balanced function the number of +1 and −1 terms agrees, so this amplitude vanishes.
Work this through by hand
4. One-bit minimum; two-bit extension
The supported minimum is n=1, which reduces exactly to Deutsch. Use it first, then set n=2 to see the multi-input case.
The gallery’s Balanced choice implements parity: f(x)=x0 XOR … XOR x(n−1).
| Stage | Calculation or state | What it means |
|---|---|---|
| n=1 truth table | f(0)=0, f(1)=1 | The two signs are + and −. |
| Final amplitudes | A(0)=0; A(1)=1 | Only the nonzero result survives. |
| Try n=2 next | f(00),f(01),f(10),f(11) = 0,1,1,0 | Its sign pattern is +,−,−,+; H on both inputs gives 11. |
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% for the n=1 example | Balanced. |
| 11 | 100% after changing to n=2 parity | Also balanced; it is not a binary count of balanced inputs. |
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.
- Input qubits (n)
- 1
- Oracle setup
- Define oracle
- 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 only the measured input register. Increasing n changes its width.
For a general promised balanced oracle, many different nonzero outcomes are possible. The fixed parity example is unusually deterministic about which one appears.
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
- A nonzero result is not a truth table.
- The classical exact worst case is 2^(n−1)+1 queries; randomized classical strategies have a different comparison. The single quantum query still assumes oracle access.
8. Check your understanding
For n=2 and constant f ≡ 1, what answer do you expect?
Reveal the reasoning
00 with certainty in the ideal circuit. A shared −1 sign is global and does not change probabilities.
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
- same f(x) for every x
- balanced
- f(x) = 0 on exactly half
Inputs & default settings
These are the gallery defaults. The worked example above may override them. Configure the card to change the inputs before loading its editable circuit.
- Input qubits (n)
- Default: 3 · Whole number from 1 to 6.
- Oracle setup
- Default: define · Choices for the current settings: Define oracle; Hidden 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.
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.