The Deutsch–Jozsa algorithm is one of the most famous algorithms in quantum computing. The problem it solves has little practical value, but the algorithm itself is one of the earliest examples of a quantum algorithm that is exponentially faster than any possible deterministic algorithm for the same problem. It is also relatively simple to explain and illustrates several very important concepts (such as quantum oracles). As such, Deutsch–Jozsa algorithm is part of almost every introductory course on quantum computing.
This tutorial will:
Let's go!
This tutorial consists of several notebooks:
You are given a classical function $f(x): \{0, 1\}^N \to \{0, 1\}$. You are guaranteed that the function $f$ is
The task is to figure out whether the function is constant or balanced.
For the single-bit functions ($N = 1$) the problem can be formulated in a simpler way: given a classical function $f(x): \{0, 1\} \to \{0, 1\}$, figure out whether $f(0) = f(1)$. Indeed, $f(0) = f(1)$ is an equivalent definition of a constant single-bit function, and $f(0) \neq f(1)$ - of a balanced single-bit function.
Examples¶
- $f(x) \equiv 0$ or $f(x) \equiv 1$ are examples of constant functions (and they are actually the only constant functions in existence).
- For single-bit functions, $f(x) = x$ and $f(x) = 1 - x$ are the only existing balanced functions.
- $f(x) = x \bmod 2$ (the least significant bit of $x$) or $f(x) = 1 \text{ if the binary notation of }x \text{ has odd number of 1s and 0 otherwise}$ are examples of multi-bit balanced functions.
Indeed, for both these functions you can check that for every possible input $x$ for which $f(x) = 0$ there exists an input $x^\prime$ (equal to $x$ with the least significant bit flipped) such that $f(x^\prime) = 1$, and vice versa, which means that the function is balanced.There exist more complicated examples of balanced functions, but we will not need to consider them for this tutorial.
Here is the implementation of these functions in Q#; it is pretty self-descriptive, since the functions are not only very simple but also classical.
Note: These are just code samples, you don't have to modify the code and they are not covered by tests.
// Function 1. f(x) = 0
function Function_Zero (x : Int) : Int {
return 0;
}
// Function 2. f(x) = 1
function Function_One (x : Int) : Int {
return 1;
}
// Function 3. f(x) = x mod 2 (least significant bit of x)
function Function_Xmod2 (x : Int) : Int {
return x % 2;
}
// Function 4. f(x) = 1 if the binary notation of x has odd number of 1s, and 0 otherwise
function Function_OddNumberOfOnes (x : Int) : Int {
mutable nOnes = 0;
mutable xBits = x;
while (xBits > 0) {
if xBits % 2 > 0 {
set nOnes += 1;
}
set xBits /= 2;
}
return nOnes % 2;
}
Try to implement a similar classical function in Q#!
Inputs:
Output: Return $f(x) = \text{the most significant bit of }x$.
Useful documentation: Q# Bitwise Expressions.
%kata T1_ClassicalFunction
function Function_MostSignificantBit (x : Int, N : Int) : Int {
// ...
}
If we solve this problem classically, how many calls to the given function will we need?
The first call will give us no information - regardless of whether it returns 0 or 1, the function could still be constant or balanced. In the best case scenario the second call will return a different value and we'll be able to conclude that the function is balanced in just $2$ calls. However, if we get the same value for the first two calls, we'll have to keep querying the function until either we get a different value or until we do $2^{N-1}+1$ queries that will return the same value - in this case we'll know for certain that the function will be constant.
Q# is a domain-specific language, so it is not designed to handle arbitrary classical computations. However, this classical algorithm is so simple that you can easily implement it in Q#. Try it!
Inputs:
You are guaranteed that the function implemented by the black box is either constant or balanced.
Goal: Return true
if the function is constant, or false
if it is balanced.
Useful documentation: Q# statements.
%kata T2_ClassicalAlgorithm
operation IsFunctionConstant_Classical (N : Int, f : (Int -> Int)) : Bool {
// ...
}
Continue to part II to learn about single-qubit quantum oracles and Deutsch algorithm for solving the problem for one-bit input functions.