"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"# Plot the data\n",
"fig, axes = pyplot.subplots(2, 2, figsize=(16, 10))\n",
"for sol in range(4):\n",
" ax = axes.flatten()[sol]\n",
" ax.plot(x_points, y_points[sol])\n",
" ax.set_xlabel('Number of iterations')\n",
" ax.set_ylabel('Success probability')\n",
" ax.set_title('M = ' + str(sol+2) + ' solutions')\n",
" ax.set_xticks(range(20))\n",
"fig.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can see that the pattern remains the same on each plot: the success probability increases to nearly 1.0 at a certain number of iterations, after that it decreases to nearly 0.0 at approximately double that number of iterations, and after that the pattern repeats. \n",
"\n",
"However, the number of iterations at which the maximum success probability is achieved is different for different problems: for problems with 1 solution it was 4 iterations, for 2 solutions - 3 iterations, for 3 and 4 solutions - 2 iterations, and for 5 solutions - 1 iteration. The formula for the optimal number of iterations is \n",
"\n",
"$$R \\approx \\frac{\\pi}{4} \\sqrt{\\frac{N}{M}}$$\n",
"\n",
"where $N$ is the size of the search space (in our case we have 5 binary variables, so $N = 2^5 = 32$), $M$ is the number of solutions to the problem (in our case between 1 and 5).\n",
"\n",
"This formula shows the reason Grover's search is so interesting - the classical solution to the search problem requires $O(N)$ evaluations of the function, and Grover's search algorithm allows to do this in $O(\\sqrt{N})$ evaluations, providing a quadratic speedup."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Calculating the optimal number of iterations\n",
"\n",
"Where does the formula $R \\approx \\frac{\\pi}{4}\\sqrt{\\frac{N}{M}} $ come from?\n",
"We can derive the optimal number of iterations from first principles, and see which assumptions went into this formula and in what cases it is not accurate.\n",
"\n",
"Grover's search begins with a uniform superposition of all $N=2^n$ states in the search space:\n",
"$$|all\\rangle = \\frac{1}{\\sqrt{N}}\\sum_{x=0}^{N-1}{|x\\rangle} $$\n",
"\n",
"When we're looking at the equation $f(x) = 1$, we can rewrite this expression in terms of basis states that are \"good\" (solutions) and \"bad\" (non-solutions):\n",
"$$ |all\\rangle = \\sqrt{\\frac{M}{N}}|good\\rangle + \\sqrt{\\frac{N-M}{N}}|bad\\rangle$$\n",
"Here $M$ is the number of states for which $f(x)=1$ (the number of equation solutions), and\n",
"$$\n",
"|good\\rangle = \\frac{1}{\\sqrt{M}}\\sum_{x,f(x)=1}{|x\\rangle}\\\\\n",
"|bad\\rangle = \\frac{1}{\\sqrt{N-M}}\\sum_{x,f(x)=0}{|x\\rangle}\n",
"$$\n",
"\n",
"The effect of the phase oracle used in Grover's algorithm on these states will be the flipping the phase of all basis states in $|good\\rangle$ and leaving $|bad\\rangle$ unchanged:\n",
"$$O|good\\rangle =-|good\\rangle \\\\ O|bad\\rangle =|bad\\rangle$$\n",
"\n",
"Let's rewrite the coefficients in the $|all\\rangle$ representation to trigonometric ones as follows:\n",
"$$ |all\\rangle = \\sin{\\theta}|good\\rangle + \\cos{\\theta}|bad\\rangle \\\\ \n",
"\\sin \\theta = \\sqrt{\\frac{M}{N}}, \\cos \\theta = \\sqrt{\\frac{N-M}{N}}$$\n",
"\n",
"Grover's operator can be represented as $G = UO$, where $O$ is the phase oracle which implements the function $f(x)$, and $U = H^{\\otimes n}(2|0\\rangle\\langle0|-I)H^{\\otimes n}$ is the \"reflection about the mean\". \n",
"\n",
"Each iteration of Grover's search adds $2\\theta$ to the current angle in the expression of the system state as a superposition of $|good\\rangle$ and $|bad\\rangle$.\n",
"After applying $R$ iterations of Grover's search the state of the system will be\n",
"\n",
"$$ G^R|all\\rangle = \\sin{(2R+1)\\theta}|good\\rangle + \\cos{(2R+1)\\theta}|bad\\rangle$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"
\n",
"\n",
"The Grover's iteration is a sequence of these two reflections, which, combined, produce a counterclockwise rotation by an angle $2\\theta$. If we repeat the iteration, reflecting the new state first along the horizontal axis and then along the $|all\\rangle$ vector, it performs a rotation by $2\\theta$ again. The angle of this rotation depends only on the angle between the reflection axes and not on the state we reflect!\n",
"\n",
"\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now let's recall that $\\theta = \\arcsin \\sqrt{\\frac{M}{N}}$. When $M$ is much smaller than $N$, $\\frac{M}{N}$ is close to 0, $\\theta$ is a small angle, and we can approximate $\\theta \\approx \\sqrt{\\frac{M}{N}}$:\n",
"\n",
"$$ 2R+1 \\approx \\frac{\\pi}{2\\theta} = \\frac{\\pi}{2}\\sqrt{\\frac{N}{M}}$$\n",
"Since $\\theta$ is small, $R$ is large, and we can ignore the $+1$ term, obtaining finally our formula:\n",
"$$ R \\approx \\frac{\\pi}{4}\\sqrt{\\frac{N}{M}}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### The optimal number of iterations when the assumption that $M$ is much smaller than $N$ is invalid\n",
"\n",
"Now, let's look at three scenarios where our assumptions are not valid.\n",
"\n",
"### 1. What happens if there are no solutions?\n",
"\n",
"We assumed that the equation $f(x) = 1$ has solutions, i.e., $M \\neq 0$. What happens if $M = 0$, i.e., our problem doesn't have solutions?\n",
"\n",
"In this case the starting system state $|\\psi\\rangle = |bad\\rangle$, and $\\theta = \\arcsin \\sqrt{\\frac{M}{N}} = 0$.\n",
"No matter how many iterations we do, the probability of our measurement yielding a marked state is $0$.\n",
"In practice this means that Grover's search will yield a random non-solution every time. \n",
"To detect that this is the case, we need to run the algorithm multiple times and note the distrubution of the results; if none of them are problem solutions, we can conclude that the problem doesn't have a solution.\n",
"\n",
"### 2. What happens if the solutions make up exactly half of the search space?\n",
"\n",
"If $M=\\frac{N}{2}$, then $\\theta = \\arcsin \\sqrt\\frac{N/2}{N} = \\arcsin \\sqrt\\frac{1}{2} = \\frac{\\pi}{4}$. \n",
"This means that after $R$ iterations $\\sin{(2R+1)\\theta} = \\sin\\frac{(2R+1)\\pi}{4} = \\pm \\frac{1}{\\sqrt{2}} $. \n",
"The probability of the measurement yielding a solution is $P(|good\\rangle) = \\sin^2\\frac{(2R+1)\\theta}{2} = (\\pm \\frac{1}{\\sqrt{2}})^2 = \\frac{1}{2}$ regardless of the number of iterations.\n",
"\n",
"### 3. What happens if the solutions make up more than half of the search space?\n",
"If $\\frac{N}{2} < M \\leq N$, then $\\frac{\\pi}{4} < \\theta \\leq \\frac{\\pi}{4}$. \n",
"Now using even one iteration doesn't always increase $P(|good\\rangle) = \\sin^2{(2R+1)\\theta}$, in fact the first iteration is likely to decrease the probability.\n",
"\n",
"> Have you ever wondered why all tutorials on Grover's search start with two-bit functions? \n",
"> That's the reason why - if you have only 1 bit, you only have $M=0$, $M=\\frac{N}{2}$, or $M=N$, and none of these make for a good illustration of the algorithm!\n",
"\n",
"If we want to handle scenarios 2 and 3 using Grover's search, we can increase the size of the search space $N$ (without changing $M$). \n",
"We can do this by increasing the number of qubits $n$ to $n' = n+j$, so that the new size of the search space $N' = 2^{n'}$ is much bigger than $M$. \n",
"In this case we also need to modify the oracle, so that it can act on $n'$ qubits instead of $n$. \n",
"One way to do this is to define the new oracle $O'$ as follows: it applies $O$ to the first $n$ qubits if remaining $j$ qubits are in state $|0 ... 0\\rangle$. \n",
"Thus $O'$ is effectively a zero-controlled variant of $O$:\n",
"$$O' = O \\otimes(|0\\rangle\\langle0|) + I^{\\otimes n} \\otimes (\\sum_{k=1}^{2^j-1}|k\\rangle\\langle k|)$$\n",
"\n",
"However, it is a lot easier to handle these scenarios classically. \n",
"Indeed, selecting a random state has a probability of being a problem solution $p = \\frac{M}{N} > \\frac{1}{2}$! \n",
"If we repeat this process $k$ times, the probability of success grows to $1- p^k$, thus by increasing $k$ we can get this probabilty as close to $1$ as we need.\n",
"For example, For $p=0.5$ and $k=10$ the probality of success is $\\approx 99.9\\%$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### But I don't know how many solutions my problem has!\n",
"\n",
"Indeed, in practical applications you don't usually know how many solutions your problem has before you start solving it. \n",
"In this case you can pick the number of iterations as a random number between 1 and $\\frac{\\pi}{4} \\sqrt{N}$, and if the search did not yield the result on the first run, re-run it with a different number of iterations."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# What's Next?\n",
"\n",
"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:\n",
"\n",
"* The [Quantum Katas](https://github.com/microsoft/QuantumKatas/) are sets of programming exercises on quantum computing that can be solved using Q#. They cover a variety of topics, from the basics like the concepts of superposition and measurements to more interesting algorithms like Grover's search.\n",
"* In particular, [GroverSearch kata](https://github.com/microsoft/QuantumKatas/tree/main/GroversAlgorithm) offers you exercises on implementing simple quantum oracles and a step-by-step implementation of Grover search algorithm (all the internals that were hidden under the hood of `GroversAlgorithm_Loop` operation in this tutorial!).\n",
"* [SolveSATWithGrover kata](https://github.com/microsoft/QuantumKatas/tree/main/SolveSATWithGrover) teaches you how to implement quantum oracles for SAT problems, starting with the simple building blocks like implementing AND and OR operations in a quantum way.\n",
"* [GraphColoring kata](https://github.com/microsoft/QuantumKatas/tree/main/GraphColoring) is another interesting kata that teaches you how to implement quantum oracles for graph coloring problems.\n",
"* [BoundedKnapsack kata](https://github.com/microsoft/QuantumKatas/tree/main/BoundedKnapsack) handles more complicated problem, the knapsack problem, showing how to use Grover's search for optimization problems."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In order to maximize the probability of finding a solution when we measure, we want the amplitude of the $|good\\rangle$ state to be as close to 1 as possible. \n",
"After $R$ iterations this amplitude equals $\\sin{(2R+1)\\theta}$, so we're looking for $R$ that is a solution to\n",
"$$\\sin (2R+1)\\theta \\approx 1 \\\\ \n",
"(2R+1)\\theta \\approx \\frac{\\pi}{2} \\\\\n",
"2R+1 \\approx \\frac{\\pi}{2\\theta}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can arrive to the same conclusion using a neat visualization of the Grover's search iterations.\n",
"\n",
"Click here for the complete proof of the above statement
\n", "\n", "*Note: The math below is terse but not that complicated. \n", "However, it requires some prior knowledge of trigonometry identities as well as ket-bra algebra.*\n", "\n", "Let's prove the result \n", "$G^R|\\psi\\rangle = \\sin{(2R+1)\\theta}|good\\rangle + \\cos{(2R+1)\\theta}|bad\\rangle$ by induction.\n", "\n", "#### Base case\n", "\n", "When $R=0$, $G^R=G^0=I$ and $2R+1=2\\times0+1=1$.\n", "\n", "Thus $G^0|\\psi\\rangle = \\sin{(2\\times 0+1)\\theta}|good\\rangle + \\cos{(2\\times 0+1)\\theta}|bad\\rangle \n", "= \\sin{\\theta}|good\\rangle + \\cos{\\theta}|bad\\rangle = |\\psi\\rangle$\n", "is true.\n", "\n", "#### Inductive step \n", "\n", "Let us assume this is true for all $R \\leq k$, i.e.,\n", "$G^{k}|\\psi\\rangle = \\sin{(2k+1)\\theta}|good\\rangle + \\cos{(2k+1)\\theta}|bad\\rangle$.\n", "\n", "#### Induction proof\n", "\n", "Let us show that $G^{k+1}|\\psi\\rangle = \\sin{(2(k+1)+1)\\theta}|good\\rangle + \\cos{(2(k+1)+1)\\theta}|bad\\rangle$. \n", "\n", "We know that since all states in $|good\\rangle$ are marked and all states in $|bad\\rangle$ are unmarked, therefore,\n", "$O|good\\rangle =-|good\\rangle$ and $O|bad\\rangle =|bad\\rangle$. \n", "\n", "Thus by linearity of the quantum oracle $O$, \n", "$$O(\\sin{(2k+1)\\theta}|good\\rangle + \\cos{(2k+1)\\theta}|bad\\rangle) = \n", "-\\sin{(2k+1)\\theta}|good\\rangle + \\cos{(2k+1)\\theta}|bad\\rangle$$\n", "\n", "Note that the states $|good\\rangle$ and $|bad\\rangle$ are orthogonal (since they don't share any basis states), i.e., $\\langle bad|good\\rangle =\\langle good|bad\\rangle=0$.\n", "\n", "Now let's consider reflection about the mean:\n", "$$U = H^{\\otimes n}(2|0\\rangle\\langle0|-I)H^{\\otimes n} \n", "= 2H^{\\otimes n}|0\\rangle\\langle0|H^{\\otimes n} - I $$\n", "\n", "We know that $H^{\\otimes n}|0\\rangle = \\frac{1}{N}\\sum_{x=0}^{N-1}|x\\rangle = |\\psi\\rangle = \\sin\\theta|good\\rangle + \\cos\\theta|bad\\rangle$.\n", "\n", "Thus, \n", "$$ U = 2|\\psi\\rangle\\langle \\psi| - I = \\\\\n", "= 2\\big(\\sin{\\theta}|good\\rangle + \\cos{\\theta}|bad\\rangle\\big)\\big(\\sin{\\theta}\\langle good| + \\cos{\\theta}\\langle bad|\\big) - I = \\\\\n", "= 2\\big(\\sin^2{\\theta}|good\\rangle\\langle good|+ \\cos{\\theta}\\sin{\\theta}|bad\\rangle\\langle good| \n", "+ \\cos{\\theta}\\sin{\\theta}|good\\rangle\\langle bad| + \\cos^2{\\theta}|bad\\rangle\\langle bad|\\big) - I$$\n", "\n", "Now we can write $G^{k+1}|\\psi\\rangle$ as follows:\n", "$$G^{k+1}|\\psi\\rangle = G\\big(G^k|\\psi\\rangle\\big) = \\\\ \n", "= G\\big(\\sin{(2k+1)\\theta}|good\\rangle + \\cos{(2k+1)\\theta}|bad\\rangle\\big) = \\\\\n", "= UO\\big(\\sin{(2k+1)\\theta}|good\\rangle + \\cos{(2k+1)\\theta}|bad\\rangle\\big) = \\\\\n", "= U\\big(-\\sin{(2k+1)\\theta}|good\\rangle + \\cos{(2k+1)\\theta}|bad\\rangle\\big) = \\\\\n", "= \\big(2(\\sin^2{\\theta}|good\\rangle\\langle good| + \\cos{\\theta}\\sin{\\theta}|bad\\rangle\\langle good| \n", "+ \\cos{\\theta}\\sin{\\theta}|good\\rangle\\langle bad| + \\cos^2{\\theta}|bad\\rangle\\langle bad|) - I\\big) \\cdot \\\\\n", "\\cdot \\big(-\\sin{(2k+1)\\theta}|good\\rangle + \\cos{(2k+1)\\theta}|bad\\rangle\\big)\n", "$$\n", "\n", "If we expand this expression, cancel out the terms where inner product is zero, and combine the coefficients at the same state, we'll get\n", "\n", "$$ G^{k+1}|\\psi\\rangle = U\\big(-\\sin{(2k+1)\\theta}|good\\rangle + \\cos{(2k+1)\\theta}|bad\\rangle\\big) = \\\\\n", "= \\big((1-2\\sin^2{\\theta})\\sin{(2k+1)\\theta} \n", "+ (2\\cos{\\theta}\\sin{\\theta})\\cos{(2k+1)\\theta}\\big)|good\\rangle + \\\\\n", "+ \\big(-(2\\cos{\\theta}\\sin{\\theta})\\sin{(2k+1)\\theta}\n", "+ (2\\cos^2{\\theta}-1)\\cos{(2k+1)\\theta}\\big)|bad\\rangle$$ \n", "\n", "Using some trigonometry we can simply it further:\n", "$$ G^{k+1}|\\psi\\rangle = \\big(\\cos2\\theta\\sin{(2k+1)\\theta} + \\sin2\\theta\\cos{(2k+1)\\theta}\\big)|good\\rangle\n", "+ \\big(-\\sin2\\theta\\sin{(2k+1)\\theta} + \\cos2\\theta\\cos{(2k+1)\\theta}\\big)|bad\\rangle = \\\\\n", "= \\sin(2\\theta + {(2k+1)\\theta})|good\\rangle + \\cos(2\\theta + {(2k+1)\\theta})|bad\\rangle = \\\\\n", "= \\sin{(2k+3)\\theta}|good\\rangle + \\cos{(2k+3)\\theta}|bad\\rangle = \\\\\n", "= \\sin{(2(k+1)+1)\\theta}|good\\rangle + \\cos{(2(k+1)+1)\\theta}|bad\\rangle $$\n", "\n", "This is exactly what we wanted to show, thus our proof by induction is complete.\n", "| \n", " | Imagine a plane on which $|good\\rangle$ and $|bad\\rangle$ vectors correspond to vertical and horizontal axes, respectively. We can represent the starting state $|all\\rangle$ as a superposition of these states: | \n", "![](\"./img/5-1-equal-superposition.png\"/) | \n",
" |
| \n", " | Each Grover's iteration consists of two steps. The first step is applying the phase oracle, which multiplies the amplitudes of \"good\" states by $-1$. On the circle plot, this transformation leaves the horizontal component of the state vector unchanged and reverses its vertical component. In other words, this operation is a reflection along the horizontal axis: | \n", "![](\"./img/5-2-first-reflection.png\"/) | \n",
" |
| \n", " | The second step is applying the diffusion operator. Its effect is another reflection, this time along the vector $|all\\rangle$: | \n", "![](\"./img/5-3-second-reflection.png\"/) | \n",
"
| \n", " | When should we perform the measurement? \n", " The probability of getting a certain basis state as the measurement outcome equals the squared amplitude of that state in the superposition. The greater the amplitude, the higher the chance of getting the corresponding state when performing the measurement.\n", " \n", "Since our goal is to get one of the \"good\" states with probability as high as possible, we need to increase the amplitudes of \"good\" states as much as we can (and reduce the amplitudes of \"bad\" states correspondingly). Geometrically, this means that we want to rotate our state vector as close to the vertical axis as possible. | \n",
" ![](\"./img/5-4-measurement.png\"/) | \n",
" |
| \n", " | Our initial state started with the angle $\\theta$ to the horizontal axis, and every iteration rotates it $2\\theta$ counterclockwise, so the angle after $R$ rotations is $(2R+1)\\theta$, and we want it to be as close to $\\frac{\\pi}{2}$ as possible to be close to the vertical axis: \n", " \n", "This also explains the decrease in success probability if we keep iterating. More iterations will over-rotate our state, which will start getting further and further away from the vertical axis, thus reducing our success probability. | \n",
" ![](\"./img/5-5-overrotation.png\"/) | \n",
"