2d:null 2e:["$","title",null,{"children":"Quantum Search | Pablo Pedemonte | Observable"}] 33:T477,md`--- # Quantum Search Let ${tex`f:\{0,\dots,N\} \rightarrow \{0,1\}`}, where ${tex`f`} is zero everywhere except at a designated value ${tex`k`}. In a classical setting, a black box search for ${tex`k`} (i.e., a search where we can't assume nothing about ${tex`f`}) requires ${tex`O(N)`} calls to ${tex`f`}. In a quantum setting, the search problem can be solved in ${tex`\Theta(\sqrt{N})`} calls. That's a quadratic speedup! The procedure is the famous [Grover's algorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm), devised by Lov Grover in 1996. An equally famous result by [Bernstein et al](https://arxiv.org/abs/quant-ph/9701001). shows that Grover's algorithm is asymptotically optimal. For starters, we need an oracle modelling the effects of ${tex`f`}. We will implement is as an operator ${tex`U_f`} such that ${tex`U_f\lvert x \rangle = (-1)^{f(x)}\lvert x \rangle`}. Note that ${tex`U_f`} will turn negative the amplitude for ${tex`k`}, since ${tex`f(k) = 1`}. For the implementation we will use a controlled not gate and an extra ancilla qubit initialized to ${tex`1/\sqrt{2}(\lvert 0 \rangle - \lvert 1 \rangle)`}.`34:T562,plot = (N, p, data, height) => { const margin = {top: 20, right: 0, bottom: 30, left: 40} const x = d3.scaleLinear() .domain([0, data.length-1]) .range([margin.left, width - margin.right - 20]) const y = d3.scaleLinear() .domain([0, 1]) .range([height - margin.bottom, margin.top]) const xAxis = g => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(x) .tickSizeOuter(0)) const yAxis = g => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) const svg = d3.select(DOM.svg(width, height)); const line = d3.line() .x((_,i) => x(i)) .y(y) .curve(d3.curveCardinal) const g = svg.append('g').append('path') .data([data]) .attr('d', line) .style('fill', 'none') .style('stroke', '#00b6cb') .style('stroke-width', '2px') svg.append("g") .call(xAxis); svg.append("g") .call(yAxis); svg.append("g") .attr("transform", `translate(${margin.left+4},10)`) .append("text") .text(`N = ${N}, p ~ ${p}`) .style("font-family", "sans-serif") .style("font-size", "small") svg.append("g") .attr("transform", `translate(${width-70},${height-16})`) .append("text") .text(`Iterations`) .style("font-family", "sans-serif") .style("font-size", "small") return svg.node(); }35:[] 31:{"id":"1a25ddf0c6d3df70","slug":"quantum-search","title":"Quantum Search","thumbnail":"9532022ddabb52f49a37afd0171350e68f8db7150252567b71cca284d0e75427","access_level":"public","create_time":"$D2018-09-03T15:52:44.041Z","update_time":"$D2020-02-13T20:41:16.493Z","view_time":null,"first_public_time":"$D2018-09-03T16:01:10.751Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"e881edf87176f896","login":"ppedemon","name":"Pablo Pedemonte","avatar_url":"https://avatars-next.observableusercontent.com/cdb0d452f0db24a87d54c4cc3977ab41006ea11f7297893c3548dd14cb8601f2","tier":"starter_2024","bio":""},"version":274,"publish_version":274,"role":null,"authored":false,"authors":[{"type":"individual","id":"fd4fed1b09df7097","login":"ppedemon","name":"Pablo Pedemonte","avatar_url":"https://avatars-next.observableusercontent.com/cdb0d452f0db24a87d54c4cc3977ab41006ea11f7297893c3548dd14cb8601f2","tier":null,"bio":""}],"members":[{"type":"individual","id":"fd4fed1b09df7097","login":"ppedemon","name":"Pablo Pedemonte","avatar_url":"https://avatars-next.observableusercontent.com/cdb0d452f0db24a87d54c4cc3977ab41006ea11f7297893c3548dd14cb8601f2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Quantum Search","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"oracle = (N,k) => q => {\n let i = k\n const bits = []\n while (i > 0) {\n const bit = i % 2\n i >>= 1\n bits.push(!!bit)\n }\n if (bits.length > N) {\n throw new Error(`k = ${k} requires ${bits.length} bits, but N = ${N}`)\n }\n while (bits.length < N) {\n bits.push(false)\n }\n return q.transform(gates.C(gates.X(N), ...bits.map((b,i) => [i,b])))\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"viewof N = slider({\n min: 2, \n max: 6, \n step: 1, \n value: 1, \n title: 'Number of bits'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"viewof k = number({title:'k', min:0, max:(1 << N) - 1, value:0})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"{\n const q0 = new PState([1 << N, 1]).transformN(gates.H, N+1)\n const q1 = oracle(N,k)(q0).transform(gates.H(N))\n const data = q1.superposition.map(({c,a}) => ({\n name: c.bits & ((1 << N) - 1),\n value: math.re(a)\n }))\n return histo(complete(data, N), 300)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"md`---\n## Grover Diffusion Operator\nThe other component of the algorithm is the so-called diffusion operator, which in plain terms will invert amplitudes about their mean. This will practically have no effect for positive amplitudes, but it will increase the amplitude for ${tex`k`} from ${tex`-1/\\sqrt{N}`} to ${tex`\\sim 3/\\sqrt{N}`}. Successive applications of the oracle and then the diffussor will further increase ${tex`k`}'s amplitude, until it will start decreasing and then increasing again, thus forming a loop. It can be shown that the optimum number of times to apply the oracle and the diffussor for maximing ${tex`k`}'s amplitude is ${tex`O(\\sqrt{N})`}. In fact, the number of iterations\ncan be pinned down exactly to ${tex`\\frac{\\pi}{4}\\sqrt{N}`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"diffusor = N => q => {\n const control = [...Array(N-1).keys()].map(i => [i,true])\n return q\n .transformN(gates.H, N)\n .transformN(gates.X, N)\n .transform(gates.C(gates.Z(N-1), ...control))\n .transformN(gates.X, N)\n .transformN(gates.H, N)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"viewof iterations = slider({\n min: 0, \n max: 18, \n step: 1, \n value: 1, \n title: 'Number of iterations'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"data = {\n const q0 = new PState([1 << N, 1]).transformN(gates.H, N+1)\n \n // Do Grover step (oracle + diffusor) {iterations} times\n const q1 = [...Array(iterations).keys()]\n .reduce((q,_) => diffusor(N)(oracle(N,k)(q)), q0)\n .transform(gates.H(N))\n \n const data = q1.probs.map(({name,value}) => ({\n name: name & ((1 << N) - 1),\n value\n }))\n \n return histo(complete(data, N), 200)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"md`\nIf you play with the iterations slider you'll notice that the probability for ${tex`k`} varies in a cyclic fashion, with a period asymptotically equals to ${tex`\\frac{\\pi}{4}\\sqrt{N}`}. Por example, if you set ${tex`N=64`} sou can see that the ${tex`k`}'s probability reaches it maximum at iterations 6 and 18, with a minimum at iteration 12. This matches nicely the expected results, since ${tex`\\frac{\\pi}{4}\\sqrt{64} \\approx 6`}. The next plot shows the oscillations of ${tex`k`}'s probability for an iteration range between 1 and 50:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":248,"value":"viewof pN = slider({\n min: 2, \n max: 6, \n step: 1, \n value: 1, \n title: 'Number of bits'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":137,"value":"{\n const k = 0\n const q0 = new PState([1 << pN, 1]).transformN(gates.H, pN+1)\n \n const [_,data] = [...Array(50).keys()]\n .reduce(([q,d],_) => {\n const qNew = diffusor(pN)(oracle(pN,k)(q)).transform(gates.H(pN))\n const point = qNew.probs[k].value\n d.push(point)\n return [qNew.transform(gates.H(pN)), d]\n }, [q0,[]])\n \n const n = Math.pow(2, pN)\n const p = math.floor(math.pi/2*math.sqrt(n))\n return plot(n, p, data, 240)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"md`---\n## Imports Section`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"import {PState, gates, histo, complete} from '@ppedemon/quantum-circuit-simulator'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"import {radio, slider, number} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"math = require(\"https://cdnjs.cloudflare.com/ajax/libs/mathjs/5.1.1/math.js\");","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"d3 = require('d3@5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1"}} 32:"$31:body"