Atenuarea erorilor de citire pentru primitiva Sampler folosind M3

Estimare utilizare: sub un minut pe un procesor Heron r2 (NOTĂ: Aceasta este doar o estimare. Timpul tău de execuție poate varia.)

Fundal

Spre deosebire de primitiva Estimator, primitiva Sampler nu are suport integrat pentru atenuarea erorilor. Mai multe dintre metodele suportate de Estimator sunt concepute specific pentru valori de așteptare și, prin urmare, nu sunt aplicabile primitivei Sampler. O excepție o constituie atenuarea erorilor de citire, care este o metodă extrem de eficientă, aplicabilă și primitivei Sampler.

Addon-ul M3 Qiskit implementează o metodă eficientă pentru atenuarea erorilor de citire. Acest tutorial explică cum să folosești addon-ul M3 Qiskit pentru a atenua erorile de citire pentru primitiva Sampler.

Ce este eroarea de citire?

Imediat înainte de măsurare, starea unui registru de qubiți este descrisă printr-o superpoziție de stări ale bazei de calcul, sau printr-o matrice de densitate. Măsurarea registrului de qubiți într-un registru de biți clasici se desfășoară în doi pași. Mai întâi are loc măsurarea cuantică propriu-zisă. Aceasta înseamnă că starea registrului de qubiți este proiectată pe o singură stare a bazei, caracterizată printr-un șir de $1$s și $0$s. Al doilea pas constă în citirea șirului de biți ce caracterizează această stare a bazei și scrierea lui în memoria calculatorului clasic. Numim acest pas citire. Se dovedește că al doilea pas (citirea) introduce mai multe erori decât primul pas (proiecția pe stările bazei). Acest lucru are sens dacă îți amintești că citirea necesită detectarea unei stări cuantice microscopice și amplificarea ei în domeniul macroscopic. Un rezonator de citire este cuplat la qubit-ul (transmon), experimentând astfel o mică schimbare de frecvență. Un puls de microunde este apoi reflectat de pe rezonator, experimentând la rândul lui mici schimbări în caracteristicile sale. Pulsul reflectat este apoi amplificat și analizat. Acesta este un proces delicat și este supus unei multitudini de erori.

Punctul important este că, deși atât măsurarea cuantică, cât și citirea sunt supuse erorilor, aceasta din urmă generează eroarea dominantă, numită eroare de citire, care este subiectul acestui tutorial.

Fundal teoretic

Dacă șirul de biți eșantionat (stocat în memoria clasică) diferă de șirul de biți ce caracterizează starea cuantică proiectată, spunem că a apărut o eroare de citire. Aceste erori sunt observate ca fiind aleatoare și necorelate de la eșantion la eșantion. S-a dovedit util să modelăm eroarea de citire ca un canal clasic zgomotos. Adică, pentru fiecare pereche de șiruri de biți $i$ și $j$, există o probabilitate fixă ca o valoare reală de $j$ să fie citită incorect ca $i$.

Mai precis, pentru fiecare pereche de șiruri de biți $(i, j)$, există o probabilitate (condiționată) ${M}_{i,j}$ ca $i$ să fie citit, știind că valoarea reală este $j.$ Adică,

$${M}_{i,j} = \Pr(\text{valoarea citită este } i | \text{valoarea reală este } j) \text{ pentru } i,j \in (0,...,2^n - 1), \tag{1}$$

unde $n$ este numărul de biți din registrul de citire. Pentru concretețe, presupunem că $i$ este un număr întreg zecimal a cărui reprezentare binară este șirul de biți ce etichetează stările bazei de calcul. Numim matricea $2^n \times 2^n$ ${M}$ matricea de atribuire. Pentru o valoare reală fixă $j$, suma probabilităților peste toate rezultatele zgomotoase $i$ trebuie să fie $1$. Adică

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

O matrice fără intrări negative care satisface (1) se numește stocastic la stânga. O matrice stocastic la stânga se mai numește și stocastic pe coloane deoarece fiecare dintre coloanele sale sumează la $1$. Determinăm experimental valori aproximative pentru fiecare element ${M}_{i,j}$ prin pregătirea repetată a fiecărei stări a bazei $|j \rangle$ și calcularea frecvențelor de apariție a șirurilor de biți eșantionate.

Dacă un experiment presupune estimarea unei distribuții de probabilitate peste șiruri de biți de ieșire prin eșantionare repetată, atunci putem folosi ${M}$ pentru a atenua eroarea de citire la nivelul distribuției. Primul pas este să repetăm un circuit de interes de multe ori, creând o histogramă a șirurilor de biți eșantionate. Histograma normalizată este distribuția de probabilitate măsurată peste cei $2^n$ șiruri de biți posibile, pe care o notăm prin ${\tilde{p}} \in \mathbb{R}^{2^n}$. Probabilitatea (estimată) ${{\tilde{p}}}_i$ de a eșantiona șirul de biți $i$ este egală cu suma peste toate șirurile de biți reale $j$, fiecare ponderat de probabilitatea că este confundat cu $i$. Această afirmație în formă matriceală este

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

unde ${\vec{p}}$ este distribuția reală. Cu alte cuvinte, eroarea de citire are efectul de a multiplica distribuția ideală peste șiruri de biți ${\vec{p}}$ cu matricea de atribuire ${M}$ pentru a produce distribuția observată ${\tilde{p}}$. Am măsurat ${\tilde{p}}$ și ${M}$, dar nu avem acces direct la ${\vec{p}}$. În principiu, vom obține distribuția reală a șirurilor de biți pentru circuitul nostru rezolvând numeric ecuația (2) pentru ${\vec{p}}$.

Înainte de a continua, merită să subliniem câteva caracteristici importante ale acestei abordări naive.

• În practică, ecuația (2) nu se rezolvă prin inversarea lui ${M}$. Rutinele de algebră liniară din bibliotecile software utilizează metode mai stabile, precise și eficiente.
• La estimarea lui ${M}$, am presupus că au apărut doar erori de citire. În particular, am presupus că nu au existat erori de pregătire a stării și de măsurare cuantică — sau cel puțin că acestea au fost altfel atenuate. În măsura în care aceasta este o presupunere bună, ${M}$ reprezintă doar eroarea de citire. Dar când folosim ${M}$ pentru a corecta o distribuție măsurată peste șiruri de biți, nu facem nicio astfel de presupunere. De fapt, ne așteptăm ca un circuit interesant să introducă zgomot, de exemplu, erori de gate. Distribuția „reală" include în continuare efectele oricăror erori care nu sunt altfel atenuate.

Această metodă, deși utilă în anumite circumstanțe, suferă de câteva limitări.

Resursele de spațiu și timp necesare pentru estimarea lui ${M}$ cresc exponențial în $n$:

• Estimarea lui ${M}$ și ${\tilde{p}}$ este supusă erorii statistice din cauza eșantionării finite. Acest zgomot poate fi redus oricât de mult se dorește cu prețul mai multor shot-uri (până la scara temporală a parametrilor hardware care derivă și care duc la erori sistematice în ${M}$). Totuși, dacă nu se fac presupuneri despre șirurile de biți observate la efectuarea atenuării, numărul de shot-uri necesar pentru estimarea lui ${M}$ crește cel puțin exponențial în $n$.
• ${M}$ este o matrice $2^n \times 2^n$. Când $n>10$, cantitatea de memorie necesară pentru a stoca ${M}$ este mai mare decât memoria disponibilă într-un laptop performant.

Limitări suplimentare sunt:

• Distribuția recuperată ${\vec{p}}$ poate avea una sau mai multe probabilități negative (în timp ce suma rămâne egală cu unu). O soluție este să minimizăm $||{M} {\vec{p}} - {\tilde{p}}||^2$ sub constrângerea că fiecare intrare din ${\vec{p}}$ să fie nenegativă. Totuși, timpul de execuție al unei astfel de metode este cu ordine de mărime mai lung decât rezolvarea directă a ecuației (2).
• Această procedură de atenuare funcționează la nivelul unei distribuții de probabilitate peste șiruri de biți. În particular, nu poate corecta o eroare într-un șir de biți individual observat.

Addon-ul Qiskit M3: scalabilitate pentru șiruri de biți mai lungi

Rezolvarea ecuației (2) folosind rutine standard de algebră liniară numerică este limitată la șiruri de biți de cel mult aproximativ 10 biți. M3, în schimb, poate gestiona șiruri de biți mult mai lungi. Două proprietăți cheie ale M3 care fac acest lucru posibil sunt:

• Se presupune că corelațiile de ordin trei și mai mare ale erorii de citire dintre colecții de biți sunt neglijabile și sunt ignorate. În principiu, cu prețul mai multor shot-uri, s-ar putea estima și corelații de ordin superior.
• În loc să construim explicit ${M}$, folosim o matrice efectivă mult mai mică ce înregistrează probabilități doar pentru șirurile de biți colectate la construirea lui ${\tilde{p}}$.

La un nivel înalt, procedura funcționează astfel.

Mai întâi, construim blocuri de bază din care putem construi o descriere simplificată și efectivă a lui ${M}$. Apoi, rulăm în mod repetat circuitul de interes și colectăm șiruri de biți pe care le folosim pentru a construi atât ${\tilde{p}}$, cât și, cu ajutorul blocurilor de bază, un ${M}$ efectiv.

Mai precis,

• Se estimează matricele de atribuire pentru un singur qubit pentru fiecare qubit. Pentru aceasta, pregătim în mod repetat registrul de qubiți în starea zero $|0 ... 0 \rangle$ și apoi în starea unu $|1 ... 1 \rangle$, și înregistrăm probabilitatea pentru fiecare qubit de a fi citit incorect.

• Corelațiile de ordin trei și mai mare sunt presupuse a fi neglijabile și sunt ignorate.

  În schimb, construim $n$ matrice de atribuire pentru un singur qubit $2 \times 2$ și $n(n-1)/2$ matrice de atribuire pentru doi qubiți $4 \times 4$. Aceste matrice de atribuire pentru unul și doi qubiți sunt stocate pentru utilizare ulterioară.

• După eșantionarea repetată a unui circuit pentru a construi ${\tilde{p}}$, construim o aproximare efectivă a lui ${M}$ folosind doar șiruri de biți care sunt eșantionate la construirea lui ${\tilde{p}}$. Această matrice efectivă este construită folosind matricele de un singur qubit și doi qubiți descrise în elementul anterior. Dimensiunea liniară a acestei matrice este cel mult de ordinul numărului de shot-uri utilizate la construirea lui ${\tilde{p}}$, care este mult mai mic decât dimensiunea $2^n$ a matricei de atribuire complete ${M}$.

Pentru detalii tehnice despre M3, poți consulta Scalable Mitigation of Measurement Errors on Quantum Computers.

Aplicarea M3 la un algoritm cuantic

Vom aplica atenuarea erorilor de citire a lui M3 la problema schimbului ascuns. Problema schimbului ascuns, și problemele strâns înrudite, precum problema subgrupului ascuns, au fost concepute inițial într-un context tolerant la erori (mai precis, înainte ca QPU-urile tolerante la erori să fi fost dovedite posibile!). Dar sunt studiate și cu procesoarele disponibile în prezent. Un exemplu de accelerare algoritmică exponențială obținută pentru o variantă a problemei schimbului ascuns pe QPU-uri IBM® de 127 de qubiți poate fi găsit în această lucrare (versiunea arXiv).

În cele ce urmează, toată aritmetica este Booleană. Adică, pentru $a, b \in \mathbb{Z}_2 = \{0, 1\}$, adunarea, $a + b$ este funcția logică XOR. Mai mult, înmulțirea $a \times b$ (sau $a b$) este funcția logică AND. Pentru $x, y \in \{0, 1\}^n$, $x + y$ este definit prin aplicarea bit cu bit a XOR. Produsul scalar $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$ este definit prin $x \cdot y = \sum_i x_i y_i$.

Operatorul Hadamard și transformata Fourier

La implementarea algoritmilor cuantici, este foarte obișnuit să se folosească operatorul Hadamard ca transformată Fourier. Stările bazei de calcul sunt uneori numite stări clasice. Ele se află într-o relație bijectivă cu șirurile de biți clasice. Operatorul Hadamard de $n$ qubiți pe stările clasice poate fi văzut ca o transformată Fourier pe hipercubul Boolean:

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

Considerăm o stare ${|{s}\rangle}$ corespunzătoare șirului de biți fix $s$. Aplicând $H^{\otimes n}$, și folosind ${\langle {x}|{s}\rangle} = \delta_{x,s}$, observăm că transformata Fourier a lui ${|{s}\rangle}$ poate fi scrisă ca

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

Hadamard este inversul propriu, adică, $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$. Astfel, transformata Fourier inversă este același operator, $H^{\otimes n}$. Explicit, avem,

$${|{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}.$$

Problema schimbului ascuns

Considerăm un exemplu simplu de problemă de schimb ascuns. Problema constă în identificarea unui schimb constant în intrarea unei funcții. Funcția pe care o considerăm este produsul scalar. Este cel mai simplu membru dintr-o clasă largă de funcții care admit o accelerare cuantică pentru problema schimbului ascuns prin tehnici similare celor prezentate mai jos.

Fie $x,y \in {\mathbb{Z}_2^m}$ șiruri de biți de lungime $m$. Definim ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ prin

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

Fie $a,b \in {\mathbb{Z}_2^m}$ șiruri de biți fixe de lungime $m$. De asemenea, definim $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ prin

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

unde $a$ și $b$ sunt parametri (ascunși). Ni se dau două cutii negre, una implementând $f$, și cealaltă $g$. Presupunem că știm că acestea calculează funcțiile definite mai sus, cu excepția că nu cunoaștem nici $a$, nici $b$. Jocul constă în determinarea șirurilor de biți ascunse (schimbările) $a$ și $b$ prin interogarea lui $f$ și $g$. Este clar că, dacă jucăm clasic, avem nevoie de $O(2m)$ interogări pentru a determina $a$ și $b$. De exemplu, putem interoga $g$ cu toate perechile de șiruri astfel încât un element al perechii să fie format din zero-uri, iar celălalt element să aibă exact un element setat la $1$. La fiecare interogare, aflăm un element din $a$ sau $b$. Totuși, vom vedea că, dacă cutiile negre sunt implementate ca circuite cuantice, putem determina $a$ și $b$ cu o singură interogare la fiecare din $f$ și $g$.

În contextul complexității algoritmice, o cutie neagră se numește oracol. Pe lângă faptul că este opac, un oracol are proprietatea că consumă intrarea și produce ieșirea instantaneu, fără a adăuga nimic la bugetul de complexitate al algoritmului în care este inclus. De fapt, în cazul de față, oracolele care implementează $f$ și $g$ se vor dovedi a fi eficiente.

Circuite cuantice pentru $f$ și $g$

Avem nevoie de următoarele ingrediente pentru a implementa $f$ și $g$ ca circuite cuantice.

Pentru stările clasice cu un singur qubit ${|{x_1}\rangle}, {|{y_1}\rangle}$, cu $x_1,y_1 \in \mathbb{Z}_2$, gate-ul controlat-$Z$ ${CZ}$ poate fi scris ca

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

Vom opera cu $m$ gate-uri CZ, unul pe $(x_1, y_1)$, unul pe $(x_2, y_2)$, și așa mai departe, până la $(x_m, y_m)$. Numim acest operator ${CZ}_{x,y}$.

$U_f = {CZ}_{x,y}$ este o versiune cuantică a lui ${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}.$$

Avem nevoie și de implementarea unui schimb de șir de biți. Notăm operatorul pe registrul $x$ prin $X^{a_1}\cdots X^{a_m}$ cu $X_a$ și similar pe registrul $y$ cu $X_b = X^{b_1}\cdots X^{b_m}$. Acești operatori aplică $X$ oriunde un singur bit este $1$, și identitatea $I$ oriunde este $0$. Atunci avem

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

A doua cutie neagră $g$ este implementată de unitara $U_g$, dată de

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

Pentru a vedea acest lucru, aplicăm operatorii de la dreapta la stânga stării ${|{x}\rangle}{|{y}\rangle}$. Mai întâi

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

Apoi,

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

În final,

$$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},$$

ceea ce este într-adevăr versiunea cuantică a lui $f(x+a, y+b)$.

Algoritmul schimbului ascuns

Acum asamblăm piesele pentru a rezolva problema schimbului ascuns. Începem prin aplicarea operatorilor Hadamard la registrele inițializate în starea zero.

$$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}.$$

Apoi, interogăm oracolul $g$ pentru a obține

$$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}.$$

În ultima linie, am omis factorul de fază globală constantă $(-1)^{a \cdot b}$, și notăm egalitatea până la o fază cu $\approx$. Apoi, aplicarea oracolului $f$ introduce un alt factor de $(-1)^{x \cdot y}$, eliminând pe cel deja prezent. Atunci avem:

$$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}.$$

Pasul final este aplicarea transformatei Fourier inverse, $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$, rezultând în

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

Circuitul este finalizat. În absența zgomotului, eșantionarea registrelor cuantice va returna șirurile de biți $b, a$ cu probabilitatea $1$.

Produsul scalar Boolean este un exemplu de așa-numitele funcții îndoite (bent functions). Nu vom defini funcțiile îndoite aici, ci vom nota doar că acestea „sunt rezistente în mod maxim împotriva atacurilor care încearcă să exploateze o dependență a ieșirilor de un subspațiu liniar al intrărilor." Acest citat este din articolul Quantum algorithms for highly non-linear Boolean functions, care oferă algoritmi eficienți pentru schimbul ascuns pentru mai multe clase de funcții îndoite. Algoritmul din acest tutorial apare în Secțiunea 3.1 a articolului.

În cazul mai general, circuitul pentru găsirea unui schimb ascuns $s \in \mathbb{Z}^n$ este

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

În cazul general, $f$ și $g$ sunt funcții de o singură variabilă. Exemplul nostru al produsului scalar are această formă dacă lăsăm $f(x, y) \to f(z)$, cu $z$ egal cu concatenarea lui $x$ și $y$, și $s$ egal cu concatenarea lui $a$ și $b$. Cazul general necesită exact două oracole: Un oracol pentru $g$ și unul pentru $\tilde{f}$, unde acesta din urmă este o funcție cunoscută sub numele de duala funcției îndoite $f$. Funcția produs scalar are proprietatea auto-duală $\tilde{f}=f$.

În circuitul nostru pentru schimbul ascuns pe produsul scalar, am omis stratul intermediar de operatori Hadamard care apare în circuitul pentru cazul general. Deși în cazul general acest strat este necesar, am economisit o mică parte din adâncime omițându-l, cu prețul unui mic post-procesare, deoarece ieșirea este ${|{b}\rangle}{|{a}\rangle}$ în loc de ${|{a}\rangle}{|{b}\rangle}$ dorit.

Cerințe

Înainte de a începe acest tutorial, asigură-te că ai instalate următoarele:

• Qiskit SDK v2.1 sau mai recent, cu suport pentru vizualizare
• Qiskit Runtime v0.41 sau mai recent (pip install qiskit-ibm-runtime)
• Add-on-ul M3 Qiskit v3.0 (pip install mthree)

Configurare

# 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

Pasul 1: Mapează intrările clasice la o problemă cuantică

Mai întâi, scriem funcțiile pentru a implementa problema deplasării ascunse ca un 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
    )

Vom începe cu un exemplu mic:

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

Pasul 2: Optimizează Circuit-urile pentru execuția pe hardware cuantic

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

Pasul 3: Execută Circuit-urile folosind primitivele Qiskit

# 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)

Pasul 4: Post-procesare și returnarea rezultatelor în format clasic

În discuția teoretică de mai sus, am stabilit că pentru intrarea $ab$, ne așteptăm la ieșirea $ba$. O complicație suplimentară este că, pentru a avea un Circuit mai simplu (pre-transpilat), am inserat porțile CZ necesare între perechile de Qubiți vecini. Aceasta echivalează cu intercalarea șirurilor de biți $a$ și $b$ sub forma $a1 b1 a2 b2 \ldots$. Șirul de ieșire $ba$ va fi intercalat în mod similar: $b1 a1 b2 a2 \ldots$. Funcția unscramble de mai jos transformă șirul de ieșire din $b1 a1 b2 a2 \ldots$ în $a1 b1 a2 b2 \ldots$, astfel încât șirurile de intrare și de ieșire să poată fi comparate direct.

# 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)

Distanța Hamming dintre două șiruri de biți reprezintă numărul de poziții în care biții diferă.

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)}

Să înregistrăm probabilitatea celui mai probabil șir de biți înainte de aplicarea mitigării erorilor de citire cu M3.

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

Acum aplicăm corecția de citire învățată de M3 la numărătoare. Funcția apply_corrections returnează o distribuție de quasi-probabilitate. Aceasta este o listă de obiecte float care însumează $1$. Totuși, unele valori pot fi negative.

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'}

Compararea identificării șirului de deplasare ascunsă înainte și după aplicarea corecției M3

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! 😊

Reprezentarea grafică a modului în care timpul CPU necesar M3 se scalează cu numărul de măsurători

# 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')

Interpretarea graficului

Graficul de mai sus arată că timpul necesar pentru aplicarea corecției M3 se scalează liniar cu numărul de măsurători.

Scalare

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)}

Observăm că șirul corect de deplasare ascunsă este identificat. Mai mult, urmtorii nouă cei mai probabili șiruri de biți sunt greșiți într-o singură poziție. Înregistrăm probabilitatea cea mai probabilă:

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! 😊

Rezultatele arată că erorile de citire au fost sursa dominantă de eroare și că mitigarea M3 a fost eficientă.