Algorithms · Quantum query algorithm
Deutsch–Jozsa query circuit
A one-query promise-problem circuit that separates constant from balanced Boolean oracles.
Strong empiricalUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
Deutsch-Jozsa on a balanced function
3 input qubits, testing f(x) = x0 XOR x1 XOR x2, which is balanced.
Step 1 of 6 · X
Probability of each outcome after this step
- 1000100%
Sets the ancilla to |1⟩, so the next step can put it into |−⟩.
The whole state moves from 0000 to 1000 — one certain outcome before, one certain outcome after, no superposition either side.
Hadamards everything: the ancilla becomes |−⟩, and the three input qubits spread into an equal superposition of all 8 inputs.
Probability spreads from 1 outcome to 16. All 16 are equally likely.
Applies f by CX-ing each input qubit onto the ancilla; against |−⟩, this kicks a phase (−1)^f(x) onto each input branch.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
A second Hadamard layer on the inputs only turns those phases into a deterministic readout.
Probability gathers from 16 outcomes onto 2. 0111 goes from 6.3% to 50.0%.
Undoes the ancilla's Hadamard.
Probability gathers from 2 outcomes onto 1. 1111 goes from 50.0% to 100.0%.
Returns the ancilla to |0⟩, purely for a tidy final state. It plays no further role in the algorithm.
The whole state moves from 1111 to 0111 — one certain outcome before, one certain outcome after, no superposition either side.
Readout The three input qubits read 111 (any nonzero result proves f is balanced, not constant); the ancilla reads 0.
Open in Studio- Steps3
- Wires3
- Qubits3
- Depthoracle-dependent
- Queries1
- Papers1
Deutsch–Jozsa is a clean record for showing how phase kickback and interference change the query model.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
The Deutsch–Jozsa problem promises that is either constant or balanced (outputs 0 and 1 equally often), and asks which. The circuit prepares the output qubit in and the input register in , queries the reversible oracle once, and applies again to the input register before measuring. Phase kickback turns each query into a sign on rather than touching the output qubit, and interference across the branches makes the input register collapse to exactly when is constant, and to a nonzero string when is balanced — one query suffices, versus up to classical queries in the worst case for a deterministic algorithm. This record reviews the phase-kickback circuit for a two-bit input against that construction; it stores one small educational oracle instance, not a general- benchmark.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Qubits
- 3
- Depth
- oracle-dependent
- Queries
- 1
- Promise
- Constant or balanced
- Quantum queries
- 1
- Classical deterministic
- 2^n / 2 + 1
Hon x[0], x[1], outU_fon x[0], x[1], outMon x[0], x[1]
Quantum vs classical
Classical baseline
Compare Quantum query algorithm with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
import cirq
q0, q1, q2 = cirq.LineQubit.range(3)
circuit = cirq.Circuit(
cirq.X(q2),
cirq.H(q0), cirq.H(q1), cirq.H(q2),
cirq.CNOT(q0, q2), cirq.CNOT(q1, q2),
cirq.H(q0), cirq.H(q1), cirq.H(q2),
cirq.measure(q0, q1, key='input'),
)
FINAL_CIRCUIT = circuitRelated entries
- Bernstein–Vazirani hidden-string circuit
Algorithms
- Grover unstructured search
Algorithms
References
- Quantum Computation and Quantum Information: 10th Anniversary Edition
Michael A. Nielsen and Isaac L. Chuang · 2010
Standard graduate textbook covering the single- and two-qubit gate definitions, matrix identities, and circuit primitives this record states.