Deutsch–Jozsa algorithm

The Deutsch–Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm.

The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. It is a black box problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need an exponential number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which EQP, the class of problems that can be solved exactly in polynomial time on a quantum computer, and P are different.

Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with BPP, the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer. Simon's problem is an example of a problem that yields an oracle separation between BQP and BPP.

Problem statement

In the Deutsch–Jozsa problem, we are given a black box quantum computer known as an oracle that implements some function:

$f\colon \{0,1\}^{n}\rightarrow \{0,1\}$

The function takes n-bit binary values as input and produces either a 0 or a 1 as output for each such value. We are promised that the function is either constant (0 on all inputs or 1 on all inputs) or balanced (1 for exactly half of the input domain and 0 for the other half). The task then is to determine if $f$ is constant or balanced by using the oracle.

Classical solution

For a conventional deterministic algorithm where $n$ is the number of bits, $2^{n-1}+1$ evaluations of $f$ will be required in the worst case. To prove that $f$ is constant, just over half the set of inputs must be evaluated and their outputs found to be identical (because the function is guaranteed to be either balanced or constant, not somewhere in between). The best case occurs where the function is balanced and the first two output values are different. For a conventional randomized algorithm, a constant $k$ evaluations of the function suffices to produce the correct answer with a high probability (failing with probability $\epsilon \leq 1/2^{k}$ with $k\geq 1$). However, $k=2^{n-1}+1$ evaluations are still required if we want an answer that has no possibility of error. The Deutsch-Jozsa quantum algorithm produces an answer that is always correct with a single evaluation of $f$.

History

The Deutsch–Jozsa algorithm generalizes earlier (1985) work by David Deutsch, which provided a solution for the simple case where $n=1$.
Specifically, given a Boolean function whose input is one bit, $f:\{0,1\}\rightarrow \{0,1\}$, is it constant?

The algorithm, as Deutsch had originally proposed it, was not deterministic. The algorithm was successful with a probability of one half. In 1992, Deutsch and Jozsa produced a deterministic algorithm which was generalized to a function which takes $n$ bits for its input. Unlike Deutsch's algorithm, this algorithm required two function evaluations instead of only one.

Further improvements to the Deutsch–Jozsa algorithm were made by Cleve et al., resulting in an algorithm that is both deterministic and requires only a single query of $f$. This algorithm is still referred to as Deutsch–Jozsa algorithm in honour of the groundbreaking techniques they employed.

Algorithm

For the Deutsch–Jozsa algorithm to work, the oracle computing $f(x)$ from $x$ must be a quantum oracle which does not decohere $x$. In its computation, it cannot make a copy of $x$, because that would violate the no cloning theorem. The point of view of the Deutsch-Jozsa algorithm of $f$ as an oracle means that it does not matter what the oracle does, since it just has to perform its promised transformation.

Deutsch-Jozsa algorithm quantum circuit

The algorithm begins with the $n+1$ bit state $|0\rangle ^{\otimes n}|1\rangle$. That is, the first n bits are each in the state $|0\rangle$ and the final bit is $|1\rangle$. A Hadamard gate is applied to each bit to obtain the state

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )$,

where $x$ runs over all $n$-bit strings, which each may be represented by a number from $0$ to $2^{n}-1$. We have the function $f$ implemented as a quantum oracle. The oracle maps its input state $|x\rangle |y\rangle$ to $|x\rangle |y\oplus f(x)\rangle$, where $\oplus$ denotes addition modulo 2. Applying the quantum oracle gives;

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle )$.

For each $x,f(x)$ is either 0 or 1. Testing these two possibilities, we see the above state is equal to

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )$.

At this point the last qubit ${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}$ may be ignored and the following remains:

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle$.

Next, we will have each qubit go through a Hadamard gate. The total transformation over all $n$ qubits can be expressed with the following identity:

$H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle$

($j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}$ is the sum of the bitwise product). This results in

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle$.

From this, we can see that the probability for a state $k$ to be measured is

$\left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot k}\right|^{2}$

The probability of measuring $k=0$, corresponding to $|0\rangle ^{\otimes n}$, is

${\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}$

which evaluates to 1 if $f(x)$ is constant (constructive interference) and 0 if $f(x)$ is balanced (destructive interference). In other words, the final measurement will be $|0\rangle ^{\otimes n}$ (all zeros) if and only if $f(x)$ is constant and will yield some other state if $f(x)$ is balanced.

Deutsch's algorithm

Deutsch's algorithm is a special case of the general Deutsch–Jozsa algorithm where n = 1 in $f\colon \{0,1\}^{n}\rightarrow \{0,1\}$. We need to check the condition $f(0)=f(1)$. It is equivalent to check $f(0)\oplus f(1)$ (where $\oplus$ is addition modulo 2, which can also be viewed as a quantum XOR gate implemented as a Controlled NOT gate), if zero, then $f$ is constant, otherwise $f$ is not constant.

We begin with the two-qubit state $|0\rangle |1\rangle$ and apply a Hadamard gate to each qubit. This yields

${\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).$

We are given a quantum implementation of the function $f$ that maps $|x\rangle |y\rangle$ to $|x\rangle |f(x)\oplus y\rangle$. Applying this function to our current state we obtain

${\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))$

$={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))$

$=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).$

We ignore the last bit and the global phase and therefore have the state

${\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).$

Applying a Hadamard gate to this state we have

${\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )$

$={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).$

$f(0)\oplus f(1)=0$ if and only if we measure $|0\rangle$ and $f(0)\oplus f(1)=1$ if and only if we measure $|1\rangle$. So with certainty we know whether $f(x)$ is constant or balanced.

Deutsch–Jozsa algorithm Qiskit implementation

Below is a simple example of how the Deutsch–Jozsa algorithm can be implemented in Python using Qiskit, an open-source quantum computing software development framework by IBM. We will walk through each part of the code step by step to show how it translates the theory into a working quantum circuit.

1. Import necessary libraries

from qiskit import QuantumCircuit, transpile
from qiskit_aer import Aer

2. Define helper functions to create oracles

def create_constant_oracle(n_qubits, output):
    """
    Creates a 'constant' oracle.

    If `output` is 0, the oracle always returns 0.
    If `output` is 1, the oracle always returns 1.

    Args:
        n_qubits (int): The number of input qubits.
        output (int): The constant output value of the function (0 or 1).

    Returns:
        QuantumCircuit: A quantum circuit implementing the constant oracle.
    """
    oracle = QuantumCircuit(n_qubits + 1)

    # If the oracle should always output 1, we flip the "output" qubit
    # using an X-gate (think of it as a NOT gate on a qubit).
    if output == 1:
        oracle.x(n_qubits)

    return oracle


def create_balanced_oracle(n_qubits):
    """
    Creates a 'balanced' oracle.

    Half of the input bit patterns output 0, and the other half output 1.

    For demonstration, this function implements a simple balanced function
    by placing X-gates on the first qubit of the input as a control,
    inverting the output qubit for half of the inputs.

    Args:
        n_qubits (int): The number of input qubits.

    Returns:
        QuantumCircuit: A quantum circuit implementing the balanced oracle.
    """
    oracle = QuantumCircuit(n_qubits + 1)

    # We'll use a simple pattern: if the first qubit is 1, flip the output.
    # This means for half of the possible inputs, the output changes.
    oracle.cx(0, n_qubits)

    return oracle

3. Deutsch-Jozsa circuit assembly function

def deutsch_jozsa_circuit(oracle, n_qubits):
    """
    Assembles the full Deutsch-Jozsa quantum circuit.

    The circuit performs the following steps:
    1. Start all 'input' qubits in |0>.
    2. Start the 'output' qubit in |1>.
    3. Apply Hadamard gates to all qubits.
    4. Apply the oracle.
    5. Apply Hadamard gates again to the input qubits.
    6. Measure the input qubits.

    Args:
        oracle (QuantumCircuit): The circuit encoding the 'mystery' function f(x).
        n_qubits (int): The number of input qubits.

    Returns:
        QuantumCircuit: The complete Deutsch-Jozsa circuit ready to run.
    """
    # Total of n_qubits for input, plus 1 for the output qubit
    dj_circuit = QuantumCircuit(n_qubits + 1, n_qubits)

    # 1. The input qubits are already set to |0>.
    # 2. The output qubit is set to |1>. We achieve this by an X gate.
    dj_circuit.x(n_qubits)

    # 3. Apply Hadamard gates to all qubits (input + output).
    for qubit in range(n_qubits + 1):
        dj_circuit.h(qubit)

    # 4. Append the oracle circuit.
    dj_circuit.compose(oracle, inplace=True)

    # 5. Apply Hadamard gates again to the input qubits ONLY.
    for qubit in range(n_qubits):
        dj_circuit.h(qubit)

    # 6. Finally, measure the input qubits.
    for qubit in range(n_qubits):
        dj_circuit.measure(qubit, qubit)

    return dj_circuit

4. Putting it all together to test constant vs balanced

def run_deutsch_jozsa_test(n_qubits, oracle_type='constant', constant_output=0):
    """
    Builds and runs the Deutsch-Jozsa circuit for either a constant oracle
    or a balanced oracle, then prints the results.

    Args:
        n_qubits (int): Number of input qubits.
        oracle_type (str): Specifies the type of oracle, either 'constant' or 'balanced'.
        constant_output (int): If the oracle is constant, determines whether it returns 0 or 1.
    """
    # Create the chosen oracle
    if oracle_type == 'constant':
        oracle = create_constant_oracle(n_qubits, constant_output)
        print(f"Using a CONSTANT oracle that always returns {constant_output}")
    else:
        oracle = create_balanced_oracle(n_qubits)
        print("Using a BALANCED oracle.")

    # Create the Deutsch-Jozsa circuit
    dj_circ = deutsch_jozsa_circuit(oracle, n_qubits)

    # Draw the circuit for visual reference
    display(dj_circ.draw())

    # Use the simulator backend to run the circuit
    simulator = Aer.get_backend('aer_simulator')
    transpiled_circ = transpile(dj_circ, simulator)
    job = simulator.run(transpiled_circ, shots=1)
    result = job.result()
    counts = result.get_counts(transpiled_circ)

    print("Measurement outcomes:", counts)

    # Interpret the measurement
    # If all measured bits are 0 (e.g., '000' for 3 qubits), then the
    # function is constant. Otherwise, it is balanced.
    measured_result = max(counts, key=counts.get)  # The most likely outcome
    if measured_result == '0' * n_qubits:
        print("Conclusion: f(x) is CONSTANT.")
    else:
        print("Conclusion: f(x) is BALANCED.")

5. Example Runs

# Test with 3 qubits
run_deutsch_jozsa_test(n_qubits=3, oracle_type='constant', constant_output=0)
print("\n" + "="*50 + "\n")
run_deutsch_jozsa_test(n_qubits=3, oracle_type='balanced')

Output:

Using a CONSTANT oracle that always returns 0
     ┌───┐┌───┐┌─┐      
q_0: ┤ H ├┤ H ├┤M├──────
     ├───┤├───┤└╥┘┌─┐   
q_1: ┤ H ├┤ H ├─╫─┤M├───
     ├───┤├───┤ ║ └╥┘┌─┐
q_2: ┤ H ├┤ H ├─╫──╫─┤M├
     ├───┤├───┤ ║  ║ └╥┘
q_3: ┤ X ├┤ H ├─╫──╫──╫─
     └───┘└───┘ ║  ║  ║ 
c: 3/═══════════╩══╩══╩═
                0  1  2 
Measurement outcomes: {'000': 1}
Conclusion: f(x) is CONSTANT.

==================================================

Using a BALANCED oracle.
     ┌───┐          ┌───┐   ┌─┐
q_0: ┤ H ├───────■──┤ H ├───┤M├
     ├───┤┌───┐  │  └┬─┬┘   └╥┘
q_1: ┤ H ├┤ H ├──┼───┤M├─────╫─
     ├───┤├───┤  │   └╥┘ ┌─┐ ║ 
q_2: ┤ H ├┤ H ├──┼────╫──┤M├─╫─
     ├───┤├───┤┌─┴─┐  ║  └╥┘ ║ 
q_3: ┤ X ├┤ H ├┤ X ├──╫───╫──╫─
     └───┘└───┘└───┘  ║   ║  ║ 
c: 3/═════════════════╩═══╩══╩═
                      1   2  0 
Measurement outcomes: {'001': 1}
Conclusion: f(x) is BALANCED.

Explanation of the Code

1. Importing Libraries

We use Qiskit’s core elements:

• QuantumCircuit to build quantum circuits
• Aer, transpile and run to run our circuit on a classical simulator

2. Creating the Oracles

• Constant Oracle: Returns the same value (0 or 1) for every possible input. In code, we flip the output qubit if the oracle should always return 1.
• Balanced Oracle: Returns 0 for half the inputs and 1 for the other half. Our example uses a CNOT gate (cx), which flips the output qubit when the first input qubit is 1.

3. Building the Deutsch–Jozsa Circuit

1. We start with all input qubits in the state $\vert 0\rangle$. The output qubit is put in state $\vert 1\rangle$ by applying an X gate.
2. We apply Hadamard gates (dj_circuit.h(qubit)) to all qubits. Recall that the Hadamard gate spreads the amplitudes “evenly” between $\vert 0\rangle$ and $\vert 1\rangle$, creating superpositions.
3. We attach the oracle circuit, which modifies the output qubit according to the function (f).
4. We apply the Hadamard gate again only to the input qubits, causing the interference pattern that will reveal whether (f) is constant or balanced.
5. Finally, we measure all input qubits.

4. Interpreting the Results

1. If (f) is constant, the circuit produces the output $\vert 0...0\rangle$ (all zeros in the measurement) with 100% probability.
2. If (f) is balanced, we expect to see any other pattern in the measurement (i.e., not all zeros).

5. Running the Algorithm

We run the circuit using Aer’s built-in aer_simulator. Because the Deutsch–Jozsa algorithm only needs one execution (one set of shots) to distinguish between constant and balanced with 100% certainty, running multiple shots will always yield the same outcome.

---

Why It’s Faster Than a Classical Deterministic Computer

Classically, you might have to “call” the function (f) (our “mystery” black box) many times—potentially up to (2^{n-1}+1) times—to be absolutely sure if it is constant or balanced. However, the quantum version of this problem can be solved with just one call to the oracle plus some extra quantum gates. Although Deutsch–Jozsa itself is considered more of a “teaching example” than a practical application, it demonstrates one of the key ideas of quantum algorithms: leveraging superposition and interference to reduce the number of required function calls dramatically.

See also

• Bernstein–Vazirani algorithm

External links

• Deutsch's lecture about the Deutsch-Jozsa algorithm