Skip to content

Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm [1], named after David Deutsch and Richard Jozsa, is one of the fundamental and first quantum algorithms showing exponential speedup over their classical counterpart\(^*\). While it has no practical applicative usage, it serves as a toy model for quantum computing, demonstrating how the concepts of super-position and interference enable quantum algorithms to overperform classical ones.

The algorithm treats the following problem:

  • Input: A black-box boolean function \(f(x)\) that acts on the integers in the range \([0, 2^{n}-1]\).

  • Promise: The function is either constant or balanced (for half of the values it is 1 and for the other half it is 0).

  • Output: Whether the function is constant or balanced.

\(^*\) The exponential speedup is in the oracle complexity setting. In addition, it only refers to deterministic classical machines.


Problem hardeness: If we require a deterministic answer to the problem, classically, we have to inquire the oracle \(2^{n-1}+1\) times in the worst case. The quantum approach requires a single query, thus, introducing a clear exponential speedup. (Without requiring deterministic determination, namely, allowing application of classical probabilistic algorithm to get the result up to some error, then the exponential speedup is lost: taking \(k\) classical evaluations of the function \(f\) determines whether the function is constant or balanced, with a probability \(1-1/2^k\)).

Next, we define the Deutsch-Jozsa algorithm, which has a quantum part and a classical postprocess part. Then, we run the algorithm on two different examples, one with a simple \(f(x)\) and another that is more complex. A mathematical explanation of the algorithm is provided at the end of this notebook.

Figure 1. The Deutsch-Jozsa algorithm

How to Build the Algorithm with Classiq

We start with defining a deutsch_jozsa quantum function, whose arguments are a quantum function for the black-box \(f(x)\), and a quantum variable on which it acts, \(x\). The Deutsch-Jozsa algorithm is composed of three quantum blocks (see Figure 1): a Hadamard transform, an arithmetic oracle for the black-box function, and another Hadamard transform.

The Quantum Part

from classiq import (
    H,
    Output,
    QBit,
    QCallable,
    QNum,
    X,
    allocate,
    hadamard_transform,
    qfunc,
    within_apply,
    write_qmod,
)


@qfunc
def prep_minus(out: Output[QBit]) -> None:
    allocate(1, out)
    X(out)
    H(out)


@qfunc
def my_oracle(predicate: QCallable[QNum, QBit], target: QNum) -> None:
    aux = QBit("aux")
    within_apply(compute=lambda: prep_minus(aux), action=lambda: predicate(target, aux))


@qfunc
def deutsch_jozsa(predicate: QCallable[QNum, QBit], x: QNum) -> None:
    hadamard_transform(x)
    my_oracle(predicate=lambda x, y: predicate(x, y), target=x)
    hadamard_transform(x)

The Classical Postprocess

The classical part of the algorithm reads: The probability of measuring the \(|0\rangle_n\) state is 1 if the function is constant and 0 if it is balanced. We define a classical function that gets the execution results from running quantum part and returns whether the function is constant or balanced:

def post_process_deutsch_jozsa(parsed_results):
    if len(parsed_results) == 1:
        if 0 not in parsed_results:
            print("The function is balanced")
        else:
            print("The function is constant")
    else:
        print(
            "cannot decide as more than one output was measured, the distribution is:",
            parsed_results,
        )

Example: Simple Arithmetic Oracle

We start with a simple example on \(n=4\) qubits, and \(f(x)= x >7\). Classicaly, in the worst case, the function should be evaluated \(2^{n-1}+1=9\) times. However, with the Deutsch-Jozsa algorithm, this function is evaluated only once.

We need to build a predicate for the specific use case:

@qfunc
def simple_predicate(x: QNum, res: QBit) -> None:
    res ^= x > 7

Next, we define a model by inserting the predicate into the deutsch_jozsa function:

from classiq import create_model, show, synthesize

NUM_QUBITS = 4


@qfunc
def main(x: Output[QNum]):
    allocate(NUM_QUBITS, x)
    deutsch_jozsa(lambda x, y: simple_predicate(x, y), x)


qmod = create_model(main)
qprog = synthesize(qmod)

Finally, we execute and call the classical post process:

from classiq import execute

results = execute(qprog).result()
results_list = [sample.state["x"] for sample in results[0].value.parsed_counts]
post_process_deutsch_jozsa(results_list)
The function is balanced
write_qmod(qmod, "simple_deutsch_jozsa")
show(qprog)
Opening: https://platform.classiq.io/circuit/5d59d5f5-4087-48c0-b873-a04a2b10bdb0?version=0.41.0.dev39%2B79c8fd0855

Example: Complex Arithmetic Oracle

Generalizing to more complex scenarios makes no difference for modeling. Let us take a complicated function, working with \(n=3\): a function \(f(x)\) that first takes the maximum between the input Bitwise-Xor with 4 and the input Bitwise-And with 3, then checks whether the result is greater or equal to 4. Can you tell whether the function is balanced or constant?

This time we provide a width bound to the Synthesis engine.

We follow the three steps as before:

from classiq import Constraints, Input, QArray, set_constraints
from classiq.qmod.symbolic import max

NUM_QUBITS = 3


@qfunc
def complex_predicate(x: QNum, res: QBit) -> None:
    res ^= max(x ^ 4, x & 3) >= 4


@qfunc
def main(x: Output[QNum]):
    allocate(NUM_QUBITS, x)
    deutsch_jozsa(lambda x, y: complex_predicate(x, y), x)


qmod = create_model(main)
qmod = set_constraints(qmod, constraints=Constraints(max_width=19))
qprog = synthesize(qmod)

results = execute(qprog).result()
results_list = [sample.state["x"] for sample in results[0].value.parsed_counts]
post_process_deutsch_jozsa(results_list)
The function is balanced

Figure 2. The Deutsch-Jozsa algorithm for the complex example, focusing on oracle implementation

We can visualize the circuit obtained from the synthesis engine. Figure 2 presents the complex structure of the oracle, generated automatically by the Synthesis engine.

show(qprog)
Opening: https://platform.classiq.io/circuit/1b14df30-4d91-4a5f-9749-73741ccaca38?version=0.41.0.dev39%2B79c8fd0855
write_qmod(qmod, "complex_deutsch_jozsa")

Technical Notes

A brief summary of the linear algebra behind the Deutsch-Jozsa algorithm. The first Hadamard transformation generates an equal super-position over all the standard basis elements: $$ |0\rangle_n \xrightarrow[H^{\otimes n}]{} \frac{1}{2^{n/2}}\sum^{2^n-1}{j=0}|j\rangle_n. $$ Arithmetic oracle gets a boolean function and adds an \(e^{\pi i}=-1\) phase to all states for which the function returns True: $$ \frac{1}{2^{n/2}}\sum^{2^n-1}}|j\rangle_n \xrightarrow[\text{Oracle}(f(j))]{}\frac{1}{2^{n/2}}\sum^{2^n-1{j=0}(-1)^{f(j)}|j\rangle_n. $$ Finally, application of the Hadamard transform, which can be written as $H^{\otimes n}\equiv \frac{1}{2^{n/2}}\sum^{2^n-1} |k\rangle \langle l| $, gives $$ \frac{1}{2^{n/2}}\sum^{2^n-1}}(-1)^{k\cdot l{j=0}(-1)^{f(j)}|j\rangle \xrightarrow[H^{\otimes n}]{} \sum^{2^n-1} \right) |k\rangle. $$} \left(\frac{1}{2^{n}}\sum^{2^n-1}_{j=0}(-1)^{f(j)+j\cdot k

The probability of getting the state \(|k\rangle = |0\rangle\) is $$ P(0)=\left|\frac{1}{2^{n}}\sum^{2^n-1}_{j=0}(-1)^{f(j)} \right|^2 = \left{ \begin{array}{l l} 1 & \text{if } f(x) \text{ is constant} \ 0 & \text{if } f(x) \text{ is balanced} \end{array} \right. $$

References

[1]: Deutsch Jozsa (Wikipedia)