<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Quantum Computing Group, IIT Roorkee on Medium]]></title>
        <description><![CDATA[Stories by Quantum Computing Group, IIT Roorkee on Medium]]></description>
        <link>https://medium.com/@qcgiitr?source=rss-63a4262f07e4------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*oTPlSagq1ycWnqPgbWHpdw.jpeg</url>
            <title>Stories by Quantum Computing Group, IIT Roorkee on Medium</title>
            <link>https://medium.com/@qcgiitr?source=rss-63a4262f07e4------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 05:06:06 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@qcgiitr/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Quantum Walks Meet Bond Pricing]]></title>
            <link>https://medium.com/@qcgiitr/quantum-walks-meet-bond-pricing-5f214703e12f?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/5f214703e12f</guid>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Sun, 16 Aug 2026 13:37:33 GMT</pubDate>
            <atom:updated>2026-08-27T07:03:44.771Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/547/1*HPGXNefVLkZauPCYtMRmSQ.jpeg" /></figure><h3>Why we’re picking this one</h3><p>Every cycle, a few “quantum finance” ideas float around the group, and honestly, most of them are soft. Someone builds a quantum random walk, notices it produces a funkier-looking probability distribution than a classical one, and points out that the funky shape resembles real market data a bit better. Then they call it a result. That’s a fine modeling exercise, but it’s not a speed claim. It doesn’t prove quantum computing is <em>better</em> at anything, just that it’s different.</p><p>So for this cycle’s open project, we wanted something with an actual spine to it, a claim we can prove rather than just gesture at. This one is built around a 1996 quantum search result and a 2004 theoretical computer science paper that happens to map almost perfectly onto a real problem in bond pricing. By the end, whoever works through this with us will have something defensible in an interview, not just something describable.</p><p>Here’s how we’re laying it out. The problem statement comes first, so everyone starts from the same understanding. Then the eight-week plan we’re following as a group, with reading and a checkpoint for each week.</p><h3>The problem statement</h3><p>A lot of fixed-income products, even ones that look completely different on the surface, reduce to the same abstract question.</p><ul><li>A <strong>callable bond</strong> lets the issuer redeem it early once interest rates cross some trigger level.</li><li>A <strong>barrier note</strong> activates or deactivates once a reference rate crosses a threshold.</li><li>In <strong>credit risk modeling</strong>, a firm is treated as defaulting the moment its asset value drops below a critical level.</li></ul><p>Strip the financial vocabulary away and it’s all the same question. If a value is wandering around randomly, how likely is it, and how long does it take, to hit a specific target level? That’s a first-passage problem, and it rarely has a clean formula. In practice, it gets estimated by brute force: simulate the random walk thousands of times, count how often it hits the barrier, and call that the probability. That’s Monte Carlo simulation, and it’s slow in a specific, measurable way. To search a space of size <em>N</em>, you need on the order of <em>N</em> simulation trials to reliably find where the barrier gets hit.</p><p>Here’s where it gets interesting for us as a quantum computing group specifically. In 1996, Lov Grover showed that a quantum computer can find a marked item among <em>N</em> unsorted possibilities in roughly √N steps, instead of the <em>N</em> steps a classical search would need on average. That result on its own became the foundation of an entire subfield. Then in 2004, Mario Szegedy extended the same underlying idea to something more general: he proved that if you “quantize” a classical random walk, turning it into a quantum walk that explores multiple paths in superposition, you can locate a marked state on a structured graph in roughly √N steps as well. This got generalized a few years later into the MNRS framework, named for its authors Magniez, Nayak, Roland, and Santha, which extended it to a much wider range of search problems. So the walk-search version we’re using is really Grover’s quadratic speedup, rebuilt to work on graphs and lattices instead of a flat unsorted list.</p><p>A short-rate lattice, the tree-like structure banks already use to model interest rates, is exactly that kind of structured space. So the project is this: build a barrier hitting-time estimator on that lattice two ways, classically with Monte Carlo and quantumly with a Szegedy quantum walk search, and show empirically that one scales like <em>N</em> and the other scales like √N. If it works, we’re not claiming quantum computers make “more realistic” models of markets. We’re demonstrating a proven speedup on a real financial instrument, with a plot to back it up.</p><p>That’s the distinction we want to hold onto throughout the project. “Quantum models produce different distributions” is a soft claim, and it invites the obvious pushback: how do you know that’s actually because it’s quantum, and not just a different modeling choice? “Quantum search provably needs fewer steps, and here’s the curve” isn’t up for debate in the same way. That’s the version we’re building.</p><h3>The 8-week plan</h3><p><strong>Week 1</strong> starts deliberately basic. Time value of money, discounting, what a bond actually is, and how price and yield move against each other. We’ll lean on <a href="https://www.khanacademy.org/economics-finance-domain/core-finance/stock-and-bonds">Khan Academy’s bonds material</a> for the intuition and skim the early chapters of <a href="https://www.pearson.com/en-us/subject-catalog/p/options-futures-and-other-derivatives/P200000005938">Hull</a> for the formal version. By the end of the week, the checkpoint is a script that prices a zero-coupon bond and shows the price-yield relationship across a few different yields.</p><p><strong>Week 2</strong> is where we actually decide what we’re building. We’ll pick a specific bond structure, most likely a callable bond with a defined rate trigger, since it’s the cleanest version of “random walk hits a barrier” wearing financial clothing. We’ll read up on barrier and knock-in/knock-out structures, and go through the <a href="https://ideas.repec.org/a/bla/jfinan/v31y1976i2p351-67.html">Black-Cox paper</a> on structural credit models, where default modeled as hitting a barrier is the same idea in different clothes. No code yet this week, just a clear written statement of what the barrier represents and why hitting it matters for the price. Everything downstream depends on this being nailed down properly. In order to help you with the transition of concepts from Week 1 to 2, attached is a link to a guide (will also help with the Week 2 Assignment): <a href="https://drive.google.com/file/d/1V7IpadSEi5CCncucTUtXgG5bTk0UMDGV/view?usp=sharing">https://drive.google.com/file/d/1V7IpadSEi5CCncucTUtXgG5bTk0UMDGV/view?usp=sharing</a></p><p><strong>Weeks 3 and 4</strong> are our quantum computing on-ramp, and we’re treating them as one continuous push rather than two separate units. Week 3 covers qubits, superposition, measurement, and basic gates, using the <a href="https://github.com/Qiskit/qiskit-textbook">Qiskit Textbook</a> and <a href="https://quantum.cloud.ibm.com/learning/en">IBM’s learning platform</a>, both built for exactly this. The checkpoint is a circuit that puts a qubit into superposition and shows a roughly 50/50 split on measurement.</p><p>Week 4 is Grover’s algorithm itself, and we’re not rushing through it, because quantum walk search later on is essentially Grover’s more structured cousin: the same amplitude amplification trick, applied to a graph instead of a flat list. Worth reading <a href="https://arxiv.org/abs/quant-ph/9605043">Grover’s original 1996 paper</a> here directly, since it’s short, readable, and the whole cycle’s project rests on the idea in it. The <a href="https://github.com/Qiskit/qiskit-textbook">Qiskit Textbook’s Grover chapter</a> has a full worked build, and for the underlying math, Nielsen and Chuang’s <a href="https://www.cambridge.org/highereducation/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE"><em>Quantum Computation and Quantum Information</em></a>, ch. 6, is the reference, though that depth is optional. The checkpoint is a working Grover search that reliably finds a marked item among a handful of possibilities.</p><p><strong>Week 5</strong> is the one we care most about getting right, because the entire final result gets compared against whatever comes out of this week. We take the barrier from week 2, build it into an actual short-rate lattice in the <a href="https://doi.org/10.1111/j.1540-6261.1986.tb02528.x">Ho-Lee style</a>, and estimate the hitting probability the standard way: run the random walk repeatedly and count the hits. <a href="https://www.pearson.com/en-us/subject-catalog/p/options-futures-and-other-derivatives/P200000005938">Hull’s binomial tree chapter</a> and <a href="https://www.quantstart.com/articles/topic/derivatives-pricing/">QuantStart’s derivatives pricing articles</a> get us there. The checkpoint is a convergence plot showing the estimate stabilizing as trials increase, and that curve is literally half of our final result.</p><p><strong>Week 6</strong> is the theoretical core, and we’re giving ourselves extra room here rather than compressing it. This is where we sit with <a href="https://doi.org/10.1109/FOCS.2004.53">Szegedy’s original paper</a> and the <a href="https://arxiv.org/abs/quant-ph/0608026">MNRS paper</a>, working through how a classical Markov chain gets “quantized” into something that finds a marked vertex in roughly √N steps. If the originals feel dense on a first read, <a href="https://link.springer.com/chapter/10.1007/978-3-540-79228-4_3">Santha’s survey</a> is a gentler entry point. We don’t need to master every proof, just enough to build a small working version. The checkpoint is a quantum walk search circuit on a toy graph that reliably finds its marked vertex in roughly √N steps.</p><p><strong>Week 7</strong> is the payoff, the week that makes the whole project worth doing. We take the exact lattice and barrier from week 5, rebuild it as a graph the quantum walk can search, and run both versions side by side as the lattice size grows. Everything comes down to one plot: classical trials on one axis, quantum steps on the other, and whether they actually separate the way the theory predicts. We’ll price the bond both ways too, to confirm the two methods agree, since a speedup that gives the wrong price isn’t a result, it’s a bug.</p><p><strong>Week 8</strong> is presentation, and it matters more than it might seem. Clean plots, an honest writeup, and a README that leads with the result instead of burying it. We’ll be precise about what we’re actually claiming. It’s tempting to oversell this as “quantum computers are faster at finance,” but the accurate version is both more defensible and, to anyone who actually knows the field, more impressive: a proven query-complexity speedup, demonstrated empirically on a real financial first-passage problem.</p><h3>What we want out of this</h3><p>We’re not building a vibes-based claim about quantum computing “understanding markets better.” We’re taking a small, well-defined class of financial problems, the ones that are secretly search problems wearing a suit, and applying an actual, proven algorithm to them. That’s a much smaller claim than “quantum revolutionizes finance,” and it’s also a true one, which in the long run is worth a lot more.</p><p>Anyone in the group who wants in on this, week 1 kicks off together. Bring your deliverable to the next submission.</p><h3>Assignments</h3><p>Attached are the links to the PDFs for Week-wise assignments. They shall be updated as the project progresses:</p><ul><li>Week 1: <a href="https://drive.google.com/file/d/1YIYpALmIIUR8PZ_V2_uNvRY96NVvxje5/view?usp=sharing">https://drive.google.com/file/d/1YIYpALmIIUR8PZ_V2_uNvRY96NVvxje5/view?usp=sharing</a></li><li>Week 2: <a href="https://drive.google.com/file/d/1r-nxEoHjJ6Z0Gu-auwsUVFPoum4Rdrxb/view?usp=sharing">https://drive.google.com/file/d/1r-nxEoHjJ6Z0Gu-auwsUVFPoum4Rdrxb/view?usp=sharing</a></li></ul><h3>Reading list, all in one place</h3><ul><li><a href="https://arxiv.org/abs/quant-ph/9605043">Grover (1996), <em>A Fast Quantum Mechanical Algorithm for Database Search</em></a>, the paper the whole idea traces back to</li><li><a href="https://doi.org/10.1109/FOCS.2004.53">Szegedy (2004), <em>Quantum Speed-Up of Markov Chain Based Algorithms</em></a>, the theorem that extends Grover’s idea to quantum walks</li><li><a href="https://arxiv.org/abs/quant-ph/0608026">Magniez, Nayak, Roland &amp; Santha (2011), <em>Search via Quantum Walk</em></a>, the MNRS framework, free on arXiv</li><li><a href="https://link.springer.com/chapter/10.1007/978-3-540-79228-4_3">Santha (2008), <em>Quantum Walk Based Search Algorithms</em></a>, a gentler survey version</li><li><a href="https://doi.org/10.1111/j.1540-6261.1986.tb02528.x">Ho &amp; Lee (1986), <em>Term Structure Movements and Pricing Interest Rate Contingent Claims</em></a></li><li><a href="https://ideas.repec.org/a/bla/jfinan/v31y1976i2p351-67.html">Black &amp; Cox (1976), <em>Valuing Corporate Securities: Some Effects of Bond Indenture Provisions</em></a></li><li><a href="https://www.pearson.com/en-us/subject-catalog/p/options-futures-and-other-derivatives/P200000005938">Hull, <em>Options, Futures, and Other Derivatives</em></a></li><li><a href="https://www.cambridge.org/highereducation/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE">Nielsen &amp; Chuang, <em>Quantum Computation and Quantum Information</em></a></li><li><a href="https://github.com/Qiskit/qiskit-textbook">IBM Qiskit Textbook</a> and <a href="https://quantum.cloud.ibm.com/learning/en">IBM Quantum Learning</a></li><li><a href="https://www.quantstart.com/articles/topic/derivatives-pricing/">QuantStart’s derivatives pricing articles</a></li><li><a href="https://www.khanacademy.org/economics-finance-domain/core-finance/stock-and-bonds">Khan Academy, Stocks and Bonds</a></li><li><a href="https://fred.stlouisfed.org/">FRED, Federal Reserve Economic Data</a>, for real yield curves, including the <a href="https://fred.stlouisfed.org/series/SOFR">SOFR series</a> specifically</li></ul><p>Written by Amirishetty Sai Vignesh</p><p>Project hosted by Amirishetty Sai Vignesh and Harshwardhan Vaibhav Navadkar</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5f214703e12f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Topological Quantum Computing]]></title>
            <link>https://medium.com/@qcgiitr/topological-quantum-computing-57a6105c8a45?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/57a6105c8a45</guid>
            <category><![CDATA[quantum-computing]]></category>
            <category><![CDATA[quantum-mechanics]]></category>
            <category><![CDATA[category-theory]]></category>
            <category><![CDATA[knot-theory]]></category>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Mon, 05 Aug 2024 15:58:43 GMT</pubDate>
            <atom:updated>2024-08-05T15:58:43.547Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*wsV9elz5UHY0V2LjXxHA1A.jpeg" /></figure><p>In this NISQ era, the race to achieve fault-tolerant quantum computers is still in its early stages, with significant challenges remaining in scaling up qubit systems, improving error correction methods, and developing robust quantum algorithms that can fully leverage the potential of these advanced machines but Topological quantum computing may be the steps to achieve fault tolerance.</p><p>Topological quantum computation takes advantage of the topological properties of quantum systems. Unlike traditional quantum computing, which relies on the precise control of qubits, topological quantum computation encodes information in the global environment, topologically invariant properties of the quantum states. These properties are robust against local disturbances, making the computation potentially more fault-tolerant.</p><h3>Introduction</h3><p>Before we start some essential prerequisites are Quantum Mechanics, Algebraic Topology, Basics of Quantum computing, and a bit of Condensed Matter Physics.</p><p>In topological quantum computation, information is stored in anyons, which are two-dimensional quasiparticles when evolved in time form world lines or braids which form gates for our system. Unlike three-dimensional particles under an exchange operator anyons neither give symmetric nor anti-symmetric wavefunction but a phase induced to the system wavefunction. Mathematically,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/495/1*2-IZpXSiFeYKcIy6JIzI2A.png" /></figure><p>the reason behind this is the topological properties of knots in two dimensions(based on knot theory), a short explanation would be that the fundamental group is ℤ which is isomorphic to π₁(S¹) for more info read the references below.</p><p>Suppose we have finitely different sets of particles, 1 as vacuum or no particle, a, b, c every particle has its anti-particle, now these different particles may fuse with the evolution of time, the fusion rule of anyons is given by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/139/1*YYOP8_-OZmPFDhR_ojPdLw.png" /></figure><p>where Nᶜₐb is an integer which describes no. of distinct quantum states that a and b can fuse into c or no. of fusion channels are present when a and b fuse to c. This rule is a consequence of axioms of Modular tensor categories.</p><p>Also, some additional rules of fusion algebra are,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/86/1*wcF0GsQ_1N0ec7KtodZhiA.png" /></figure><p>the fusion of particle and anti-particle gives vacuum or creation of particle anti-particle pair from vacuum.</p><p>For Abelian anyons, the fusion product is unique,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/140/1*V2dFBavTlJfMzdRs16vwXQ.png" /></figure><p>where,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/80/1*RJz2HPg6Eig7sjtPhGwQnA.png" /></figure><p>which gives us the following product,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/77/1*r4mEcrsqAfdOKYhOmLVaDw.png" /></figure><p>Whereas in non-abelian anyons, multiple fusion channels give rise to multi-dimensional fusion space.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/96/1*kpHazSpF1lT67TmokZa2Fw.png" /></figure><h4>Fusion Matrix</h4><p>Suppose we have three anyons a, b, c with total fusion channel d (Fig. is given below). It can be done in two different ways, first a and b fuse to form a set of i topological charges, which then fuse with c to form d, the second way is to fuse b and c first which gives a set of j topological charge, then fuse with a to form d.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/348/1*5FKOT1bYAxEvJ2KenV3bSQ.png" /><figcaption>Fusion Matrix changes our basis from j to i</figcaption></figure><p>To change the order of fusion we need to rotate the fusion space which is given by F-Matrix or Fusion Matrix. This is a Rank-2 Mixed Tensor, Linear algebraically speaking this same as the transformation of an input covector to another covector by an operator ℒ,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/115/1*llXjfmtNG2dSehC-F--TDA.png" /></figure><p>Now we have a set of basis we have what’s called an Anyonic Hilbert space or Fusion space. Different fusion processes with different fusion outcomes are orthogonal to each other.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/353/1*Yyx_2eN8DVKWRm7MOE94SQ.png" /><figcaption>Fusion of n anyons with aₙ as final outcome</figcaption></figure><p>The dimension of Hilbert space of n anyons is given by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/367/1*rffIVDkLwaw2-cMBI1UdYw.png" /></figure><p>Assuming all n anyons are identical, this gives Nₐ in summation term which is a matrix with the largest eigenvalue as dₐ. This is the quantum dimension of anyon a (where different energy levels become degenerate due to symmetric well potential). Therefore the above equation becomes</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/170/1*UUk-gSO526qZ1Jqfq1r73w.png" /></figure><p>This relation is only true for large values of n. The total quantum dimension of a topological model is given by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/112/1*ecTtdUCKUInf4PSW89n18w.png" /></figure><p>where 𝒟² is the no. of superselection sectors over the medium.</p><h4>Rotation Matrix</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/851/1*wh_xGN5Z7Sm7AQMK7NHgFg.png" /><figcaption>R-matrix</figcaption></figure><p>Exchanging two anyons a and b, when their fusion outcome is fixed, the exchange can be viewed as a twist of particle c This is called rotation of fusion outcome, and the operator used is called an R-matrix.</p><h4>Braiding Matrix</h4><p>To Exchange two anyons b and c which don’t have a direct fusion channel we use two F-moves and an R-move without changing the basis. This matrix is called the Braiding matrix or B-matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/812/1*rMISDqiWtZN0oA3SOA7OZQ.png" /><figcaption>Braiding process of anyons</figcaption></figure><p>The B-matrix is the irreducible representation of Braid group σ.</p><h4>Pentagon and Hexagon Identities</h4><p>The anyons are categorized under ribbon categories(or braided monoidal categories) which follow three axioms: pentagon, triangle, and hexagon axiom. These axioms give rise to Pentagon and Hexagon identities for F and R-Matrices. The pentagon identity is given by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/968/1*Gg-kgZ4s0ypMELzc02CARA.png" /><figcaption>Geometrical representation of pentagon identity</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*1xgGyG6QFD8RLrqPDEglNw.png" /></figure><p>This relation captures all the F-matrices in our anyonic system. Similarly, the hexagon identity is given by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/1*37T0YsGYKxxQ8X76mFpEkg.png" /><figcaption>Geometrical representation of hexagon identity</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/359/1*IKh-nvAuWJOrArz3Jzojxw.png" /></figure><p>Solving these relations will give the values of the elements of F and R-matrix, some of these F-matrices may be forbidden cause they might not follow the rules of fusion based on the model.</p><h4>Spin Statistics Theorem</h4><p>Before we move on to compute the F and R-matrix for a certain model, there is one last thing to discuss which is the spin-statistics theorem, remember we discussed twisting the fusion outcomes and R-matrix, shouldn’t the matrix be insignificant cause imagine you rotate a particle about it center the state of the particle should remain same right well no! as discussed we called evolution of anyons in time-space as worldlines but they should be called world-ribbons, the rigid braided monoidal structure of anyons gives map called the twist map which is a phase induced when a particle is twisted, also the symmetry exchanges are of particles is same twisting the fusion outcome.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/583/1*kDxHq7Ok3R3Ly5TohxgagQ.png" /><figcaption>Twist map</figcaption></figure><p>So by spin-statistics theorem we get,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/221/1*Cr8SGeqp96sKgByVHvUrUw.png" /></figure><p>where s is the spin of the particle.</p><h3>Ising and Fibonacci Anyons</h3><p>So some of the practical non-Abelian anyonic models are Ising and Fibonacci models which have been theorized upon to make actual working components for topological quantum computers. Their minimal set of fusion rules makes it easier for computation.</p><h4>Ising Anyons</h4><p>These anyons are based on the Ising model in statistical mechanics, but here instead of just fermion and vacuum we have a non-abelian anyon σ. The physical realization of ising anyons is Majorana fermions.</p><p>The Fusion rules are:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/388/1*3pF50_OmFeWagzgDhRdv4g.png" /></figure><p>Using the pentagon equation we can find the F-Matrix for Ising anyons, will give a brief overview of how it comes,</p><p>Considering the fusion of 4 identical anyons the pentagon equation is given by,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/583/1*WM_WsO0DqvoT3dR1Wu-fbQ.png" /></figure><p>where we get some forbidden fusion trees which simplifies our equation to this,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/89/1*jIgkf7Ut_kQXEgnncXzgrQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/762/1*qpNHtbkbUk-0MQrsI--t5w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/775/1*ThzE0dHMRzPZcyeQ3zr5AQ.png" /><figcaption>Forbidden fusion trees</figcaption></figure><p>Now from the fusion of a fermion and 3 anyons, we get,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/592/1*Vmut_fb2dU28hs6mKyj-2A.png" /></figure><p>After some calculation, we get the equation as,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/104/1*_mcLrctVk7rLt8rkRvOj6Q.png" /></figure><p>The final F-matrix comes out to be,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/191/1*AWg6oa_QWPTwvaoAoLD7eg.png" /></figure><p>where the ± comes from the Frobenius-Schur indicator.</p><p>Similarly, from hexagon identities, we get R-matrix as,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/161/1*aaDVRHzDZCRya1UhUhq_pQ.png" /></figure><p>Now we compute Elementary Braiding Operators(EBO), the braiding between the ith and (i+1)th anyons as σᵢ, the corresponding EBO matrice is denoted by ρ(σᵢ), will compute EBO matrices later while discussing quantum gates.</p><h4>Fibonacci anyons</h4><p>Fibonacci anyons are the most widely accepted anyonic model used for fault-tolerant quantum computation cause only one additional fusion rule is applied:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/115/1*FfheOMiO9kNhx02MWp_MZA.png" /></figure><p>The quantum dimension of τ is given (d_τ)²=1+ d_τ which gives as d_τ=φ, φ is the golden ratio, to know why this model named after Fibonacci is cause suppose n anyons are fused this gives,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/178/1*S5fZiCy6Kv5rMpOm6Y9VIg.png" /></figure><p>where fₘ denotes the mth Fibonacci number in the series. The F and R matrix is given by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/160/1*nz-XCyg6xU0GLG_g3TunPg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/175/1*i_08Ybtp6kBcsx9z92xZ1Q.png" /></figure><h4>Quantum Gates with Anyons</h4><p>Consider the fusion diagram of n+3 anyons with a total spin of 0, the spin of anyon is 1/2, vacuum is 0 and fermion is 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/841/1*PdddKlkQyJgWt1eKtFtCIg.png" /><figcaption>Pairwise fusion tree of identical anyons with spin 1/2</figcaption></figure><p>Now the first EBO matrix is just R⁻¹ cause we have direct fusion outcome x₁ is given by,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/195/1*ikCPm3J9gBmzaNGXSUX3Ew.png" /></figure><p>whereas second EBO matrix is σ₂=FRF⁻¹ or given by the matrix,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/221/1*y6vi2MHD96CU8PnK0VEivw.png" /></figure><p>The successive EBO matrices depend on the basis we chose i.e. |x₁x₂…xₙ&gt; where values taken by x1,x2 … are given in the above figure.</p><p>Now let&#39;s talk about the Hadamard gate, will need 4 ising anyons applying the operation σ₁σ₂σ₁ will give Hadamard operation but with a global phase,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/905/1*PNKe2AxMOvESCJmuYi2a2g.png" /><figcaption>Hadamard Gate</figcaption></figure><p>Similarly, we can get a list of single-qubit quantum gates</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/397/1*h304y8fsOL9arSRDDaE6rg.png" /><figcaption>Single qubit gates</figcaption></figure><p>For two-qubit systems, the operation becomes complex as for the CNOT gate we get two fusion trees with different operations one for the spin 0 sector other for the spin 1 sector.</p><h3>Majorana Fermions as Qubits</h3><p>The vortices of the Honeycomb Lattice model behave as Ising Anyons. The continuum limit of this model supports Majorana modes. The Majorana zero modes are bound to these vortices.</p><p>The Majorana operator γ at a given position i, the γᵢ operator is an annihilation operator that annihilates the fermion at position i or creates an anti-particle. The γ⁺ᵢ (that&#39;s a dagger or adjoint) is the creation of fermion at ith Majorana mode. The Majorana character is defined as the particle and antiparticle being the same i.e. γᵢ=γ⁺ᵢ. Due to this property, it is not possible to define a local degree of freedom for an isolated majorana mode. However, we can make complex fermion modes,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/155/1*CSF36e9ZwejQWRCIeHlRVA.png" /></figure><p>the occupation of this is a non-local property of the Majorana pair.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/268/1*UobuS_qmaM3d1DKYTJYqJQ.png" /><figcaption>Fermionic representations of zero modes</figcaption></figure><p>Let us take four localized Majorana fermions γ₁,.. γ₄. From this we can have two different fermionic representations:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/382/1*1HBl90QsvWellzQFaPu0KA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/392/1*xCoZjsEcSjsyBvrI_RCNQA.png" /></figure><p>These fermionic representations are not independent cause {zᵢ,wᵢ} =1/2. For fusion properties of Majorana fermions, consider a superconducting nanowire where two fermions are combined to form a cooper pair. The population state of z fermions is described as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/156/1*Hn_YzTQ0qzQ0ymXcLm304g.png" /></figure><p>where i,j=0,1.</p><p>To get the F-Matrix we see how the basis changes when we write the w-basis in terms of the z-basis we get this relation,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/333/1*3ZRihGgPfJi_11cym7VRGg.png" /></figure><p>and,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/349/1*-SpnDiLovxKpmK6YwtwoyA.png" /></figure><p>This gives the F matrix as,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/153/1*Q0B3IG0Rw41wJwGDmS7q6g.png" /></figure><p>Consider the exchange of two Majorana fermions by considering a general unitary operator for it and solving we get the unitary evolution as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/150/1*3KGW22gtmsjMQ6bMpa14Pg.png" /></figure><p>By this matrix, you can make braid matrices and gates just as Ising anyons.</p><h4>Conclusion</h4><p>Fault-tolerant qubits could pave the way for more stable and reliable quantum systems, potentially revolutionizing fields ranging from cryptography to complex simulations. As research in this area continues to advance, the dream of harnessing the power of topological quantum computing for practical applications grows ever closer to becoming a reality.</p><h3>References</h3><ol><li><a href="https://arxiv.org/abs/1610.09260">Intro to abelian and non-abelian anyons</a></li><li><a href="https://books.google.co.in/books/about/Introduction_to_Topological_Quantum_Comp.html?id=XDciVh6bAE0C&amp;redir_esc=y">“Introduction to topological quantum computation” by Jiannis K. Pachos</a></li><li><a href="https://arxiv.org/abs/1003.1253">Braid Matrices</a></li><li><a href="https://arxiv.org/abs/1509.00903">Simulation of anyons using matrix product states</a></li><li><a href="https://arxiv.org/abs/0902.3275">Fibonacci anyons</a></li></ol><p><strong><em>Written by Anish Sharma</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=57a6105c8a45" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Quantum Fourier Transform]]></title>
            <link>https://medium.com/@qcgiitr/quantum-fourier-transform-6ced371a99ee?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/6ced371a99ee</guid>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Fri, 15 Dec 2023 06:09:44 GMT</pubDate>
            <atom:updated>2023-12-15T06:09:44.003Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XdiTnGnhM9JNlZ7NV23EcQ.jpeg" /><figcaption>Source: <a href="https://www.heise.de/hintergrund/Quantencomputer-programmieren-Nur-eine-Phase-7358148.html?seite=2">https://www.heise.de/hintergrund/Quantencomputer-programmieren-Nur-eine-Phase-7358148.html?seite=2</a></figcaption></figure><p>Fourier transform is an important mathematical operation that has applications in a wide variety of fields. It allows us to transform signals between domains, most commonly time and frequency domains. It essentially allows us to do a basis transformation.</p><p>Every signal can be decomposed into a collection of complex exponential signals of certain frequencies. We want to find out the amplitudes of signals of each frequency. This allows us to find out how much each frequency contributes to the total signal. This can be done using Fourier transform. It converts amplitude vs time graph to amplitude vs frequency graph. It has applications in signal and image</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*93y1WDV6SzseV85E2kk7Ew.jpeg" /><figcaption>Fig 1: Shows how a signal(right) is composed of many signals of different frequencies(left)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/540/1*BIV4OyTLqhrWBIJGIQDC_Q.jpeg" /><figcaption>Fig 2: Shows conversion of a signal between time and frequency domain. Source:<a href="https://www.nti-audio.com/portals/0/pic/news/FFT-Time-Frequency-View-540.png">https://www.nti-audio.com/portals/0/pic/news/FFT-Time-Frequency-View-540.png</a></figcaption></figure><p><strong>Applications of Fourier Transform in Signal and Image Processing</strong></p><p>Fourier transform is an indispensable part of signal processing. Taking the example of RADAR, the echo it receives back after sending out electromagnetic waves, is in the time domain. Applying Fourier transform on this time-domain signal allows us to extract its frequency content. The frequency-domain signal is easier to use in computer aided signal processing.</p><p>In image processing, the usual images we see are in spatial domain. In spatial domain, an image is represented as a 2-D matrix where each element represents the intensity of the pixel at that position in space. The image can be converted to frequency domain using Fourier transform. This domain represents the rate of change of intensity of pixels. Therefore, the edges or boundaries in an image have higher frequency than the smooth inner regions. The frequency domain makes it easy for us to extract additional features of the image and do operations on it like blurring and sharpening. Due to its usefulness, a quantum equivalent of the Fourier transform has great applications.</p><p><strong>Quantum Fourier Transform</strong></p><p>Quantum Fourier Transform(QFT) is the quantum equivalent of the classical Fast Fourier Transform(FFT). QFT is an integral part of quantum algorithms like Shor’s algorithm and quantum phase estimation. It offers exponential speedup and can be evaluated in polynomial time on a quantum computer. QFT is essentially a change of basis from a computational basis to a Fourier basis. In the case of a single qubit system, applying QFT on it is equivalent to applying a Hadamard gate on it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/272/1*4CSTfTClv5K0Mwow_6I__Q.jpeg" /><figcaption>Fig 3: Shows operation of Hadamard gate on |0⟩ and |1⟩</figcaption></figure><p><strong>QFT on n qubit system</strong></p><p>In case of an n qubit system, QFT converts it from computational basis to Fourier basis. For n=1, The Fourier basis is the Hadamard basis, as demonstrated in the previous section. Similarly, for all values of n, there are corresponding Fourier bases. The formula for converting an n-qubit system from computational to Fourier basis is given below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1005/1*cOj9-lsRL7s3Fz4417GunA.png" /><figcaption>Fig 4: Shows the result when QFT is applied on an n qubit system |x⟩. Source: <a href="https://hgmin1159.github.io/quantum/quantum3_eng/">https://hgmin1159.github.io/quantum/quantum3_eng/</a></figcaption></figure><p>There are two equivalent representations of QFT as shown in the figure given above, but the second one is more useful in understanding how the quantum circuit is built.</p><p><strong>QFT on Bloch sphere</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/259/1*j1WoYf-HnaEGja27AH9SoA.png" /><figcaption>Fig 5: Source: Fundamentals and Frontiers of the Josephson Effect (pp.703–741)</figcaption></figure><p>In the computational basis, each qubit is in a superposition of states, |0⟩ or |1⟩, represented along the z axis.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/868/1*ZiReRgblkLfvI5LN53wMWA.gif" /><figcaption>Fig 6: Source: <a href="https://learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform">https://learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform</a></figcaption></figure><p>In Fig 5, a 4 qubit system is represented using 4 Bloch spheres. The left most sphere represents the least significant qubit and the rightmost represents the most significant qubit. It shows how the different qubits change on counting from 0 to 15 in computational state. The qubits flip between |0⟩ and |1⟩ with different frequencies, the leftmost flips every increment and the right most with every 8 increments.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/867/1*YlFo-6jH6Sm1HJkmWY73mA.gif" /><figcaption>Fig 7: Source: <a href="https://learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform">https://learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform</a></figcaption></figure><p>Fig 7 represents the same 4 qubit system after QFT has been applied to it. Each qubit is represented as a rotation about the z axis, therefore, it will lie on the x-y plane. Qubit 0 rotates π/8 radians every increment and this angle increases by two times as we move to the qubits to the right. Qubit 1 rotates π/4 radians, qubit 2 rotates π/2 radians and qubit 3 rotates π radians with every increment.</p><p><strong>Components necessary for QFT circuit</strong></p><ol><li><strong>Hadamard Gate</strong>: The Hadamard gate introduces superposition in a qubit. When applied on a qubit in computational basis, it converts it into Hadamard basis and vice versa.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/283/1*s-KA6pR1n0hSQVXstnET2Q.png" /><figcaption>Shows matrix representation of Hadamard gate</figcaption></figure><p>2. <strong>UROT Gate : </strong>The Unitary rotation gate applies a phase to a state.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/432/1*75lQyIIXug9dwPo32BECRg.png" /><figcaption>Shows matrix representation of UROT gate.</figcaption></figure><p>3. <strong>CROT Gate : </strong>The controlled Unitary rotation gate applies a phase only if the control bit is 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/481/1*-UPZFluiU-RUzllcepjqTg.png" /><figcaption>Here, we can see that when control qubit is 0, it does not apply any phase.</figcaption></figure><p><strong>QFT Circuit</strong></p><p>Given below is the QFT circuit of a 3 qubit system.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/860/1*l88PNviNGf6qZKwVfR1rFw.png" /><figcaption>Here H represents Hadamard gate and R2 represents UROT gate with k=2</figcaption></figure><p>Step 1: Apply H gate on first qubit, which is |j1⟩.</p><p>Step 2: Apply CROT gate on |j1⟩ with k=2 and |j2⟩ as control qubit.</p><p>Step 3: Apply CROT gate on |j1⟩ with k=3 and |j3⟩ as control qubit.</p><p>After these 3 steps, we obtain the final state of |j1⟩ as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/236/1*fibhE4vsLK32Cd93QgzDhw.png" /></figure><p>Now, we move on to the second qubit |j2⟩.</p><p>Step 4: Apply H gate on second qubit, which is |j2⟩.</p><p>Step 5: Apply CROT gate on |j2⟩ with k=2 and |j3⟩ as control qubit.</p><p>After steps 4 and 5, we obtain final state of |j2⟩ as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/221/1*5EpwcUsTW7KtvzPSGdyk7A.png" /></figure><p>Step 6: Apply H gate on |j3⟩.</p><p>After this steps, we get |j3⟩ as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/1*1nOPxslecFTW-FwY63ydwQ.png" /></figure><p>On comparing these final states obtained above to the QFT formula on n-qubits discussed earlier, it is clear that the order of the qubits have been reversed. The final result of |j1⟩ should be the final state of |j3⟩ according to the QFT equation. On extending this circuit to n qubit systems, we can see that we have to swap the values of kth qubit and the (n+1-k)th qubit to get the correct answer.</p><p><strong>How is QFT different from classical Fourier transform?</strong></p><p>It is different from the classical Fourier transform in a number of ways. Firstly, QFT acts on qubits which can be in a superposition of states, whereas classical Fourier transform acts on classical bits. Secondly, in case of classical Fourier transforms, some information is lost forever in the transformation. So, it cannot be reversed. QFT, on the other hand, can be reversed using the inverse QFT operation.</p><p>References</p><ol><li><a href="https://learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform">https://learn.qiskit.org/course/ch-algorithms/quantum-fourier-transform</a></li><li><a href="https://iipvapi.com/spatial-domain-and-frequency-domain-for-image-enhancement">https://iipvapi.com/spatial-domain-and-frequency-domain-for-image-enhancement</a></li><li><a href="https://www.youtube.com/playlist?list=PLOFEBzvs-VvrXTMy5Y2IqmSaUjfnhvBHR">https://www.youtube.com/playlist?list=PLOFEBzvs-VvrXTMy5Y2IqmSaUjfnhvBHR</a></li></ol><p>Written by - Parvathi Nair</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6ced371a99ee" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dead & Alive 2.0: IIT Roorkee Qiskit Fall Fest 2023]]></title>
            <link>https://medium.com/@qcgiitr/dead-alive-2-0-iit-roorkee-qiskit-fall-fest-2023-80adfc829d78?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/80adfc829d78</guid>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Thu, 14 Dec 2023 16:47:49 GMT</pubDate>
            <atom:updated>2024-02-08T13:18:47.143Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>Dead &amp; Alive: IIT Roorkee Qiskit Fall Fest 2023</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*AsCBuPPgojxKPExFkXBX7A.jpeg" /><figcaption>Introductory workshop Day 1, IIT Roorkee Qiskit Fall Fest 2023</figcaption></figure><p>Carrying forth the saga that continues to draw inspiration from Schrödinger’s obscure cat, the <strong>Quantum Computing Group at IIT Roorkee</strong> successfully conducted the <strong>third edition </strong>of <strong>Qiskit Fall Fest ‘Dead &amp; Alive’</strong> this year as well. The event was conducted in collaboration with (and sponsored by) IBM Quantum Community as part of their Fall Fest 2023 and IITR.</p><p>While the hackathon took place between 3–5 November 2023, there was an exciting lineup of events preceding it from 18 October 2023 until the weekend of the hackathon. It was open for all IIT Roorkee students, and there were workshops covering Quantum Computing basics, Quantum Algorithms and a touch of Cryptography as well. These insightful hours gave budding quantum computing enthusiasts a starting point to explore and innovate.</p><p>On 3rd November’23, the Opening Ceremony marked the start of the hack day, followed by a hands-on Qiskit session. The judging criteria, hackathon prompts and rules were revealed during the ceremony and a discord server was set up to ensure smooth interaction. There were two tracks- General and Freshers Track. The two-day hackathon brought forth incredible projects, reinforcing the vastness of quantum technology. The closing ceremony closed the curtains to the event with project presentations from all participants and a QnA segment by the organisers for each project. The winners received medals, gift cards and IBM Swag, thanks to the generous sponsors of the fest.</p><p>This year’s fest saw 70+ enthusiastic participants in total within IIT Roorkee itself, which was an incredible leap from previous years’ numbers. All important information pertaining to the hackathon was made available on <a href="https://qcg.iitr.ac.in/hackathon.html">QCG’s web page</a>. Let’s delve into the thrilling saga of quantum possibilities and breakthroughs in this year’s edition of Dead and Alive Fest; as we hear from the winners of the hackathon themselves.</p><p><strong><em>&gt;&gt; The </em>GENERAL PROMPT<em> asked participants to make novel Quantum Software based projects, be it code based, research based or any other implementation that is essentially rooted in Quantum Computing.</em></strong></p><h4><strong>First place (General Prompt)- Quantum Codebreakers</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wCpkTxDe372iRUUy1lDqMw.jpeg" /></figure><p>Vineet Kumar, Shourya Goel, Parvathi Nair, Atul Kumar collaborated on crafting an educative game called “Quantum Crush.” Explore their innovative project <a href="https://github.com/Sh0g0-1758/Zenith-zealots">here</a>.</p><p>This is what the team had to say about their experience and the idea behind their project:</p><blockquote>Quantum Codebreakers proudly present “Quantum Crush,” an <strong>innovative game designed to demystify the fundamentals of quantum computing</strong> while offering an engaging and entertaining experience. Drawing inspiration from the addictive dynamics of popular games like Candy Crush and 2048, Quantum Crush introduces players to the intriguing realm of quantum mechanics through an interactive and intuitive gameplay format.</blockquote><blockquote>The game unfolds within a 4 by 4 grid, each border representing a distinct quantum gate. The grid is populated with movable tiles that respond to player commands using designated control keys. As these tiles traverse the grid, colliding with the walls, the corresponding quantum gate manipulates their quantum states. Additionally, when two identical tiles converge, they merge — a strategic aspect that players must leverage to advance in the game.</blockquote><blockquote>The <strong>ultimate objective</strong> in Quantum Crush is to strategically maneuver the tiles, leveraging quantum gates effectively, and progressively reduce their number within the grid. The game’s brilliance lies in its adaptability — through varying the initial tile configurations and the complexity of the gates, Quantum Crush offers a scalable challenge that caters to beginners and advanced learners alike. This flexibility enables the creation of multiple levels, each presenting a unique set of quantum puzzles to solve and conquer.</blockquote><blockquote>Quantum Crush stands as an interactive gateway to the world of quantum computing, fostering an enjoyable learning experience that encourages exploration and understanding of this cutting-edge technology. With its blend of entertainment and education, this game serves as an excellent tool for enthusiasts and novices to grasp the fundamentals of quantum mechanics in an engaging and immersive manner.</blockquote><p>Congratulations to Quantum Codebreakers on securing first place in the hackathon!</p><h4>Second place (General Prompt)- Grover’s Lover</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/602/1*De8ThiuqXC3wQZ1S9_ZnIw.jpeg" /></figure><p>Satyam Sonaniya, a one-man team, went on to create “SPEEDY block cipher.” Find the project <a href="https://smart-office-54c.notion.site/Dead-and-Alive-team-Grover-sLover-eeab3ffe80d3443c8f7674dfbbb2172d">here</a>.</p><p>This is what Grover’s Lover had to say about Dead and Alive event and the submission:</p><blockquote>SPEEDY block cipher is <strong>an encryption algorithm meant for encrypting low latency hardware.</strong> To explore the power of Grover’s Quantum alogirthm, I came across the research paper on “SPEEDY Quantum Circuit for Grover’s Algorithm” [<a href="https://inspirehep.net/files/e1ea5c9944ae30efb760b9618fb66d6d">https://inspirehep.net/files/e1ea5c9944ae30efb760b9618fb66d6d</a>]. Here the authors proposed a quantum circuit for the SPEEDY block cipher and estimated its security strengths. Based on their findings, increasing the number of rounds of encryption is insufficient to ensure security against quantum attacks on quantum computers.</blockquote><blockquote>I found it fascinating, so I decided to code the Qiskit implementation for the given algorithm. The major challenge was writing different functions for the Oracle of Grover’s algorithm and then correctly executing them in the Oracle.</blockquote><blockquote>The Dead &amp; Alive event provided me with a day and two nights, so I tried to make most out of it. It taught me the power of doing projects to learn a concept. Thanks QCG and IBM for organizing such a great event.</blockquote><p>Kudos on achieving the second spot in the hackathon!</p><h4>Third place (General Prompt)- Quad</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7IS-ulgfCUvTV3OZXAeDNA.jpeg" /></figure><p>Ankit Lal, Yug Maheshwari, Swastika Sanghi teamed up to work on “Quantum Error Correction”. Their project can be seen <a href="https://github.com/ankitlal-iitr/qcg_quantum.git">here</a>.</p><p>Describing their journey in the hackathon, this is what Quad said:</p><blockquote>Hello! I am Yug from team Quad. We started our project on Saturday evening (4th November) after quiz . With only basic knowledge it was challenging at first. We had recently read about quantum error correction and with the guidance of Priyanshu and Arnav sir we were able to do it.</blockquote><p>Congratulations Team Quad, the third place is yours!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*y6zzlclpkkfwXll9fPYPsQ.jpeg" /></figure><p><strong><em>&gt;&gt; The</em> FRESHERS PROMPT <em>involved solving a graded python notebook containing code and theory based challenges on Quantum Computing Fundamentals, which was then scored.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/889/1*r5a3U4AzwrGVF3Pckgt3DA.jpeg" /></figure><h4>First place (Freshers Prompt)- Parth Baranwal</h4><h4>Second Place (Freshers Prompt)- Dhairya Kotecha</h4><h4>Third place (Freshers Prompt)- Daksh Pandey</h4><p>Daksh scored the third highest points in this track. As a fresher, the hackathon was a truly enriching experience and this is what Daksh had to say about it:</p><blockquote>This hackathon is one of the best things that happened to me in college. I was very interested in quantum computing, and I never imagined myself gaining an understanding of quantum computing like I have now. The hackathon pushed me to learn quantum computing and, more importantly, understand what was happening behind these quantum algorithms. Brainstorming and those “aha” moments made this hackathon worth it.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*isp0jg38emsP-cFIhIS6uA.jpeg" /><figcaption>All the winners at the award ceremony together!</figcaption></figure><p>It was a pleasure to organise the event and witness the passion of the students who participated in IIT Roorkee’s Qiskit Fall Fest Event 2023. We thank everyone who supported us in making this event a success. Quantum Computing Group hopes this sparked an interest in Quantum Computing in atleast a few of the participants and now the readers of this blog, and we hope to hear from you in the future. Stay tuned for more!</p><p><strong><em>~Written by Aastha Khaitan</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=80adfc829d78" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Variational Quantum Algorithms]]></title>
            <link>https://medium.com/@qcgiitr/variational-quantum-algorithms-66367053a2f3?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/66367053a2f3</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[quantum-physics]]></category>
            <category><![CDATA[quantum-computing]]></category>
            <category><![CDATA[quantum-mechanics]]></category>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Fri, 23 Jun 2023 04:17:33 GMT</pubDate>
            <atom:updated>2023-06-23T04:17:33.572Z</atom:updated>
            <content:encoded><![CDATA[<p>The emergence of quantum computation as a solution to high computational complexity problems on classical devices, such as large-scale linear algebra and discrete optimization, has led to a key technological question: How can today’s NISQ (Noisy Intermediate Scale Quantum) devices be optimally utilized to achieve quantum advantage?</p><p>In addressing this question, Variational Quantum Algorithms have emerged as promising solutions that respect the aforementioned constraints. These algorithms adopt the concept of training quantum computers in a similar manner to training neural networks, that is, finding the optimum parameters of the model to minimize/maximize some objective function related to that model.</p><p>In order leverage NISQ devices, it is necessary that there exists a certain subroutine of larger algorithm that a quantum circuit can perform. Variational Quantum algorithms are such near-term quantum-classical algorithms, and the quantum subroutine is explained by the Variational Quantum Circuit. This quantum circuit takes input data (or the state preparation) and outputs measurement statistics. It is also subject to certain parameters. While the measurements and cost functions are processed using quantum resources, the optimizer updates the parameters via an outer classical loop.</p><h3><strong>Brief overview of VQA</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*SREyympa_7L6lAU_VG2mEQ.png" /><figcaption>Fig 1: source: <a href="https://arxiv.org/pdf/2012.09265.pdf">https://arxiv.org/pdf/2012.09265.pdf</a></figcaption></figure><p>Quantum Variational Algorithms are inspired by the <strong>Variational Principle</strong> (explained in detail in a bit) in Quantum Mechanics. These algorithms contain modular circuit components, are problem statement agnostic and work to calculate approximate solutions for a given problem. The versatility of VQAs translates to different algorithmic structures with varying complexity levels, but there’s a core framework (as shown in Fig 1) that remains common to all variational algorithms:</p><ul><li><strong>Problem initialization:</strong> The quantum computer is initialized in a default state<strong><em> |00..0&gt;</em></strong>, transformed by a non-parameterized unitary reference operator <strong><em>Ur</em></strong> and the reference state<strong><em> |R&gt;</em></strong> is obtained.</li><li><strong>Circuit Ansatz:</strong> (the architecture of the circuit) sometimes fixed for an algorithm, sometimes user dependent. Helps us go from the default state <strong><em>|00..0&gt;</em></strong> to target state <strong><em>|Y(x)&gt;.</em></strong> The transformation is aided by a variational operator of the form <strong><em>Uv(x)</em></strong> which is a collection of explorable parameterized states. Ansatz operator can be collectively thought of as:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/242/1*4dI4EdRkyauYYgFNKjJiug.png" /></figure><ul><li><strong>Cost function: </strong>A problem-specific objective function is required to systemize the particular objective we wish to maximize/ minimize in the end. We encode it as<strong><em> C(t)</em></strong>, which is a linear combination of Pauli operators running on a quantum system.</li><li><strong>Training procedure:</strong> This subroutine essentially uses a function computed from the output measurements of the quantum circuit and iteratively updates the circuit parameters based on that information until it converges to an optimal solution. If a sub-optimal solution is already known, the information could be leveraged by making it the initial point to bootstrap the optimization process.</li></ul><h3><strong>The Variational Principle</strong></h3><p>The variational principle is one of the most fundamental one in Quantum Mechanics. It helps us find approximations to the energy of the ground state of a system, and some excited states. It holds far reaching implications, and helps when we can’t find an analytical solution to the Schrodinger equation. For example, using the variational principle, we can estimate wavefunctions of molecular orbitals.</p><p>In very superficial terms, this method consists of choosing an unnormalized trial wavefunction <strong><em>Y(x)</em></strong> which depends on variational parameters <strong><em>x</em></strong>. We then try and find values of <strong><em>x</em></strong> for which the expectation of the energy of the system is minimum. The wavefunction obtained at these parameter values then becomes an approximation to the ground state wavefunction, and the expectation value itself becomes an upper bound to the ground state energy.</p><p>In quantum mechanics, energy translates in the form of a quantum observable, referred to as the Hamiltonian. Why is knowing the upper value of the ground state energy of value to us? Because the upper bound of energy a physical system acts as a good estimate to the real value (which is often difficult to obtain). Ground state energy is fundamental to quantum chemistry, and the knowledge of this value helps us quantify interesting intricacies of molecule properties, such as binding energy, molecular pathways etc. The closer our approximate value for ground state energy is to the real value, the more accurately we can derive the subsequent, more complex properties. Quantum computers are of tremendous help in ensuring a good approximation ratio for such cases and are thus deployed for use here.</p><p><strong>Let&#39;s dive deeper into the formulation of the Variational Principle:</strong></p><p>Given a Hilbert space and a Hermitian operator over it, called a Hamiltonian <strong><em>H</em></strong>, we consider the discrete spectrum of <strong><em>H</em></strong> (using <a href="https://en.wikipedia.org/wiki/Spectral_theorem">Finite Discrete Spectral Theorem</a> in order to ignore the complications that arise with continuous spectra) and a basis formed by<strong><em> |Yi&gt;</em></strong> [The eigenvectors, where <strong><em>&lt;Yj|Yi&gt; = 1</em></strong> if <strong><em>i=j</em></strong>, and <strong><em>0</em></strong> elsewhere].</p><p>The characteristic equation for <strong><em>H</em></strong> would hold, forming the relation,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/183/1*mn1eIhAIJDoDG_TPK-Tr7Q.png" /></figure><p>where <strong><em>Ei </em></strong>is the i-th eigenvalue (physically the i-th energy level), <strong><em>i</em></strong> ranges within the <strong><em>N</em></strong> dimensional space of states and <strong><em>|Yi&gt;</em></strong> is the corresponding eigenstate. Along the same lines, the spectral decomposition of <strong><em>H</em></strong> would be,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/230/1*EAoPwLdG6I8qAu4-q2A-_A.png" /></figure><p>To get the energy value for the given state<strong><em> |Y&gt;</em></strong> we calculate the expectation value of <em>H</em>, <strong><em>&lt;Y|H|Y&gt; = E(Y)</em></strong>. If the state being considered is an eigenstate, we get <strong><em>&lt;Yi|H|Yi&gt; = E(Yi).</em></strong> For the eigenstate associated with the lowest eigenvalue, we obtain the ground state energy <strong><em>E0</em></strong>.</p><p><strong><em>E0</em></strong> is theoretically the lowest possible energy, hence energy <strong><em>E(Y)</em></strong> of an arbitrary state <strong><em>|Y&gt;</em></strong> would always follow <strong><em>E(Y)≥E0</em></strong>. Equality holds only when the arbitrary state is the ground state itself. This is so because,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/950/1*NBU0Kr_pQ5l0WTgp3OgW1w.png" /></figure><p>This is the variational method in brief, and we do obtain <strong><em>E(Y)</em></strong>, which is always an upper bound to the ground state energy. Exactly what we wanted, right? Turns out, knowing just any upper bound yields no value, and the upper bound closest to <strong><em>E0</em></strong> is what we’re looking for.</p><p>In an attempt to locate an upper bound as close as possible to the ground state energy (and the corresponding ground state), we try to minimize the expectation value of <strong><em>H</em></strong>. For this, we must vary over all possible normalized states so that they’re inherently an eigenstate of <strong><em>H</em></strong> too (which is what the proof begins with). There’s a problem though- varying over the entire Hilbert space is quite complex to realize for physical calculations. How would we, then, proceed to calculate a good estimate of the upper bound practically? ansatz solve the issue by smartly considering an appropriate subset of the Hilbert Space for optimally choosing the state that gives the minimum expectation value. More on ansatz in the next section.</p><p>There’s another underlying issue that we did not consider. It is an established fact that we seldom know the true eigenstates<strong><em> |Yi&gt;</em></strong> or the eigenvalue <strong><em>E</em></strong> for the studied system. This rips us from the very start of the variational method as we just described it. A workaround to this that’s commonly used is to take a trial (unnormalized) wavefunction <strong><em>|z&gt;</em></strong>, parameterize it to <strong><em>|z(a_i)&gt;</em></strong>, and express it as an expansion of a normalized wave function,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*rMxKjDo2qKT_Ndr7oDLbXQ.png" /></figure><p>This trial wavefunction would too, give us <strong><em>&lt;Z|H|Z&gt; ≥ E0</em></strong> because the ground state wavefunction will always have the lowest energy, and a trial wavefunction works just as well in keeping the inequality intact.<strong><em> Z</em></strong> can be expanded as a linear combination of the real eigenfunctions of <strong><em>H</em></strong> (assumed to be normalized and orthogonal) with the initial parameters acting as the set of multiplied constants,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/178/1*j9VzkSpDOZ7Yz1WXCh-SdA.png" /></figure><p>so that,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/218/1*m7PCuNutTJateR9MMmyUKw.png" /></figure><p>Therefore,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/212/1*PN_W0HEki5R1aftSuhWY8Q.png" /></figure><p>If trial wavefunction <strong><em>|z&gt;</em></strong> is normalized,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/445/1*0-1grKDqpRqea5kJ4LtfDA.png" /></figure><p>confirming our initial expansion of<strong><em> |Z&gt;</em></strong>.</p><p>Tying the entire formulation up, let’s reiterate a few key points again:</p><p>For the Hamiltonian<strong><em> H</em></strong> that describes the studied system, we choose an unnormalized trial wave function <strong><em>|z(a_i)&gt;</em></strong> which depends on variational parameters <strong><em>a_i,</em></strong> and minimize the functional <strong><em>E[a_i]</em></strong> (with respect to <strong><em>a_i</em></strong>)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/213/1*mPL6BwDEXU1h3b0nrMPWQw.png" /></figure><p>This gives an approximation to the wave function, which gets closer to ground truth with a clever choice of <strong><em>|Z(a_i)&gt;</em></strong> and number of parameters. For more rigorous methods, a set of basic functions with expansion coefficients <strong><em>a_i</em></strong> may be used.</p><p>To this extent, the variational principle states that:</p><ul><li><strong><em>E[a_i] ≥ E0 </em></strong>is the lowest energy eigenstate (ground state) of the Hamiltonian H.</li><li><strong><em>E[a_i] = E0</em></strong> if and only if<strong><em> |Y&gt;</em></strong> is exactly equal to wavefunction corresponding to the lowest energy (ground state) of the system.</li></ul><h3>The Ansatz</h3><p>In general Quantum computing terms, ansatz is a way to make an educated guess about the value/form/solution of an unknown function and after knowing the guess we can arrive at the real solution quicker and better. They hold direct relevance in solving Variational Quantum Algorithms on NISQ Hardware effectively, and have been used in popular algorithms such as VQEs, QAOA etc. Also known as the state-preparation circuit/ variational form, an ansatz translates as a subroutine formed by parameterized gates acting on certain wires in a quantum circuit and provides us with a trial (starting) point. This model is directly analogous to that of a Neural Network architecture- in the sense that artificial neural networks too are parameterized mathematical models, with the purpose of mimicking real, unknown functions of high dimensions in a way that’s just a good enough approximation of said function. The more intricate correlations between the two will be elaborated upon in a bit, following a deeper understanding of ansatz themselves.</p><p>Let’s get back to the reason which led to ansatz in the first place. We wanted to explore the entire Hilbert space in search for the variational solution (which is encoded as the minimum eigenvalue) of the modeled problem in a reasonable manner. Parameterized circuits offer a good way out. A parameterized quantum circuit is a tunable unitary operation on <strong><em>n</em></strong> qubits, <strong><em>U(x)</em></strong>, which is applied to the input state (<strong><em>x</em></strong> is a vector of a polynomial number of circuit parameters). Taking an example, say we have a circuit, with a simple RY gate. It is subjected to a single parameter, which is the rotation angle <strong><em>x0</em></strong>. Even with this simple arrangement, we’re able to traverse a wide spectrum of quantum states. In order to cover more states, we add different gates such as RX, RZ and expand our spectrum of traversable quantum states, without actually having to undergo the process to move around the entire Hilbert space. This is how ansatz are used to optimally restrict the variational search to a limited, more appropriate subspace. In conclusion, an ansatz will prepare the state on which the variational principle will be applied.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/865/1*AEcv9iYWlyInrOLQCNRtDA.png" /><figcaption>Schematic diagram of an ansatz. The unitary circuits, with a set of parameters applied sequentially have been shown. They can be expressed as a product of L unitary circuits acting on input state, which can further be decomposed into a series of gates. source: <a href="https://arxiv.org/pdf/2012.09265.pdf">https://arxiv.org/pdf/2012.09265.pdf</a></figcaption></figure><p>For the cost function pertaining to the problem, we encode the parameters <strong><em>x </em></strong>in a unitary <strong><em>U(x)</em></strong> and apply it to the input states of the quantum circuit. <strong><em>U(x)</em></strong> can be expressed as the product of <strong><em>L</em></strong> unitary circuits applied sequentially,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/392/1*jeTb6ZiLa2DV8KDxZye1lw.png" /></figure><p>and they can be decomposed further into certain sets of gates as shown in above figure,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/344/1*qzNCF3Jl4602Eg_WKkTV1w.png" /></figure><p>where <strong><em>W_m</em></strong> is an unparameterized unitary gate, and <strong><em>H_m</em></strong> is a Hermitian operator, subject to parameter vector <strong><em>x</em></strong>. This is analogous to the <strong><em>Ua(x) </em></strong>as mentioned in the brief overview of VQAs.</p><p>Retracing to our analogy with Neural Networks. Neural networks have a non-linear scalar function that non-linearly transforms each neuron layer into the next. All these layers form part of its internal hidden layers and work well to generalize on the data decently. With ansatzes too, we now notice, that this structure directly resembles the variational quantum circuit model. The gates in the quantum circuit apply a linear unitary transformation to each layer, leading to transformation of our input states. One tiny difference is not all entities of the transformation matrix of a quantum circuit acts as parameters, it&#39;s just the ones corresponding to the tunable parameters of the gates. It is in this sense that the variational quantum circuits can be fundamentally looked at as an efficient parameterization of linear transformation in high dimensions.</p><p>Several general ansatz architectures have been proposed in literature, some of them being Hardware Efficient Ansatz (HEA), Unitary Coupled Ansatz (UC), Quantum alternating operator ansatz etc.</p><p>The performance of a VQA depends on if and/or how well the eigenstate with respect to the smallest eigenvalue can be reached. The architecture of the ansatz and how well the parameters have been tuned to the specific VQA are crucial in deciding this. As the model architectures in Machine Learning follow the no-free-lunch theorem, so do the ansatz choices for variational algorithms, their strength depends on the use-case, and there’s no universally good ansatz. There are some ‘problem-inspired’ ansatzes, while others are ‘problem-agnostic’ and can be used when no relevant information of the problem is available. The key is to be able to cover a reasonable amount of space, with a smaller number of gates (and parameters), making it less error-prone, and giving us control over its optimization.</p><h3>The Cost Function</h3><p>Encoding our problem into a cost function is an important step in VQA. As in its classical analogy, the cost function here maps the parameters we train our quantum circuit on to real numbers. Qualitatively, it encapsulates the cost surface of the problem, over which the classical optimization loop traverses to search for the global minima.</p><p>The cost function can be generally expressed as <strong><em>C(x)</em></strong>, where.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/307/1*V82omaSU3hzT-EQqns8KjQ.png" /></figure><p>here, <strong><em>f </em></strong>is the functional dependent on the problem, <strong><em>U(x)</em></strong> is the parameterized unitary which is derived from the ansatz, <strong><em>x</em></strong> is the set of continuous or discrete parameters, <strong><em>P_k</em></strong> are the input states from training set and <strong><em>O_k</em></strong> is a set of observables. As we figure out the cost function, our main goal is to figure out the formulation of <strong><em>f</em></strong>.</p><p>The cost function must be formulated in a way that respects the following properties:</p><ul><li>The minimum of <strong><em>C(x)</em></strong> must correspond to the solution of the problem.</li><li>The formulated <strong><em>C(x)</em></strong> should be such that it can be estimated reasonably well by performing measurements on a quantum circuit and after classical post-processing. (It is taken as obvious that the cost function is expensive to compute with purely classical methods, implying that VQA provides a quantum advantage).</li><li>The cost function must be ‘trainable’, i.e., the parameters<strong><em> x</em></strong> must be efficiently optimizable. For implementation in NISQ hardware, the circuit depth and ancilla requirements must be kept small.</li></ul><h3>Training procedure and Optimizers.</h3><p>Optimizers are used in Variational Quantum Algorithms to find the optimal solution by performing efficient exploration of the parameter space and so, the success of a Variational Quantum Algorithm depends on efficiency and reliability of the optimization technique employed. The parameters of the Ansatz Circuit are varied to minimize the energy expectation value. This is where optimizers come in.</p><p>Optimizers provide the means to adjust these parameters iteratively, moving towards the optimal configuration that minimizes the energy efficiently. Various optimization algorithms, such as gradient descent or stochastic gradient descent, can be employed to search for the minimum energy solution. Let’s briefly explore some of these optimization techniques.</p><h4>- <strong>Gradient descent methods:</strong></h4><p>Gradient descent methods are a family of optimization algorithms commonly used to find the minimum of a function. Mathematically, the goal of gradient descent is to iteratively update the parameters of a function in the direction of the negative gradient, which points towards the steepest descent. Given a cost or loss function, gradient descent aims to minimize it by adjusting the parameters in small increments.</p><p>The update step in gradient descent can be represented as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/281/1*Gwxf-1pSNI-htGyQQFIe-A.png" /></figure><p>Here, <strong><em>x </em></strong>represents the parameters of the function, <strong><em>alpha</em></strong> is the learning rate (a small positive constant that controls the step size), and <strong><em>dJ(x)</em></strong> denotes the gradient of the cost function <strong><em>J</em></strong> with respect to the parameters <strong><em>x</em></strong> at iteration<strong><em> t</em></strong>.</p><p>The method starts with an initial guess for the parameters and then repeatedly updates them using the gradient until convergence or a stopping criterion is reached. The learning rate determines the step size in each iteration. It is crucial to choose an appropriate learning rate, as a small value may result in slow convergence, while a large value may cause overshooting and instability.</p><h4>- Meta Learning:</h4><p>In the context of VQAs, meta-learning focuses on learning an optimization strategy or an initialization scheme that can be applied across multiple instances of VQA problems by leveraging insights gained from previous optimization tasks.</p><p>During meta-training, the meta-optimizer adapts its parameters based on the performance of various optimization algorithms on the training tasks. It learns to recognize patterns in the problem characteristics and the corresponding optimization strategies that lead to improved convergence and accuracy. This way, it can capture high-level knowledge about the relationship between VQA problems and optimization techniques.</p><p>When faced with a new VQA problem, the trained meta-optimizer applies the learned optimization strategy or initialization scheme to optimize the VQA parameters efficiently. By transferring knowledge from previous tasks, it can provide a more informed and effective optimization process, potentially accelerating convergence and improving the quality of the obtained solutions.</p><h3>VQE in brief</h3><p>The Variational Quantum Eigen-solver (VQE) is a variational quantum algorithm designed to estimate the ground state energy of a given quantum system. It combines classical optimization techniques with a quantum circuit (ansatz) to find the optimal parameters that minimize the energy expectation value.</p><p>Mathematically, let’s consider a quantum system described by a Hamiltonian <strong><em>H</em></strong>. The goal is to find the lowest eigenvalue <strong><em>E0</em></strong> and its corresponding eigenvector <strong><em>|Y0&gt;</em></strong>. The VQE algorithm approximates this ground state energy by preparing a parameterized trial state <strong><em>|Y(x)&gt;</em></strong> using a quantum circuit, where <strong><em>x</em></strong> represents the parameters of the ansatz.</p><p>The trial state is prepared by applying a sequence of quantum gates to an initial state, typically the computational basis state<strong><em> |00...0&gt;</em></strong>. The ansatz circuits can be designed to capture specific properties of the system under study.</p><p>The energy expectation value <strong><em>&lt;Y(t)|H|Y(t)&gt;</em></strong> is then measured using quantum measurements. Since these measurements are probabilistic, multiple measurements are performed to estimate the expectation value accurately.</p><p>The VQE algorithm employs classical optimization methods, such as gradient descent, to find the optimal parameters <strong><em>x</em></strong> that minimize the energy expectation value. The final set of parameters obtained represents an approximation of the ground state energy <strong><em>E0</em></strong>. The corresponding state <em>|Y(t)&gt;</em> can also provide an approximation of the ground state <strong><em>|Y0&gt;</em></strong>.</p><p>The VQE algorithm allows for variational optimization of the parameters, enabling the exploration of the parameter space to find the minimum energy solution. By combining classical optimization techniques with the power of quantum circuits, VQE offers a promising approach for solving problems in quantum chemistry, materials science, and simulation of very large quantum systems on quantum computers.</p><h3>Challenges faced by VQA.</h3><p>Although VQAs can provide quantum advantage in solving different problems on near-term quantum computers, there are several challenges prominent that restricts the efficiency and accuracy of VQAs. The most common challenges are Barren Plateaus and Accuracy issues.</p><h4>- Barren Plateaus:</h4><p>Barren plateaus in VQAs refer to regions in the parameter space where the gradients of the cost function become exceedingly small, leading to slow convergence or no progress in optimization. Mathematically, this is represented by a very small or vanishing norm of the gradient <strong><em>||dJ||</em></strong>. Imagine traversing a vast landscape with flat regions where the slope becomes nearly imperceptible. In VQAs, as the complexity of the quantum circuits increases, the parameter landscape becomes flatter, making it difficult for optimization algorithms to find the optimal solution efficiently. To tackle barren plateaus, researchers explore techniques like adaptive optimization methods, better initialization strategies, and introducing additional structure in the circuits to provide better guidance for efficient optimization. Check out the section in reference [1] for further details on optimization methods.</p><h4>- Accuracy Issues:</h4><p>Reduction in accuracy arises due to the effect of noise on training and the reduced efficiency in calculating the energy expectation values in Variational Quantum Algorithms (VQAs). Noise in quantum systems, caused by factors like decoherence and gate errors, can introduce errors in the computation and measurement process. These errors propagate throughout the optimization process, impacting the accuracy of the results. Moreover, the calculation of energy expectation values often requires multiple measurements, which can be resource-intensive in terms of time and qubit resources. The accumulation of noise and the increased number of measurements further reduce the overall efficiency and accuracy of VQAs. Techniques such as error mitigation, classical shadows, neural network tomography, error-correcting codes, and noise modeling are employed to alleviate the impact of noise and enhance accuracy.</p><h3>Where can we use VQAs?</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/820/1*3Z_QIS3IaiksMnqvS0EM8g.png" /><figcaption>source: <a href="https://arxiv.org/pdf/2012.09265.pdf">https://arxiv.org/pdf/2012.09265.pdf</a></figcaption></figure><p><strong>Quantum Chemistry: </strong>VQAs have been used to address problems in quantum chemistry, such as calculating molecular energies, capturing intricating interactions and optimizing molecular structures of highly complex molecules. By mapping the electronic structure problem onto a quantum circuit and employing VQAs, researchers aim to estimate ground state energies and simulate molecular properties. This has implications for drug discovery, material design, and catalyst optimization.</p><p><strong>Optimization:</strong> VQAs can be applied to optimization problems across various industries, and one in particular, the QAOA has been proven efficient in optimizing combinatorial problems, which we will cover in future blog. One example of such combinatorial problem is the traveling salesman problem (TSP), where the QAOA has been explored to find efficient routes with minimal distance. Additionally, VQAs have been used for portfolio optimization, logistics planning, and supply chain management, where finding optimal solutions can significantly improve efficiency and resource utilization.</p><p><strong>Machine Learning:</strong> VQAs have been explored for machine learning tasks like data classification and pattern recognition. By leveraging quantum circuits as feature maps or kernels, VQAs hold promise for improving the handling of complex datasets. Examples of VQA-based approaches in machine learning include Variational Quantum Support Vector Machines (VQSVMs) and Quantum Generative Adversarial Networks (QGANs). These applications demonstrate the potential of VQAs to enhance machine learning techniques by leveraging quantum computing principles.</p><h3><strong>References.</strong></h3><ul><li><a href="https://arxiv.org/pdf/2012.09265.pdf">https://arxiv.org/pdf/2012.09265.pdf</a></li><li><a href="https://www2.ph.ed.ac.uk/~gja/qp/qp8.pdf">https://www2.ph.ed.ac.uk/~gja/qp/qp8.pdf</a></li><li><a href="https://en.wikipedia.org/wiki/Variational_method_(quantum_mechanics)">https://en.wikipedia.org/wiki/Variational_method_(quantum_mechanics)</a></li><li><a href="https://arxiv.org/pdf/1905.10876.pdf">https://arxiv.org/pdf/1905.10876.pdf</a></li><li><a href="https://dash.harvard.edu/handle/1/42029810">Variational Quantum Information Processing (harvard.edu)</a></li></ul><p><strong><em>Written by Aastha Khaitan, Priyanshu Parakhiya.</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=66367053a2f3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Quantum Dot Qubits]]></title>
            <link>https://medium.com/@qcgiitr/quantum-dot-qubits-75708d0d7215?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/75708d0d7215</guid>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Thu, 04 May 2023 16:42:52 GMT</pubDate>
            <atom:updated>2023-05-04T17:42:02.191Z</atom:updated>
            <content:encoded><![CDATA[<h3>Introduction to bits and qubits:</h3><p>In modern computers, information/data is encoded as binary bit strings(01101…) on which we operate to get the result. How do we do it? Well, at the physical level, we encode and access data by adjusting the voltages of transistor gates which act as a switch inside the circuits. These transistors are then used to build logical units to perform operations controlled by applied voltages and memory units to store data. We start from a particular state, i.e., by initialising them, performing operations on them using logic gates and then reading and interpreting the results.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lmaXKOAqimX4JmdvcMnx5A.png" /><figcaption>Fig 1: Metal Oxide Semiconductors (MOS) transistors are shown in Figure (a), along with logic gates built using these transistors (NOT and AND gates from left to right) in Figure (b), storage elements (DRAM and SRAM, Respectively from left to right) in Figure (c).</figcaption></figure><p>The system designed and built as described above can only be in one specific state at a given instant. Suppose each of these bits could simultaneously hold and process multiple data. In that case, the computational advantage is enormous in terms of processing time, which is the idea behind building a quantum computer. Qubits are made by exploiting the quantum mechanical nature of the physical systems, such as spins of electrons, the polarisation of photons, level of the electron in the atom or by manufactured devices that mimic these physical systems via an inherent quantum nature, such as superconducting qubits ion traps etc., These devices aren’t just exponentially faster, but they can simulate physics which isn’t possible to do with transistor-based technology. The topic of this blog is one such system called “Quantum dots qubits” These are essentially electron spins in quantum dots. Read on to know more about this.</p><h4>Quantum dots:</h4><p>A quantum dot is just a zero-dimensional(zero-dimensional materials typically refer to nanoscale particles or clusters that could be considered point particles) material. The purpose of making this is to hold just one or a few entities, such as an electron, so how can we make one of these from the three-dimensional world we live in? Firstly we should make a 2D(it will have a thickness, but it’s extremely low, so it could be considered 2D). Two-dimensional space where electrons are trapped, called the electron gas layer (2DEG — two-dimensional electron gas), is formed by heterostructures, for example, a thin layer of AlGaAs grown on top of a GaAs wafer; this leads to a lowering of energy in the GaAs side at the interface, due to strain in its bonds as it tries to adhere to the lattice structure of AlGaAs at the interface, due to which the electrons accumulate on the GaAs side of the interface.</p><p>On the surface of the wafer, metallic gate electrodes are placed at specific locations to deplete electrons in those regions selectively to facilitate the formation of quantum dots. There is also a different set of metal gates that are in contact (called ohmic contacts) with the 2DEG, allowing electrons to flow into and out of the 2DEG through the surface of the wafer. There are much more efficient ways to gate the wafer to make a quantum dot. Multiple gate layers could be stacked on top of each other, insulated from one another, each layer for a specific purpose. The first layer of gates on the wafer gets to the one-dimensional transport layer and then an additional layer to deplete electrons in this 1D layer to form quantum dots. This kind of design gives better control over the one described in the below Figure. Follow the references given to know more.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/766/1*5piyVOeQBLBPpUj7z9QCdA.png" /><figcaption>Fig 2: (a) Planar double quantum dot device schematic. Surface electrodes define depleted regions in the 2DEG below. Small puddles of charge formed by the depleted region represent the quantum dots. Scanning electron micrographs of a single quantum dot (b).</figcaption></figure><h4>Qubits:</h4><p>Now that you know how the one-dimensional electron traps are made, let us look at the idea behind quantum dot devices. Figure 3, depicted below, was the first proposal for a device made out of quantum dot qubits. The circular objects in the Figure represent the wavefunctions of single electrons in quantum dots.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/622/1*6lNUD1AiD1fRRA6YvO4CZA.png" /><figcaption>Fig 3: Loss-DiVincenzo architecture, the very first proposal for quantum dot qubits.</figcaption></figure><p>Qubit levels are defined by a single electron’s spin-up and spin-down states in a magnetic field. States are initialised by cooling the electrons in a uniform magnetic field. At the same time, qubits are operated on to put them into different states by controlling the interaction of a single quantum dot with a local ferromagnet(strong magnet), shown in Figure 4. Two-qubit control is done by modulating a tunnel barrier between two neighbouring dots by applying a gate voltage as the control signal.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ew52Urskh-YRuPqODXRW1Q.png" /><figcaption>Fig 4: This is a Si/SiGe heterostructure; here, this QD is designed such that spin-up and spin-down electrons have a different energy, allowing us to address the spins separately.</figcaption></figure><p>Finally, since spin-up and spin-down electrons have different energies in the presence of a magnetic field, the spin state can be read out by tunnelling through a spin valve(it is at the junction separating the quantum dot and reservoir at which a sensitive charge sensor is placed) to a neighbouring reservoir. If the presence of the electron is detected on the reservoir using a sensitive electrometer, then we know it was a spin-up electron (Figure 5).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/552/1*fGkyv3Ca0Uzoij1qrY20jA.png" /><figcaption>Fig 5: Here, only spin-up electrons tunnel out as they have sufficient energies. Hence the two basis states are distinguished from one another.</figcaption></figure><p>Now that you know how qubits are initialised and read, with a slight idea of how to operate on these qubits. Keep a look out for future blogs to know more about superposition, building logic gates, especially CNOT gates and so on, with mathematical rigour! Can’t wait? Go ahead and learn about it from the references given below.</p><h4>Further Reading Material:</h4><p><a href="https://doi.org/10.1103/PhysRevA.57.120">https://doi.org/10.1103/PhysRevA.57.120</a></p><p><a href="http://arks.princeton.edu/ark:/88435/dsp01f4752k519">http://arks.princeton.edu/ark:/88435/dsp01f4752k519</a></p><p>Written by Bhoomika Tanikonda.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=75708d0d7215" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dead & Alive: IIT Roorkee Qiskit Fall Fest 2022]]></title>
            <link>https://medium.com/@qcgiitr/dead-alive-iit-roorkee-qiskit-fall-fest-2022-d5e3e3018f83?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/d5e3e3018f83</guid>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Sun, 08 Jan 2023 10:59:54 GMT</pubDate>
            <atom:updated>2023-01-08T11:28:19.487Z</atom:updated>
            <content:encoded><![CDATA[<p>The Quantum Computing Group, IIT Roorkee conducted the Qiskit Fall Fest “Dead &amp; Alive”, a quantum computing based hackathon in association with IBM Qiskit. Yes, the title is inspired by Schrodinger’s famous cat thought experiment. The hackathon was conducted from 4th November, 2022 to 6th November, 2022.</p><p>QCG conducted two workshops: one introducing the fundamental concepts and the diverse potential of quantum computing and the other was a hands-on session on Qiskit. The workshops served to familiarize the newcomers with QC, enabling them to explore and innovate further. These were followed by the opening ceremony, where the rules and judging criteria were revealed. Students participated in teams of 2–4 members and the 42 hour hackathon began. A discord server was created for sharing resources and smooth communication between the organizing team and the participants.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FYD8WIYjhYx8Ctfs1oCKiw.jpeg" /><figcaption>Workshop 1: Introduction to Quantum Computing</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FnFCLahWYvObjKNuAXU8cw.jpeg" /><figcaption>Our inspiration: Schrodinger’s famous cat, in a superposition of both ‘Dead’ &amp; ‘Alive’ states</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hinLGyXntRfySu7TLLE7GQ.jpeg" /><figcaption>Workshop 2: Hands-on Session on Qiskit</figcaption></figure><p>On 6th November, the hackathon ended with participants uploading their projects on GitHub. All participating teams who had completed and submitted their projects presented their work to the judges followed by Q&amp;A. Refreshments were served during the workshops and closing ceremony.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JjWmlq_jCDLDinjjte2jEw.jpeg" /><figcaption>Presentations and Closing Ceremony</figcaption></figure><p>The top three teams for the general prompt were awarded a cash prize of Rs. 3500, Rs. 2000, Rs. 1500 respectively along with medals. In this blog, we share the results and experiences of the top three teams.</p><h3><strong>First Place: |Quantelligent&gt;</strong></h3><p><strong>Project: |Qricket&gt;</strong></p><p><em>We, team |Quantelligent&gt;, wanted to see how quantum circuits can be used to simulate actual cricket matches. Hence, our project ‘|QricKet&gt;’ was able to successfully simulate an innings for a cricket match using actual statistical data of various cricketers against various types of bowlers. The main idea was to use quantum circuits to simulate each ball’s outcome and possible variation in strategies. The two main libraries we used were Qiskit and pandas (for data processing).</em></p><p><em>We decided to work with T-20 matches. With reference to actual strategies, we calculated the probabilities of choosing a type of bowler facing the batsman (like 96% chance of selecting a fast bowler in overs 1–3 and 19–20, 95% chance of choosing a spin bowler in overs 9–15 and equal probabilities otherwise). Using these probabilities, we initialize our state vector to a corresponding state and perform a measurement using which we choose the bowler for that over. Using data of probabilities of various batters against various types of bowlers. We also simulate each ball with a known batter and bowler using the help of a quantum circuit where we initialize our state vector with the probabilities of that particular batsman against a specific type of bowler. The other rules are like those of actual cricket. For the sake of simplification and due to lack of sufficient data, we made certain assumptions: no doubles, no wide/no balls, each ball is an independent event etc.</em></p><p><em>In the future, ideas of AI can be incorporated to closely simulate the behavior of individual cricketers. With further modifications, we can actually use this for the purpose of virtual sports entertainment.</em></p><p><strong>Link to the Project</strong>: <a href="https://github.com/aarav-rm8/QricKet/">https://github.com/aarav-rm8/QricKet/</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*hCv6B-iRuFIRKnoK" /><figcaption>|Quantelligent&gt;: Aarav Ratra, Ankit Patel, Nandini Gupta, Keerthi</figcaption></figure><h3><strong>Second Place: Code Beyond</strong></h3><p><strong>Project: QDECC</strong></p><p><em>QDECC stands for Quantum Decryption, Encryption and Classification of Cyphers this was the project presented by team Code Beyond at the Dead &amp; Alive Hackathon. QDECC comprises a Decryptor, Encryptor and Classifier. The Decryptor uses Shor’s Algorithm to decrypt RSA-encrypted data. The encryptor uses BB84 protocol to securely encrypt data and The classifier utilizes Machine learning with Long Short Term Memory(LSTM) cell, a Quantum circuit comprising of a Rotation gate and SoftMax for classification of cyphers.</em></p><p><em>The team’s overall experience with the hackathon was in one word enthralling.</em></p><p><em>All the members were new to the domain of quantum computing and had to learn concepts and code implementations from the very scratch.</em></p><p><em>The team first came together as enthusiasts to explore quantum computing and we started reading basic content about Quant and attended the introductory workshops held by QCG. The Hackathon began at 9 pm on the 4th of march but we took our time familiarizing ourselves with qiskit and quantum concepts and held our first team project meeting at 2 am, the project was selected as an attempt to integrate Quantum computing with Machine learning and Information Security. The work division went well and the Decryptor, Encryptor and classifier were at first developed independently and then later combined as one finished product. The Hackathon had different phases for us: the initial phase was of doubt and confusion regarding how we were going to implement the project that we had ideated upon and learning the concepts of encryption and decryption. Then came the ugly phase of debugging where no code seems to run correctly and fixing a part of the code leads to a bug in another. Anyhow persevering through the phase on Sunday morning we finally had a workable code and then we developed a frontend for it, with satisfaction for our efforts and nervousness about the results we made our final submission.</em></p><p><em>The team members each had a unique personal experience at the hackathon as Ronnit says, “The 2-days of brainstorming and adrenaline rush was a good experience as we were able to learn about qiskit in a short time frame and apply it in real world application.” While Yathartha Rana feels “The Quantum hackathon was a great experience for me. I learned a lot within 42 hours.” From Yatharth Mishra “without any doubt it was a wonderful experience for me as the amount of learning I gained in that period was incredible. It was also my first Hackathon which taught me how to work collectively as a team.” And from me, Yash Tanwar as the team leader and member I would say “Dead &amp; Alive was an exhilarating experience of learning, bonding and exploring for me.”</em></p><p><strong>Link to the Project</strong>: <a href="https://github.com/YatharthaRana/TeamCodeBeyond-QDECC">https://github.com/YatharthaRana/TeamCodeBeyond-QDECC</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*qiXcoH9QkzhSwjdU" /><figcaption>Code Beyond: Yash, Ronnit Gupta, Yathartha Rana, Yatharth Mishra</figcaption></figure><h3><strong>Third Place: QuanTech</strong></h3><p><strong>Project: Quantum-Password-Generator</strong></p><p><em>The main motivation behind making this project was utilizing the absolute randomness of quantum random number generators. Contrary to this, in the classical methods a pseudorandom number is generated which is made by manipulating constants like date and time. Next, we wanted to create a Password manager which automatically creates random passwords and stores them, so that users do not have to remember all the passwords.</em></p><p><em>Our project provides two layers of security to the user. Firstly, we use quantum computing to create an untraceable password for the user. Secondly, to access this set of passwords the software checks the MAC address of the device being used along with the user’s registered password to decrypt the database. This ensures that even if the system is compromised, the data and stored passwords are safe.</em></p><p><em>In the project, we used a Hadamard gate on seven qubits to create a circuit with equal probability for every number. On measurement a random number between 0–127 is generated. Then, this number will be turned into the corresponding ascii value and a string with random characters will be generated.</em></p><p><em>Talking about the interface, the user needs to enter the name of the website/application for which the password needs to be created, the interface then generates the password, encrypts it and stores it in the database. To access the database, the user needs to enter the password of the database, followed by the name of the application/website they need to access the password for, the system decrypts it and returns it back to the user.</em></p><p><strong>Link to the Project: </strong><a href="https://github.com/aakashks/Quantum-Password-Generator">https://github.com/aakashks/Quantum-Password-Generator</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*kUeJGdYPdOEtxSxc" /><figcaption>QuanTech: Aakash Kumar Singh, Shree Singhi, Samarth</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*k35xMPJt1-EgIMXs" /><figcaption>All winners of the General Prompt</figcaption></figure><p>Apart from the usual projects, a separate challenge was created for the freshman year, based on fundamentals of quantum computing, which had to be submitted by the freshers individually.</p><p>The top three freshers in the individual challenge were awarded medals along with IBM Swags.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*eGsv3K335mpt-N8w" /><figcaption>Winners of Freshers Prompt: Atish Kumar Sahoo, Pratham Agarwal, Kishan Singh</figcaption></figure><p>It was an incredible experience for everyone, including the organizers who finally had the opportunity to see the events unfold offline. We congratulate all the winners and participants for developing such exciting projects, spanning multiple domains of quantum computing and for contributing to the Qiskit community.</p><p>Stay tuned for more such events from QCG IITR in the future!</p><p><em>Written by Anvita Prasad</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d5e3e3018f83" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Post Quantum Cryptography]]></title>
            <link>https://medium.com/@qcgiitr/post-quantum-cryptography-214b4e4b269a?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/214b4e4b269a</guid>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Fri, 21 Oct 2022 07:06:19 GMT</pubDate>
            <atom:updated>2022-10-21T07:06:19.978Z</atom:updated>
            <content:encoded><![CDATA[<p>It’s an exciting time to work on quantum technologies; quantum computers are nearly upon us. It is a common belief that commercially viable quantum computers will be available within the next twenty years. While we are yet to grasp the implications of quantum effects being fully exploited, we will undoubtedly see significant developments in fields like AI and Data Science, where quantum computing will help us truly understand and make the most of existing data.</p><p>Unfortunately, not everyone gets to view the arrival of quantum computers with nothing but excitement. Cryptographers, the practitioners responsible for protecting people’s data and privacy on the internet and beyond, are preparing to see decades of well-tuned techniques for hiding data invalidated by the first wave of sophisticated quantum machines.</p><p>Before we get to precisely what Post-Quantum Cryptography (PQC) is, let us first go over the basics of the prerequisites required to understand it.</p><h3><strong>Cryptography (Classical):</strong></h3><p>“Cryptography is the practice and study of techniques for secure communication in the presence of adversarial behaviour. Cryptography is generally about constructing and analyzing protocols that prevent third parties or the public from reading private messages.”</p><p>That was the Wikipedia definition of cryptography. Basically, what cryptographers do is solve and analyze variants of the following problem:</p><p>“Alice wants to send a secret message to Bob, but she has no private channel through which to send this message. Furthermore, she worries that Eve may try to intercept her secret message and obtain the information in the message. So, what can Alice do?”</p><p>This is where encryption comes in. Assume that there is a key only known to Alice and Bob. Alice can use this key to encrypt a message (imagine putting it in a locked box), and once Bob receives this message, he can decrypt it (unlocking the box) with the key. Even if Eve intercepts the communication, she won’t be able to make sense of the message (she has the locked box but not the key).</p><p>This type of cryptography is known as Symmetric Key Cryptography, as the same key is used in both the encryption and decryption processes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*L9MRQBthjNlE-1g-8rjP9Q.png" /><figcaption>Figure 1: Overview of Symmetric Cryptography (Source: CryptoQuantique)</figcaption></figure><p>However, there is an obvious shortcoming associated with this method. What if Alice and Bob can’t or haven’t agreed on their secret key? In the real world as well, parties are unlikely to have been able to agree on a key in advance. Just think about it, when you enter your bank details to complete a transaction on a website you’ve never been on before, you haven’t agreed on any secret key in advance, yet you don’t encounter any security lapses. This is where we come across the techniques of Public Key Cryptography.</p><p>Coming back to Alice, Bob and Eve, in Public Key Cryptography, Bob makes a pair of keys: a public key and a private key. He sends the public key out in the world. When Alice wants to send a message to Bob, she uses the public key to encrypt the message. Once Bob receives the message, he uses the private key to decrypt the message. If Eve intercepts the communication, she only has the message and the public key but not the private key, so she can’t make sense of the message.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/829/1*-SUg0esFWhtuc6LnHjR4nw.png" /><figcaption>Figure 2: Overview of Public Key Cryptography (Source: Tutorialspoint)</figcaption></figure><p>So, the question is, how secure is Public Key Cryptography? If Bob can decrypt a message encrypted with a public key using a private key, there must be some relationship between these keys. Thus, all Eve has to do to read the message is extract the private key from her knowledge of the public key and the encryption scheme. Therefore, the scheme’s security is directly proportional to the computational complexity of finding the private key from the public key.</p><p>Consider the famous RSA cryptosystem; here, Bob’s public key is a large integer (say n), and the private key is the pair of primes (say p and q) where n = p*q. So, Eve’s task here is finding p and q from n. As simple as it may sound, there is no efficient algorithm (classical) that can find p and q from n. Here, an efficient algorithm refers to one that has polynomial time complexity. This problem is referred to as the famous ‘integer factorization’ problem.</p><p>Another famous mathematical problem used to enhance the security of cryptosystems is the ‘discrete logarithm’ problem. In this problem, one has to find n such that aⁿ ≡ b (mod p) where we know a, b and p. The ‘≡’ denotes the modular congruence operator. (Notice how the equation looks analogous to n = logₐb, hence the discrete logarithm name). There isn’t any efficient algorithm (classical) that can find n in this problem as well. This fact is used in the Diffie-Hellman protocol.</p><p>This was an overview of classical cryptography and some techniques used to ensure communications security.</p><h3>The Quantum Angle:</h3><p>While Classical Cryptography uses the ‘hardness’ of certain mathematical problems to ensure security, Quantum Cryptography (not to be associated with PQC, they are pretty different) uses certain favourable principles of quantum mechanics to do the same. The no-cloning theorem states that it is impossible to create an independent and identical copy of an unknown quantum state, guaranteeing that a message can’t be copied without the sender’s knowledge. Quantum mechanics also provides the ability to detect the presence of an eavesdropper attempting to learn something about the message. This is because when Eve wants to observe something, she must make a measurement. As soon as she makes this measurement, she disturbs the state of the message qubits, which is immediately known to the sender. Via these properties, the security of communication is ensured in Quantum Cryptography. To learn more about Quantum Cryptography and Quantum Key Distribution protocols, follow this <a href="https://medium.com/@qcgiitr/fundamentals-of-quantum-key-distribution-bb84-b92-e91-protocols-e1373b683ead">link</a>.</p><h3>PQC:</h3><p>While quantum mechanics’ properties can help secure communications, quantum attacks can also be powerful enough to render classical cryptosystems obsolete. Shor’s algorithm, developed by American mathematician Peter Shor in 1994, is an algorithm that can factorize an integer on a ‘feasible’ quantum computer in polynomial time. Shor’s algorithm breaks the RSA cryptosystem.</p><p>Even worse, the main building block of Shor’s algorithm, the Quantum Fourier Transform, can be adapted to break most other commonly implemented cryptography, such as Diffie-Helman key exchange and Elliptic Curve Digital Signatures. The only reason practices like the RSA and Diffie-Hellman are still in practice is that we don’t have a feasible quantum computer.</p><p>To prepare for this eventuality, cryptographers have developed the subject of Post-Quantum Cryptography: the study of cryptography which can be run on classical computers while being resistant to quantum attacks.</p><p>We have seen how quantum computers are effective against existing public-key cryptography protocols. However, they won’t be able to provide much improvement on symmetric key cryptosystems. This is because typical symmetric schemes, like the AES, rely on the “fast and efficient” mixing of objects. To decrypt the ciphertext, you must manually perform the unmixing steps. Due to Grover’s algorithm, any symmetric key cryptosystem would incur a significant security loss, but this can be mitigated simply by doubling the key length. Thus, the main focus of PQC is updating public key cryptography.</p><p>To update public key cryptography, we need to find problems that are ‘hard’ for a quantum computer as well. Let us look at some of the leading computational problems in PQC. The bulk of proposed PQC schemes lies in one of four main categories: lattice, code-based, multivariate, and isogeny-based cryptography. Let us look over some of the aspects of the first three.</p><p>Starting with the most popular category: lattice cryptography. A lattice can be understood as a regular grid of points in space. The points on the lattice are chosen systematically from an object called its basis, which describes the lattice by explaining how you move between lattice points.</p><p>There have been computationally complex problems on lattices long before the RSA and Diffie-Hellman schemes even existed. This provides some confidence in the belief that these problems will also withstand quantum attacks.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/763/1*BQCm1VW7wVGJDVo17JT2_g.png" /><figcaption>Figure 3: A Lattice with Two Different Bases</figcaption></figure><p>The backbone of lattice cryptography comes from an interesting observation about these bases. Using the green basis, it is straightforward to understand the shape of the lattice and how to get from one point to another using the shortest path. On the other hand, the red basis overly complicates finding paths from one point to another, and it is also tough to verify that there isn’t a shorter path. So, one can consider the green basis as a ‘good’ basis and the red as a ‘bad’ one. This is the idea used in Lattice-based cryptosystems: a bad basis is used as a public key, and a good basis as the private key. The bad basis’s description of the lattice will be complicated enough to hide the message, and only the receiver can solve the problem quickly, as this requires knowledge of the good basis. Lattice cryptography tends to be the most flexible category of PQC since there is a lot of design space to work with regarding how one chooses lattices and hides points.</p><p>Code-based cryptography includes cryptosystems whose security relies, partially or totally, on the hardness of decoding a linear error-correcting code. A well-chosen error-correcting code serves as the private key for a cryptosystem based on this, and the accompanying public key is the method of encoding the message. Encryption is straightforward: the sender encodes the message as usual and then simulates an unreliable channel by manually inserting some errors. An adversary without access to the description of the error-correcting code cannot recover the message as long as there are enough errors, whereas the intended recipient can decode it using their error-correcting code. These schemes have huge public keys and compare poorly with existing schemes like the RSA. However, we may see a shift back to Code-based cryptography as they seem secure against quantum attacks.</p><p>Multivariate cryptography is based on the problem of solving systems of multivariate polynomial equations. A typical multivariate quadratic equation looks something like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-N7RpNzBJx1HC0ZeTLLmzg.png" /></figure><p>This problem is an NP-Complete problem. It is not expected that quantum computers will be able to solve NP-Complete problems. Current schemes in Multivariate cryptography perform poorly as compared to lattice-based schemes. However, it demonstrates potential, and there is hope that we will see tremendous advances in the future.</p><h3>Standardization:</h3><p>Standardization is developing a protocol that is fit for practical use based on specific guidelines. In 2016, the National Institute of Standards and Technology (NIST) initiated this process via an open call asking for proposals for post-quantum algorithms and key-encapsulation methods.</p><p>The two main features NIST are looking for are security and efficiency: if a protocol isn’t secure, then there’s no point in using it to protect data, and if it isn’t efficient, it will slow down internet communications. PQC tends to perform slower than its pre-quantum counterpart, so an algorithm can be considered efficient if there is little to no drop in performance when using it in place of an existing pre-quantum scheme.</p><p>After a proposal is submitted, it is subjected to months of cryptanalysis and is thoroughly examined. Initially, there were 69 proposals submitted. As of now, there are only four schemes selected for further examination. Although these schemes have all been thoroughly vetted, they each come with different strengths and weaknesses that are useful to understand.</p><h3>Conclusion:</h3><p>It is not long before we see the first sophisticated quantum computer. To ensure data security, one must start preparing for this eventuality. Keeping up to date with happenings around the NIST process will satiate the curious observer. For people tasked with keeping data safe, they need to consider the pros and cons of each algorithm, factoring in what they need. For your sake and mine, we need to hope that PQC advances fast enough to protect us when the first wave of capable quantum computers arrives.</p><h3>Further Reading Material:</h3><p><a href="https://csrc.nist.gov/projects/post-quantum-cryptography">The Official NIST Website</a></p><p><a href="https://en.wikipedia.org/wiki/Post-quantum_cryptography">PQC — Wikipedia</a></p><p><a href="https://link.springer.com/content/pdf/10.1007/978-3-540-88702-7.pdf">A Book on PQC — Contains information on Lattice, Code-Based, Multivariate Cryptography and more.</a></p><p>How MNCs Are Contributing: <a href="https://cloud.google.com/blog/products/identity-security/how-google-is-preparing-for-a-post-quantum-world">Google</a>, <a href="https://aws.amazon.com/blogs/security/tag/post-quantum-cryptography/">Amazon</a>, <a href="https://www.microsoft.com/en-us/research/project/post-quantum-cryptography/">Microsoft</a></p><p><a href="https://twitter.com/PQCryptoConf">Updates on the PQCrypto Conference 2022</a></p><p><em>Written by Sudarshan Shenoy</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=214b4e4b269a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Quantum Walk]]></title>
            <link>https://medium.com/@qcgiitr/quantum-walk-9acb8ae2a20a?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/9acb8ae2a20a</guid>
            <category><![CDATA[quantum-computing]]></category>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Sat, 09 Jul 2022 16:51:29 GMT</pubDate>
            <atom:updated>2022-07-09T16:51:29.077Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/350/1*9MGPAj_8etxtbQg5oLyR8Q.png" /><figcaption>Source : SciTech Daily</figcaption></figure><p><strong>Motivation</strong></p><p>Dealing with exponential solution space is a big challenge for modern-day computer science. Most of the time, we have to turn to a probabilistic approach to know about the structure of such solutions. Markov chains or random walks are one of the resorts in such cases. We start with an initial state and change the state randomly (based on a random measurement such as a coin flip) until the probabilistic distribution spreads throughout the space. Random walks can be performed in n-dimensions, though the simplest to understand is a one-dimensional walk. The distribution in the one-dimensional case is binomial, i.e., if the walker has an equal probability of taking either a left or right step, then the distribution is a bell curve with the starting point as the peak.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*WdMufR3ptSv18e9SXCeA5Q.png" /><figcaption>The coordinates of the dimension on the X-axis vs Probability on Y-axis</figcaption></figure><p>This can be explained as : If the walker has N steps to take, and he wants to get to X coordinate, and he takes L step left and R step right, then L+R=N and R-L = X, thus we get a specific value of L and R. As how we reach to X doesn’t matter (We can first take R steps then L or first L and then R or anywhere between), the probability to get to X is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/43/1*tAIPrZR5iHncTD3VhM3Vfg.png" /></figure><p>multiplied by the probabilities of taking L left and R right steps. This clearly results in a binomial distribution.</p><p>Natural processes like genetic drift or polymer chaining evolve randomly. In finance, share prices are modelled using random walks as they can’t be precisely predicted. Google uses random walks to calculate Page Rank, and many other web properties can be found by traversing it randomly. Thus, if applied to general problems (for example, check <a href="https://arxiv.org/pdf/quant-ph/0210064.pdf">this</a>), a quantum walk has great use cases as it will provide exponential or polynomial speedups over the classical counterparts.</p><p><strong>The Quantum Alternative</strong></p><p>In the classical version, we use probabilistic measurements to decide where to move next (There are also continuous-time random walks, which will be explained later in this blog). The quantum model differs from the stochastic one in that different states (or positions in terms of walk), as well as the state change (direction in which walker moves), can exist in superposition and thus produce interference. It leads directly to the fact that the standard deviation of the distribution is proportional to the number of time steps for the quantum case. Thus, the quantum walk spreads quadratically faster than the classical random walk on the solution space, thus providing exponential speedups in cases where oracle can be designed in such a way.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/534/1*toHC_WR2i6burtSrkU480g.png" /></figure><p>A simple way to understand it is to perform the quantum walk on a ring-shaped graph. We can form a Hilbert space spanned by the basis state |j&gt;, j=0,1…N-1 (total N nodes) for the jᵗʰ node. The direction of the movement at each step can be found by using a quantum coin consisting of two basis states for the two directions. The whole space of the system is then the tensor product of these two Hilbert spaces. The shift operator below is then applied to the state to perform the quantum walk.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/853/1*m14Raj_7QXduT3ebgbNigQ.png" /></figure><p>It can be then calculated that:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/456/1*0lhzPfMIaAa6qHkt1tJspg.png" /><figcaption>When coin state is |0&gt;, the walk goes to the previous node</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/456/1*nbxUu0Czf-OYnRN8MsJX4A.png" /><figcaption>When coin state is |1&gt;, the walk goes to the next node</figcaption></figure><p>The coin state can be randomized by using the Hadamard gate on it, and thus any quantum walk step can be represented by the unitary operator</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/258/1*SsWrqyTbb8NTq5KKrIgbTg.png" /><figcaption>I being identity</figcaption></figure><p>The distribution in the case of Quantum Walk looks like below(assuming we initialise the coin vector in the |+&gt; state, if we start with |0&gt; the distribution won’t be symmetric and will tend towards left, as can be understood by applying multiple H-gates to |0&gt; and analysing the probability) :</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/378/0*ROZfiVWpyHTonIhg.png" /><figcaption>The spread is more with peaks at the ends. (Source: Google QuantumAI)</figcaption></figure><p>The reason for drift towards left/right when initialized with |0&gt;/|1&gt; is constructive and destructive interference of amplitudes which makes the case different from classical which is symmetric.</p><p><strong>Continuous-Time Quantum Walk</strong></p><p>Summarizing the discrete case, the walker’s state can be given by a stochastic matrix acting on the previous state, i.e., p(t+1) = M⋅p(t). We can easily extend this to the continuous domain by forming this equation as a differential equation dp(t)/dt = H⋅p(t), with H being a time-independent matrix. The solution for this is known to be p = exp(Ht)⋅p(0). It can be extended to the quantum case with now H being a Hamiltonian and the unitary operator being</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/255/1*jQVhUG3r5wx4vaSMPGIQng.png" /></figure><p>It can be understood as the evolution of a discrete position space in continuous time (rather than flipping a coin to move), which basically means the Schrödinger equation on a discrete spatial domain.</p><p><strong>Conclusion</strong></p><p>The Quantum walk approach has the potential to tackle many problems which are limited by the speed of current classical algorithms. It also can be applied to many searching problems like element distinctness or structure finding, which can’t even be solved by Grover efficiently. Some examples can be found <a href="https://cdn.intechopen.com/pdfs/15646/InTech-Search_via_quantum_walk.pdf">here</a>.</p><p>If you want to further dive into this topic, here are some resources:</p><p><a href="https://arxiv.org/pdf/1201.4780.pdf">Quantum walks: a comprehensive review</a></p><p><a href="https://en.wikipedia.org/wiki/Quantum_walk">https://en.wikipedia.org/wiki/Quantum_walk</a></p><p><a href="https://quantumai.google/cirq/experiments/quantum_walks#classical_random_walks">https://quantumai.google/cirq/experiments/quantum_walks</a></p><p><a href="https://arxiv.org/pdf/quant-ph/0311001.pdf">Quantum Walk Algorithm for element distinctness</a></p><p><em>Written by Aman Pandey</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9acb8ae2a20a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Grover’s Algorithm: A Simplified Interpretation]]></title>
            <link>https://medium.com/@qcgiitr/grovers-algorithm-a-simplified-interpretation-dcf04228bc9d?source=rss-63a4262f07e4------2</link>
            <guid isPermaLink="false">https://medium.com/p/dcf04228bc9d</guid>
            <dc:creator><![CDATA[Quantum Computing Group, IIT Roorkee]]></dc:creator>
            <pubDate>Mon, 16 May 2022 15:45:38 GMT</pubDate>
            <atom:updated>2022-05-16T15:45:38.603Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="A big marble and a prism lying next to each other." src="https://cdn-images-1.medium.com/max/1024/0*EL8_H5eIEH8VBiDX" /><figcaption>Photo by <a href="https://unsplash.com/@lazycreekimages?utm_source=medium&amp;utm_medium=referral">Michael Dziedzic</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Quantum algorithms can be classified based on the techniques used. They are classified as follows:</p><ul><li>Algorithms based on Phase Estimation — These include algorithms like Shor’s algorithm, HHL algorithm etc.</li><li>Algorithms based on amplitude amplification — These include Grover’s algorithm, Oblivious Amplitude Amplification etc.</li><li>Algorithms based on quantum walks — This family of algorithms include algorithms for searching, Hamiltonian Simulation etc.</li><li>Adiabatic Algorithm — This family consists of many algorithms for searching, solving linear systems etc.</li><li>Hybrid quantum-classical algorithms — This family includes variational algorithms like VQE, QAOA, VQLS etc.</li></ul><p>For the time being, we will focus on Grover’s algorithm, which is actually a member of amplitude amplification based algorithms.</p><h3>The Grover’s search problem</h3><p>The problem that Grover’s algorithm deals with is as follows:</p><p>Suppose you have an unstructured list of N items which means the list is not sorted and lacks any kind of pattern or structure. We want to search for an element in this list, what is the best known classical solution we have?</p><p>Since the list is unstructured, the best we can do is a linear search and in the worst case it will take O(N) time. But with Grover’s algorithm, it turns out that we can do this in O(√N). Thus Grover&#39;s algorithm gives a quadratic speedup which becomes significant when we use a list with many elements.</p><p>Now we shall look at the trick behind Grover’s algorithm, the answer to why it does what it does.</p><h3>Major concepts involved in Grover’s algorithm</h3><p>As you would imagine, analyzing Grover’s algorithm is more difficult than describing it. When analyzing, it will help to think about reflections and rotations in the plane.</p><h4>Reflection</h4><p>Here is a reflection of a vector<strong> |𝜓&gt;</strong> about the line L:</p><figure><img alt="a vector in a 2D plane reflected about a line L gives another vector which makes equal angle with the line L." src="https://cdn-images-1.medium.com/max/404/0*rmsTwIx3Mzk0p-8J" /><figcaption>Source: <em>John Watrous’s notes</em></figcaption></figure><h4>Rotation</h4><p>Rotation of a vector |<strong>𝜓&gt;</strong> in anti-clockwise direction by an angle θ:</p><figure><img alt="A vector in a 2D space is rotated by an angle theta i.e. after rotation the angle between them is theta." src="https://cdn-images-1.medium.com/max/368/0*aQw36xnAVADa796f" /><figcaption>Source: John Watrous’s notes</figcaption></figure><p>Now, suppose we have two lines L1 and L2, and the angle between them is θ. Then for any choice of<strong> |𝜓&gt;</strong> if you reflect<strong> |𝜓&gt; </strong>about L1 and then reflect about L2, the effect will be the same as rotating by an angle 2θ. From this, we know that two reflections are the same as one rotation.</p><figure><img alt="image contains two lines l1 and l2, angle between them is theta and reflecting a vector one by one about these lines rotates the vector by angle 2*theta." src="https://cdn-images-1.medium.com/max/560/1*R1X3isvTh4Awky3flGKk9A.png" /><figcaption>Source: John Watrous’s notes</figcaption></figure><p>So now we’ll see how these two concepts are important for our understanding of the Algorithm.</p><h3>Description of Grover’s algorithm</h3><p>Let’s denote the element we want to find as |x₀&gt;. Now we define two functions f(x) and f⁰(x).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/196/1*0O5PDa9turEC0Y7IeOI_FA.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/1*kJxyCwgOqJT_8gSyECB8Eg.gif" /></figure><p>They are implemented as an oracle (R𝒻) and a diffusion operator (RD) respectively. R𝒻 applies a negative sign before |x₀&gt; and leaves all the other states as it is and RD applies a negative sign to all states orthogonal to the state |00…0&gt;.</p><p>Mathematically these operators are defined as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/152/1*QMs4_N2yzhUiwqrOcx465Q.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/162/1*GfyhfdgDiluIalBcWekcLA.gif" /></figure><p>You can read more about quantum oracles <a href="https://docs.microsoft.com/en-us/azure/quantum/concepts-oracles">here</a>.</p><p>In Grover’s algorithm we start with a state which is the superposition of all the n-qubit states, let’s call this state |D&gt;, we then apply R𝒻 followed by RD.</p><p>|D&gt;, R𝒻 and RD can be written as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/140/1*Qr6ZIWIjtgzisExuuQoslw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/146/1*VauF-GL2bq-EnfzHGA5N1g.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/145/1*wbMyFZ6n6FibjWK9ClYY3w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/367/0*VFu4r2FS8iM9OThn" /></figure><p>We can understand the effect of the operators on |D&gt; from the figure above. Let’s assume a 2-D subspace where the y-axis is the vector |x₀&gt; and the x-axis denotes all the vector orthogonal to |x₀&gt;. We have |D&gt; making an angle of θ/2 with the x-axis.</p><p>Our current state is |D&gt; and we want the state |x₀&gt;. So we can say that we want to rotate our vector |D&gt; and the vector after rotation should align with the y axis. We have seen how two reflections are equivalent to a rotation. Here we will use this fact along with amplification of our result.</p><p>We first apply the R𝒻 operator which reflects the state |D&gt; about the x-axis and gives the state R𝒻|D&gt; then we apply the RD operator which reflects the state about |D&gt;.</p><p>This is it! We have rotated our initial vector by an angle θ. What can we do to increase the angle further? We just repeat this process!</p><h3>Amplitude Amplification</h3><p>In this algorithm, amplitude amplification is used to maximize the probability density of the state |x₀&gt; (that we want to find), and reduce the probability densities of the other states simultaneously after each iteration. Now, from the 2D subspace diagram mentioned above we can show that the ordinate value is constant at any point on the circle which equals the mean value of the unstructured list (i.e. 1/√N).</p><p>Therefore we can write</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/144/1*YyQJh6lvM-mStQcDqKRVww.png" /></figure><p>And</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/226/0*DAA2lHBraHr-gmZN.png" /></figure><p>where |xb&gt; is the vector orthogonal to |x₀&gt;, i.e. x axis represented in the 2D subspace above.</p><p>Now, the conjugate of |D&gt; can be written as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/233/0*cVYAd5acy6Q6gbD1.png" /></figure><p>And also,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/231/0*1aaGopZdyLOzA2hR.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/230/0*j0IoVdoJ0n-gMKen.png" /></figure><p>The search algorithm starts with the |D&gt; state, then applying R𝒻 will give the state:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/487/0*K2NOc9GJ6_QhDxKA.png" /></figure><p>Then after applying operator RD we get the state:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/518/0*U-ibGWPU9G75AQYf.png" /></figure><p>It is easy to verify by induction that after k iterations of the Grover iterator (U = RD.R𝒻) starting with state |D&gt; = H|00…..0&gt; we get,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/657/0*VJjx07e84quho5ys.png" /></figure><p>In order to obtain |x₀&gt; with high probability we must select k such that sin((2k + 1)θ) ≈ 1, which means that we would like (2k + 1)θ ≈ π/2 and thus</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/164/0*AWNvvYNdY-pJhZEz.png" /></figure><p>which means, we can obtain the desired result after only k iterations and k is of the order of √N hence the time complexity of Grover&#39;s algorithm is O(√N)!</p><p>Grover’s Algorithm can be generalized for searching more than one element from the given unstructured list, to know more check <a href="https://quantumcomputing.stackexchange.com/questions/5318/grover-algorithm-for-more-than-one-element">this</a>.</p><p>To know more about other quantum algorithms, follow our medium page.</p><p><a href="https://medium.com/@qcgiitr">Quantum Computing Group, IIT Roorkee - Medium</a></p><p><em>Written by Riya Malani and Prashik Somkuwar</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dcf04228bc9d" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>