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,
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
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:
Arithmetic oracle gets a boolean function and adds an \(e^{\pi i}=-1\) phase to all states for which the function returns True:
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} \sum^{2^n-1}}(-1)^{f(j)}|j\rangle \xrightarrow[H^{\otimes n}]{{k=0} \left(\frac{1}{2^{n}}\sum^{2^n-1} \right) |k\rangle.}(-1)^{f(j)+j\cdot k
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. $$