Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 39 ยท Quantum Algorithms

Deutsch-Jozsa and Bernstein-Vazirani Algorithms

Build the Deutsch-Jozsa and Bernstein-Vazirani circuits from scratch with a NumPy state-vector simulator and see how one query beats many.

The first quantum algorithms were not useful in practice, but they proved something important: a quantum computer can answer some questions with fewer queries to a black box than any classical computer. The Deutsch-Jozsa algorithm (1992) and the Bernstein-Vazirani algorithm (1993) are the cleanest examples. Both use the same circuit, and both show the main trick behind most quantum speed-ups: put the input in superposition, let interference cancel the wrong answers, and measure.

In this lesson you build both circuits yourself in a small simulator. If you need a refresher on the gates used here, see how a Hadamard gate creates equal superposition, and how a CNOT flips a target qubit conditioned on a control.

The oracle model

Many quantum algorithms are described with an oracle: a black-box function you can call but not open. Here the function is f: {0,1}^n -> {0,1}. The quantum version of the oracle is a unitary U_f acting on n input qubits and one output qubit:

Text
U_f |x>|y> = |x>|y XOR f(x)>

Because it only flips the output qubit when f(x) = 1, it is reversible, which every quantum gate must be. Counting how often an algorithm calls the oracle is called query complexity.

The Deutsch-Jozsa problem

You are promised that f is either:

  • constant: it returns the same value (all 0 or all 1) for every input, or
  • balanced: it returns 0 for exactly half of the inputs and 1 for the other half.

Decide which. A classical algorithm may need 2^(n-1) + 1 queries in the worst case, because you could see the same answer half the time before the first different one. A deterministic classical algorithm needs that many to be certain. The quantum algorithm needs exactly one query.

The circuit

  1. Start with n input qubits in |0> and one output qubit in |1>.
  2. Apply a Hadamard gate to every qubit.
  3. Apply the oracle U_f.
  4. Apply a Hadamard gate to the n input qubits again.
  5. Measure the input qubits.

If the result is all zeros, f is constant. Any other result means f is balanced.

Why it works

The output qubit is in the state |-> = (|0> - |1>)/sqrt(2). When the oracle flips a qubit in this state, it only multiplies the state by -1 (a phase). So the oracle turns into |x> -> (-1)^f(x) |x> on the input register. This trick is called phase kickback.

After the first Hadamards, the input register is an equal superposition of all x. The oracle attaches a sign (-1)^f(x) to each. The final Hadamards sum these signs: the amplitude of |00...0> becomes the average of (-1)^f(x) over all x. For a constant function that average is +1 or -1, so you always measure zeros. For a balanced function the plus and minus signs cancel exactly and the amplitude of |00...0> is zero.

Deutsch-Jozsa in four steps

Superpose Hadamard on every qubit
One query Oracle adds a sign to each input
Interfere Hadamard again mixes the signs
Measure All zeros means constant

One oracle call decides what classical code may need 2^(n-1)+1 calls to decide.

1 / 2

Build it

The helper apply below applies a gate to chosen qubits of a state vector with numpy.tensordot. Qubit 0 is the leftmost bit of a basis-state label.

Python Deutsch-Jozsa with 3 input qubits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The probability of 000 is exactly 1 for the constant oracles and exactly 0 for the balanced ones. There is no probabilistic error, which is why the algorithm is called exact.

Counting the classical cost

A classical algorithm can never beat the worst case: a constant function and a balanced one look identical until you have seen more than half the inputs. The next example counts how many queries a deterministic classical search needs for a stubborn balanced function.

Python Classical worst case vs one quantum query

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 20, the classical code makes more than half a million queries. The quantum circuit still makes one. Keep the caveat in mind: a randomized classical algorithm solves the same problem with a handful of queries and a tiny error probability, so this is a speed-up against deterministic algorithms only.

The Bernstein-Vazirani problem

Now a harder promise: f(x) = s . x mod 2, the parity of the bits of x selected by a hidden string s. Find s. Classically you need n queries, one per bit (ask for f on each unit vector). The same circuit as before returns s directly with one query.

Why? The oracle attaches the sign (-1)^(s.x) to each x. The final layer of Hadamard gates is the Walsh-Hadamard transform, which maps the state with signs (-1)^(s.x) to the single basis state |s>.

Python Bernstein-Vazirani: find the secret in one query

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The measured string equals the secret every time, with probability 1.

Common mistakes

  • Forgetting the |1> on the output qubit. Without it there is no phase kickback and the circuit just computes f into an unused qubit.
  • Mixing qubit orderings. Libraries differ on whether qubit 0 is the leftmost or rightmost bit. Check before comparing results.
  • Over-claiming the speed-up. The advantage is over deterministic classical algorithms, and the problem is artificial. The value of these algorithms is the technique, not the application.

Simon's algorithm (1994) extends the same idea to a problem where the quantum advantage is exponential even against randomized classical algorithms. It finds a hidden XOR-mask s with f(x) = f(x XOR s) using about n queries, and it directly inspired Shor's algorithm.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many oracle queries does the Deutsch-Jozsa algorithm need?

    The circuit calls the oracle once. The interference pattern after the final Hadamards decides constant vs balanced.
  2. 2. What does measuring all zeros on the input register mean?

    The amplitude of |00...0> is the average of (-1)^f(x), which is plus or minus 1 for constant functions and 0 for balanced ones.
  3. 3. Why is the output qubit prepared in |1> and then hit with a Hadamard?

    X on |-> only multiplies the state by -1, so the oracle writes (-1)^f(x) into the input register. This is phase kickback.
  4. 4. How many classical queries does Bernstein-Vazirani need to learn an n-bit secret?

    Querying each unit vector reveals one secret bit at a time, so n queries are needed. The quantum circuit needs one.

Summary

  • An oracle U_f maps |x>|y> to |x>|y XOR f(x)>; query complexity counts oracle calls.
  • Deutsch-Jozsa separates constant from balanced functions with one query, versus 2^(n-1) + 1 for deterministic classical code.
  • Phase kickback turns the oracle into a sign (-1)^f(x) on each input state.
  • Bernstein-Vazirani uses the same circuit to read a hidden bit string in one query instead of n.
  • These problems are artificial, but the pattern (superpose, add phases, interfere, measure) returns in Grover's, QFT and Shor's algorithms.

Next: Grover's Search Algorithm