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.

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,
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(within=lambda: prep_minus(aux), apply=lambda: predicate(target, aux))

@qfunc
def deutsch_jozsa(predicate: QCallable[QNum, QBit], x: QNum) -> None:
my_oracle(predicate=lambda x, y: predicate(x, y), target=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


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=0}|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,l=0}(-1)^{k\cdot l} |k\rangle \langle l|$, gives

$\frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}(-1)^{f(j)}|j\rangle \xrightarrow[H^{\otimes n}]{} \sum^{2^n-1}_{k=0} \left(\frac{1}{2^{n}}\sum^{2^n-1}_{j=0}(-1)^{f(j)+j\cdot k} \right) |k\rangle.$

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.$