Exponential speedup with the Deutsch-Jozsa algorithm¶
Introduction¶
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 exponential speedup is in the oracle complexity setting. In addition, it only refers to determenistic classical machines (see comments below).
The algorithm treats the following problem:
- Consider a black-box boolean function $f(x)$ which acts on the integers in the range $[0, 2^{n}-1]$.
- It is guaranteed that the function is either constant or balanced ($\equiv$ for half of the values it is 1 and for the other half 0).
- The goal is to find in a deterministic way whether the function is constant or balanced.
Let us start with an example with $n=4$. We load an arithmetic expression on the numbers between 0 to $2^4-1=15$.
import urllib
expr = (
urllib.request.urlopen(
"https://classiq-docs-images.s3.amazonaws.com/simple_black_box.txt"
)
.read()
.decode("utf-8")
)
black_box_expression = expr.split("\n")[0]
Classicaly, in the worst case, we will have to evaluate the function $2^{n-1}+1=9$ times. Let us do this:
import sympy as sm
from sympy.parsing.sympy_parser import parse_expr
x = sm.symbols("x")
expr = parse_expr(black_box_expression, evaluate=0)
for k in range(2**4 // 2 + 1):
print(expr.subs(x, k))
We found out that the function is not constant, hance, it musy be balanced. Let us now move to the quantum algorithm. We go directly to the implementation of the algorithm, where the mathematical explanation will be given at the end of this demo. The Duetsch-Jozsa algorithm is composed of three function blocks: it starts with an Hadamard transform, continues with an arithmetic oracle for the black-box function, and ends with another Hadamard transform.
The probability of measuring the $|0\rangle_n$ state is 1 if the function is constant and 0 if it is balanced.
The black-box function is thus evaluated only once when implementing the oracle: this is exponentially more efficient than the classical approach.
Let us code this with Classiq in a one code block
from classiq import Model, RegisterUserInput, execute, show, synthesize
from classiq.builtin_functions import ArithmeticOracle, HadamardTransform
N = 4
# model
model = Model()
hadamard_params = HadamardTransform(num_qubits=N)
out = model.HadamardTransform(params=hadamard_params)
params = ArithmeticOracle(
expression=black_box_expression,
definitions=dict(
x=RegisterUserInput(size=N),
),
uncomputation_method="optimized",
)
arith_out = model.ArithmeticOracle(params, in_wires={"x": out["OUT"]})
out = model.HadamardTransform(params=hadamard_params, in_wires={"IN": arith_out["x"]})
model.set_outputs({"OUT": out["OUT"]})
model.sample()
# synthesize
qprog = synthesize(model.get_model())
# execute
results = execute(qprog).result()
results_list = [sample.state["OUT"] for sample in results[0].value.parsed_counts]
# output the result
if len(results_list) == 1:
if 0 not in results_list:
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:",
results[0].value.counts_of_output("OUT"),
)
with open("simple_deutsch_jozsa.qmod", "w") as f:
f.write(model.get_model())
show(qprog)
In the above example, we worked with a very simple black-box function
print(black_box_expression)
However, generalizing to much more complex scenarios makes no difference for modeling. Let us take a more complicated function, working with $n=3$: we take the maximum between the input Bitwise-Xor with 3 and the input Bitwise-And with 3, we then perform 2 Right-Bit-Shift, and check whether the result is equal to 1. Can you tell whether the function is balanced or constant?
This time we provide a width bound to the Synthesis engine
expression = "(max(x ^ 3, x & 3)>>2) == 1"
from classiq.model import Constraints
N = 3
# model
model = Model()
hadamard_params = HadamardTransform(num_qubits=N)
out = model.HadamardTransform(params=hadamard_params)
params = ArithmeticOracle(
expression=expression,
definitions=dict(
x=RegisterUserInput(size=N),
),
uncomputation_method="optimized",
)
arith_out = model.ArithmeticOracle(params, in_wires={"x": out["OUT"]})
out = model.HadamardTransform(params=hadamard_params, in_wires={"IN": arith_out["x"]})
model.set_outputs({"OUT": out["OUT"]})
model.constraints = Constraints(max_width=15)
model.sample()
# synthesize
qprog = synthesize(model.get_model())
# execute
results = execute(qprog).result()
results_list = [sample.state["OUT"] for sample in results[0].value.parsed_counts]
# output the result
if len(results_list) == 1:
if 0 not in results_list:
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:",
results[0].value.counts_of_output("OUT"),
)
We can visualize the circuit obtained from the synthesis engine. In Figure 2 we present the complex structure of the oracle, generated automatically by the Synthesis engine.
show(qprog)
with open("complex_deutsch_jozsa.qmod", "w") as f:
f.write(model.get_model())
Mathematical explanation¶
Below we briefly go over 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, we apply 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| $, to find $$ \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}|j\rangle \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)}|j\rangle \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. $$
Comments¶
If we do not require deterministic determination, namely, we can apply classical probabilistic algorithm to get the result up to some error, then we lose the exponential speedup: taking $k$ classical evaluations of the function $f$ determines whether the function is constant or balanced, with a probability $1-1/2^k$.