# Constructing the Deutsch-Jozsa Algorithm

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 bits^{1} 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 happens^{2} 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:

- Let ,
- Let
- Let
- Measure