Algorithm lab · reviewed 2026-10-25
Deutsch–Jozsa n=2
Tell a balanced oracle from a constant one with a single run of the circuit, and see why the answer is never in doubt.
Recorded simulator example · open starter templates to create your own run. Open starter templates →
- Qubits
- 3
- Operations
- 10
- Shots
- 4,096
Define
State the oracle and the constant-or-balanced promise.
oracle noteQuery
Apply the oracle once between two layers of Hadamard gates.
Qiskit + OpenQASMSimulate
Execute 4,096 seeded shots on local Aer.
complete counts + traceReview
Read a non-zero result as balanced and state the promise.
reviewer note
Workflow question
What this sample is testing.
Prepare two input qubits and one ancilla, apply a balanced oracle f(x) = x0 XOR x1 built from two controlled-X gates, interfere the inputs with Hadamard gates, and verify that measuring the inputs returns a non-zero string, which identifies the oracle as balanced.
Route rationale
Local Qiskit Aer simulator, no provider token required
Non-zero input string 11 on all 4,096 shots, identifying the balanced oracle
Method
Put the ancilla q2 in the minus state with X then H, and both inputs in an equal superposition with H. The oracle applies a controlled-X from each input onto the ancilla, which computes the parity of the two input bits. A final Hadamard on each input turns the resulting phase pattern into a measurable bitstring, and the two inputs are measured.
Run the generated Qiskit circuit on the local Qiskit Aer simulator for 4,096 shots with simulator and transpiler seed 2048. Store the circuit, source, complete counts, route note, and export manifest together.
How to read the result
A constant oracle makes the input register return 00; a balanced oracle returns a non-zero string. This oracle is balanced and the stored fixture returns 11 for all 4,096 shots. The same circuit with both oracle gates removed, a constant oracle, was run on the same simulator and returned 00 for all 4,096 shots.
The decision needs one oracle query in the quantum circuit, where a deterministic classical method may need up to 2^(n-1) + 1 = 3 evaluations of f for two input bits. The page exposes the oracle because the answer is only meaningful when the reviewer knows which function it queries.
Measured distribution
Complete seeded count table
4,096 shots
Complete ideal-simulator distribution. Engine Qiskit Aer 0.17.0; simulator and transpiler seed 2048. This static public fixture is not a live provider run.
Proof boundary
- With only two input bits the classical problem is trivially small, so this sample shows how the algorithm works, not a practical speedup.
- The algorithm relies on a promise that the function is constant or balanced. It does not say which balanced function it is, and it gives no guarantee for functions outside the promise.
- This is an ideal local simulation. Hardware noise can return 00 for a balanced oracle or a non-zero string for a constant one. It is a seeded local simulation, not a live provider job.
Generated representations
Inspect the source behind the counts.
The public code is a review fixture. Provider credentials, workspace members, billing context, and private notes stay excluded.
Qiskit circuit
Pythonfrom qiskit import QuantumCircuit
qc = QuantumCircuit(3, 2)
qc.x(2)
qc.h([0, 1, 2])
qc.cx(0, 2)
qc.cx(1, 2)
qc.h([0, 1])
qc.measure([0, 1], [0, 1])OpenQASM circuit
OpenQASM 3OPENQASM 3;
include "stdgates.inc";
bit[2] c;
qubit[3] q;
x q[2];
h q[0];
h q[1];
h q[2];
cx q[0], q[2];
cx q[1], q[2];
h q[0];
h q[1];
c[0] = measure q[0];
c[1] = measure q[1];Evidence manifest
JSON{
"workflowId": "QF-SAMPLE-DEUTSCH-JOZSA-N2",
"runner": "qiskit-aer",
"artifacts": [
"oracle-notes.md",
"generated-qiskit.py",
"generated-openqasm.qasm",
"counts.json",
"reviewer-note.md"
],
"privateFieldsExcluded": [
"providerCredentialId",
"userEmail",
"billingState",
"adminNotes"
]
}What the reviewer receives
- oracle-notes.md
- generated-qiskit.py
- generated-openqasm.qasm
- counts.json
- reviewer-note.md
Explicitly excluded
- providerCredentialId
- userEmail
- billingState
- adminNotes
Questions this record answers
Workflow FAQ
What does the Deutsch–Jozsa algorithm decide?
Given a function known to be either constant or balanced, it decides which with one quantum query. If the input register measures all zeros the function is constant; any other result means it is balanced.
Why does the ancilla start in the minus state?
X followed by H puts q2 in the minus state, which turns each controlled-X into a phase flip on the input register. This phase kickback is what the final Hadamard layer converts into a measurable result.
Does this prove a quantum speedup?
No. For two input bits a classical program is trivial. The sample is a readable, checkable demonstration of the circuit and its evidence.