Grover's search algorithm is one of the most famous algorithms in quantum computing. The problem it solves is often referred to as "searching a database", but it is more accurate to think of it as "inverting a function". The algorithm can have practical value when applied on its own, but it can also be generalized and used as a building block for other algorithms. As such, Grover's algorithm is part of almost every introductory course on quantum computing.
This tutorial will:
In the last section of the tutorial you will continue exploration of Grover's algorithm in a companion Python notebook that will use the code we've written to build some interesting graphs and finish the discussion.
Grover's algorithm is a massive topic that can hardly be covered in a single tutorial. This tutorial will not:
Let's go!
You are given a classical function $f(x): \{0, 1\}^N \to \{0, 1\}$. The task is to find an input $x_0$ for which $f(x_0) = 1$.
Boolean satisfiability problem (abbreviated as SAT problem) is a problem of finding an assignment of values to boolean variables that satisfies a given boolean formula or determining that such assignment does not exist.
The input $x$ is the set of $N$ boolean variables $(x_0, x_1, ..., x_{N-1})$, each of which can be assigned value 0 (false) or 1 (true).
The function $f(x)$ is represented as a conjunction (an AND operation, denoted as $\wedge$) of $M$ clauses. Each clause is a disjunction (an OR operation, denoted as $\vee$) of one or several variables $x_j$ or negated variables $\neg x_j$:
$$f(x) = \bigwedge_i \big(\bigvee_k y_{ik} \big),\text{ where }y_{ik} =\text{ either }x_j\text{ or }\neg x_j\text{ for some }j \in \{0, \dots, N-1\}$$As an small example of a SAT problem, consider the following formula: $$f(x_0, x_1) = x_0 \wedge (\neg x_0 \vee \neg x_1)$$
- For the formula to be satisfied (i.e., to have $f(x)$ evaluate to true), both clauses have to evaluate to true.
- The first clause is simply $x_0$, so we know that $x_0$ has to be true.
- The second clause is $\neg x_0 \vee \neg x_1$, which can be true if either of $x_0$ or $x_1$ is false;
since we know that $x_0$ has to be true, $x_1$ has to be false.
- We conclude that the formula can be satisfied using the variables assignment $x = (true, false)$.
SAT problem is an excellent match for Grover's search algorithm: it maps naturally to the description of the problem solved by the algorithm, and can be implemented relatively easily using quantum gates. For more details on implementing instances of SAT problem as quantum oracles, see SolveSATWithGrover quantum kata.
In our Q# code, we will represent an instance of SAT problem as a 2-dimensional array of tuples problem
in the following format:
problem
describes the $i$-th clause of $f(x)$;it is an array of one or more tuples, each of them describing one literal of the clause.
(Int, Bool)
pair: the first element is the index $j$ of the variable $x_j$, and the second element is true
if the variable is included as itself ($x_j$) and false
if it is included as a negation ($\neg x_j$)The example of a SAT problem we considered earlier, $f(x_0, x_1) = x_0 \wedge (\neg x_0 \vee \neg x_1)$, is represented in this format as [[(0, true)], [(0, false), (1, false)]]
.
You can use a Q# function SATInstanceAsString
to convert the array representation of a SAT instance to a string representation of the formula. Try it out!
SATInstanceAsString
on one example of SAT problem.SATInstanceAsString
on other instances of SAT problem.
- All exercises in this tutorial are implemented as pairs of code cells: the first code cell defines the code you want to execute, and the second cell executes this code.
- You can run and re-run each cell using
Ctrl+Enter
(or⌘+Enter
on a Mac).- Any compilation errors will be reported when you run the first cell, any runtime errors - when you run the second cell.
- You can turn on line numbers in the code cells using
View > Toggle Line Numbers
menu.
Here are some interesting SAT instances with 3 variables that you might want to use later in the tutorial:
- $f_1(x) = (x_0) \wedge (\neg x_0 \vee \neg x_1) \wedge (x_1 \vee x_2)$ (1 solution):
`[[(0, true)], [(0, false), (1, false)], [(1, true), (2, true)]]`
- $f_2(x) = (x_0 \vee x_1) \wedge (\neg x_0 \vee \neg x_1) \wedge (x_1 \vee x_2) \wedge (\neg x_1 \vee \neg x_2)$ (2 solutions):
`[[(0, true), (1, true)], [(0, false), (1, false)], [(1, true), (2, true)], [(1, false), (2, false)]]`
- $f_3(x) = (\neg x_1) \wedge (x_0 \vee x_2)$ (3 solutions):
`[[(1, false)], [(0, true), (2, true)]]`
- $f_4(x) = (x_0 \vee x_1) \wedge (\neg x_0 \vee \neg x_1)$ (4 solutions):
`[[(0, true), (1, true)], [(0, false), (1, false)]]`
// This namespace contains helpful operations for you to use during the tutorial
open Quantum.Kata.ExploringGroversAlgorithm;
function ConvertSATInstanceToString () : Unit {
// Function "Message" prints its string argument to the output
Message(SATInstanceAsString( [[(0, true)], [(0, false), (1, false)]] ));
}
%simulate ConvertSATInstanceToString
If we solve this problem classically, how many evaluations of the given function will we need?
If we don't know anything about the internal structure of the function, we can not do better than try evaluating the function on different inputs until we either hit one which produces the desired output or try all inputs and conclude that the desired input doesn't exist. This requires $O(2^N)$ function evaluations, since in the worst case scenario we'll need to try all inputs.
You are given the number of bits in the function input $N$ and the quantum oracle - a "black box" quantum operation $U_f$ that implements a classical function $f(x)$. The oracle $U_f$ is defined by its effect on the individual inputs ("basis states"): if the value of the function on the input register $\vec{x}$ $f(x) = 1$, the state of the output $y$ is flipped (0 becomes 1 and vice versa). Formally this can be written as follows:
$$U_f |\vec{x} \rangle |y\rangle = |\vec{x} \rangle |y \oplus f(x) \rangle$$The oracle is implemented in a way which allows to perform calculations not only on individual inputs, but also on superpositions of inputs. The details of this implementation are outside of the scope of this tutorial, but this implementation is the key that makes Grover's algorithm possible.
The high-level outline of the algorithm is very simple:
In this tutorial we will use pre-written implementation of the well-known sections of the algorithm (including the actual quantum operations). This will allow us to focus on the more interesting nuances of the algorithm and applying it to solving problems.
Let's start with the most basic implementation of Grover's algorithm and see how it works to solve a problem. We will tweak this code and improve it in the later tasks.
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_SimpleLoop () : Unit {
// Create a data structure describing the SAT instance we want to solve
let problem = [[(0, true)], [(0, false), (1, false)]];
// The number of variables in this formula is 2
let variableCount = 2;
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
// We start by defining a quantum oracle for the instance of a SAT problem we want to solve.
// We use a pre-written operation "CreateOracleForSATInstance" to do that.
let oracle = CreateOracleForSATInstance(problem);
// We will discuss choosing the right number of iterations later
let iterationCount = 1;
// Allocate the qubits for running the algorithm
use register = Qubit[variableCount];
// Run the iterations using a pre-written operation
GroversAlgorithm_Loop(register, oracle, iterationCount);
// Perform measurements to get the variables assignment.
// "MultiM" operation measures all qubits and returns an array of measurement results, and
// "ResultArrayAsBoolArray" converts it to an array of boolean variables.
let assignment = ResultArrayAsBoolArray(MultiM(register));
// Output the results
Message($"{VariableAssignmentAsString(assignment)}");
// Reset the qubits before releasing them, otherwise you'll get a ReleasedQubitsAreNotInZeroState exception
ResetAll(register);
}
%simulate RunGroversAlgorithm_SimpleLoop
If you've tried running the algorithm from part II on different SAT instances, you've probably noticed that for some formulas the algorithm produces incorrect results. This is to be expected: Grover's algorithm is a probabilistic algorithm, which means that even in the best case it has a non-zero failure probability. In the next section we will look at how to verify that the answer produced by the algorithm is correct, and how to re-run the algorithm if the first run produced an incorrect answer.
There are two ways to verify that the output of the algorithm $x_0$ is correct:
In the case of the SAT problem, you would assign the values produced by the algorithm to the variables in the formula and check whether this assignment satisfies the formula.
2. In the general case the algorithm only gets the oracle as an input and doesn't have the information about the classical problem structure.
However, all information necessary to verify the output is already contained in the oracle itself!
The effect of the oracle on inputs, encoded as basis states of the qubit register, is defined as
$$U_f |\vec{x} \rangle |y\rangle = |\vec{x} \rangle |y \oplus f(x) \rangle$$
This means that if you encode the vector state $\vec{x_0}$ produced by the algorithm as a basis state of the qubit register,
allocate an extra qubit in the $|0\rangle$ state, and apply the oracle $U_f$ to these qubits, you'll get
$$U_f |\vec{x_0} \rangle |0\rangle = |\vec{x} \rangle |f(x) \rangle$$
If you measure the extra qubit afterwards, you'll get exactly $f(x)$: if it is 1, the algorithm produced a correct answer, otherwise it did not (but you can re-run the algorithm from scratch again and hopefully get a correct answer on the next attempt!)
Modify the following code to add output verification to Grover's algorithm.
When you execute the following cell for the first time, it will produce several compilation errors.
Your task is to fill in the missing sections of the code (denoted by `...`) following the prompts given in the code comments to fix the compilation errors and to implement the required functionality.
If you get stuck, scroll down to the next text cell for the complete code for the answer check!</font>
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_OutputVerification () : Unit {
// Use a different SAT instance to get a higher probability of failure
let problem = [[(0, true), (1, true)], [(0, false), (1, false)]];
let variableCount = 2;
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
let oracle = CreateOracleForSATInstance(problem);
let iterationCount = 1;
use register = Qubit[variableCount];
GroversAlgorithm_Loop(register, oracle, iterationCount);
let assignment = ResultArrayAsBoolArray(MultiM(register));
Message($"{VariableAssignmentAsString(assignment)}");
// ========================== Check that the answer is correct. ==========================
// Allocate another qubit to keep the result of evaluating the function.
// You can allocate a single qubit with the following syntax in using statement: <variable name> = Qubit()
use ...
// After measuring "register" on line 17, the qubits in "register" end up
// in the state that encodes the answer produced by the algorithm (decoded in "assignment" variable).
// Call oracle with "register" as the first parameter (function input x)
// and the newly allocated qubit as the second parameter (function output f(x))
// to evaluate the function on that answer.
...
// Measure the newly allocated qubit and check if the measurement result is Zero or One;
// One means the algorithm returned correct answer, Zero - incorrect.
// You can measure the qubit and reset it immediately using MResetZ operation,
// and compare the measurement result to the constants Zero or One using "==" operator.
if ... {
// Report the correct/incorrect result using Message function.
Message(...);
} else {
Message(...);
}
ResetAll(register);
}
%simulate RunGroversAlgorithm_OutputVerification
use y = Qubit() {
oracle(register, y);
if MResetZ(y) == One {
Message("Correct!");
} else {
Message("Incorrect");
}
}
Modify the following code to re-run Grover's algorithm if the first run produced an incorrect answer. This logic is implemented by Q#'s repeat ... until
loop.
You can copy the code from the previous exercise to use as loop body.
If you get stuck, scroll down to the next text cell for the complete code for rerunning the algorithm!</font>
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_RerunIncorrectAnswer () : Unit {
// Use a different SAT instance to get a higher probability of failure
let problem = [[(0, true), (1, true)], [(0, false), (1, false)]];
let variableCount = 2;
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
let oracle = CreateOracleForSATInstance(problem);
let iterationCount = 1;
use register = Qubit[variableCount];
// ======== Use repeat-until-success loop to re-run algorithm in case of a failure ========
// Define a mutable variable to serve as the exit condition.
mutable isAnswerCorrect = false;
// Define a mutable variable to store the answer once you've found a correct one.
mutable finalAnswer = [false, false];
repeat {
// Loop body: run Grover's search using "GroversAlgorithm_Loop",
// measure the answer and check whether it is correct.
// Use "set <variable name> = <value>;" to update mutable variables.
...
// Remember to reset the qubits in "register" at the end of each iteration!
} until (isAnswerCorrect);
// Output the final answer.
Message($"{finalAnswer}");
}
%simulate RunGroversAlgorithm_RerunIncorrectAnswer
mutable isAnswerCorrect = false;
mutable finalAnswer = [false, false];
repeat {
GroversAlgorithm_Loop(register, oracle, iterationCount);
set finalAnswer = ResultArrayAsBoolArray(MultiM(register));
Message($"Verifying answer {finalAnswer}");
use y = Qubit() {
oracle(register, y);
if (MResetZ(y) == One) {
set isAnswerCorrect = true;
}
}
ResetAll(register);
} until (isAnswerCorrect);
If you've tried running the algorithm from part II on different SAT instances, you've probably noticed that different instances of the problem have different probability of the algorithm successfully finding a solution to them. This probability depends on several parameters:
In this section we will take a look at how varying these parameters affects the success probability of Grover's search algorithm, and at how to tune the algorithm to increase the success probability.
Modify the following code to run Grover's algorithm multiple times, check whether the algorithm found correct answer each time, and aggregate the results into success probability of the algorithm.
You can copy the code from the exercises 3-4 to use as loop body.
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Measurement;
open Quantum.Kata.ExploringGroversAlgorithm;
operation RunGroversAlgorithm_CalculateSuccessProbability () : Unit {
// Here are the SAT instances with different success probabilities mentioned earlier to get you started
// 1 solution: [[(0, true)], [(0, false), (1, false)], [(1, true), (2, true)]]
// 2 solutions: [[(0, true), (1, true)], [(0, false), (1, false)], [(1, true), (2, true)], [(1, false), (2, false)]]
// 3 solutions: [[(1, false)], [(0, true), (2, true)]]
// 4 solutions: [[(0, true), (1, true)], [(0, false), (1, false)]]
let variableCount = 3;
let problem = [[(1, false)], [(0, true), (2, true)]];
Message($"Solving SAT problem {SATInstanceAsString(problem)}...");
let oracle = CreateOracleForSATInstance(problem);
let iterationCount = 1;
use register = Qubit[variableCount];
// ======== Use for loop to run algorithm a fixed number of times ========
// Define a mutable variable to store the number of times the algorithm succeeded.
mutable successCount = 0;
for i in 1 .. 100 {
// Loop body: run Grover's search using "GroversAlgorithm_Loop",
// measure the answer and check whether it is correct.
// Use "set successCount += 1;" to increment the success counter.
...
// Remember to reset the qubits in "register" at the end of each iteration!
}
// Output the success probability of the algorithm.
Message($"The algorithm succeeds with {successCount}% probability.");
}
%simulate RunGroversAlgorithm_CalculateSuccessProbability
mutable successCount = 0;
for (i in 1 .. 100) {
GroversAlgorithm_Loop(register, oracle, iterationCount);
let answer = ResultArrayAsBoolArray(MultiM(register));
use y = Qubit() {
oracle(register, y);
if MResetZ(y) == One {
set successCount += 1;
}
}
ResetAll(register);
}
Message($"The algorithm succeeds with {successCount}% probability.");
At this stage you have completed the quantum code necessary to run Grover's algorithm and estimate its success probability. To continue our exploration of Grover's algorithm, we'll switch to a companion Python notebook that shows how to invoke Q# code from Python host, uses the code we've written to build some interesting graphs and finishes the discussion of the algorithm.
We hope you've enjoyed this tutorial and learned a lot from it! If you're looking to learn more about quantum computing and Q#, here are some suggestions:
GroversAlgorithm_Loop
operation in this tutorial!).