Deutsch-Jozsa Algorithm
The Deutsch-Jozsa algorithm [1], named after David Deutsch and Richard Jozsa, is one of the first fundamental quantum algorithms showing exponential speedup over its classical counterpart\(^*\). While it has no practical applicative use, it serves as a toy model for quantum computing, demonstrating how the concepts of superposition and interference enable quantum algorithms to outperform 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. It only refers to deterministic classical machines.
Problem hardness: If we require a deterministic answer to the problem, classically, we have to inquire of 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 the 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 of \(1-1/2^k\)).
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 define 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 comprising 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 *
@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:
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 the 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\). Classically, 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 build a predicate for this 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:
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, out_file="simple_deutsch_jozsa")
qprog = synthesize(qmod)
Finally, we execute and call the classical postprocess:
result = execute(qprog).result_value()
results_list = [sample.state["x"] for sample in result.parsed_counts]
post_process_deutsch_jozsa(results_list)
The function is balanced
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.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, out_file="complex_deutsch_jozsa")
qmod = set_constraints(qmod, constraints=Constraints(max_width=19))
qprog = synthesize(qmod)
result = execute(qprog).result_value()
results_list = [sample.state["x"] for sample in result.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
Technical Notes
A brief summary of the linear algebra behind the Deutsch-Jozsa algorithm. The first Hadamard transformation generates an equal superposition over all the standard basis elements:
The arithmetic oracle gets a Boolean function and adds an \(e^{\pi i}=-1\) phase to all states for which the function returns true:
Finally, applying 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
The probability of getting the state \(|k\rangle = |0\rangle\) is