<?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 Nadia Milazzo on Medium]]></title>
        <description><![CDATA[Stories by Nadia Milazzo on Medium]]></description>
        <link>https://medium.com/@nadimilaz?source=rss-cc131443486------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*S3Df5-zbU9OrWBNw_PFeog.jpeg</url>
            <title>Stories by Nadia Milazzo on Medium</title>
            <link>https://medium.com/@nadimilaz?source=rss-cc131443486------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 21:39:00 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@nadimilaz/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 error mitigation]]></title>
            <link>https://medium.com/colibritd-quantum/quantum-error-mitigation-ab21e9887327?source=rss-cc131443486------2</link>
            <guid isPermaLink="false">https://medium.com/p/ab21e9887327</guid>
            <category><![CDATA[nisq]]></category>
            <category><![CDATA[error-mitigation]]></category>
            <category><![CDATA[quantum-computing]]></category>
            <dc:creator><![CDATA[Nadia Milazzo]]></dc:creator>
            <pubDate>Tue, 01 Aug 2023 11:04:59 GMT</pubDate>
            <atom:updated>2023-08-01T11:04:59.052Z</atom:updated>
            <content:encoded><![CDATA[<h4>Experimenting with Mitiq</h4><p>A very recent work published in Nature [1] has again put the spotlight on a very interesting topic for near-term quantum devices: how to reduce the errors arising from calculations running on faulty hardware. And why those errors arise? That’s our old friend <strong><em>noise</em> </strong>coming back<strong> </strong>to make research always more fun! The researchers in [1] have used one of the biggest quantum hardware currently available to run computations on circuits for which classical techniques break down. They have shown that existing <strong>quantum</strong> <strong>error mitigation </strong>(QEM)<strong> </strong>techniques allow one to obtain reliable results despite the presence of noise, concluding that:</p><blockquote>[…] there is indeed merit to pursuing research towards deriving a practical computational advantage from noise-limited quantum circuits.</blockquote><p>In this article we will take a quick tour to understand the importance of QEM, how one among the several existing techniques works, and finally, how we can play with it using some simple code!</p><h4><strong>1. How is error mitigation different from error correction and why it is important?</strong></h4><p>A related field much more explored than error mitigation is quantum error <em>correction </em>(QEC)<em>. </em>As the names indicate, the former aims at reducing the errors, while the latter at completely removing them; in fact, fault tolerant quantum computing is reachable when the errors stay under a certain threshold (see [2] if you want to learn more about this <em>threshold theorem</em>). If the qubit demand of QEC was not that high, we would always apply QEC schemes to correct the results of noisy simulations; unfortunately, the number of qubits needed to do that overcomes currently available resources (some experiments showing the benefits of QEC schemes can be found in [3,4]). The need for simpler and more practical techniques started then the work around error mitigation (for a recent review on the topic see [5]), which instead does not require additional qubits, at the cost of more samples and partial error suppression. Let’s dive a bit deeper!</p><h4>2.<strong> How does Zero Noise Extrapolation work?</strong></h4><p>QEM techniques mostly rely on the post-processing of the results obtained from noisy devices and deal with expectation values of an observable. Among the most known and used we find Zero-Noise Extrapolation (ZNE) and Probabilistic Error Cancellation [6], Clifford Data Regression [7], Readout-Error Mitigation [8] and many others. We’ll have a look at the ZNE since it was the one used in [1]. A great feature of this method is that it can be applied even if the noise model is not known in detail (i.e. without tomographic knowledge of the hardware gates) and the main idea behind it is quite fun: we have noise which ruins the results of the great simulations we are running (not cool), but we do not despair! On the contrary, we embrace it and increase it higher and higher… and then we extrapolate the ideal result from those noisy measurements! There is a very important point to keep in mind when using this technique:</p><p><strong>Errors cannot be arbitrarily suppressed increasing noise indefinitely [5].</strong></p><p>To see why, we need to think about the resource overhead that this entails; we will follow [9] in the reasoning and equations below. Let Â be the observable we want to measure and 𝒩<strong> </strong>the noise process which introduces a small error ε.<strong> </strong>Then we can expand the expectation value of Â as a function of ε according to Taylor expansion:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/597/1*33-3MJmlldEnEgrdYTSLFw.png" /></figure><p>To estimate the ideal expectation value ⟨Â⟩(0), we consider different error rates and run several different noisy measurements; using <a href="https://en.wikipedia.org/wiki/Richardson_extrapolation">Richardson extrapolation</a> we can write an approximation of it as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/844/1*rpLyU22vk4pARW2R3le3UA.png" /></figure><p>In the expression above, all the <strong>a</strong> coefficients are greater than 1 (we are <em>increasing </em>the error rate) and the <strong>γ</strong> coefficients must be chosen such that:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*VXHOIoGhsS4oMPZdjA4E4g.png" /></figure><p>Doing so, we can estimate ⟨Â⟩(0) suppressing the error to</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/124/1*9cbUXHl0p7juVRQatPvZ2Q.png" /></figure><p>This results in the method being very efficient when ε is small! But wait, why were we doing all this (not that math is not fun…)? Let’s refocus on the <strong>cost of the error mitigation method</strong> outlined above and let us look at the variance of the approximated expectation value:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/622/1*COJt54VWSuuqMEw__K7oUQ.png" /></figure><p>The variance above is <strong>bigger </strong>than the one of ⟨Â⟩, meaning that we need to take more samples (or equivalently to allow for more “shots”) in order to achieve the same accuracy as in the ideal case!</p><p>Until now we have neglected another essential step of the ZNE method: how do we increase noise in practice? We’ll keep it very simple here consider the case of a quantum circuit where we increase the noise <em>at the gate level: </em>we can do that<em> </em>intentionally increasing its <strong>depth</strong>, a technique which is known as <em>unitary folding </em>[10].</p><h4>3.<strong> Pieces of implementation with Mitiq</strong></h4><p>True, we have seen very little theory, but we’ll take here a more hands-on approach and directly test some error mitigation techniques on the “Hello World” of quantum computing: a circuit to create a <a href="https://en.wikipedia.org/wiki/Bell_state">Bell state</a>. We’ll do that with an open-source toolkit called <a href="https://mitiq.readthedocs.io/en/stable/readme.html">Mitiq</a> [11], which allows you to use many different SDKs and backends (simulators and real hardware) and compare different methods and performances! The language used is Python (with no surprises ;)). The documentation of this package is rich of examples and starts with a very clear and coincise explanation of QEM objective:</p><blockquote>Current quantum computers are noisy due to interactions with the environment, imperfect gate applications, state preparation and measurement errors, etc. Error mitigation seeks to reduce these effects at the software level by compiling quantum programs in clever ways.</blockquote><p>In the following, we’ll use a bit of <a href="https://docs.aws.amazon.com/braket/">braket</a> and a bit of <a href="https://qiskit.org/">qiskit</a> with corresponding available hardware or simulators. As observable, we’ll use the fidelity (following definition in [12]) between the Bell state output of the noisy circuit and the ideal one; this quantity measures how <em>close</em> two quantum states are (for two identical states the fidelity is 1). We can give a visual representation of the distance between two quantum states in the 1-qubit case thanks to the Bloch ball representation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/891/1*sUMZXqsWVQ3Hpft1MUDzhg.png" /><figcaption>From left to right: An X gate acting on the |0⟩ state gives the state |1⟩. An imperfect X gate will map |0⟩ into the blue vector instead. The fidelity measures the distance between the orange (ideal) and blue (faulty) output.</figcaption></figure><p>In our case, the fidelity will tell us how well the hardware can prepare an entangled pair despite the noise. Let’s start!</p><p>We begin with testing ZNE on the available simulator via <a href="https://amazon-braket-sdk-python.readthedocs.io/en/latest/index.html">braket</a>. We need to import the needed packages and define circuit and observable:</p><pre>################################################# mitiq functions<br>from mitiq import zne<br>from mitiq.zne import mitigate_executor<br>from mitiq.zne.inference import RichardsonFactory<br>################################################# braket functions<br>import braket<br>from braket.devices import LocalSimulator<br>from braket.circuits import Circuit, Noise, Observable<br>################################################# other packages<br>import numpy as np<br><br>################################################# ideal density matrix |ψ⟩⟨ψ|<br>def density_matrix_pure(state_vector: np.ndarray) -&gt; np.ndarray:<br>    return np.outer(state_vector, np.transpose(np.conjugate(state_vector)))<br>bell_state = np.array([1/np.sqrt(2),0,0,1/np.sqrt(2)])<br>ideal_target_bell = density_matrix_pure(bell_state)<br><br>################################################# circuit for Bell state<br>circuit = Circuit()<br>circuit.h(0).cnot(0,1)<br>print(circuit)</pre><pre>T  : |0|1|<br>          <br>q0 : -H-C-<br>        | <br>q1 : ---X-<br><br>T  : |0|1|</pre><p>In the following block of code we define the <em>Executor</em>, one of the fundamental classes in Mitiq, which takes a circuit as input and outputs an expectation value (the simulator and the observable are specified inside the function). The noisy executor makes use of the noiseless one; as type of noise here we chose the <a href="https://en.wikipedia.org/wiki/Quantum_depolarizing_channel">depolarizing</a> one:</p><pre>def noiseless_executor(circ: Circuit) -&gt; float:<br>    device = LocalSimulator(&#39;braket_dm&#39;) <br>    circ.expectation(observable=Observable.Hermitian(matrix=ideal_target_bell), target=range(2))<br>    task = device.run(circ)<br>    result = task.result()<br>    return result.values<br><br>def executor_with_noise(circ: Circuit) -&gt; float:<br>    noise = Noise.Depolarizing(probability=0.04)<br>    circ.apply_gate_noise(noise)<br>    return noiseless_executor(circ)<br><br>noise_fidelity = np.sqrt(executor_with_noise(circuit))<br>print(noise_fidelity)</pre><pre>0.94775274 <br><br># Noisy result. The ideal value is 1, giving a discrepancy of ~0.05.</pre><p>As we can see, the fidelity is smaller than one! Let’s see now what happens if we mitigate with ZNE. We use three different noise levels, as specified in the <em>RichardsonFactory </em>function:</p><pre>fac = RichardsonFactory(scale_factors=[1, 3, 5])<br>mitigated_executor = mitigate_executor(executor_with_noise, factory=fac)<br>mitigated_fidelity = np.sqrt(mitigated_executor(circuit))<br>print(mitigated_fidelity)</pre><pre>0.9915175318851517 # mitigated<br><br>UserWarning: The input circuit is very short. <br>This may reduce the accuracy of noise scaling.</pre><p>Yay! The result has indeed improved and it is now much closer to 1. But, we got a warning ⚠ We should not worry, but it is useful to understand why it appears. We are increasing the noise by increasing the depth of the circuit, and we are using the <a href="https://mitiq.readthedocs.io/en/stable/apidoc.html#mitiq.zne.scaling.folding.fold_gates_at_random">default method</a> in Mitiq to do so; if we have very few gates in our circuit, the precision of this scaling is affected because “t<em>he folded circuit has a number of gates approximately equal to scale_factor * n where n is the number of gates in the input circuit</em>” [11]. This means that the scaled circuits are not that deep in the end for very small circuits!</p><p>If you want to make a more pondered decision — instead of using the default methods — it is possible to run a calibration of the ZNE technique on a benchmark circuit to see which combination of scaling and extrapolation methods works best (see <a href="https://mitiq.readthedocs.io/en/stable/examples/calibration-tutorial.html">this example</a> to know how to do that).</p><h4><strong>Warning! This is not a simulation!</strong></h4><p>Like in video games when you reach the last level and you need to defeat the final boss, we have now arrived at the ultimate test of this small QEM adventure: run our circuit on a real quantum computer. There, you don’t get to choose the type of noise or the intensity, you have the whole noisy package to deal with! To see how ZNE performs, we’ll use the available IBM devices. Here we go!</p><pre>################################################# qiskit functions<br>from qiskit import QuantumCircuit<br>from qiskit.quantum_info import SparsePauliOp<br>from qiskit_ibm_runtime import QiskitRuntimeService, Session, Options, Estimator<br><br>################################################# ideal density matrix |ψ⟩⟨ψ|<br>observable = SparsePauliOp(&quot;XX&quot;, coeffs = 1/4)+<br>             SparsePauliOp(&quot;YY&quot;, coeffs = -1/4)+ <br>             SparsePauliOp(&quot;ZZ&quot;, coeffs = 1/4)+<br>             SparsePauliOp(&quot;II&quot;, coeffs = 1/4)<br><br>################################################# circuit for Bell state<br>circuit = qiskit.QuantumCircuit(2) <br>circuit.h(0)<br>circuit.cx(0,1)</pre><p>As we can see, while the circuit construction remains untouched, we need to facilitate the “reading” of the observable for the hardware decomposing it in Pauli terms.</p><p>When running an observable job on an IBM real device, the easiest thing to do is to use the <em>primitives </em>of Qiskit Runtime. In this case, we will not make use of Mitiq, but we’ll directly set the “resilience level” option (ZNE corresponds to resilience_level = 2). As backend, we choose <a href="https://quantum-computing.ibm.com/services/resources?systems=yours&amp;tab=systems&amp;skip=20">ibmq_manila</a>, a 5-qubit device:</p><pre>backend = &quot;ibmq_manila&quot;<br>service = QiskitRuntimeService()<br><br>with Session(service=service, backend=backend) as session:<br>    options = Options()<br>    options.resilience_level = 2<br>    est = Estimator(session=session, options=options)<br>    job = est.run(circuit, observable)<br><br>result = job.result()<br>print(f&quot;  &gt; Expectation value: {result.values[0]}&quot;) </pre><pre>&gt; Expectation value: 0.9354479166666667</pre><p>Usually, when submitting a job to a Qiskit Runtime session, the job will first go to the queue and once your session is opened, it will run until you get the final result (you can have additional information on the job calling for the whole result output).</p><p>Here, the fidelity we got is quite low, despite ZNE. Let’s see if we can do better with another device (we chose this time <a href="https://quantum-computing.ibm.com/services/resources?systems=yours&amp;tab=systems&amp;skip=10">ibm_lagos</a>, a 7-qubit device):</p><pre>backend = &quot;ibm_lagos&quot;<br>service = QiskitRuntimeService()<br><br>with Session(service=service, backend=backend) as session:<br>    options = Options()<br>    options.resilience_level = 2<br>    est = Estimator(session=session, options=options)<br>    job = est.run(circuit, observable)<br><br>result = job.result()<br>print(f&quot;  &gt; Expectation value: {result.values[0]}&quot;)</pre><pre>  &gt; Expectation value: 0.9639375000000004</pre><p>The result has indeed improved! The two hardware have though the same <a href="https://en.wikipedia.org/wiki/Quantum_volume">quantum volume</a>, so there is no unique or straightforward criterium that tells us that one is better than the other.</p><p>A last remark here is essential: each quantum device of the IBM Quantum Resources has associated calibration data containing the details of the errors (single- and 2-qubit gates, readout and so on). We can check those data every time before running a simulation to choose the device with smaller errors, but due to the queue, sometimes after the job is completed the data have changed and errors are not the same anymore. So always keep an eye on those data and enjoy your quantum runs!</p><h4>Code</h4><p>You can find the code seen in this article <a href="https://github.com/ColibrITD-SAS/OpenQuick/blob/main/ErrorMitigationOpenGit.ipynb">here</a>!</p><h4>At ColibrITD</h4><p><em>To achieve a practical advantage in the near future for real use cases, it is essential to explore noise mitigation methods. The interest for us as a quantum software company in quantum error mitigation goes without saying! ;)</em></p><h4>References</h4><p>[1] Kim, Y., Eddins, A., Anand, S. et al<em>.</em> <em>Evidence for the utility of quantum computing before fault tolerance</em>. Nature <strong>618</strong>, 500–505 (2023).</p><p>[2] Aharonov, Dorit, and Michael Ben-Or. <em>Fault-tolerant quantum computation with constant error</em>. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (1997).</p><p>[3] Google Quantum AI. <em>Exponential suppression of bit or phase errors with cyclic error correction</em>. Nature <strong>595</strong>, 383–387 (2021).</p><p>[4] Google Quantum AI. <em>Suppressing quantum errors by scaling a surface code logical qubit</em>. Nature <strong>614</strong>, 676–681 (2023).</p><p>[5] Endo, Suguru, et al. <em>Hybrid quantum-classical algorithms and quantum error mitigation</em>. Journal of the Physical Society of Japan 90.3 (2021).</p><p>[6] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta, <em>Error Mitigation for Short-Depth Quantum Circuits</em>, Phys. Rev. Lett. <strong>119</strong> (2017).</p><p>[7] Czarnik, Piotr, et al. <em>Error mitigation with Clifford quantum-circuit data,</em> Quantum <strong>5</strong> (2021).</p><p>[8] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay, and Jay M. Gambetta, <em>Mitigating measurement errors in multiqubit experiments</em>, Phys. Rev. A <strong>103 (</strong>2021).</p><p>[9] Endo, S., <em>Hybrid Quantum-Classical Algorithms and Error Mitigation,</em> PhD thesis<em>, </em>University of Oxford, (2019).</p><p>[10] T. Giurgica-Tiron, Y. Hindy, R. LaRose, A. Mari and W. J. Zeng, <em>Digital zero noise extrapolation for quantum error mitigation</em>, IEEE International Conference on Quantum Computing and Engineering (QCE) pp. 306–316, (2020).</p><p>[11] LaRose, Ryan, et al., <em>Mitiq: A software package for error mitigation on noisy quantum computers.,</em> Quantum <strong>6, </strong>774 (2022).</p><p>[12] Nielsen, Michael A., and Isaac L. Chuang. <em>Quantum computation and quantum information.,</em> Phys. Today 54.2: 60 (2001).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ab21e9887327" width="1" height="1" alt=""><hr><p><a href="https://medium.com/colibritd-quantum/quantum-error-mitigation-ab21e9887327">Quantum error mitigation</a> was originally published in <a href="https://medium.com/colibritd-quantum">ColibrITD Quantum</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How is energy spent in computation?]]></title>
            <link>https://medium.com/colibritd-quantum/how-is-energy-spent-in-computation-e17565067400?source=rss-cc131443486------2</link>
            <guid isPermaLink="false">https://medium.com/p/e17565067400</guid>
            <dc:creator><![CDATA[Nadia Milazzo]]></dc:creator>
            <pubDate>Thu, 27 Apr 2023 07:46:58 GMT</pubDate>
            <atom:updated>2023-04-28T07:31:44.397Z</atom:updated>
            <content:encoded><![CDATA[<h4>The story of a forgetful demon</h4><p>In the mindset of a computer scientist, every problem requires an algorithm which solves it, and every algorithm requires resources to run. Those resources are the object of any computational analysis, and they usually correspond to time, space and <em>energy. </em>A lot of debates and discussions around energy consumption in quantum computation animate the community at present — see e.g. the <a href="https://quantum-energy-initiative.org/">Quantum Energy Initiative</a> launched in 2022 — but here we will take a step back and look at the fundamentals of how energy is spent in both classical and quantum computation, in a more physical mindset. This will be the occasion to recall how beautifully physics, information and computation theories connect, revealing fascinating interpretations of fundamental concepts in all those worlds.</p><h4><strong>Logical reversibility</strong></h4><p>Elementary operations in classical and quantum computation are often described by logic gates performing Boolean functions on one or more inputs. Let’s take two among the simplest classical ones: the NOT and the AND gate; the first one takes a single bit as input and outputs its opposite (it performs logical negation), while the second one takes two inputs in and outputs only one after performing logical conjunction. We present the so-called truth tables for these two simple gates in Fig. 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*tUeU0AiCMWTecGjQfSAoNA.png" /><figcaption>Fig. 1 Truth tables for the NOT and the AND gate.</figcaption></figure><p>What if we want to retrieve the input from those outputs? It clearly appears that we can always unambiguously do that for the NOT gate, but this is not true anymore if we get a 0 from the AND gate, since it corresponds to three different inputs — 00, 01 and 10. We call the NOT gate a <em>reversible</em> gate, while the AND gate is an <em>irreversible</em> one. The ability to retrieve the output from the input and viceversa is only one of the possible descriptions of reversibility; we can simply say that a reversible operation can be <em>undone</em> or, in more mathematical terms, that it is bijective, but the point of view that most interests us here is the following one: in a reversible operation <em>no information is lost</em>.</p><blockquote>Information is physical — Rolf Landauer</blockquote><p>In 1961 Landauer published a work [1] in which he presented how irreversibility can be connected to the energy spent in computation, showing how in particular the <em>erasure</em> of information dissipates energy into the environment. Even further, this amount of energy can be lower bounded, leading to what is nowadays known as the Landauer’s principle:</p><blockquote>Suppose a computer erases a single bit of information. The amount of energy dissipated into the environment is at least <strong>k T ln2</strong>, where k is a universal constant known as Boltzmann’s constant, and T is the temperature of the environment of the computer. [2]</blockquote><p>The statement above can be equivalently expressed in terms of entropy, given its thermodynamic definition: erasing one bit of information <em>increases</em> the entropy of the environment by at least <strong>k ln2</strong>. After having been extensively challenged and debated, Landauer’s principle was finally experimentally verified in different classical settings [3–5] and further extended also to a quantum one [6]. Moreover, deeper investigations on the connection between logical and thermodynamic reversibilities also led to extensions of Landauer’s principle [7]. But what about the achievability of such a bound? Are modern computers anywhere close to it? At <em>room temperature (≃ 25</em>° C<em>)</em>, the energy dissipated would at least be 18 meV, a very small amount (for example, when a single molecule of gas methane is combusted, the energy released — as heat — is 500 times bigger)! Current technology does much worse than that [2, 8], and even though advances have been made in this direction, e.g. with nanomagnet memories [9], some scientists believe that the semiconductor miniaturization used in modern computers is soon going to stop providing greater energy efficiency [8]. What is needed is instead a revolution in the fundamentals of computation: How could that look like?</p><h4><strong>Reversible computing</strong></h4><p>We have seen that the energy dissipated in elementary computation is related to the irreversibility of operations, or in other terms, to the loss of information. Can we then improve the energy efficiency using a reversible model of computation? From a physical point of view, the answer is simply yes! There is no fundamental reason why we cannot go below the bound set by Landauer’s principle. While this is great news, the actual design and manufacturing of practical reversible computing hardware is not simple at all. Research is being conducted on the topic (see e.g. [8,10] and references therein), but here we will only mention a very simple model to get an idea of what reversible computing might look like and what challenges it presents. The model of a “billiard-ball” computer dates back to the beginning of the ’80s, when Fredkin and Toffoli (Yes, as the well-known gates! ^^) published their work on <em>conservative</em> logic: a model of computation which mirrors physics much more closely than the others.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HALTuys0s4C6LvF6kGdIOw.png" /><figcaption>Fig. 3 a) The balls can occupy different sites in the grid. b) They can collide in an elastic way. c) We can deflect the trajectories of the balls.</figcaption></figure><p>As represented in Fig. 3, the billiard balls can occupy or not a certain site; to make the correspondance with a standard model of computation, we can think of the presence or absence of a ball as the encoding of a signal, representing a logical 1 or 0. Moreover, the balls move in a friction-free environment; the collisions that happen when they cross paths and the corresponding outputs simulate the action of gates in a circuit model. It can be shown that this extremely simple model is universal, meaning that it can simulate any computation possible in the standard circuit model (more precisely, the billiard-ball computer can implement a Fredkin gate — also known as controlled SWAP gate — which is universal). Other models of reversible computation can be based instead on the Toffoli gate, more known also in quantum computation to be universal when combined with the single qubit Hadamard gate. Without going in too many details, the overhead of those reversible computations with respect to irreversible ones is the number of ancilla bits which are required to allow reversibility; this number scales anyway at most linearly with the number of gates in the irreversible circuit.</p><p>However, more difficult challenges stand in the way of reversible computers implementation. If we look closer at the billiard-ball model, we can soon realise that it is highly unstable, since the paths followed by a ball moving without friction will be “disturbed” by any small perturbations, destroying the assumption of the implementation of perfect operations. We could correct those errors, but this would require then erasing the information associated with such protocols: so here we are again, spending energy to reduce any external noise source! All the discussion above must sound so familiar to any reader who has, at least once, crossed an article on a much newer, complicated and fascinating technology… Yes, quantum computing suffers exactly of the same problems as the simplest model of reversible computation we could think of! It is indeed reversible since it uses only <em>unitary</em> operations which act on qubits and give rise to the so-called <em>quantum circuit</em> model of computation. For example, the NOT gate discussed at the beginning of this article finds its corresponding quantum version in the Pauli-X gate (with respect to the computational basis {|0⟩, |1⟩}). Quantum computers are very susceptible to external perturbations (they must be cooled down to fight e.g. thermal noise) and they also rely on perfect gate implementation to achieve reliable computations. Once again,<em> the energy consumed in quantum computation is due to the need of reducing all the possible sources of noise.</em></p><p>This quite long (but hopefully pleasant ^^) detour on reversible computing led us to the last part of this article, where we will again have the opportunity to explore from a physical point of view what could look like a purely computational problem, and go all the way down to the fundamental laws of thermodynamics.</p><h4><strong>Quantum Error Correction and the </strong>Maxwell’s demon</h4><p>Errors induced by any form of noise must at some point be corrected to do quantum information processing reliably. The field of quantum error correction (QEC) is wide and rich, and researchers are unstoppably working to make it always closer and closer to reality to provide fault-tolerant quantum computing. We will not discuss here any QEC scheme in particular and focus exclusively on what are their generic energy requirements.</p><blockquote>Quantum error-correction may be thought of as a type of refrigeration process, capable of keeping a quantum system at a constant entropy, despite the influence of noise processes which tend to change the entropy of the system. [2]</blockquote><p>This unusual interpretation of QEC allowing a <em>reduction</em> of entropy may sound at first a bit worrying to physicists passionate about thermodynamics; indeed, following its second law, we know that the entropy of a closed system can <em>never</em> decrease! Where is the catch? In 1871 Maxwell conjectured for the first time a little “demon” who could violate this law in a very simple scenario, represented in Fig. 4.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/599/1*cekCPBQIhrv11HEHci0Oog.png" /><figcaption>Fig. 4 Maxwell’s thought experiments of a little demon able to violate the second law of thermodynamics reducing the entropy of a system.</figcaption></figure><p>We imagine a gas at equilibrium inside a container with two different chambers separated by a wall; the little demon has access to a small door on the wall that he can open at his will and let the gas particles go from one side to the other. He observes the particles moving and when he <em>sees </em>a fast particle approaching the door, it opens it to let it through. By repeating this several times, he could separate the fast particles from the slow ones, thus decreasing the total entropy of the system. This paradox kept scientists busy for many years [12], until they realised how to defeat the tricky demon: to <em>know </em>the velocity of the gas particles, he had to measure them! The act of measurement requires acquisition of information, which has to be stored somewhere, i.e. in the demon’s memory. Unfortunately, all the memories are finite, also demons’ ones, so he will have at some point to start erasing the collected information to make space for new one. We now know very well that by Landauer’s principle this erasure increases the entropy of the total system composed by the demon, the gas and their environment, thus compensating the efforts of the demon in decreasing it. The second law of thermodynamics is finally safe!</p><p>If we now substitute the demon’s memory with a computer one, and the velocity measurements with the so-called <em>syndrome </em>measurements of QEC (to understand which errors occur), we can soon realise that the refrigeration process represented by QEC is simply an analogue of Maxwell’s demon protocol. Indeed, the bits used to store the measurement results needed for error correction must eventually be erased; this can be more precisely proven and quantified by using fundamental theorems in the theory of information, but we leave the curious reader refer to [2] for the full proof.</p><p>We conclude this article by stressing what is the take-home message here and why it is important: <em>in principle </em>all computation can be done reversibly at zero energy cost, <em>in practice </em>we<em> </em>still spend energy trying to make systems stable and to protect them from noise. It is then very important to continue studying and searching for new techniques against noise [13], since this will improve the energy efficiency of any computing device.</p><h4>At ColibrITD</h4><p><em>We work to understand what noise mitigation techniques can be useful to achieve reliable computation in the NISQ era and we search for</em> <em>precise estimations of energy consumption for current hardware to provide useful benchmark of quantum technologies.</em></p><h4>References</h4><p>[1] R. Landauer, “Irreversibility and Heat Generation in the Computing Process.” <em>IBM Journal of Research and Development</em>, vol. 5, no. 3, pp. 183–191 (1961).</p><p>[2] Nielsen, M. A., &amp; Chuang, I. “Quantum computation and quantum information” (2002).</p><p>[3] Bérut, A., Arakelyan, A., Petrosyan, A. <em>et al.</em> “Experimental verification of Landauer’s principle linking information and thermodynamics.” <em>Nature</em> <strong>483</strong>, 187–189 (2012).</p><p>[4] Yonggun Jun, Momčilo Gavrilov, and John Bechhoefer, “High-Precision Test of Landauer’s Principle in a Feedback Trap.” <em>Phys. Rev. Lett</em>. <strong>113</strong>, 190601 (2014).</p><p>[5] Hong, Jeongmin, et al. “Experimental test of Landauer’s principle in single-bit operations on nanomagnetic memory bits.” <em>Science advances</em> 2.3 (2016).</p><p>[6] Gaudenzi, R., Burzurí, E., Maegawa, S. <em>et al.</em> “Quantum Landauer erasure with a molecular nanomagnet.” <em>Nature Phys</em> <strong>14</strong>, 565–568 (2018).</p><p>[7] Takahiro Sagawa, “Thermodynamic and logical reversibilities revisited”, <em>J. Stat. Mech.</em> (2014).</p><p>[8] Frank, M.P. “The Future of Computing Depends on Making It Reversible.” <em>IEEE Spectrum </em>(2017).</p><p>[9] Brian Lambson, David Carlton, and Jeffrey Bokor, “Exploring the Thermodynamic Limits of Computation in Integrated Systems: Magnetic Memory, Nanomagnetic Logic, and the Landauer Limit.”, <em>Phys. Rev. Lett.</em> <strong>107</strong>, 010604 (2011).</p><p>[10] Frank, M.P. “Foundations of Generalized Reversible Computing.” In <em>Phillips, I., Rahaman, H. (eds) Reversible Computation. RC 2017. Lecture Notes in Computer Science(), vol 10301. Springer, Cham.</em> (2017).</p><p>[11] Fredkin, E., Toffoli, T. “Conservative logic.” <em>Int J Theor Phys</em> <strong>21</strong>, 219–253 (1982)</p><p>[12] Bennett, Charles H. “Demons, Engines and the Second Law.” <em>Scientific American</em> 257, no. 5 (1987).</p><p>[13] Reina, M. “Can we really deal with bit flip?” <em>Medium </em>(2022).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e17565067400" width="1" height="1" alt=""><hr><p><a href="https://medium.com/colibritd-quantum/how-is-energy-spent-in-computation-e17565067400">How is energy spent in computation?</a> was originally published in <a href="https://medium.com/colibritd-quantum">ColibrITD Quantum</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[To reject or not to reject, that is the question.]]></title>
            <link>https://medium.com/colibritd-quantum/to-reject-or-not-to-reject-that-is-the-question-e74c547566b6?source=rss-cc131443486------2</link>
            <guid isPermaLink="false">https://medium.com/p/e74c547566b6</guid>
            <category><![CDATA[quantum-certification]]></category>
            <category><![CDATA[quantum-computing]]></category>
            <dc:creator><![CDATA[Nadia Milazzo]]></dc:creator>
            <pubDate>Thu, 20 Oct 2022 08:00:14 GMT</pubDate>
            <atom:updated>2022-10-20T08:17:25.403Z</atom:updated>
            <content:encoded><![CDATA[<h4>The story of a decision problem for quantum systems</h4><p>While quantum technologies progress and advance rapidly, many questions arise around their properties, functioning and potential. According to the European Quantum Technologies Roadmap [1], there are four main areas of research that form the landscape of this rich field, each with its different goals and challenges. Some examples of important technologies with their respective fields are [2]:</p><ol><li>Quantum memories — <em>Quantum communication</em></li><li>Robust logical qubits, fault-tolerant gates — <em>Quantum computation</em></li><li>Digital/Analogue quantum simulators (Quantum circuits/Annealers) — <em>Quantum simulation</em></li><li>Quantum-enhanced sensors (atomic/optical) — <em>Quantum metrology and sensing</em></li></ol><p>The increasing availability of these technologies naturally requires testing them efficiently, raising very deep questions on the feasibility of such tasks:</p><blockquote>If a quantum experiment solves a problem which is proven to be intractable for classical computers, how can one verify the outcome of the experiment? <em>[3]</em></blockquote><p>The question above could sound familiar to some readers, especially the ones who have dealt with classical computer science. Indeed, there exists a similar open problem there, known as the P ≟ NP problem: Can a problem whose solution can be quickly verified also be solved? Currently, most of the scientific community seems to lean towards P ≠ NP. This would imply that solutions to problems in the NP class would be more “easily” verified than found. This problem does not answer our question, but it gives us an insight into the potential difficulty in answering it (the P/NP problem has been unsolved for the better part of a century now!).</p><p>But let’s now take a step back and start with a better definition of the problem in the quantum context!</p><h4>How to characterize quantum systems?</h4><p>When reading the multitude of scientific articles on the characterization of quantum systems, one could at first get confused by all the different words used to address (apparently) the same thing: <strong><em>characterization, certification, verification, benchmarking</em></strong>… Where is then the difference (if there is one)?</p><p>In a recent review [4], the authors make a distinction based on different layers of complexity, as well as on some specificities of the method and its ultimate goal. In their framework, they identify, among others, a “physical” layer, i.e., everything regarding quantum states and processes (a.k.a. channels), and an “application” layer, which instead refers to more complex tasks (e.g., testing for the correctness of the solution that a quantum computer outputs). We can associate characterization and certification to the physical layer, while verification refers to the application one.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KRrjRi5eBxeD881Yr-2bvA.png" /><figcaption>The “physical” layer includes quantum states and processes.</figcaption></figure><p>More specifically, certification can be seen as a subtask of characterization since the final certificate for a quantum system could contain less information than its characterization (for instance, for a quantum state, one could be interested in full tomography or only in some specific property of the state, e.g., entanglement).</p><p>At the end, where does benchmarking fit in all this? It is also related to characterization, but its goal is slightly different since it aims at comparing the performances of different quantum devices.</p><p>In the following, the term <em>certification </em>will be used<em> </em>to address the different existing protocols. The landscape of methods is very diversified since this problem can be tackled in several ways and from different perspectives; this results from many disciplines coming together, such as mathematics, computer science, physics, and engineering.</p><p>The most known and general certification process for quantum states and processes is <em>quantum tomography</em>. It provides full knowledge of the quantum system. Still, the number of measurements needed for completing the task scales very badly with the dimension of the system (e.g., for pure states, it scales as 2 to the <em>n-th</em> power, where <em>n </em>is the number of quantum bits), and it thus becomes soon infeasible (it is already difficult to fully characterize a 2 quantum bits channel).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/721/1*ihtE575hpTbDEZn5nxBLsQ.png" /><figcaption>Full tomography of the quantum state ρ: measurements have to be performed on several copies of the state.</figcaption></figure><p>Many efforts have been spent to avoid performing quantum full tomography or to identify cases in which it can be simplified (see, for instance, the results in [5–14]). Quantum system certification approaches have a different point of view and formulate the problem of testing functionalities of quantum systems as a protocol that outputs “ACCEPT” or “REJECT” based on the hypothesis of correct functioning. A description and classification of the different methods can be found in [4] and [15]. The latter work uses two axes of comparison to classify the existing methods, one considering the<em> </em><strong><em>information gain</em> </strong>provided, the other looking at how many and how strong the assumptions are for the protocol to work. Some of the authors of [15] have also created an online library of certification protocols on the Quantum Protocol Zoo to help the community advance in this crucial field for the development of quantum technologies (you can have a look <a href="https://wiki.veriqloud.fr/index.php?title=Certification_Library">here</a>!).</p><p>In particular, for quantum devices, and more precisely for noisy and intermediate scale quantum (NISQ) machines available at present, the most used certification methods are <strong><em>randomized benchmarking </em></strong>[16–18] and <strong><em>cross-entropy benchmarking </em></strong>[19–20]. The former aims at estimating the performance of quantum gates by evaluating the error that accumulates when applying random gate sequences of different lengths, and they are known to be robust against state preparation and measurement (SPAM) errors. The latter deals with the problem of correct sampling from the measurement output distribution of a quantum circuit; a quantity called cross-entropy fidelity F is calculated from the set of samples collected: if F=1, it means that the quantum computer outputting those samples is noiseless. If instead F=0, the quantum computer is too noisy, and it will thus not outperform classical machines.</p><h4>Another protocol on the horizon</h4><p>In a recent pre-print entitled “Principles of quantum functional testing” [21]— to which I contributed — a new path was taken to tackle the certification of quantum channels performed by quantum devices. As with the other certification protocols, the core of this method is a decision problem: given some specifications on the characterizing parameters by the device’s producer, one aims at accepting or rejecting the device <strong><em>as quickly as possible </em></strong>(at the same time providing a level of confidence that the decision is correct).<strong><em> </em></strong>This is the key to this approach to conclude in the shortest time possible; this is also the motivation that guides classical functional testing, where it is, in particular, desired to waste as little time as possible on devices that do<strong><em> not </em></strong>function properly.</p><p>Let’s see the fundamental ideas and concepts used in the following sections.</p><p><strong>Bayesian parameter estimation — A set of continuous parameters typically characterizes a quantum channel</strong>; for this reason, the decision problem can be described as a quantum parameter estimation problem. In particular, in [21], Bayes parameter estimation (BPE) techniques were applied; they are indeed widely used to estimate the probability density function of random variables with unknown parameters, which in turn is then used for decision-making or future inference. BPE is based on Bayes’ theorem, which allows one to incorporate prior knowledge into the decision-making process. The procedure followed in BPE can be summarized in 3 steps:</p><ol><li>Identify a <strong><em>prior </em></strong>distribution for the unknown parameters</li></ol><p>2. Collect data to calculate the <strong><em>likelihood </em></strong>function</p><p>3. Update the distribution of the parameters using 1 and 2 to get the <strong><em>posterior</em></strong> distribution</p><p>The last point can be very hard to achieve analytically after a few updates of the probability distribution. This is why numerical methods have been implemented to overcome these difficulties, and they are the subject of the next paragraph.</p><p><strong>Sequential Monte Carlo (SMC) methods — </strong>Known algorithms to approximate the posterior probability distribution often involve Monte Carlo methods. In particular, in the SMC approach [22], the collected data are processed sequentially, meaning that at each update of the probability distribution, the last posterior is set as the new prior. This is done by approximating the continuous distribution with a discrete one, described by ‘particles’ (i.e., parameter values) and ‘weights’ (i.e., probabilities) — forming the so-called <em>particle filter —</em> and updating the weights according to Bayes’ rule. New particle locations have to be resampled at some point in the algorithm to avoid numerical instabilities as data are collected. The SMC calculations in [21] were performed with the available python package QInfer, presented in [23].</p><p>In the case of the certification of quantum channels, new data are collected through measurements on the quantum system; including new knowledge coming from data via sequential updates of the posterior probability distribution suggests the possibility of optimizing the possible available measurements adaptively. Let’s see how!</p><p><strong>Experimental design and utility functions — </strong>Adaptive strategies for choosing the next best measurement (or, more generally, the next best experiment) in the update process can be translated into optimizing a <strong><em>utility function</em></strong> U [24–25]. If this optimization is performed at <strong><em>each</em></strong> step, the corresponding adaptive experimental design is often referred to as a <em>myopic </em>or <em>greedy</em> approach. However, the optimization could be performed on one or more steps; in that case, one deals with a <em>non</em>-<em>greedy </em>design<em>. </em>Common choices of utility function U for parameter estimation problems are functions of the posterior covariance matrix (e.g., the variance itself in the case of single parameter estimation) or information-based functions [26], which follow the basic principle that going from before posterior distribution should increase the available information (e.g., the information gain or the mutual information [25]).</p><p>Now that the bases are all set, we are ready to ask the question: <em>Is there a way of accelerating the testing process in the specific case of quantum channels?</em></p><h4><strong>New ingredients to speed up the decision problem</strong></h4><p>The quantum-mechanical context allows the investigation of some new ideas for functional testing; in the following paragraphs, three new principles are discussed.</p><p><strong><em>Iteration of the channel — </em></strong>Imagine you receive from a producer a quantum device that is supposed to perform a channel Φ (e.g., a rotation channel), and instead, what it performs, in reality, is a faulty channel Φ’ (for instance the rotation angle or the rotation axis is not exact). Repeated application of the channel before measurement of the output can enhance the detection of such error: the channel&#39;s coherence can be exploited to gain a factor N in efficiency, where N is the number of iterations of the channel. The conclusion might not always be straightforward; in fact, while the iteration of the channel can make coherent errors more detectable, it could lead to the opposite effect when acting on incoherent errors (e.g., depolarization). A more rigorous investigation of the different cases can be done using results on the quantum Chernoff bound [27].</p><p><strong><em>Non-greedy adaptive experimental design — </em></strong>The possibility of adopting a non-greedy adaptive experimental design is now more appealing after having introduced the idea of iteration of the quantum channel. This results in finding not only the next best measurement but an optimal <em>sequence</em> of measurements. More precisely, the decision whether to repeat the channel or measure the output is made by looking at the information already gathered at each step, stating which of the two actions is the most advantageous.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nqrEJKsgv_nic7kkyYdyRA.jpeg" /><figcaption>Sketch of the certification protocol in the experiment-limited scenario explored in [21].</figcaption></figure><p><strong><em>Efficient decision criteria — </em></strong>Together with the quantum device, the provider gives you a <em>confidence region</em> associated with the characterizing parameters of the channel. This region can be used to define the decision criterion to accept or reject the producer&#39;s claim. Different decision criteria can impact the method&#39;s efficiency; for instance, in the case of single parameter estimation, the region is simply an interval, and one could, e.g., look at the position of the mean of the posterior probability distribution concerning this interval. A slightly more complex option relies instead on comparing this interval with a <em>credible region</em>, e.g., the highest posterior density (HPD) region defined as the region containing 95% of the probability mass, depicted in the figure below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9YFSmAk5kQNVKF8ygHZ1HA.png" /><figcaption>Examples of posterior probability distributions and corresponding credible regions (the area under the curve delimited by the violet interval) in the single parameter estimation case (rotation angle). The dotted red lines represent the confidence interval given by the producer. From left to right: the decision criterion based on the 95% HPD outputs ACCEPT, INCONCLUSIVE and REJECT, respectively. The curves above were obtained with the QInfer python package.</figcaption></figure><p>If you are interested in more technical details (e.g., the Chernoff bound investigation) and/or results for the specific quantum channels considered, you can look at the pre-print <a href="https://arxiv.org/pdf/2209.11712.pdf">here</a>!</p><p><em>Progress on the certification and verification problem of quantum systems is crucial for the research we conduct at ColibrITD, especially in the context of quantum algorithms and software, where efficient protocols for the certification of correct quantum computation become essential, in particular when dealing with noisy machines as the ones available at present.</em></p><h4>References</h4><p>[1] QUROPE Quantum Information Processing and Communication in Europe, <em>QT roadmap</em>, <a href="http://qurope.eu/h2020/qtflagship/roadmap2016">QT roadmap 2016 | QUROPE</a> (2016).</p><p>[2] Antonio Acín et al.<em>,</em> <em>The quantum technologies roadmap: a European community view</em>, <a href="https://iopscience.iop.org/article/10.1088/1367-2630/aad1ea">New J. Phys<em>.</em> <strong>20</strong> 080201</a> <em>(</em>2018).</p><p>[3] Gheorghiu, A. et al., <em>Verification of Quantum Computation: An Overview of Existing Approaches,</em> <a href="https://link.springer.com/article/10.1007/s00224-018-9872-3">Theory Comput Syst <strong>63</strong>, 715–808</a> (2019).</p><p>[4] Martin Kliesch and Ingo Roth, <em>Theory of Quantum System Certification</em>, <a href="https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.2.010201">PRX Quantum <strong>2</strong>, 010201</a> (2021).</p><p>[5] Cramer, M. et al., <em>Efficient quantum state tomography,</em> <a href="https://doi.org/10.1038/ncomms1147">Nat Commun <strong>1</strong>, 149</a> (2010).</p><p>[6] Christopher Ferrie, <em>Self-Guided Quantum Tomography</em>, <a href="https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.113.190404">Phys. Rev. Lett. <strong>113</strong>, 190404</a> (2014).</p><p>[7] Christopher Granade et al., <em>Practical Bayesian tomography</em>, <a href="https://iopscience.iop.org/article/10.1088/1367-2630/18/3/033024">New J. Phys. <strong>18</strong> 033024</a> (2016).</p><p>[8] F. Huszár and N. M. T. Houlsby, <em>Adaptive Bayesian quantum tomography</em>, <a href="https://journals.aps.org/pra/abstract/10.1103/PhysRevA.85.052120">Phys. Rev. A <strong>85</strong>, 052120</a> (2012).</p><p>[9] Tobias Moroder et al., <em>Permutationally invariant state reconstruction</em>, <a href="https://iopscience.iop.org/article/10.1088/1367-2630/14/10/105001">New J. Phys. <strong>14</strong> 105001</a> (2012).</p><p>[10] Erik Nielsen et al., <em>Gate Set Tomography</em>, <a href="https://quantum-journal.org/papers/q-2021-10-05-557/">Quantum <strong>5</strong>, 557</a> (2021).</p><p>[11] Ahmad, S. et al., <em>Self-guided quantum state tomography for limited resources,</em><a href="https://doi.org/10.1038/s41598-022-09143-7"> Sci Rep <strong>12</strong>, 5092</a> (2022).</p><p>[12] David Gross et al., <em>Quantum State Tomography via Compressed Sensing</em>, <a href="https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.105.150401">Phys. Rev. Lett. <strong>105</strong>, 150401</a> (2010).</p><p>[13] T Baumgratz et al., <em>A scalable maximum likelihood method for quantum state tomography</em>, <a href="https://iopscience.iop.org/article/10.1088/1367-2630/15/12/125004">New J. Phys. <strong>15</strong> 125004</a> (2013).</p><p>[14] Quek, Y. et al., <em>Adaptive quantum state tomography with neural networks,</em> <a href="https://doi.org/10.1038/s41534-021-00436-9">npj Quantum Inf <strong>7</strong></a>, 105 (2021).</p><p>[15] Eisert, J. et al., <em>Quantum certification and benchmarking,</em> <a href="https://doi.org/10.1038/s42254-020-0186-4">Nat Rev Phys <strong>2</strong>, 382–390</a> (2020).</p><p>[16] E. Knill et al., <em>Randomized benchmarking of quantum gates</em>, <a href="https://journals.aps.org/pra/abstract/10.1103/PhysRevA.77.012307">Phys. Rev. A <strong>77</strong>, 012307</a> (2008).</p><p>[17] Easwar Magesan et al., <em>Scalable and Robust Randomized Benchmarking of Quantum Processes</em>, <a href="https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.106.180504">Phys. Rev. Lett. <strong>106</strong>, 180504</a> (2011).</p><p>[18] Easwar Magesan et al., <em>Efficient Measurement of Quantum Gate Error by Interleaved Randomized Benchmarking</em>, <a href="https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.109.080505">Phys. Rev. Lett. <strong>109</strong>, 080505</a> (2012).</p><p>[19] Boixo, S. et al<em>.,</em> <em>Characterizing quantum supremacy in near-term devices,</em> <a href="https://doi.org/10.1038/s41567-018-0124-x">Nature Phys <strong>14</strong>, 595–600</a> (2018).</p><p>[20] Arute, F. et al.<em>,</em> <em>Quantum supremacy using a programmable superconducting processor,</em> <a href="https://doi.org/10.1038/s41586-019-1666-5">Nature <strong>574</strong>, 505–510</a> (2019).</p><p>[21] N. Milazzo et al., <em>Principles of quantum functional testing</em>, <a href="https://arxiv.org/abs/2209.11712">arXiv:2209.11712</a> (2022).</p><p>[22] Doucet, A. et al., <em>On sequential Monte Carlo sampling methods for Bayesian filtering,</em> <a href="https://doi.org/10.1023/A:1008935410038">Statistics and Computing <strong>10</strong>, 197–208</a> (2000).</p><p>[23] C. Granade et al., <em>QInfer: Statistical inference software for quantum applications</em>, <a href="http://quantum-journal.org/papers/q-2017-04-25-5/">Quantum <strong>1</strong>, 5 </a>(2017).</p><p>[24] K. Chaloner et al., <em>Bayesian Experimental Design: A Review</em>, <a href="https://doi.org/10.1214/ss/1177009939">Statistical Science, <strong>10(3)</strong>: 273–304</a> (1995).</p><p>[25] E. G. Ryan et al., <em>A Review of Modern Computational Algorithms for Bayesian Optimal Design</em>, <a href="https://doi.org/10.1111/insr.12107">International Statistical Review <strong>84</strong>, 128</a> (2016).</p><p>[26] Christopher E Granade et al<em>.,</em> <em>Robust online Hamiltonian learning</em>, <a href="https://iopscience.iop.org/article/10.1088/1367-2630/14/10/103013">New J. Phys. <strong>14</strong> 103013</a> (2012).</p><p>[27] K. M. R. Audenaert et al., <em>Discriminating States: The Quantum Chernoff Bound</em>, <a href="https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.98.160501">Phys. Rev. Lett. <strong>98</strong>, 160501</a> (2007).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e74c547566b6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/colibritd-quantum/to-reject-or-not-to-reject-that-is-the-question-e74c547566b6">To reject or not to reject, that is the question.</a> was originally published in <a href="https://medium.com/colibritd-quantum">ColibrITD Quantum</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What stands in the way of variational quantum algorithms toward the quantum advantage]]></title>
            <link>https://medium.com/colibritd-quantum/what-stands-in-the-way-of-variational-quantum-algorithms-towards-quantum-advantage-de004fd3d31d?source=rss-cc131443486------2</link>
            <guid isPermaLink="false">https://medium.com/p/de004fd3d31d</guid>
            <dc:creator><![CDATA[Nadia Milazzo]]></dc:creator>
            <pubDate>Wed, 30 Mar 2022 12:52:38 GMT</pubDate>
            <atom:updated>2022-03-30T13:07:02.678Z</atom:updated>
            <content:encoded><![CDATA[<p>We are living in the exciting era of the first available quantum computers, complex devices which aim at tackling problems by playing by the rules of quantum mechanics. Although still imperfect (too small, too noisy, too error-prone…) they are the result of years and years of research and of the great effort of scientists all over the world, so instead of focusing on what they cannot do, let’s see what they CAN do!</p><p>Those imperfect computers are more precisely called Noisy Intermediate-Scale Quantum devices (NISQ) [1]. To make use of any kind of computer, we need algorithms to run on them, so in this case, we need algorithms suitable for NISQ machines. The most known and used ones are the so-called Variational Quantum Algorithms (VQA) [2], whose features and main challenges will be outlined in the following. The first question that comes to mind is then: where do they originate from?</p><h4>The variational principle</h4><p>The variational method in quantum mechanics is an approximation method based on a theorem, the so-called variational principle, which is very useful to find approximations to the ground state energy of a system, that is the expectation value of the corresponding Hamiltonian in the ground state. The statement of the theorem can be expressed with a simple formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/265/1*DyWKEXWnXLqr2x34ss1wyA.png" /><figcaption>Variational theorem: the ground state energy is always less or equal than any expectation value of the Hamiltonian in any trial parametrized state.</figcaption></figure><p>or in words, as Any (parametrized) trial wavefunction will always give an expectation value larger than or equal to the ground state energy, since, <strong>by definition</strong>, the ground state wavefunction has the lowest energy!</p><p>Variational quantum algorithms make use of this principle: it can be exploited exactly as written above when the interest is finding the ground state eigenvalue and eigenvector of a Hamiltonian; knowing the structure of a molecule can indeed be very important in different areas of science, as in quantum chemistry, e.g. to improve drug discovery, or in material science, e.g. to analyze superconductivity properties. In a more general way, one can instead translate different problems into Hamiltonian ones or also define alternative functions, called <strong>cost functions</strong>, to parametrize and minimize.</p><p>But why are these algorithms suited for NISQ devices?</p><h4>Hybrid Quantum/Classical Algorithms</h4><p>If we were to apply the variational method to a system of N qubits with a generical trial wavefunction written classically, we would need an exponential number, in N, of complex numbers. What if we delegate this hard task to our first-generation quantum computers? Well, it turns out that this is a very good idea! A quantum computer can write a generic state with less than an exponential number of parameters, through a parametrized quantum circuit (PQC), called the <strong>Ansatz</strong> of the VQA. But what is even better, is to make NISQ devices cooperate with our (very powerful) classical computers: the result is an example of what we will call a <em>hybrid</em> algorithm. The word hybrid in this case refers to assigning different parts of our algorithm to the quantum or classical device, based on the different strengths of the two machines. Once the state is prepared, the expectation value of the observable chosen as the cost function can be calculated, performing many measurements to obtain a good estimate. The <strong>quantum measurements</strong> performed in NISQ devices are usually restricted to the computational basis. At this point, the classical computer comes into play with its powerful ways of optimizing the variational parameters; several different methods are known, both gradient-based and gradient-free. The optimized parameters are finally given back to the quantum computer to re-run the PQC, thus starting again the hybrid loop.</p><p>It can be useful to emphasize how the quantum and classical devices <em>communicate, </em>or in other words<em> </em>how classical and quantum information are exchanged in such hybrid algorithms. The classical parameters are converted into quantum information since they parametrize quantum gates, which in turn produce a quantum state. Viceversa, the quantum information contained in the state is translated back into classical as a result of quantum measurement, as depicted in the figure below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ooKJh12q-LMwSV9lFVjpxQ.png" /><figcaption>Quantum and classical information in a circuit representation (the single line represents a qubit, while the double line is a classical bit).</figcaption></figure><p>Among the several examples of applications of VQAs, we can find the <em>Variational Quantum Eigensolver</em> (VQE) in the context of quantum chemistry [3,4,5,6], the <em>Quantum Approximate Optimization Algorithm </em>(QAOA) in the context of optimization, and combinatorial problems [7,8,9,10] and the <em>Variational Quantum Linear Solver</em> (VQLS) in the context of linear algebra [11,12,13,14]. All these algorithms have attracted a lot of attention and quite a big amount of works have advanced in these directions, showing e.g., in quantum chemistry problems, the reduction of coherence times requirements for the calculation of ground-state molecular energy [15], the experimental implementation of VQE with up to six qubits and more than one hundred Pauli terms [5] or the extension of VQE to the calculation of transition energies between the ground state and low excited states of a molecule [16].</p><p>Nevertheless, we still have not experienced a drastic change in the solution of complex problems and we keep facing not only hardware limitations but also software ones (see e.g. [17]). Why is that?</p><p>Let’s get an idea!</p><h4>Roadblocks</h4><p>One of the reasons why VQAs are attractive is their being task-oriented algorithms. Their modular structure allows one to change each piece (ansatz, cost function, optimizer) depending on the problem at hand. The wide exploration of several different applications has shed light on some common challenges that can arise in running such algorithms, affecting their efficiency and their solution accuracy [2]. We will discuss some of them, neglecting the classical part and only focusing on the quantum one (for an example of different performances of classical optimizers see e.g. [18]). As depicted in the figure below, noise affects the whole algorithm implementation, while some of the problems can arise only for a specific part of it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZKUV8k6EVODgG7GAsGiVxA.png" /></figure><p><strong><em>Expressibility and entangling power</em></strong> The choice of the Ansatz in a VQA is a crucial one, and the performance of the algorithm can strongly depend on it, so it would be nice to have some general figures of merit in order to evaluate how good the chosen Ansatz is, and if it is the right pick for the specific use case considered. Two quantities were recently proposed in [19]. The first one, called <em>expressibility</em>, represents the capability of a quantum circuit of generating states in the Hilbert space; the ideal case would be a uniform distribution in the state space. Low expressibility means the possibility of exploring only a limited set of states, thus the higher the expressibility, the larger the set of accessible states. The second one is instead the <em>entangling power</em> of a quantum circuit, which refers to how entangled are the states generated by it; this is done by averaging a chosen entanglement measure over a certain number of parametrized samples states. Tests are needed to verify whether these two quantities are indeed good figures of merit to discriminate among different Ansätze; in [20] it was shown for instance that in the presence of noise, the expressibility of the Ansatz chosen for the VQE studied did not perform well as a criterion to choose an optimal circuit, since it resulted not correlated to the performance of the algorithm.</p><p><strong><em>Barren Plateau</em></strong> Some cost function landscapes could present a flat region, known as the <em>Barren plateau,</em> and they could become flatter as the number of qubits in the circuit increases; the problem, in this case, is that one needs an exponentially large precision to find a minimization direction, potentially compromising the possibility of gaining an advantage from the VQA compared to a fully classical algorithm, to which an exponential scaling is usually associated. It was shown in [21] that randomly initialized PQC can lead to Barren plateaus, but they can also depend on the choice of the cost function, whether it is global or local (relative to the whole register or to the single qubit), as discussed in [22].</p><p><strong><em>Number of measurements</em></strong><em> </em>A very well-known<em> </em>problem in the estimation of the expectation value of the cost function is the limited number of available resources, more specifically the number of quantum measurements that one can perform in order to reach enough precision, which could be too many to be performed in the time available. This again represents a threat to the potential quantum advantage of a VQA. Moreover, what is usually done in current algorithms, e.g. for a Hamiltonian in a VQE, is to decompose the operator in Pauli terms and to evaluate the sum of the single term expectation values; depending on the complexity of the operator, this decomposition could contain many terms, with a corresponding increase in the number of measurements.</p><p><strong><em>Noise</em></strong><em> </em>It is well-known that noise is the number one enemy for quantum hardwares since it leads any quantum system to decohere (after a sufficiently long time). It is then only natural to ask how it affects quantum algorithms, especially the ones running on NISQ devices, which cannot implement full quantum error correction because of the restricted number of qubits. The consequence of this is limited circuit depth to avoid as much as possible the propagation of gate errors. Noise can also be responsible for some of the VQA problems discussed above: it can for instance induce Barren plateaus [23] independently of the Ansatz used, affecting the trainability of the cost function, or it can compromise the final value of the cost function, which is an important quantity in some VQAs.</p><p>All the above-mentioned problems could sound overwhelming, but if we look at them as challenges, then we are left with a bunch of new open questions, which increase interest and curiosity in trying and finding an answer to them.</p><h4>Final destination: Quantum Advantage</h4><p>Much different research directions have started addressing the problems above, offering possible solutions and new insights, pursuing the final goal of quantum advantage in practical applications. For instance, the choice of the optimal Ansatz should be done keeping always in mind the noise model and the desired use case one wants to solve since the performance of the circuit will depend on both these factors [20]. The choice of the Ansatz also is crucial for avoiding Barren plateaus, and parameters initialization strategies have been proposed to reduce randomization [24]. The number of measurements to estimate an expectation value could instead be reduced by considering commuting (e.g. which can be measured simultaneously) subsets of Pauli strings in the decomposition of the observable [25]; moreover, this could be improved by optimizing the allocation of shots among the Pauli operators (the ones with smaller coefficients contribute less to the variance) [26].</p><p>Finally, the question remains: are VQAs noise resilient? At present knowledge, the answer is that it depends on the type of noise; if it is coherent, like a unitary operation which instead of performing a rotation of an angle A results in a rotation of A+Err, then the VQA is not affected by it and the parameter optimization will adjust itself [27]. When the noise is incoherent (e.g. decoherence), only a few results are available (see e.g. [28]) and further investigations are needed to get a clearer picture.</p><h3>At <strong>ColibrITD </strong>we work to find efficient VQAs, use case oriented and noise resilient. We seek new strategies to get a quantum advantage for practical and useful applications accessible in the NISQ era, laying the foundations for the fault-tolerant one.</h3><h4><strong>References</strong></h4><p>[1] Preskill, J. (2018). Quantum computing in the NISQ era and beyond. <em>Quantum</em>, <em>2</em>, 79.</p><p>[2] Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., … &amp; Coles, P. J. (2021). Variational quantum algorithms. <em>Nature Reviews Physics</em>, <em>3</em>(9), 625–644.</p><p>[3] Tilly, J., Chen, H., Cao, S., Picozzi, D., Setia, K., Li, Y., … &amp; Tennyson, J. (2021). The Variational Quantum Eigensolver: a review of methods and best practices. <em>arXiv preprint arXiv:2111.05176</em>.</p><p>[4] Wang, D., Higgott, O., &amp; Brierley, S. (2019). Accelerated variational quantum eigensolver. <em>Physical review letters</em>, <em>122</em>(14), 140504.</p><p>[5] Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., &amp; Gambetta, J. M. (2017). Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. <em>Nature</em>, <em>549</em>(7671), 242–246.</p><p>[6] Liu, J. G., Zhang, Y. H., Wan, Y., &amp; Wang, L. (2019). Variational quantum eigensolver with fewer qubits. <em>Physical Review Research</em>, <em>1</em>(2), 023025</p><p>[7] Niu, M. Y., Lu, S., &amp; Chuang, I. L. (2019). Optimizing qaoa: Success probability and runtime dependence on circuit depth. <em>arXiv preprint arXiv:1905.12134</em>.</p><p>[8] Willsch, M., Willsch, D., Jin, F., De Raedt, H., &amp; Michielsen, K. (2020). Benchmarking the quantum approximate optimization algorithm. <em>Quantum Information Processing</em>, <em>19</em>(7), 1–24.</p><p>[9] Zhou, L., Wang, S. T., Choi, S., Pichler, H., &amp; Lukin, M. D. (2020). Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. <em>Physical Review X</em>, <em>10</em>(2), 021067.</p><p>[10] Shaydulin, R., &amp; Alexeev, Y. (2019, October). Evaluating quantum approximate optimization algorithm: A case study. In <em>2019 tenth international green and sustainable computing conference (IGSC)</em> (pp. 1–6). IEEE.</p><p>[11] Bravo-Prieto, C., LaRose, R., Cerezo, M., Subasi, Y., Cincio, L., &amp; Coles, P. J. (2019). Variational quantum linear solver. <em>arXiv preprint arXiv:1909.05820</em>.</p><p>[12] Huang, H. Y., Bharti, K., &amp; Rebentrost, P. (2019). Near-term quantum algorithms for linear systems of equations. <em>arXiv preprint arXiv:1909.07344</em>.</p><p>[13] Xu, X., Sun, J., Endo, S., Li, Y., Benjamin, S. C., &amp; Yuan, X. (2021). Variational algorithms for linear algebra. <em>Science Bulletin</em>, <em>66</em>(21), 2181–2188.</p><p>[14] Patil, H., Wang, Y., &amp; Krstić, P. S. (2022). Variational quantum linear solver with a dynamic ansatz. <em>Physical Review A</em>, <em>105</em>(1), 012423.</p><p>[15] Peruzzo, A., McClean, J., Shadbolt, P., Yung, M. H., Zhou, X. Q., Love, P. J., … &amp; O’brien, J. L. (2014). A variational eigenvalue solver on a photonic quantum processor. <em>Nature communications</em>, <em>5</em>(1), 1–7.</p><p>[16] Parrish, R. M., Hohenstein, E. G., McMahon, P. L., &amp; Martínez, T. J. (2019). Quantum computation of electronic transitions using a variational quantum eigensolver. <em>Physical review letters</em>, <em>122</em>(23), 230401.</p><p>[17] Guerreschi, G. G., &amp; Matsuura, A. Y. (2019). QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. <em>Scientific reports</em>, <em>9</em>(1), 1–7.</p><p>[18] Pellow-Jarman, A., Sinayskiy, I., Pillay, A., &amp; Petruccione, F. (2021). A comparison of various classical optimizers for a variational quantum linear solver. <em>Quantum Information Processing</em>, <em>20</em>(6), 1–14.</p><p>[19] Sim, S., Johnson, P. D., &amp; Aspuru‐Guzik, A. (2019). Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum‐classical algorithms. <em>Advanced Quantum Technologies</em>, <em>2</em>(12), 1900070.</p><p>[20] Saib, W., Wallden, P., &amp; Akhalwaya, I. (2021, October). The Effect of Noise on the Performance of Variational Algorithms for Quantum Chemistry. In <em>2021 IEEE International Conference on Quantum Computing and Engineering (QCE)</em> (pp. 42–53). IEEE.</p><p>[21] McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., &amp; Neven, H. (2018). Barren plateaus in quantum neural network training landscapes. <em>Nature communications</em>, <em>9</em>(1), 1–6.</p><p>[22] Cerezo, M., Sone, A., Volkoff, T., Cincio, L., &amp; Coles, P. J. (2021). Cost function dependent barren plateaus in shallow parametrized quantum circuits. <em>Nature communications</em>, <em>12</em>(1), 1–12.</p><p>[23] Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., &amp; Coles, P. J. (2021). Noise-induced barren plateaus in variational quantum algorithms. <em>Nature communications</em>, <em>12</em>(1), 1–11.</p><p>[24] Volkoff, T., &amp; Coles, P. J. (2021). Large gradients via correlation in random parameterized quantum circuits. <em>Quantum Science and Technology</em>, <em>6</em>(2), 025008.</p><p>[25] McClean, J. R., Romero, J., Babbush, R., &amp; Aspuru-Guzik, A. (2016). The theory of variational hybrid quantum-classical algorithms. <em>New Journal of Physics</em>, <em>18</em>(2), 023023.</p><p>[26] Rubin, N. C., Babbush, R., &amp; McClean, J. (2018). Application of fermionic marginal constraints to hybrid quantum algorithms. <em>New Journal of Physics</em>, <em>20</em>(5), 053020.</p><p>[27] O’Malley, P. J., Babbush, R., Kivlichan, I. D., Romero, J., McClean, J. R., Barends, R., … &amp; Martinis, J. M. (2016). Scalable quantum simulation of molecular energies. <em>Physical Review X</em>, <em>6</em>(3), 031007.</p><p>[28] Sharma, K., Khatri, S., Cerezo, M., &amp; Coles, P. J. (2020). Noise resilience of variational quantum compiling. <em>New Journal of Physics</em>, <em>22</em>(4), 043006.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=de004fd3d31d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/colibritd-quantum/what-stands-in-the-way-of-variational-quantum-algorithms-towards-quantum-advantage-de004fd3d31d">What stands in the way of variational quantum algorithms toward the quantum advantage</a> was originally published in <a href="https://medium.com/colibritd-quantum">ColibrITD Quantum</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>