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: http://localhost:4200/circuit/09d1e7fc-31ee-4f69-9188-1c579464dc52?version=0.0.0
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: http://localhost:4200/circuit/bd89fe64-2fba-4d50-b765-f2ca72c38d1d?version=0.0.0
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. $$