Readout error mitigation para sa Sampler primitive gamit ang M3

Tinatayang paggamit: wala pang isang minuto sa Heron r2 processor (PAALALA: Ito ay isang tantya lamang. Maaaring mag-iba ang inyong runtime.)

Kaligiran

Hindi tulad ng Estimator primitive, ang Sampler primitive ay walang built-in na suporta para sa error mitigation. Ilang mga pamamaraan na sinusuportahan ng Estimator ay partikular na dinisenyo para sa expectation values, at sa gayon ay hindi naaangkop sa Sampler primitive. Ang isang eksepsyon ay ang readout error mitigation, na isang lubhang epektibong pamamaraan na naaangkop din sa Sampler primitive.

Ang M3 Qiskit addon ay nag-implement ng isang mahusay na pamamaraan para sa readout error mitigation. Ang tutorial na ito ay nagpapaliwanag kung paano gamitin ang M3 Qiskit addon upang mapawi ang readout error para sa Sampler primitive.

Ano ang readout error?

Kaagad bago ang pagsukat, ang estado ng isang qubit register ay inilarawan ng isang superposition ng computational basis states, o ng isang density matrix. Ang pagsukat ng qubit register tungo sa isang classical bit register ay umuusad sa dalawang hakbang. Una, ang tunay na quantum measurement ay isinasagawa. Nangangahulugan ito na ang estado ng qubit register ay naipro-project sa isang solong basis state na nailalarawan ng isang string ng $1$s at $0$s. Ang ikalawang hakbang ay binubuo ng pagbasa sa bitstring na naglalarawan ng basis state na ito at pagsusulat nito sa classical computer memory. Tinatawag natin ang hakbang na ito na readout. Lumalabas na ang ikalawang hakbang (readout) ay may mas maraming error kaysa sa unang hakbang (projection sa basis states). Makatuwirang isipin ito kung aalalahanin ninyo na ang readout ay nangangailangan ng pagtuklas sa isang microscopic quantum state at pagpapalakas nito tungo sa macroscopic realm. Ang readout resonator ay nakakonekta sa (transmon) qubit, at dahil dito ay nakakaranas ng napakaliit na frequency shift. Ang isang microwave pulse ay ibinabato pabalik mula sa resonator, na naman ay nakakaranas ng maliliit na pagbabago sa katangian nito. Ang na-reflect na pulse ay pinapalakas at sinusuri. Ito ay isang delikadong proseso at napapailalim sa maraming uri ng errors.

Ang mahalagang punto ay na, habang parehong quantum measurement at readout ay napapailalim sa error, ang huli ay may mas nangingibabaw na error, na tinatawag na readout error, na siyang pokus sa tutorial na ito.

Teoretikal na kaligiran

Kung ang sampled bitstring (na naka-imbak sa classical memory) ay naiiba mula sa bitstring na naglalarawan sa projected quantum state, sinasabi natin na naganap ang isang readout error. Ang mga error na ito ay napapansin na random at walang korelasyon mula sa sample hanggang sample. Napatunayang kapaki-pakinabang na i-modelo ang readout error bilang isang noisy classical channel. Ibig sabihin, para sa bawat pares ng bitstrings $i$ at $j$, may nakapirming probabilidad na ang tunay na halaga ng $j$ ay mali ang pagbasa bilang $i$.

Sa mas tiyak na paraan, para sa bawat pares ng bitstrings $(i, j)$, may isang (conditional) probability ${M}_{i,j}$ na ang $i$ ay mabasa, kung ibinigay na ang tunay na halaga ay $j.$ Iyon ay,

$${M}_{i,j} = \Pr(\text{readout value is } i | \text{true value is } j) \text{ for } i,j \in (0,...,2^n - 1), \tag{1}$$

kung saan $n$ ay ang bilang ng bits sa readout register. Para sa concreteness, ipinagpapalagay natin na ang $i$ ay isang decimal integer na ang binary representation ay ang bitstring na naglalabel sa computational basis states. Tinatawag natin ang $2^n \times 2^n$ matrix ${M}$ na assignment matrix. Para sa nakapirming tunay na halaga $j$, ang pagbubuod ng probabilidad sa lahat ng maingay na kinalabasan $i$ ay dapat magbigay ng $1$. Iyon ay

$$\sum_{i=0}^{2^n - 1} {M}_{i,j} = 1 \text{ for all } j$$

Ang isang matrix na walang negatibong entries na nakakatugon sa (1) ay tinatawag na left-stochastic. Ang left-stochastic matrix ay tinatawag ding column-stochastic dahil ang bawat column nito ay may kabuuan na $1$. Eksperimental na tinutukoy natin ang approximate values para sa bawat element ${M}_{i,j}$ sa pamamagitan ng paulit-ulit na paghahanda sa bawat basis state $|j \rangle$ at pagkatapos ay pagkompyut ng frequencies ng pagkakaroon ng sampled bitstrings.

Kung ang isang eksperimento ay nagsasangkot ng pagtatantya sa isang probability distribution sa output bitstrings sa pamamagitan ng paulit-ulit na pag-sample, kung gayon ay maaari nating gamitin ang ${M}$ upang mapawi ang readout error sa antas ng distribution. Ang unang hakbang ay ulitin ang isang nakapirming circuit ng interes nang maraming beses, lumilikha ng histogram ng sampled bitstrings. Ang normalized histogram ay ang sinukat na probability distribution sa $2^n$ posibleng bitstrings, na tinutukoy natin bilang ${\tilde{p}} \in \mathbb{R}^{2^n}$. Ang (tinantyang) probability ${{\tilde{p}}}_i$ ng pag-sample ng bitstring $i$ ay katumbas ng kabuuan sa lahat ng tunay na bitstrings $j$, bawat isa ay may timbang ng probabilidad na ito ay pagkakamali para sa $i$. Ang pahayag na ito sa matrix form ay

$${\tilde{p}} = {M} {\vec{p}}, \tag{2},$$

kung saan ang ${\vec{p}}$ ay ang tunay na distribution. Sa mga salita, ang readout error ay may epekto ng pagpaparami ng ideal distribution sa bitstrings ${\vec{p}}$ gamit ang assignment matrix ${M}$ upang makagawa ng nakitang distribution ${\tilde{p}}$. Nasukat natin ang ${\tilde{p}}$ at ${M}$, ngunit walang direktang access sa ${\vec{p}}$. Sa prinsipyo, makukuha natin ang tunay na distribution ng bitstrings para sa ating circuit sa pamamagitan ng paglutas ng equation (2) para sa ${\vec{p}}$ nang numerical.

Bago tayo magpatuloy, sulit na pansinin ang ilang mahalagang katangian ng naive approach na ito.

• Sa praktika, ang equation (2) ay hindi nilulutas sa pamamagitan ng pag-invert sa ${M}$. Ang linear algebra routines sa software libraries ay gumagamit ng mga pamamaraang mas stable, tumpak, at mahusay.
• Kapag tinatantya ang ${M}$, ipinagpalagay natin na readout errors lamang ang naganap. Sa partikular, ipinagpapalagay natin na walang state preparation at quantum measurement errors — o hindi bababa sa ito ay napawi sa ibang paraan. Hanggang sa ito ay isang mabuting pagpapalagay, ang ${M}$ ay tunay na kumakatawan lamang sa readout error. Ngunit kapag ginagamit natin ang ${M}$ upang itama ang isang sinukat na distribution sa bitstrings, hindi natin ginagawa ang gayong pagpapalagay. Sa katunayan, inaasahan natin ang isang kawili-wiling circuit na magpakilala ng ingay, halimbawa, gate errors. Ang "tunay" na distribution ay kasama pa rin ang mga epekto mula sa anumang errors na hindi napawi sa ibang paraan.

Ang pamamaraang ito, bagaman kapaki-pakinabang sa ilang pangyayari, ay nakakaranas ng ilang limitasyon.

Ang space at time resources na kailangan upang tantiyahin ang ${M}$ ay lumalaki nang exponential sa $n$:

• Ang pagtatantya ng ${M}$ at ${\tilde{p}}$ ay napapailalim sa statistical error dahil sa finite sampling. Ang ingay na ito ay maaaring gawing kasing liit ng nais sa gastos ng mas maraming shots (hanggang sa timescale ng drifting hardware parameters na nagreresulta sa systematic errors sa ${M}$). Gayunpaman, kung walang mga pagpapalagay na ginawa sa bitstrings na nakikita kapag nagsasagawa ng mitigation, ang bilang ng shots na kinakailangan upang tantiyahin ang ${M}$ ay lumalaki hindi bababa sa exponential sa $n$.
• Ang ${M}$ ay isang $2^n \times 2^n$ matrix. Kapag $n>10$, ang dami ng memory na kinakailangan upang mag-imbak ng ${M}$ ay mas malaki kaysa sa memory na available sa isang makapangyarihang laptop.

Ang karagdagang mga limitasyon ay:

• Ang nabalik na distribution ${\vec{p}}$ ay maaaring may isa o higit pang negatibong probabilities (habang pa ring may kabuuan ng isa). Ang isang solusyon ay i-minimize ang $||{M} {\vec{p}} - {\tilde{p}}||^2$ na napapailalim sa constraint na bawat entry sa ${\vec{p}}$ ay non-negative. Gayunpaman, ang runtime ng gayong pamamaraan ay mga order of magnitude na mas mahaba kaysa direktang paglutas ng equation (2).
• Ang mitigation procedure na ito ay gumagana sa antas ng probability distribution sa bitstrings. Sa partikular, hindi nito maitatama ang error sa isang indibidwal na nakitang bitstring.

Qiskit M3 addon: Scaling sa mas mahabang bitstrings

Ang paglutas ng equation (2) gamit ang standard numeric linear algebra routines ay limitado sa bitstrings na hindi hihigit sa mga 10 bits. Ang M3, gayunpaman, ay kayang hawakan ang mas mahabang bitstrings. Ang dalawang pangunahing katangian ng M3 na ginagawang posible ito ay:

• Ang mga korelasyon sa readout error ng order three at mas mataas sa mga koleksyon ng bits ay ipinagpapalagay na negligible at binabalewala. Sa prinsipyo, sa gastos ng mas maraming shots, maaari ding tantiyahin ang mas mataas na korelasyon.
• Sa halip na tuwiran na bumuo ng ${M}$, ginagamit natin ang mas maliit na effective matrix na nagrerekord ng mga probabilidad lamang para sa bitstrings na nakolekta kapag bumubuo ng ${\tilde{p}}$.

Sa mataas na antas, ang pamamaraan ay gumagana sa sumusunod na paraan.

Una, bumubuo tayo ng mga building blocks kung saan tayo maaaring bumuo ng isang pinasimpleng, effective, na paglalarawan ng ${M}$. Pagkatapos, paulit-ulit nating pinapatakbo ang circuit ng interes at nakolekta ang bitstrings na ginagamit natin upang bumuo ng parehong ${\tilde{p}}$ at, sa tulong ng mga building blocks, isang effective ${M}$.

Sa mas tiyak na paraan,

• Ang mga single-qubit assignment matrices ay tinatantya para sa bawat qubit. Upang gawin ito, paulit-ulit tayong naghahanda ng qubit register sa all-zero state $|0 ... 0 \rangle$ at pagkatapos ay sa all-one state $|1 ... 1 \rangle$, at nagrerekord ng probabilidad para sa bawat qubit na ito ay maling nabasa.

• Ang mga korelasyon ng order three at mas mataas ay ipinagpapalagay na negligible at binabalewala.

  Sa halip, bumubuo tayo ng bilang $n$ ng $2 \times 2$ single-qubit assignment matrices, at bilang $n(n-1)/2$ ng $4 \times 4$ two-qubit assignment matrices. Ang mga one- at two-qubit assignment matrices na ito ay naka-imbak para sa susunod na paggamit.

• Matapos paulit-ulit na mag-sample ng isang circuit upang bumuo ng ${\tilde{p}}$, bumubuo tayo ng isang effective approximation sa ${M}$ gamit lamang ang bitstrings na na-sample kapag bumubuo ng ${\tilde{p}}$. Ang effective matrix na ito ay binuo gamit ang mga single- at two-qubit matrices na inilarawan sa nakaraang item. Ang linear dimension ng matrix na ito ay hindi hihigit sa order ng bilang ng shots na ginamit sa pagbuo ng ${\tilde{p}}$, na mas maliit pa kaysa dimension $2^n$ ng buong assignment matrix ${M}$ .

Para sa mga teknikal na detalye tungkol sa M3, maaari ninyong tingnan ang Scalable Mitigation of Measurement Errors on Quantum Computers.

Aplikasyon ng M3 sa isang quantum algorithm

Ilalapat natin ang readout mitigation ng M3 sa hidden shift problem. Ang hidden shift problem, at mga malapit na nauugnay na problema tulad ng hidden subgroup problem, ay orihinal na nabuo sa fault-tolerant setting (sa mas tiyak na paraan, bago pa napatunayan na posible ang fault-tolerant QPUs!). Ngunit pinag-aaralan din ang mga ito gamit ang mga available processors. Ang isang halimbawa ng algorithmic exponential speedup na nakuha para sa isang variant ng hidden shift problem na nakuha sa 127-qubit IBM® QPUs ay matatagpuan sa paper na ito (arXiv version).

Sa sumusunod, lahat ng arithmetic ay Boolean. Iyon ay, para sa $a, b \in \mathbb{Z}_2 = \{0, 1\}$, addition, $a + b$ ay ang logical XOR function. Bukod pa rito, multiplication $a \times b$ (o $a b$) ay ang logical AND function. Para sa $x, y \in \{0, 1\}^n$, $x + y$ ay tinukoy sa pamamagitan ng bitwise application ng XOR. Ang dot product $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$ ay tinukoy sa pamamagitan ng $x \cdot y = \sum_i x_i y_i$.

Hadamard operator at Fourier transform

Sa pag-implement ng mga quantum algorithms, napaka-karaniwan na gamitin ang Hadamard operator bilang isang Fourier transform. Ang computational basis states ay kung minsan ay tinatawag na classical states. Sila ay nasa one-to-one relation sa classical bitstrings. Ang $n$-qubit Hadamard operator sa classical states ay maaaring tingnan bilang isang Fourier transform sa Boolean hypercube:

$$H^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x,y \in {\mathbb{Z}_2^n}} (-1)^{x \cdot y} {|{y}\rangle}{\langle{x}|}.$$

Isaalang-alang ang isang state ${|{s}\rangle}$ na tumutugma sa nakapirming bitstring $s$. Sa paglalapat ng $H^{\otimes n}$, at paggamit ng ${\langle {x}|{s}\rangle} = \delta_{x,s}$, nakikita natin na ang Fourier transform ng ${|{s}\rangle}$ ay maaaring isulat bilang

$$H^{\otimes n} {|{s}\rangle} = \frac{1}{\sqrt{2^n}} \sum_{y \in {\mathbb{Z}_2^n}} (-1)^{s \cdot y} {|{y}\rangle}.$$

Ang Hadamard ay sariling inverse, iyon ay, $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$. Kaya, ang inverse Fourier transform ay ang parehong operator, $H^{\otimes n}$. Sa malinaw na paraan, mayroon tayo,

$${|{s}\rangle} = H^{\otimes n} H^{\otimes n} {|{s}\rangle} = H^{\otimes n} \frac{1}{\sqrt{2^n}} \sum_{y \in {\mathbb{Z}_2^n}} (-1)^{s \cdot y} {|{y}\rangle}.$$

Ang hidden shift problem

Isaalang-alang natin ang isang simpleng halimbawa ng isang hidden shift problem. Ang problema ay kilalanin ang isang constant shift sa input sa isang function. Ang function na ating isaalang-alang ay ang dot product. Ito ay ang pinakasimpleng miyembro ng isang malaking klase ng functions na tumatanggap ng quantum speedup para sa hidden shift problem sa pamamagitan ng mga teknikang katulad ng mga ipinakita sa ibaba.

Hayaan ang $x,y \in {\mathbb{Z}_2^m}$ na mga bitstrings ng haba $m$. Tinukoy natin ang ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ bilang

$${f}(x, y) = (-1)^{x \cdot y}.$$

Hayaan ang $a,b \in {\mathbb{Z}_2^m}$ na nakapirming bitstrings ng haba $m$. Bukod pa rito, tinukoy natin ang $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ bilang

$$g(x, y) = {f}(x+a, y+b) = (-1)^{(x+a) \cdot (y+b)},$$

kung saan ang $a$ at $b$ ay (nakatagong) parameters. Binigyan tayo ng dalawang black boxes, isa ay nag-implement ng $f$, at ang isa pa ay $g$. Ipinagpapalagay natin na alam natin na kinocompute nila ang mga function na tinukoy sa itaas, maliban sa hindi natin alam ang $a$ ni $b$. Ang laro ay upang matukoy ang mga nakatagong bitstrings (shifts) $a$ at $b$ sa pamamagitan ng paggawa ng mga query sa $f$ at $g$. Malinaw na kung nilalaro natin ang laro nang classical, kailangan natin ng $O(2m)$ queries upang matukoy ang $a$ at $b$. Halimbawa, maaari nating i-query ang $g$ sa lahat ng pares ng strings na ang isang elemento ng pares ay lahat ay zero, at ang iba pang elemento ay may eksaktong isang elemento na naka-set sa $1$. Sa bawat query, matututuhan natin ang isang elemento ng alinman sa $a$ o $b$. Gayunpaman, makikita natin na, kung ang mga black boxes ay ipinatupad bilang quantum circuits, maaari nating matukoy ang $a$ at $b$ sa isang solong query sa bawat isa sa $f$ at $g$.

Sa konteksto ng algorithmic complexity, ang isang black box ay tinatawag na oracle. Bilang karagdagan sa pagiging opaque, ang isang oracle ay may katangiang kinokonsumo nito ang input at gumagawa ng output kaagad, hindi nagdadagdag ng anuman sa complexity budget ng algorithm kung saan ito ay nakabaon. Sa katunayan, sa kasong ito, ang mga oracles na nag-implement ng $f$ at $g$ ay makikitang mahusay.

Quantum circuits para sa $f$ at $g$

Kailangan natin ng mga sumusunod na sangkap upang i-implement ang $f$ at $g$ bilang quantum circuits.

Para sa single-qubit classical states ${|{x_1}\rangle}, {|{y_1}\rangle}$, na may $x_1,y_1 \in \mathbb{Z}_2$, ang controlled-$Z$ gate ${CZ}$ ay maaaring isulat bilang

$${CZ} {|{x_1}\rangle}{|{y_1}\rangle}{x_1} = (-1)^{x_1 y_1} {|{x_1}\rangle}{x_1}{|{y_1}\rangle}.$$

Gagana tayo gamit ang $m$ CZ gates, isa sa $(x_1, y_1)$, at isa sa $(x_2, y_2)$, at iba pa, hanggang $(x_m, y_m)$. Tinatawag natin ang operator na ito na ${CZ}_{x,y}$.

Ang $U_f = {CZ}_{x,y}$ ay isang quantum version ng ${f} = {f}(x,y)$:

$$U_f {|{x}\rangle}{|{y}\rangle} = {CZ}_{x,y} {|{x}\rangle}{|{y}\rangle} = (-1)^{x \cdot y} {|{x}\rangle}{|{y}\rangle}.$$

Kailangan din nating i-implement ang isang bitstring shift. Tinutukoy natin ang operator sa $x$ register $X^{a_1}\cdots X^{a_m}$ bilang $X_a$ at gayundin sa $y$ register $X_b = X^{b_1}\cdots X^{b_m}$. Ang mga operator na ito ay naglalapat ng $X$ kung saan ang isang single bit ay $1$, at ang identity $I$ kung saan ito ay $0$. Pagkatapos ay mayroon tayo

$$X_a X_b {|{x}\rangle}{|{y}\rangle} = {|{x+a}\rangle}{|{y+b}\rangle}.$$

Ang pangalawang black box $g$ ay ipinatupad ng unitary $U_g$, na ibinigay ng

$$U_g = X_aX_b {CZ}_{x,y} X_aX_b.$$

Upang makita ito, inilalapat natin ang mga operators mula kanan hanggang kaliwa sa state ${|{x}\rangle}{|{y}\rangle}$. Una

$$X_a X_b {|{x}\rangle}{|{y}\rangle} = {|{x+a}\rangle}{|{y+b}\rangle}.$$

Pagkatapos,

$${CZ}_{x,y} {|{x+a}\rangle}{|{y+b}\rangle} = (-1)^{(x+a)\cdot (y+b)} {|{x+a}\rangle}{|{y+b}\rangle}.$$

Sa wakas,

$$X^a X^b (-1)^{(x+a)\cdot (y+b)} {|{x+a}\rangle}{|{y+b}\rangle} = (-1)^{(x+a)\cdot (y+b)} {|{x}\rangle}{|{y}\rangle},$$

na tunay na ang quantum version ng $f(x+a, y+b)$.

Ang hidden shift algorithm

Ngayon ay pinagsasama natin ang mga piraso upang malutas ang hidden shift problem. Nagsisimula tayo sa pag-apply ng mga Hadamards sa mga registers na sinimulan sa all-zero state.

$$H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} = \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot y} {|{x}\rangle}{|{y}\rangle}.$$

Susunod, i-query natin ang oracle $g$ upang makarating sa

$$U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} = \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{(x+a) \cdot (y+b)} {|{x}\rangle}{|{y}\rangle}$$ $$\approx \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot y + x \cdot b + y \cdot a} {|{x}\rangle}{|{y}\rangle}.$$

Sa huling linya, inalis natin ang constant global phase factor $(-1)^{a \cdot b}$, at tinutukoy ang pagkakapantay-pantay hanggang sa phase bilang $\approx$. Susunod, ang pag-apply ng oracle $f$ ay nagpapakilala ng isa pang factor ng $(-1)^{x \cdot y}$, na nagkakansela sa isa nang naroroon. Mayroon tayo:

$$U_f U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} \approx \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot b + y \cdot a} {|{x}\rangle}{|{y}\rangle}.$$

Ang huling hakbang ay ilapat ang inverse Fourier transform, $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$, na nagreresulta sa

$$H^{\otimes 2m} U_f U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} \approx {|{b}\rangle}{|{a}\rangle}.$$

Ang circuit ay tapos na. Sa kawalan ng ingay, ang pag-sample ng quantum registers ay magbabalik ng mga bitstrings $b, a$ na may probabilidad na $1$.

Ang Boolean inner product ay isang halimbawa ng tinatawag na bent functions. Hindi natin tutukuyin ang mga bent functions dito ngunit pansinin lamang na sila "ay maximally resistant laban sa mga atake na naghahangad na samantalahin ang dependensya ng mga outputs sa ilang linear subspace ng mga inputs." Ang quote na ito ay mula sa artikulong Quantum algorithms for highly non-linear Boolean functions, na nagbibigay ng mahusay na hidden shift algorithms para sa ilang klase ng bent functions. Ang algorithm sa tutorial na ito ay lumalabas sa Section 3.1 ng artikulo.

Sa mas pangkalahatang kaso, ang circuit para sa paghahanap ng hidden shift $s \in \mathbb{Z}^n$ ay

$$H^{\otimes n} U_{\tilde{f}} H^{\otimes n} U_g H^{\otimes n} {|{0}\rangle}^{\otimes n} = {|{s}\rangle}.$$

Sa pangkalahatang kaso, ang $f$ at $g$ ay mga functions ng isang solong variable. Ang ating halimbawa ng inner product ay may ganitong anyo kung hayaan nating $f(x, y) \to f(z)$, na may $z$ na katumbas ng concatenation ng $x$ at $y$, at $s$ na katumbas ng concatenation ng $a$ at $b$. Ang pangkalahatang kaso ay nangangailangan ng eksaktong dalawang oracles: Isang oracle para sa $g$ at isa para sa $\tilde{f}$, kung saan ang huli ay isang function na kilala bilang dual ng bent function $f$. Ang inner product function ay may self-dual property $\tilde{f}=f$.

Sa ating circuit para sa hidden shift sa inner product, inalis natin ang gitnang layer ng mga Hadamards na lumalabas sa circuit para sa pangkalahatang kaso. Habang sa pangkalahatang kaso ang layer na ito ay kailangan, nakatipid tayo ng kaunting depth sa pag-alis nito, sa gastos ng kaunting post-processing dahil ang output ay ${|{b}\rangle}{|{a}\rangle}$ sa halip na ninanais na ${|{a}\rangle}{|{b}\rangle}$.

Mga kinakailangan

Bago magsimula sa tutorial na ito, tiyakin na mayroon kayong mga sumusunod na naka-install:

• Qiskit SDK v2.1 o mas bago, na may suportang visualization
• Qiskit Runtime v0.41 o mas bago (pip install qiskit-ibm-runtime)
• M3 Qiskit addon v3.0 (pip install mthree)

Setup

# Added by doQumentation — required packages for this notebook
!pip install -q matplotlib mthree qiskit qiskit-ibm-runtime

from collections.abc import Iterator, Sequence
from random import Random
from qiskit.circuit import (
    CircuitInstruction,
    QuantumCircuit,
    QuantumRegister,
    Qubit,
)
from qiskit.circuit.library import CZGate, HGate, XGate
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import QiskitRuntimeService
import timeit
import matplotlib.pyplot as plt
from qiskit_ibm_runtime import SamplerV2 as Sampler
import mthree

Hakbang 1: I-map ang classical inputs sa quantum problem

Una, isusulat natin ang mga functions upang i-implement ang hidden shift problem bilang isang QuantumCircuit.

def apply_hadamards(qubits: Sequence[Qubit]) -> Iterator[CircuitInstruction]:
    """Apply a Hadamard gate to every qubit."""
    for q in qubits:
        yield CircuitInstruction(HGate(), [q], [])

def apply_shift(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Apply X gates where the bits of the shift are equal to 1."""
    for i, q in zip(range(shift.bit_length()), qubits):
        if shift >> i & 1:
            yield CircuitInstruction(XGate(), [q], [])

def oracle_f(qubits: Sequence[Qubit]) -> Iterator[CircuitInstruction]:
    """Apply the f oracle."""
    for i in range(0, len(qubits) - 1, 2):
        yield CircuitInstruction(CZGate(), [qubits[i], qubits[i + 1]])

def oracle_g(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Apply the g oracle."""
    yield from apply_shift(qubits, shift)
    yield from oracle_f(qubits)
    yield from apply_shift(qubits, shift)

def determine_hidden_shift(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Determine the hidden shift."""
    yield from apply_hadamards(qubits)
    yield from oracle_g(qubits, shift)
    # We omit this layer in exchange for post processing
    # yield from apply_hadamards(qubits)
    yield from oracle_f(qubits)
    yield from apply_hadamards(qubits)

def run_hidden_shift_circuit(n_qubits, rng):
    hidden_shift = rng.getrandbits(n_qubits)

    qubits = QuantumRegister(n_qubits, name="q")
    circuit = QuantumCircuit.from_instructions(
        determine_hidden_shift(qubits, hidden_shift), qubits=qubits
    )
    circuit.measure_all()
    # Format the hidden shift as a string.
    hidden_shift_string = format(hidden_shift, f"0{n_qubits}b")
    return (circuit, hidden_shift, hidden_shift_string)

def display_circuit(circuit):
    return circuit.remove_final_measurements(inplace=False).draw(
        "mpl", idle_wires=False, scale=0.5, fold=-1
    )

Magsisimula tayo sa isang maliit na halimbawa:

n_qubits = 6
random_seed = 12345
rng = Random(random_seed)
circuit, hidden_shift, hidden_shift_string = run_hidden_shift_circuit(
    n_qubits, rng
)

print(f"Hidden shift string {hidden_shift_string}")

display_circuit(circuit)

Hidden shift string 011010

Hakbang 2: I-optimize ang circuits para sa quantum hardware execution

job_tags = [
    f"shift {hidden_shift_string}",
    f"n_qubits {n_qubits}",
    f"seed = {random_seed}",
]
job_tags

['shift 011010', 'n_qubits 6', 'seed = 12345']

# Uncomment this to run the circuits on a quantum computer on IBMCloud.
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=100
)

# from qiskit_ibm_runtime.fake_provider import FakeMelbourneV2
# backend = FakeMelbourneV2()
# backend.refresh(service)

print(f"Using backend {backend.name}")

def get_isa_circuit(circuit, backend):
    pass_manager = generate_preset_pass_manager(
        optimization_level=3, backend=backend, seed_transpiler=1234
    )
    isa_circuit = pass_manager.run(circuit)
    return isa_circuit

isa_circuit = get_isa_circuit(circuit, backend)
display_circuit(isa_circuit)

Using backend ibm_kingston

Hakbang 3: Isagawa ang circuits gamit ang Qiskit primitives

# submit job for solving the hidden shift problem using the Sampler primitive
NUM_SHOTS = 50_000

def run_sampler(backend, isa_circuit, num_shots):
    sampler = Sampler(mode=backend)
    sampler.options.environment.job_tags
    pubs = [(isa_circuit, None, NUM_SHOTS)]
    job = sampler.run(pubs)
    return job

def setup_mthree_mitigation(isa_circuit, backend):
    # retrieve the final qubit mapping so mthree knows which qubits to calibrate
    qubit_mapping = mthree.utils.final_measurement_mapping(isa_circuit)

    # submit jobs for readout error calibration
    mit = mthree.M3Mitigation(backend)
    mit.cals_from_system(qubit_mapping, rep_delay=None)

    return mit, qubit_mapping

job = run_sampler(backend, isa_circuit, NUM_SHOTS)
mit, qubit_mapping = setup_mthree_mitigation(isa_circuit, backend)

Hakbang 4: Post-process at ibalik ang mga resulta sa classical format

Sa teoretikal na talakayan sa itaas, natukoy natin na para sa input $ab$, inaasahan natin ang output na $ba$. Ang karagdagang komplikasyon ay na, upang magkaroon ng mas simpleng (pre-transpiled) circuit, ipinasok natin ang kinakailangang CZ gates sa pagitan ng magkatabi na pares ng qubits. Ito ay katumbas ng pag-interleave ng mga bitstrings $a$ at $b$ bilang $a1 b1 a2 b2 \ldots$. Ang output string $ba$ ay i-interleave din sa katulad na paraan: $b1 a1 b2 a2 \ldots$. Ang function unscramble sa ibaba ay nagbabago ng output string mula $b1 a1 b2 a2 \ldots$ tungo sa $a1 b1 a2 b2 \ldots$ upang ang input at output strings ay maaaring direktang ikumpara.

# retrieve bitstring counts
def get_bitstring_counts(job):
    result = job.result()
    pub_result = result[0]
    counts = pub_result.data.meas.get_counts()
    return counts, pub_result

counts, pub_result = get_bitstring_counts(job)

Ang Hamming distance sa pagitan ng dalawang bitstrings ay ang bilang ng mga indeks kung saan ang mga bits ay nag-iiba.

def hamming_distance(s1, s2):
    weight = 0
    for c1, c2 in zip(s1, s2):
        (c1, c2) = (int(c1), int(c2))
        if (c1 == 1 and c2 == 1) or (c1 == 0 and c2 == 0):
            weight += 1

    return weight

# Replace string of form a1b1a2b2... with b1a1b2a1...
# That is, reverse order of successive pairs of bits.
def unscramble(bitstring):
    ps = [bitstring[i : i + 2][::-1] for i in range(0, len(bitstring), 2)]
    return "".join(ps)

def find_hidden_shift_bitstring(counts, hidden_shift_string):
    # convert counts to probabilities
    probs = {
        unscramble(bitstring): count / NUM_SHOTS
        for bitstring, count in counts.items()
    }

    # Retrieve the most probable bitstring.
    most_probable = max(probs, key=lambda x: probs[x])

    print(f"Expected hidden shift string: {hidden_shift_string}")
    if most_probable == hidden_shift_string:
        print("Most probable bitstring matches hidden shift 😊.")
    else:
        print("Most probable bitstring didn't match hidden shift ☹️.")
    print("Top 10 bitstrings and their probabilities:")
    display(
        {
            k: (v, hamming_distance(hidden_shift_string, k))
            for k, v in sorted(
                probs.items(), key=lambda x: x[1], reverse=True
            )[:10]
        }
    )

    return probs, most_probable

probs, most_probable = find_hidden_shift_bitstring(
    counts, hidden_shift_string
)

Expected hidden shift string: 011010
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their probabilities:

{'011010': (0.9743, 6),
 '001010': (0.00812, 5),
 '010010': (0.0063, 5),
 '011000': (0.00554, 5),
 '011011': (0.00492, 5),
 '011110': (0.00044, 5),
 '001000': (0.00012, 4),
 '010000': (8e-05, 4),
 '001011': (6e-05, 4),
 '000010': (6e-05, 4)}

Itala natin ang probabilidad ng pinaka-malamang na bitstring bago ilapat ang readout error mitigation gamit ang M3.

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

Ngayon ay ilalapat natin ang readout correction na natutunan ng M3 sa counts. Ang function apply_corrections ay nagbabalik ng quasi-probability distribution. Ito ay isang listahan ng float objects na may kabuuan na $1$. Ngunit ang ilang mga halaga ay maaaring negatibo.

def perform_mitigation(mit, counts, qubit_mapping):
    # mitigate readout error
    quasis = mit.apply_correction(counts, qubit_mapping)

    # print results
    most_probable_after_m3 = unscramble(max(quasis, key=lambda x: quasis[x]))

    is_hidden_shift_identified = most_probable_after_m3 == hidden_shift_string
    if is_hidden_shift_identified:
        print("Most probable bitstring matches hidden shift 😊.")
    else:
        print("Most probable bitstring didn't match hidden shift ☹️.")
    print("Top 10 bitstrings and their quasi-probabilities:")
    topten = {
        unscramble(k): f"{v:.2e}"
        for k, v in sorted(quasis.items(), key=lambda x: x[1], reverse=True)[
            :10
        ]
    }
    max_probability_after_M3 = float(topten[most_probable_after_m3])
    display(topten)

    return max_probability_after_M3, is_hidden_shift_identified

print(f"Expected hidden shift string: {hidden_shift_string}")
max_probability_after_M3, is_hidden_shift_identified = perform_mitigation(
    mit, counts, qubit_mapping
)

Expected hidden shift string: 011010
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their quasi-probabilities:

{'011010': '1.01e+00',
 '001010': '8.75e-04',
 '001000': '7.38e-05',
 '010000': '4.51e-05',
 '111000': '2.18e-05',
 '001011': '1.74e-05',
 '000010': '6.42e-06',
 '011001': '-7.18e-06',
 '011000': '-4.53e-04',
 '010010': '-1.28e-03'}

Ikumpara ang pagtuklas sa hidden shift string bago at pagkatapos mag-apply ng M3 correction

def compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
):
    is_probability_improved = (
        max_probability_after_M3 > max_probability_before_M3
    )
    print(f"Most probable probability before M3: {max_probability_before_M3}")
    print(f"Most probable probability after M3: {max_probability_after_M3}")
    if is_hidden_shift_identified and is_probability_improved:
        print("Readout error mitigation effective! 😊")
    else:
        print("Readout error mitigation not effective. ☹️")

compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
)

Most probable probability before M3: 0.9743
Most probable probability after M3: 1.01
Readout error mitigation effective! 😊

I-plot kung paano ang CPU time na kinakailangan ng M3 ay sumusukat gamit ang shots

# Collect samples for numbers of shots varying from 5000 to 25000.
shots_range = range(5000, NUM_SHOTS + 1, 2500)
times = []
for shots in shots_range:
    print(f"Applying M3 correction to {shots} shots...")
    t0 = timeit.default_timer()
    _ = mit.apply_correction(
        pub_result.data.meas.slice_shots(range(shots)).get_counts(),
        qubit_mapping,
    )
    t1 = timeit.default_timer()
    print(f"\tDone in {t1 - t0} seconds.")
    times.append(t1 - t0)

fig, ax = plt.subplots()
ax.plot(shots_range, times, "o--")
ax.set_xlabel("Shots")
ax.set_ylabel("Time (s)")
ax.set_title("Time to apply M3 correction")

Applying M3 correction to 5000 shots...
	Done in 0.003321983851492405 seconds.
Applying M3 correction to 7500 shots...
	Done in 0.004425413906574249 seconds.
Applying M3 correction to 10000 shots...
	Done in 0.006366567220538855 seconds.
Applying M3 correction to 12500 shots...
	Done in 0.0071477219462394714 seconds.
Applying M3 correction to 15000 shots...
	Done in 0.00860048783943057 seconds.
Applying M3 correction to 17500 shots...
	Done in 0.010026784148067236 seconds.
Applying M3 correction to 20000 shots...
	Done in 0.011459112167358398 seconds.
Applying M3 correction to 22500 shots...
	Done in 0.012727141845971346 seconds.
Applying M3 correction to 25000 shots...
	Done in 0.01406092382967472 seconds.
Applying M3 correction to 27500 shots...
	Done in 0.01546052098274231 seconds.
Applying M3 correction to 30000 shots...
	Done in 0.016769016161561012 seconds.
Applying M3 correction to 32500 shots...
	Done in 0.019537431187927723 seconds.
Applying M3 correction to 35000 shots...
	Done in 0.019739801064133644 seconds.
Applying M3 correction to 37500 shots...
	Done in 0.021093040239065886 seconds.
Applying M3 correction to 40000 shots...
	Done in 0.022840639110654593 seconds.
Applying M3 correction to 42500 shots...
	Done in 0.023974396288394928 seconds.
Applying M3 correction to 45000 shots...
	Done in 0.026412792038172483 seconds.
Applying M3 correction to 47500 shots...
	Done in 0.026364430785179138 seconds.
Applying M3 correction to 50000 shots...
	Done in 0.02820305060595274 seconds.

Text(0.5, 1.0, 'Time to apply M3 correction')

Pagbibigay-kahulugan sa plot

Ang plot sa itaas ay nagpapakita na ang oras na kinakailangan upang mag-apply ng M3 correction ay sumusukat nang linear sa bilang ng shots.

Pag-scale up

n_qubits = 80
rng = Random(12345)
circuit, hidden_shift, hidden_shift_string = run_hidden_shift_circuit(
    n_qubits, rng
)

print(f"Hidden shift string {hidden_shift_string}")

Hidden shift string 00000010100110101011101110010001010000110011101001101010101001111001100110000111

isa_circuit = get_isa_circuit(circuit, backend)

job = run_sampler(backend, isa_circuit, NUM_SHOTS)
mit, qubit_mapping = setup_mthree_mitigation(isa_circuit, backend)

counts, pub_result = get_bitstring_counts(job)

probs, most_probable = find_hidden_shift_bitstring(
    counts, hidden_shift_string
)

Expected hidden shift string: 00000010100110101011101110010001010000110011101001101010101001111001100110000111
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their probabilities:

{'00000010100110101011101110010001010000110011101001101010101001111001100110000111': (0.50402,
  80),
 '00000010100110101011101110010001010000110011100001101010101001111001100110000111': (0.0396,
  79),
 '00000010100110101011101110010001010000110011101001101010101001111001100100000111': (0.0323,
  79),
 '00000010100110101011101110010001010000110011101001101010101001101001100110000111': (0.01936,
  79),
 '00000010100110101011101110010011010000110011101001101010101001111001100110000111': (0.01432,
  79),
 '00000010100110101011101110010001010000110011101001101010101001011001100110000111': (0.0101,
  79),
 '00000010100110101011101110010001010000110011101001101010101001110001100110000111': (0.00924,
  79),
 '00000010100110101011101110010001010000010011101001101010101001111001100110000111': (0.00908,
  79),
 '00000010100110101011100110010001010000110011101001101010101001111001100110000111': (0.00888,
  79),
 '00000010100110101011101110010001010000110011101001100010101001111001100110000111': (0.0082,
  79)}

Makikita natin na ang tamang hidden shift string ay natagpuan. Bukod pa rito, ang siyam na susunod na pinaka-malamang na bitstrings ay mali lamang sa isang posisyon. Itala ang pinakamalamang na probabilidad:

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.50402

print(f"Expected hidden shift string: {hidden_shift_string}")
max_probability_after_M3, is_hidden_shift_identified = perform_mitigation(
    mit, counts, qubit_mapping
)

Expected hidden shift string: 00000010100110101011101110010001010000110011101001101010101001111001100110000111
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their quasi-probabilities:

{'00000010100110101011101110010001010000110011101001101010101001111001100110000111': '9.85e-01',
 '00000010100110101011101110010001010000110011100001101010101001111001100110000111': '6.84e-03',
 '00000010100110101011100110010001010000110011101001101010101001111001100110000111': '3.87e-03',
 '00000010100110101011101110010011010000110011101001101010101001111001100110000111': '3.42e-03',
 '00000010100110101011101110010001010000110011101001101010101001111001100100000111': '3.30e-03',
 '00000010100110101011101110010001010000110011101001101010101001110001100110000111': '3.28e-03',
 '00000010100010101011101110010001010000110011101001101010101001111001100110000111': '2.62e-03',
 '00000010100110101011101110010001010000110011101001101010101001101001100110000111': '2.43e-03',
 '00000010100110101011101110010000010000110011101001101010101001111001100110000111': '1.73e-03',
 '00000010100110101011101110010001010000110011101001101010101001111001000110000111': '1.63e-03'}

compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
)

Most probable probability before M3: 0.54348
Most probable probability after M3: 0.99
Readout error mitigation effective! 😊

Ang mga resulta ay nagpapakita na ang readout error ay ang nangingibabaw na pinagmumulan ng error at ang M3 mitigation ay epektibo.