This is a short note on the 1-qbit version of the Deutsch-Jozsa algorithm. Instead of describing the algorithm and explaining how it works, I’ve attempted to work backwards from the problem statement. This helped me understand the concept a little better.

Problem Statement

Given a quantum implementation of a 1 bit function , , that performs the operation , compute with just one query to . is the binary XOR operation and the weird bit in is a trick to convert a possibly irreversible to a reversible circuit (all quantum circuits are reversible so irreversible functions cannot be implemented as-is as quantum circuits).

Construction

Let’s assume we’re looking for a quantum circuit that will give a deterministic answer for .

For this to happen, we’d want one qbit of the output of circuit to be with probability if is and for it to be with probability if is . Without loss of generality, let this measured bit be the 0’th bit. Since deals with two bits, let’s also assume this measured bit is one out of two bits1 in the circuit.

The state of the system before measurement is then and we want when , otherwise we want .

[For brevity let be , be , and , be their logical NOTs.]

A little bit of fiddling shows that this happens2 if is and is . Therefore we somehow need to have the pre-measurement state be .

[I’ve stopped renormalizing the probabilities since that’s not super important.]

Re-associating the desired end state, we see it is equal to . This can be created from by applying the Hadamard gate to the first qbit.

This pre-Hadamard state expands to , which is something we know how to compute! It is simply where is the Hadamard gate. This yields the 1 qbit version of the Deutsch-Jozsa algorithm:

  1. Let ,
  2. Let
  3. Let
  4. Measure
  1. Of course, it is far from obvious that this has to be the case – it could be that the algorithm we were looking for requires more than two bits. 

  2. For example, if then and so = =