One oracle query decides whether a Boolean function is constant or balanced.
The promise: f:{0,1}ⁿ → {0,1} is either constant or balanced (exactly half of the inputs map to 1). Classically you may need 2ⁿ⁻¹+1 queries. Deutsch-Jozsa uses one query.
Prepare the ancilla in |−⟩ (X then H), put the inputs in uniform superposition, apply U_f: |x⟩|y⟩ ↦ |x⟩|y ⊕ f(x)⟩, then H on the inputs. If every input qubit reads 0, f is constant. Any 1 means balanced.
Default: n = 2, balanced XOR oracle f(x) = x₀ ⊕ x₁ implemented as CX from each input onto the ancilla.
How it works
-
1
Ancilla |−⟩
X 2 then H on all wires. Inputs are |+⟩⊗², ancilla is |−⟩.
-
2
Oracle
CX [0,2]; CX [1,2] kick the XOR phase back onto the inputs.
-
3
Interfere
H (0,1). Balanced XOR sends the inputs to |11⟩.
X 2 H (0,1,2) CX [0,2] CX [1,2] H (0,1)
Function form: Deutsch("balanced")
State. Inputs |11⟩. Ancilla remains |−⟩.
Input bits (q0, q1) = 11 with probability 1, so the function is classified as balanced. Measuring all three qubits splits 110 and 111 at 1/2 each because of |−⟩ on q2.
| Basis | Amplitude | Probability |
|---|---|---|
|011⟩ (q2 q1 q0, ancilla |0⟩ piece) |
1/√2 |
|
|111⟩ |
−1/√2 |
Notes
- Constant-0 oracle: omit the CX pair (identity on the ancilla).
- Constant-1 oracle: X on the ancilla instead of the CX pair.
- Do not measure the ancilla for the decision; only the input register matters.
Change parameters
The write-up above is for the default circuit. Use this control to generate other variants and load them in the simulator.