Select Git revision
groversAlgorithm.html
Forked from
Jannik Hellenkamp / Introduction to Quantum Computing
14 commits ahead of the upstream repository.
Stefan Stump authored
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
groversAlgorithm.html 42.71 KiB
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en"><head>
<meta charset="utf-8">
<meta name="generator" content="quarto-1.7.31">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<title>12 Grover’s algorithm – Introduction to Quantum Computing</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
ul.task-list li input[type="checkbox"] {
width: 0.8em;
margin: 0 0.8em 0.2em -1em; /* quarto-specific, see https://github.com/quarto-dev/quarto-cli/issues/4556 */
vertical-align: middle;
}
</style>
<script src="../site_libs/quarto-nav/quarto-nav.js"></script>
<script src="../site_libs/quarto-nav/headroom.min.js"></script>
<script src="../site_libs/clipboard/clipboard.min.js"></script>
<script src="../site_libs/quarto-search/autocomplete.umd.js"></script>
<script src="../site_libs/quarto-search/fuse.min.js"></script>
<script src="../site_libs/quarto-search/quarto-search.js"></script>
<meta name="quarto:offset" content="../">
<link href="../content/shorsAlgorithm.html" rel="prev">
<script src="../site_libs/quarto-html/quarto.js" type="module"></script>
<script src="../site_libs/quarto-html/tabsets/tabsets.js" type="module"></script>
<script src="../site_libs/quarto-html/popper.min.js"></script>
<script src="../site_libs/quarto-html/tippy.umd.min.js"></script>
<script src="../site_libs/quarto-html/anchor.min.js"></script>
<link href="../site_libs/quarto-html/tippy.css" rel="stylesheet">
<link href="../site_libs/quarto-html/quarto-syntax-highlighting-e1a5c8363afafaef2c763b6775fbf3ca.css" rel="stylesheet" id="quarto-text-highlighting-styles">
<script src="../site_libs/bootstrap/bootstrap.min.js"></script>
<link href="../site_libs/bootstrap/bootstrap-icons.css" rel="stylesheet">
<link href="../site_libs/bootstrap/bootstrap-364982630eef5352dd1537128a8ed5cb.min.css" rel="stylesheet" append-hash="true" id="quarto-bootstrap" data-mode="light">
<script id="quarto-search-options" type="application/json">{
"location": "sidebar",
"copy-button": false,
"collapse-after": 3,
"panel-placement": "start",
"type": "textbox",
"limit": 50,
"keyboard-shortcut": [
"f",
"/",
"s"
],
"show-item-context": false,
"language": {
"search-no-results-text": "No results",
"search-matching-documents-text": "matching documents",
"search-copy-link-title": "Copy link to search",
"search-hide-matches-text": "Hide additional matches",
"search-more-match-text": "more match in this document",
"search-more-matches-text": "more matches in this document",
"search-clear-button-title": "Clear",
"search-text-placeholder": "",
"search-detached-cancel-button-title": "Cancel",
"search-submit-button-title": "Submit",
"search-label": "Search"
}
}</script>
<script src="https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6"></script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml-full.js" type="text/javascript"></script>
<script type="text/javascript">
const typesetMath = (el) => {
if (window.MathJax) {
// MathJax Typeset
window.MathJax.typeset([el]);
} else if (window.katex) {
// KaTeX Render
var mathElements = el.getElementsByClassName("math");
var macros = [];
for (var i = 0; i < mathElements.length; i++) {
var texText = mathElements[i].firstChild;
if (mathElements[i].tagName == "SPAN") {
window.katex.render(texText.data, mathElements[i], {
displayMode: mathElements[i].classList.contains('display'),
throwOnError: false,
macros: macros,
fleqn: false
});
}
}
}
}
window.Quarto = {
typesetMath
};
</script>
</head>
<body class="nav-sidebar floating quarto-light">
<div id="quarto-search-results"></div>
<header id="quarto-header" class="headroom fixed-top">
<nav class="quarto-secondary-nav">
<div class="container-fluid d-flex">
<button type="button" class="quarto-btn-toggle btn" data-bs-toggle="collapse" role="button" data-bs-target=".quarto-sidebar-collapse-item" aria-controls="quarto-sidebar" aria-expanded="false" aria-label="Toggle sidebar navigation" onclick="if (window.quartoToggleHeadroom) { window.quartoToggleHeadroom(); }">
<i class="bi bi-layout-text-sidebar-reverse"></i>
</button>
<nav class="quarto-page-breadcrumbs" aria-label="breadcrumb"><ol class="breadcrumb"><li class="breadcrumb-item"><a href="../content/bernsteinVazirani.html">Quantum algorithms</a></li><li class="breadcrumb-item"><a href="../content/groversAlgorithm.html"><span class="chapter-number">12</span> <span class="chapter-title">Grover’s algorithm</span></a></li></ol></nav>
<a class="flex-grow-1" role="navigation" data-bs-toggle="collapse" data-bs-target=".quarto-sidebar-collapse-item" aria-controls="quarto-sidebar" aria-expanded="false" aria-label="Toggle sidebar navigation" onclick="if (window.quartoToggleHeadroom) { window.quartoToggleHeadroom(); }">
</a>
<button type="button" class="btn quarto-search-button" aria-label="Search" onclick="window.quartoOpenSearch();">
<i class="bi bi-search"></i>
</button>
</div>
</nav>
</header>
<!-- content -->
<div id="quarto-content" class="quarto-container page-columns page-rows-contents page-layout-article">
<!-- sidebar -->
<nav id="quarto-sidebar" class="sidebar collapse collapse-horizontal quarto-sidebar-collapse-item sidebar-navigation floating overflow-auto">
<div class="pt-lg-2 mt-2 text-left sidebar-header">
<div class="sidebar-title mb-0 py-0">
<a href="../">Introduction to Quantum Computing</a>
<div class="sidebar-tools-main">
<a href="https://git.rwth-aachen.de/unruh/script-intro-qc/" title="Source Code" class="quarto-navigation-tool px-1" aria-label="Source Code"><i class="bi bi-git"></i></a>
<a href="../Introduction-to-Quantum-Computing.pdf" title="Download PDF" class="quarto-navigation-tool px-1" aria-label="Download PDF"><i class="bi bi-file-pdf"></i></a>
</div>
</div>
</div>
<div class="mt-2 flex-shrink-0 align-items-center">
<div class="sidebar-search">
<div id="quarto-search" class="" title="Search"></div>
</div>
</div>
<div class="sidebar-menu-container"> <ul class="list-unstyled mt-1">
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../index.html" class="sidebar-item-text sidebar-link">
<span class="menu-text">Welcome</span></a>
</div>
</li>
<li class="sidebar-item sidebar-item-section">
<div class="sidebar-item-container">
<a class="sidebar-item-text sidebar-link text-start" data-bs-toggle="collapse" data-bs-target="#quarto-sidebar-section-1" role="navigation" aria-expanded="true">
<span class="menu-text">Quantum basics</span></a>
<a class="sidebar-item-toggle text-start" data-bs-toggle="collapse" data-bs-target="#quarto-sidebar-section-1" role="navigation" aria-expanded="true" aria-label="Toggle section">
<i class="bi bi-chevron-right ms-2"></i>
</a>
</div>
<ul id="quarto-sidebar-section-1" class="collapse list-unstyled sidebar-section depth1 show">
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/introduction.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">1</span> <span class="chapter-title">Introduction</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/probabilisticSystems.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">2</span> <span class="chapter-title">Probabilistic systems</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/quantumSystems.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">3</span> <span class="chapter-title">Quantum systems</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/observingSystems.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">4</span> <span class="chapter-title">Observing probabilistic and measuring quantum systems</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/partialObserving.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">5</span> <span class="chapter-title">Partial observing and measuring systems</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/compositeSystems.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">6</span> <span class="chapter-title">Composite Systems</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/quantumCircuits.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">7</span> <span class="chapter-title">Quantum Circuits</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/ketNotation.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">8</span> <span class="chapter-title">Ket Notation</span></span></a>
</div>
</li>
</ul>
</li>
<li class="sidebar-item sidebar-item-section">
<div class="sidebar-item-container">
<a class="sidebar-item-text sidebar-link text-start" data-bs-toggle="collapse" data-bs-target="#quarto-sidebar-section-2" role="navigation" aria-expanded="true">
<span class="menu-text">Quantum algorithms</span></a> <a class="sidebar-item-toggle text-start" data-bs-toggle="collapse" data-bs-target="#quarto-sidebar-section-2" role="navigation" aria-expanded="true" aria-label="Toggle section">
<i class="bi bi-chevron-right ms-2"></i>
</a>
</div>
<ul id="quarto-sidebar-section-2" class="collapse list-unstyled sidebar-section depth1 show">
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/bernsteinVazirani.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">9</span> <span class="chapter-title">Bernstein-Vazirani Algorithm</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/dft.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">10</span> <span class="chapter-title">Discrete Fourier Transformation</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/shorsAlgorithm.html" class="sidebar-item-text sidebar-link">
<span class="menu-text"><span class="chapter-number">11</span> <span class="chapter-title">Shor’s Algorithm</span></span></a>
</div>
</li>
<li class="sidebar-item">
<div class="sidebar-item-container">
<a href="../content/groversAlgorithm.html" class="sidebar-item-text sidebar-link active">
<span class="menu-text"><span class="chapter-number">12</span> <span class="chapter-title">Grover’s algorithm</span></span></a>
</div>
</li>
</ul>
</li>
</ul>
</div>
</nav>
<div id="quarto-sidebar-glass" class="quarto-sidebar-collapse-item" data-bs-toggle="collapse" data-bs-target=".quarto-sidebar-collapse-item"></div>
<!-- margin-sidebar -->
<div id="quarto-margin-sidebar" class="sidebar margin-sidebar">
<nav id="TOC" role="doc-toc" class="toc-active">
<h2 id="toc-title">Table of contents</h2>
<ul>
<li><a href="#preparations" id="toc-preparations" class="nav-link active" data-scroll-target="#preparations"><span class="header-section-number">12.1</span> Preparations</a>
<ul class="collapse">
<li><a href="#constructing-the-oracle-v_f" id="toc-constructing-the-oracle-v_f" class="nav-link" data-scroll-target="#constructing-the-oracle-v_f"><span class="header-section-number">12.1.1</span> Constructing the oracle <span class="math inline">\(V_f\)</span></a></li>
<li><a href="#constructing-operatornameflip_" id="toc-constructing-operatornameflip_" class="nav-link" data-scroll-target="#constructing-operatornameflip_"><span class="header-section-number">12.1.2</span> Constructing <span class="math inline">\(\operatorname{FLIP}_*\)</span></a></li>
</ul></li>
<li><a href="#the-algorithm-for-searching" id="toc-the-algorithm-for-searching" class="nav-link" data-scroll-target="#the-algorithm-for-searching"><span class="header-section-number">12.2</span> The algorithm for searching</a>
<ul class="collapse">
<li><a href="#understanding-the-algorithm-for-searching" id="toc-understanding-the-algorithm-for-searching" class="nav-link" data-scroll-target="#understanding-the-algorithm-for-searching"><span class="header-section-number">12.2.1</span> Understanding the algorithm for searching</a></li>
</ul></li>
</ul>
</nav>
</div>
<!-- main -->
<main class="content" id="quarto-document-content">
<header id="title-block-header" class="quarto-title-block default"><nav class="quarto-page-breadcrumbs quarto-title-breadcrumbs d-none d-lg-block" aria-label="breadcrumb"><ol class="breadcrumb"><li class="breadcrumb-item"><a href="../content/bernsteinVazirani.html">Quantum algorithms</a></li><li class="breadcrumb-item"><a href="../content/groversAlgorithm.html"><span class="chapter-number">12</span> <span class="chapter-title">Grover’s algorithm</span></a></li></ol></nav>
<div class="quarto-title">
<h1 class="title"><span class="chapter-number">12</span> <span class="chapter-title">Grover’s algorithm</span></h1>
</div>
<div class="quarto-title-meta">
</div>
</header>
<p>Another well known quantum algorithm is Grover’s algorithm for searching. It was developed by Lov Grover in 1996.</p>
<p>Grover’s algorithm takes a function <span class="math inline">\(f: \{0,1\}^n \rightarrow \{0,1\}\)</span>, where exactly one <span class="math inline">\(x_0\)</span> exists, such that <span class="math inline">\(f(x_0) = 1\)</span>. The goal is to find <span class="math inline">\(x_0\)</span>.</p>
<p>There are a number of interesting problems, which can be reduced to this general definition. One of these problems is the breaking of a (symmetric) encryption. The function <span class="math inline">\(f\)</span> would take a key as an input and output a <span class="math inline">\(1\)</span>, if the decryption is successful. Otherwise it will output a <span class="math inline">\(0\)</span>.</p>
<p>Classically, finding this <span class="math inline">\(x_0\)</span> takes approximately <span class="math inline">\(2^n\)</span> steps (when simply bruteforcing the function). Using Grover’s algorithm, we can reduce this runtime to approximately <span class="math inline">\(\sqrt{2^n}\)</span> steps. As an example, a <span class="math inline">\(128\)</span>-bit encryption would only take about <span class="math inline">\(2^{64}\)</span> steps to break it, instead of about <span class="math inline">\(2^{128}\)</span> steps for the classical bruteforce.</p>
<section id="preparations" class="level2" data-number="12.1">
<h2 data-number="12.1" class="anchored" data-anchor-id="preparations"><span class="header-section-number">12.1</span> Preparations</h2>
<p>To construct Grover’s algorithm, we first need to introduce two new gates <span class="math inline">\(V_f\)</span> and <span class="math inline">\(\operatorname{FLIP}_*\)</span>.</p>
<p>The uniform superposition <span class="math inline">\(\ket{*}\)</span> simply denotes the superposition over all classical possibilities <span class="math inline">\(\ket{*} = \frac{1}{\sqrt{2^n}} \sum_{x \in\{0,1\}^n} \ket{x}\)</span>.</p>
<section id="constructing-the-oracle-v_f" class="level3" data-number="12.1.1">
<h3 data-number="12.1.1" class="anchored" data-anchor-id="constructing-the-oracle-v_f"><span class="header-section-number">12.1.1</span> Constructing the oracle <span class="math inline">\(V_f\)</span></h3>
<p>In the previous algorithms, we have learned that we can implement a function <span class="math inline">\(f\)</span> as a unitary <span class="math inline">\(U_f\)</span> with <span class="math inline">\(U_f\ket{x,y} = \ket{x, y \oplus f(x)}\)</span>. We construct a different unitary called <span class="math inline">\(V_f\)</span> from this, which has the following behavior:</p>
<p><span class="math display">\[
V_f \ket{x} \coloneqq
\begin{cases}
-\ket{x} & \text{if } f(x) = 1 \\
\ket{x} & \text{else}
\end{cases}
\]</span></p>
<p>We can construct <span class="math inline">\(V_f\)</span> from <span class="math inline">\(U_f\)</span> using the following circuit:</p>
<div class="quarto-figure quarto-figure-center">
<figure class="figure">
<p><img src="img/vf.svg" class="img-fluid figure-img" style="width:60.0%"></p>
<figcaption>The circuit for <span class="math inline">\(V_f\)</span></figcaption>
</figure>
</div>
<p>The bottom wire can be discarded, since it always contains a <span class="math inline">\(\ket{-}\)</span> and thus is not entangled with the upper wire.</p>
</section>
<section id="constructing-operatornameflip_" class="level3" data-number="12.1.2">
<h3 data-number="12.1.2" class="anchored" data-anchor-id="constructing-operatornameflip_"><span class="header-section-number">12.1.2</span> Constructing <span class="math inline">\(\operatorname{FLIP}_*\)</span></h3>
<p>As a second ingredient for Grover’s algorithm, we need a unitary <span class="math inline">\(\operatorname{FLIP}_*\)</span> (defined below). To realize this, we first need <span class="math inline">\(\operatorname{FLIP}_0\)</span>, which ist defined by the unitary <span class="math display">\[
\operatorname{FLIP}_0 \ket{x} \coloneqq
\begin{cases}
\ket{0} & \text{if } x = 0 \\
-\ket{x} & \text{else}.
\end{cases}
\]</span></p>
<p><span class="math inline">\(\operatorname{FLIP}_0\)</span> is implemented by the following quantum circuit:</p>
<div class="quarto-figure quarto-figure-center">
<figure class="figure">
<p><img src="img/flip_zero.svg" class="img-fluid figure-img" style="width:50.0%"></p>
<figcaption>The circuit for <span class="math inline">\(\operatorname{FLIP}_0\)</span></figcaption>
</figure>
</div>
<p><span class="math inline">\(Z\)</span> is the Pauli matrix from definition <a href="quantumCircuits.html#def-gates-pauli" class="quarto-xref">Definition <span>7.2</span></a>. The empty circles indicates a negative control wire. So <span class="math inline">\(Z\)</span> is only applied if the other wires are <span class="math inline">\(\ket{0}\)</span>.</p>
<p>Now we can define the unitary called <span class="math inline">\(\operatorname{FLIP}_*\)</span>. This unitary does nothing, if it is applied on the uniform superposition <span class="math inline">\(\ket{*}\)</span>. For any other quantum state <span class="math inline">\(\ket{\psi}\)</span> orthogonal to <span class="math inline">\(\ket{*}\)</span> it maps to <span class="math inline">\(-\ket{\psi}\)</span>. So <span class="math inline">\(\operatorname{FLIP}_*\)</span> is described by:</p>
<p><span class="math display">\[
\operatorname{FLIP}_* \ket{\psi} \coloneqq
\begin{cases}
\ket{*} & \text{if } \ket{\psi} = \ket{*} \\
-\ket{x} & \text{if } \braket{\psi | *} = 0 \text{ (orthogonal)}.
\end{cases}
\]</span></p>
<p>We can construct this <span class="math inline">\(\operatorname{FLIP}_*\)</span> by the following quantum circuit:</p>
<div class="quarto-figure quarto-figure-center">
<figure class="figure">
<p><img src="img/flip_star.svg" class="img-fluid figure-img" style="width:60.0%"></p>
<figcaption>The circuit for <span class="math inline">\(\operatorname{FLIP}_*\)</span></figcaption>
</figure>
</div>
</section>
</section>
<section id="the-algorithm-for-searching" class="level2" data-number="12.2">
<h2 data-number="12.2" class="anchored" data-anchor-id="the-algorithm-for-searching"><span class="header-section-number">12.2</span> The algorithm for searching</h2>
<p>The actual algorithm takes a function <span class="math inline">\(f: \{0,1\}^n \rightarrow \{0,1\}\)</span> and outputs an <span class="math inline">\(x_0\)</span> with <span class="math inline">\(f(x_0)=1\)</span>. For simplicity, we assume that there is only one <span class="math inline">\(x_0\)</span> for which <span class="math inline">\(f(x_0) = 1\)</span> holds and for each other <span class="math inline">\(x \neq x_0\)</span> it holds that <span class="math inline">\(f(x)=0\)</span>.</p>
<p>With the two new unitaries <span class="math inline">\(V_f\)</span> and <span class="math inline">\(\operatorname{FLIP}_*\)</span> defined, we can construct the circuit for Grover’s algorithm, which is shown in the following figure:</p><div class="quarto-figure quarto-figure-center">
<figure class="figure">
<p><img src="img/grover.svg" class="img-fluid figure-img" style="width:70.0%"></p>
<figcaption>The quantum circuit for Grover’s algorithm</figcaption>
</figure>
</div>
<p>The algorithm works as follows:</p>
<ol type="1">
<li>We start with a <span class="math inline">\(\ket{0}\)</span> entry on every qubit.</li>
<li>We bring the system into the superposition over all entries by applying <span class="math inline">\(H^{\otimes n}\)</span>. The quantum state is then <span class="math inline">\(\frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} \ket{x}\)</span> which we also call <span class="math inline">\(\ket{*}\)</span>.</li>
<li>We apply the unitary <span class="math inline">\(V_f\)</span>.</li>
<li>We apply the unitary <span class="math inline">\(\operatorname{FLIP}_*\)</span>.</li>
<li>We repeat steps 3 and 4 <span class="math inline">\(t\)</span> times.</li>
<li>We do a measurement.</li>
</ol>
<p>The measurement in step 6 will then give us <span class="math inline">\(x_0\)</span> with high probability.</p>
<section id="understanding-the-algorithm-for-searching" class="level3" data-number="12.2.1">
<h3 data-number="12.2.1" class="anchored" data-anchor-id="understanding-the-algorithm-for-searching"><span class="header-section-number">12.2.1</span> Understanding the algorithm for searching</h3>
<p>When looking at the quantum circuit, it is not completely intuitive why the algorithm gives the correct result. We therefore now look into what is happening in each step.</p>
<p>The desired quantum state after the algorithm finishes is <span class="math inline">\(\ket{x_0}\)</span>. At the beginning of the algorithm, we bring the system into the uniform superposition <span class="math inline">\(\ket{*} = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} \ket{x}\)</span>. We know that <span class="math inline">\(\ket{x_0}\)</span> is part of this superposition, therefore we can rewrite <span class="math inline">\(\ket{*}\)</span> as follows <span class="math display">\[
\ket{*}
= \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} \ket{x}
= \frac{1}{\sqrt{2^n}} \underbrace{\ket{x_0}}_{\textit{good}} + \sqrt{\frac{2^n-1}{2^n}} \underbrace{\sum_{x\neq x_0} \frac{1}{\sqrt{2^n-1}}\ket{x}}_{\textit{bad}}
\]</span></p>
<p>So the current state can be seen as a superposition of a “good” state <em>good</em> and a “bad” state <em>bad</em>.</p>
<p>The geometric interpretation of this superposition can be drawn as follows:</p>
<div class="quarto-figure quarto-figure-center">
<figure class="figure">
<p><img src="img/grover_plot_1.svg" class="img-fluid figure-img" style="width:30.0%"></p>
<figcaption>Geometric interpretation of <span class="math inline">\(\ket{*}\)</span></figcaption>
</figure>
</div>
<p>The angel <span class="math inline">\(\theta\)</span> denotes, how “good” the resulting outcome will be. If <span class="math inline">\(\theta = 0\)</span>, the state is completely bad, if <span class="math inline">\(\theta = \frac{\pi}{2}\)</span>, the state is completely good.</p>
<p>We can calculate <span class="math inline">\(\cos \theta = \lvert\braket{*|bad}\rvert = \frac{\sqrt{2^n-1}}{\sqrt{2^n}}\)</span>. From this we can derivate that the angle <span class="math inline">\(\theta\)</span> is <span class="math inline">\(\cos^{-1} \sqrt{\frac{2^n-1}{2^n}}\)</span> at the beginning, which is approximately <span class="math inline">\(\sqrt{\frac{1}{2^n}}\)</span>.</p>
<p>We now apply <span class="math inline">\(V_f\)</span> on this quantum state. This will negate the amplitude off our desired <span class="math inline">\(\ket{x_0}\)</span> and not change the amplitude to the rest of the state.</p>
<p><span class="math display">\[
V_f\ket{*}= -\frac{1}{\sqrt{2^n}} \underbrace{\ket{x_0}}_{\text{good}} + \sqrt{\frac{2^n-1}{2^n}} \underbrace{\sum_{x\neq x_0} \ket{x}}_{\text{bad}}
\]</span></p>
<p>This looks like this in the geometric interpretation:</p>
<div class="quarto-figure quarto-figure-center">
<figure class="figure">
<p><img src="img/grover_plot_2.svg" class="img-fluid figure-img" style="width:30.0%"></p>
<figcaption>Geometric interpretation after <span class="math inline">\(V_f\)</span></figcaption>
</figure>
</div>
<p>We can see that by applying <span class="math inline">\(V_f\)</span>, we mirror the vector across the <em>bad</em> axis.</p>
<p>After <span class="math inline">\(V_f\)</span>, we apply the <span class="math inline">\(\operatorname{FLIP}_*\)</span> operation on the quantum state. Since <span class="math inline">\(\operatorname{FLIP}_*\)</span> does nothing on the <span class="math inline">\(\ket{*}\)</span> entries and negates the amplitude of any vector orthogonal to it, <span class="math inline">\(\operatorname{FLIP}_*\)</span> mirrors the vector across <span class="math inline">\(\ket{*}\)</span>. This can be seen in the following figure:</p>
<div class="quarto-figure quarto-figure-center">
<figure class="figure">
<p><img src="img/grover_plot_3.svg" class="img-fluid figure-img" style="width:30.0%"></p>
<figcaption>Geometric interpretation after <span class="math inline">\(\operatorname{FLIP}_*\)</span></figcaption>
</figure>
</div>
<p>All in all, we have seen that by applying <span class="math inline">\(V_f\)</span> and <span class="math inline">\(\operatorname{FLIP}_*\)</span>, we can increase the angle of the quantum state in relation to the “good” and “bad” states by <span class="math inline">\(2\theta\)</span>. Therefore two reflection give rotation. By repeating this step often enough, we can get the amplitude of <span class="math inline">\(\ket{x_0}\)</span> close to 1.</p>
<p>To be more precise: Since we know <span class="math inline">\(\theta\)</span> and we know that we will increase the <em>good</em>-ness of our quantum state by <span class="math inline">\(2\theta\)</span> each time, we can calculate that only <span class="math inline">\(t\)</span> iterations are necessary with <span class="math display">\[
t \approx \frac{\frac{\pi / 2}{\theta} - 1}{2} \approx \frac{\pi}{4 \theta} \approx \frac{\pi}{4} \cdot \sqrt{2^n}.
\]</span> Grover’s algorithm therefore takes <span class="math inline">\(O(\sqrt{2^n})\)</span> steps, where an evaluation of the circuit counts as one step.</p>
</section>
</section>
</main> <!-- /main -->
<script id="quarto-html-after-body" type="application/javascript">
window.document.addEventListener("DOMContentLoaded", function (event) {
const icon = "";
const anchorJS = new window.AnchorJS();
anchorJS.options = {
placement: 'right',
icon: icon };
anchorJS.add('.anchored');
const isCodeAnnotation = (el) => {
for (const clz of el.classList) {
if (clz.startsWith('code-annotation-')) {
return true;
}
}
return false;
}
const onCopySuccess = function(e) {
// button target
const button = e.trigger;
// don't keep focus
button.blur();
// flash "checked"
button.classList.add('code-copy-button-checked');
var currentTitle = button.getAttribute("title");
button.setAttribute("title", "Copied!");
let tooltip;
if (window.bootstrap) {
button.setAttribute("data-bs-toggle", "tooltip");
button.setAttribute("data-bs-placement", "left");
button.setAttribute("data-bs-title", "Copied!");
tooltip = new bootstrap.Tooltip(button,
{ trigger: "manual",
customClass: "code-copy-button-tooltip",
offset: [0, -8]});
tooltip.show();
}
setTimeout(function() {
if (tooltip) {
tooltip.hide();
button.removeAttribute("data-bs-title");
button.removeAttribute("data-bs-toggle");
button.removeAttribute("data-bs-placement");
}
button.setAttribute("title", currentTitle);
button.classList.remove('code-copy-button-checked');
}, 1000);
// clear code selection
e.clearSelection();
}
const getTextToCopy = function(trigger) {
const codeEl = trigger.previousElementSibling.cloneNode(true);
for (const childEl of codeEl.children) {
if (isCodeAnnotation(childEl)) {
childEl.remove();
}
}
return codeEl.innerText;
}
const clipboard = new window.ClipboardJS('.code-copy-button:not([data-in-quarto-modal])', {
text: getTextToCopy
});
clipboard.on('success', onCopySuccess);
if (window.document.getElementById('quarto-embedded-source-code-modal')) {
const clipboardModal = new window.ClipboardJS('.code-copy-button[data-in-quarto-modal]', {
text: getTextToCopy,
container: window.document.getElementById('quarto-embedded-source-code-modal')
});
clipboardModal.on('success', onCopySuccess);
}
var localhostRegex = new RegExp(/^(?:http|https):\/\/localhost\:?[0-9]*\//);
var mailtoRegex = new RegExp(/^mailto:/);
var filterRegex = new RegExp("https:\/\/qis\.rwth-aachen\.de\/teaching\/25ss\/intro-quantum-computing\/script\/");
var isInternal = (href) => {
return filterRegex.test(href) || localhostRegex.test(href) || mailtoRegex.test(href);
}
// Inspect non-navigation links and adorn them if external var links = window.document.querySelectorAll('a[href]:not(.nav-link):not(.navbar-brand):not(.toc-action):not(.sidebar-link):not(.sidebar-item-toggle):not(.pagination-link):not(.no-external):not([aria-hidden]):not(.dropdown-item):not(.quarto-navigation-tool):not(.about-link)');
for (var i=0; i<links.length; i++) {
const link = links[i];
if (!isInternal(link.href)) {
// undo the damage that might have been done by quarto-nav.js in the case of
// links that we want to consider external
if (link.dataset.originalHref !== undefined) {
link.href = link.dataset.originalHref;
}
}
}
function tippyHover(el, contentFn, onTriggerFn, onUntriggerFn) {
const config = {
allowHTML: true,
maxWidth: 500,
delay: 100,
arrow: false,
appendTo: function(el) {
return el.parentElement;
},
interactive: true,
interactiveBorder: 10,
theme: 'quarto',
placement: 'bottom-start',
};
if (contentFn) {
config.content = contentFn;
}
if (onTriggerFn) {
config.onTrigger = onTriggerFn;
}
if (onUntriggerFn) {
config.onUntrigger = onUntriggerFn;
}
window.tippy(el, config);
}
const noterefs = window.document.querySelectorAll('a[role="doc-noteref"]');
for (var i=0; i<noterefs.length; i++) {
const ref = noterefs[i];
tippyHover(ref, function() {
// use id or data attribute instead here
let href = ref.getAttribute('data-footnote-href') || ref.getAttribute('href');
try { href = new URL(href).hash; } catch {}
const id = href.replace(/^#\/?/, "");
const note = window.document.getElementById(id);
if (note) {
return note.innerHTML;
} else {
return "";
}
});
}
const xrefs = window.document.querySelectorAll('a.quarto-xref');
const processXRef = (id, note) => {
// Strip column container classes
const stripColumnClz = (el) => {
el.classList.remove("page-full", "page-columns");
if (el.children) {
for (const child of el.children) {
stripColumnClz(child);
}
}
}
stripColumnClz(note)
if (id === null || id.startsWith('sec-')) {
// Special case sections, only their first couple elements
const container = document.createElement("div");
if (note.children && note.children.length > 2) {
container.appendChild(note.children[0].cloneNode(true));
for (let i = 1; i < note.children.length; i++) { const child = note.children[i];
if (child.tagName === "P" && child.innerText === "") {
continue;
} else {
container.appendChild(child.cloneNode(true));
break;
}
}
if (window.Quarto?.typesetMath) {
window.Quarto.typesetMath(container);
}
return container.innerHTML
} else {
if (window.Quarto?.typesetMath) {
window.Quarto.typesetMath(note);
}
return note.innerHTML;
}
} else {
// Remove any anchor links if they are present
const anchorLink = note.querySelector('a.anchorjs-link');
if (anchorLink) {
anchorLink.remove();
}
if (window.Quarto?.typesetMath) {
window.Quarto.typesetMath(note);
}
if (note.classList.contains("callout")) {
return note.outerHTML;
} else {
return note.innerHTML;
}
}
}
for (var i=0; i<xrefs.length; i++) {
const xref = xrefs[i];
tippyHover(xref, undefined, function(instance) {
instance.disable();
let url = xref.getAttribute('href');
let hash = undefined;
if (url.startsWith('#')) {
hash = url;
} else {
try { hash = new URL(url).hash; } catch {}
}
if (hash) {
const id = hash.replace(/^#\/?/, "");
const note = window.document.getElementById(id);
if (note !== null) {
try {
const html = processXRef(id, note.cloneNode(true));
instance.setContent(html);
} finally {
instance.enable();
instance.show();
}
} else {
// See if we can fetch this
fetch(url.split('#')[0])
.then(res => res.text())
.then(html => {
const parser = new DOMParser();
const htmlDoc = parser.parseFromString(html, "text/html");
const note = htmlDoc.getElementById(id);
if (note !== null) {
const html = processXRef(id, note);
instance.setContent(html);
}
}).finally(() => {
instance.enable(); instance.show();
});
}
} else {
// See if we can fetch a full url (with no hash to target)
// This is a special case and we should probably do some content thinning / targeting
fetch(url)
.then(res => res.text())
.then(html => {
const parser = new DOMParser();
const htmlDoc = parser.parseFromString(html, "text/html");
const note = htmlDoc.querySelector('main.content');
if (note !== null) {
// This should only happen for chapter cross references
// (since there is no id in the URL)
// remove the first header
if (note.children.length > 0 && note.children[0].tagName === "HEADER") {
note.children[0].remove();
}
const html = processXRef(null, note);
instance.setContent(html);
}
}).finally(() => {
instance.enable();
instance.show();
});
}
}, function(instance) {
});
}
let selectedAnnoteEl;
const selectorForAnnotation = ( cell, annotation) => {
let cellAttr = 'data-code-cell="' + cell + '"';
let lineAttr = 'data-code-annotation="' + annotation + '"';
const selector = 'span[' + cellAttr + '][' + lineAttr + ']';
return selector;
}
const selectCodeLines = (annoteEl) => {
const doc = window.document;
const targetCell = annoteEl.getAttribute("data-target-cell");
const targetAnnotation = annoteEl.getAttribute("data-target-annotation");
const annoteSpan = window.document.querySelector(selectorForAnnotation(targetCell, targetAnnotation));
const lines = annoteSpan.getAttribute("data-code-lines").split(",");
const lineIds = lines.map((line) => {
return targetCell + "-" + line;
})
let top = null;
let height = null;
let parent = null;
if (lineIds.length > 0) {
//compute the position of the single el (top and bottom and make a div)
const el = window.document.getElementById(lineIds[0]);
top = el.offsetTop;
height = el.offsetHeight;
parent = el.parentElement.parentElement;
if (lineIds.length > 1) {
const lastEl = window.document.getElementById(lineIds[lineIds.length - 1]);
const bottom = lastEl.offsetTop + lastEl.offsetHeight;
height = bottom - top;
}
if (top !== null && height !== null && parent !== null) {
// cook up a div (if necessary) and position it
let div = window.document.getElementById("code-annotation-line-highlight");
if (div === null) {
div = window.document.createElement("div");
div.setAttribute("id", "code-annotation-line-highlight");
div.style.position = 'absolute';
parent.appendChild(div);
}
div.style.top = top - 2 + "px"; div.style.height = height + 4 + "px";
div.style.left = 0;
let gutterDiv = window.document.getElementById("code-annotation-line-highlight-gutter");
if (gutterDiv === null) {
gutterDiv = window.document.createElement("div");
gutterDiv.setAttribute("id", "code-annotation-line-highlight-gutter");
gutterDiv.style.position = 'absolute';
const codeCell = window.document.getElementById(targetCell);
const gutter = codeCell.querySelector('.code-annotation-gutter');
gutter.appendChild(gutterDiv);
}
gutterDiv.style.top = top - 2 + "px";
gutterDiv.style.height = height + 4 + "px";
}
selectedAnnoteEl = annoteEl;
}
};
const unselectCodeLines = () => {
const elementsIds = ["code-annotation-line-highlight", "code-annotation-line-highlight-gutter"];
elementsIds.forEach((elId) => {
const div = window.document.getElementById(elId);
if (div) {
div.remove();
}
});
selectedAnnoteEl = undefined;
};
// Handle positioning of the toggle
window.addEventListener(
"resize",
throttle(() => {
elRect = undefined;
if (selectedAnnoteEl) {
selectCodeLines(selectedAnnoteEl);
}
}, 10)
);
function throttle(fn, ms) {
let throttle = false;
let timer;
return (...args) => {
if(!throttle) { // first call gets through
fn.apply(this, args);
throttle = true;
} else { // all the others get throttled
if(timer) clearTimeout(timer); // cancel #2
timer = setTimeout(() => {
fn.apply(this, args);
timer = throttle = false;
}, ms);
}
};
}
// Attach click handler to the DT
const annoteDls = window.document.querySelectorAll('dt[data-target-cell]');
for (const annoteDlNode of annoteDls) {
annoteDlNode.addEventListener('click', (event) => {
const clickedEl = event.target;
if (clickedEl !== selectedAnnoteEl) {
unselectCodeLines();
const activeEl = window.document.querySelector('dt[data-target-cell].code-annotation-active');
if (activeEl) {
activeEl.classList.remove('code-annotation-active');
}
selectCodeLines(clickedEl);
clickedEl.classList.add('code-annotation-active');
} else {
// Unselect the line
unselectCodeLines();
clickedEl.classList.remove('code-annotation-active'); }
});
}
const findCites = (el) => {
const parentEl = el.parentElement;
if (parentEl) {
const cites = parentEl.dataset.cites;
if (cites) {
return {
el,
cites: cites.split(' ')
};
} else {
return findCites(el.parentElement)
}
} else {
return undefined;
}
};
var bibliorefs = window.document.querySelectorAll('a[role="doc-biblioref"]');
for (var i=0; i<bibliorefs.length; i++) {
const ref = bibliorefs[i];
const citeInfo = findCites(ref);
if (citeInfo) {
tippyHover(citeInfo.el, function() {
var popup = window.document.createElement('div');
citeInfo.cites.forEach(function(cite) {
var citeDiv = window.document.createElement('div');
citeDiv.classList.add('hanging-indent');
citeDiv.classList.add('csl-entry');
var biblioDiv = window.document.getElementById('ref-' + cite);
if (biblioDiv) {
citeDiv.innerHTML = biblioDiv.innerHTML;
}
popup.appendChild(citeDiv);
});
return popup.innerHTML;
});
}
}
});
</script>
<nav class="page-navigation">
<div class="nav-page nav-page-previous">
<a href="../content/shorsAlgorithm.html" class="pagination-link" aria-label="Shor's Algorithm">
<i class="bi bi-arrow-left-short"></i> <span class="nav-page-text"><span class="chapter-number">11</span> <span class="chapter-title">Shor’s Algorithm</span></span>
</a>
</div>
<div class="nav-page nav-page-next">
</div>
</nav>
</div> <!-- /content -->
</body></html>