The Deutsch–Jozsa algorithm quantum kata is a series of exercises designed to get you familiar with programming in Q#.
It covers the following topics:
You can read more about the quantum oracles, Deutsch and Deutsch-Jozsa algorithms in the ExploringDeutschJozsaAlgorithm tutorial.
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blanks (marked with // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell with Ctrl+Enter (⌘+Enter on macOS).
In this section you will implement oracles defined by classical functions using the following rules:
You can read more about quantum oracles in Q# documentation.
Inputs:
Goal: transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2).
%kata T11_Oracle_Zero
operation Oracle_Zero (x : Qubit[], y : Qubit) : Unit {
// Since f(x) = 0 for all values of x, |y ⊕ f(x)⟩ = |y⟩.
// This means that the operation doesn't need to do any transformation to the inputs.
// Run the cell (using Ctrl/⌘ + Enter) to see that the test passes.
}
Inputs:
Goal: transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2).
%kata T12_Oracle_One
operation Oracle_One (x : Qubit[], y : Qubit) : Unit {
// ...
}
Inputs:
Goal: transform state $|x, y\rangle$ into state $|x, y \oplus x_k\rangle$ ($\oplus$ is addition modulo 2).
%kata T13_Oracle_Kth_Qubit
open Microsoft.Quantum.Diagnostics;
operation Oracle_Kth_Qubit (x : Qubit[], y : Qubit, k : Int) : Unit {
// The following line enforces the constraints on the value of k that you are given.
// You don't need to modify it. Feel free to remove it, this won't cause your code to fail.
EqualityFactB(0 <= k and k < Length(x), true, "k should be between 0 and N-1, inclusive");
// ...
}
Inputs:
Goal: transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2).
%kata T14_Oracle_OddNumberOfOnes
operation Oracle_OddNumberOfOnes (x : Qubit[], y : Qubit) : Unit {
// ...
}
Inputs:
Int[]
.
You are guaranteed that the qubit array and the bit vector have the same length.Goal: transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2).
%kata T15_Oracle_ProductFunction
open Microsoft.Quantum.Diagnostics;
operation Oracle_ProductFunction (x : Qubit[], y : Qubit, r : Int[]) : Unit {
// The following line enforces the constraint on the input arrays.
// You don't need to modify it. Feel free to remove it, this won't cause your code to fail.
EqualityFactI(Length(x), Length(r), "Arrays should have the same length");
// ...
}
Inputs:
Int[]
.
You are guaranteed that the qubit array and the bit vector have the same length.Goal: transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2).
%kata T16_Oracle_ProductWithNegationFunction
open Microsoft.Quantum.Diagnostics;
operation Oracle_ProductWithNegationFunction (x : Qubit[], y : Qubit, r : Int[]) : Unit {
// The following line enforces the constraint on the input arrays.
// You don't need to modify it. Feel free to remove it, this won't cause your code to fail.
EqualityFactI(Length(x), Length(r), "Arrays should have the same length");
// ...
}
Inputs:
Int[]
($1 \le K \le N$).Goal: transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2).
A prefix of length K of a state $|x\rangle = |x_0, ..., x_{N-1}\rangle$ is the state of its first K qubits $|x_0, ..., x_{K-1}\rangle$. For example, a prefix of length 2 of a state $|0110\rangle$ is 01.
%kata T17_Oracle_HammingWithPrefix
open Microsoft.Quantum.Diagnostics;
operation Oracle_HammingWithPrefix (x : Qubit[], y : Qubit, prefix : Int[]) : Unit {
// The following line enforces the constraint on the input arrays.
// You don't need to modify it. Feel free to remove it, this won't cause your code to fail.
let K = Length(prefix);
EqualityFactB(1 <= K and K <= Length(x), true, "K should be between 1 and N, inclusive");
// ...
}
Inputs:
Goal: transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2).
%kata T18_Oracle_MajorityFunction
open Microsoft.Quantum.Diagnostics;
operation Oracle_MajorityFunction (x : Qubit[], y : Qubit) : Unit {
// The following line enforces the constraint on the input array.
// You don't need to modify it. Feel free to remove it, this won't cause your code to fail.
EqualityFactI(3, Length(x), "x should have exactly 3 qubits");
// ...
}
In this section you will implement the Deutsch-Jozsa algorithm and run it on the oracles you've defined in part I to observe the results.
This algorithm solves the following problem. You are given a quantum oracle which implements a classical function $f(x): \{0, 1\}^N \to \{0, 1\}$. You are guaranteed that the function $f$ is either constant (has the same value for all inputs) or balanced (has value 0 for half of the inputs and 1 for the other half of the inputs). The goal of the algorithm is to figure out whether the function is constant or balanced in just one oracle call.
Inputs:
Goal:
%kata T21_DJ_StatePrep
operation DJ_StatePrep (query : Qubit[], answer : Qubit) : Unit is Adj {
// ...
}
Inputs:
Output: true
if the function f is constant, or false
if the function f is balanced.
%kata T22_DJ_Algorithm
operation DJ_Algorithm (N : Int, oracle : ((Qubit[], Qubit) => Unit)) : Bool {
// Create a boolean variable for storing the return value.
// You'll need to update it later, so it has to be declared as mutable.
// ...
// Allocate an array of N qubits for the input register x and one qubit for the answer register y.
use (x, y) = (Qubit[N], Qubit());
// Newly allocated qubits start in the |0⟩ state.
// The first step is to prepare the qubits in the required state before calling the oracle.
// Each qubit of the input register has to be in the |+⟩ state.
// ...
// The answer register has to be in the |-⟩ state.
// ...
// Apply the oracle to the input register and the answer register.
// ...
// Apply a Hadamard gate to each qubit of the input register again.
// ...
// Measure each qubit of the input register in the computational basis using the M operation.
// If any of the measurement results is One, the function implemented by the oracle is balanced.
// ...
// Before releasing the qubits make sure they are all in the |0⟩ state.
// ...
// Return the answer.
// ...
}
Goal: Use your implementation of Deutsch-Jozsa algorithm from task 2.1 to test each of the oracles you've implemented in part I for being constant or balanced.
This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the
Run_DeutschJozsa_Algorithm
operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (%simulate Run_DeutschJozsa_Algorithm
).
Note that this task relies on your implementations of the previous tasks. If you are getting the "No variable with that name exists." error, you might have to execute previous code cells before retrying this task.
open Microsoft.Quantum.Diagnostics;
operation Run_DeutschJozsa_Algorithm () : String {
// You can use the Fact function to check that the return value of DJ_Algorithm operation matches the expected value.
// Uncomment the next line to test the algorithm on the oracle for f(x) = 0.
// Fact(DJ_Algorithm(4, Oracle_Zero), "f(x) = 0 not identified as constant");
// Run the algorithm for the rest of the oracles
// ...
// If all tests pass, report success!
return "Success!";
}
%simulate Run_DeutschJozsa_Algorithm
In this section you will implement the Bernstein-Vazirani algorithm and run it on the oracles you've defined in part I to observe the results.
This algorithm solves the following problem. You are given a quantum oracle which implements a classical function $f(x): \{0, 1\}^N \to \{0, 1\}$. You are guaranteed that the function $f$ can be represented as a scalar product, i.e., there exists a bit vector $r = (r_0, ..., r_{N-1})$ such that $f(x) = \bigoplus \limits_{i=0}^{N-1} x_i r_i$. The goal of the algorithm is to reconstruct the bit vector $r$ in just one oracle call.
You can read more about the Bernstein-Vazirani algorithm in "Quantum Algorithm Implementations for Beginners", section III.
Inputs:
Output: The bit vector $r$ reconstructed from the oracle.
%kata T31_BV_Algorithm
operation BV_Algorithm (N : Int, oracle : ((Qubit[], Qubit) => Unit)) : Int[] {
// The algorithm is very similar to Deutsch-Jozsa algorithm; try to implement it without hints.
// ...
}
Goal: Use your implementation of Bernstein-Vazirani algorithm from task 3.1 to reconstruct the hidden vector $r$ for the oracles you've implemented in part I.
This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the
Run_BernsteinVazirani_Algorithm
operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (%simulate Run_BernsteinVazirani_Algorithm
).
Note that this task relies on your implementations of the previous tasks. If you are getting the "No variable with that name exists." error, you might have to execute previous code cells before retrying this task.
open Microsoft.Quantum.Diagnostics;
operation Run_BernsteinVazirani_Algorithm () : String {
// Now use the library function AllEqualityFactI in Microsoft.Quantum.Diagnostics to verify the results of the algorithm.
// Uncomment the following lines to test the algorithm on the oracle for f(x) = 0.
// AllEqualityFactI(BV_Algorithm(3, Oracle_Zero), [0, 0, 0], "Incorrect result for f(x) = 0");
// Run the algorithm on the rest of the oracles
// ...
// If all tests pass, report success!
return "Success!";
}
%simulate Run_BernsteinVazirani_Algorithm
In this section you will come up with your own algorithm to solve a problem similar to the one described in part III.
The problem is formulated as follows. You are given a quantum oracle which implements a classical function $f(x): \{0, 1\}^N \to \{0, 1\}$. You are guaranteed that there exists a bit vector $r = (r_0, ..., r_{N-1})$ such that the function $f$ can be represented as follows: $f(x) = \bigoplus \limits_{i=0}^{N-1} \left( x_i r_i + (1 - x_i)(1 - r_i) \right)$. You have to reconstruct the bit vector $r$ in just one oracle call.
Note that you have implemented the oracle for this function in task 1.6.
Inputs:
Output: Any bit vector $r$ that would generate the same oracle as the one you are given.
%kata T41_Noname_Algorithm
operation Noname_Algorithm (N : Int, oracle : ((Qubit[], Qubit) => Unit)) : Int[] {
// The algorithm is very similar to Bernstein-Vazirani algorithm; try to implement it without hints.
// ...
}