Mitygacja błędów odczytu dla prymitywu Sampler z użyciem M3

Szacowane użycie: poniżej jednej minuty na procesorze Heron r2 (UWAGA: To jest wyłącznie szacunek. Twój czas wykonania może się różnić.)

Wprowadzenie

W odróżnieniu od prymitywu Estimator, prymityw Sampler nie ma wbudowanego wsparcia dla mitygacji błędów. Kilka metod obsługiwanych przez Estimator jest zaprojektowanych specjalnie dla wartości oczekiwanych i dlatego nie ma zastosowania do prymitywu Sampler. Wyjątkiem jest mitygacja błędów odczytu, która jest wysoce skuteczną metodą mającą zastosowanie również do prymitywu Sampler.

Dodatek M3 do Qiskit implementuje efektywną metodę mitygacji błędów odczytu. Ten samouczek wyjaśnia, jak używać dodatku M3 do Qiskit w celu mitygacji błędów odczytu dla prymitywu Sampler.

Czym jest błąd odczytu?

Bezpośrednio przed pomiarem stan rejestru Qubitów jest opisany superpozycją stanów bazy obliczeniowej lub macierzą gęstości. Pomiar rejestru Qubitów do klasycznego rejestru bitów przebiega dwuetapowo. Najpierw wykonywany jest właściwy pomiar kwantowy. Oznacza to, że stan rejestru Qubitów jest rzutowany na pojedynczy stan bazowy charakteryzowany ciągiem $1$-ek i $0$-ek. Drugi etap polega na odczytaniu bitstringa charakteryzującego ten stan bazowy i zapisaniu go w pamięci klasycznego komputera. Nazywamy ten krok odczytem. Okazuje się, że drugi etap (odczyt) generuje więcej błędów niż pierwszy (rzutowanie na stany bazowe). Ma to sens, gdy przypomnisz sobie, że odczyt wymaga wykrycia mikroskopowego stanu kwantowego i wzmocnienia go do sfery makroskopowej. Rezonator odczytu jest sprzężony z Qubitem (transmonem), dzięki czemu doświadcza bardzo małego przesunięcia częstotliwości. Impuls mikrofalowy jest następnie odbijany od rezonatora, przy czym doświadcza małych zmian swoich charakterystyk. Odbity impuls jest następnie wzmacniany i analizowany. Jest to delikatny proces i podlega szeregowi błędów.

Ważny wniosek jest taki, że choć zarówno pomiar kwantowy, jak i odczyt są obarczone błędami, ten drugi generuje dominujący błąd, zwany błędem odczytu, który jest przedmiotem tego samouczka.

Podstawy teoretyczne

Jeśli próbkowany bitsring (przechowywany w pamięci klasycznej) różni się od bitstringa charakteryzującego rzutowany stan kwantowy, mówimy, że wystąpił błąd odczytu. Obserwuje się, że te błędy są losowe i nieskorelowane między próbkami. Okazało się użyteczne modelowanie błędu odczytu jako zaszumionego kanału klasycznego. To znaczy, dla każdej pary bitstringów $i$ i $j$, istnieje stałe prawdopodobieństwo, że prawdziwa wartość $j$ zostanie błędnie odczytana jako $i$.

Dokładniej, dla każdej pary bitstringów $(i, j)$ istnieje (warunkowe) prawdopodobieństwo ${M}_{i,j}$, że $i$ zostanie odczytane, pod warunkiem że prawdziwa wartość to $j.$ Czyli,

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

gdzie $n$ jest liczbą bitów w rejestrze odczytu. Dla konkretności zakładamy, że $i$ jest dziesiętną liczbą całkowitą, której binarna reprezentacja jest bitstringiem etykietującym stany bazy obliczeniowej. Macierz $2^n \times 2^n$ ${M}$ nazywamy macierzą przypisań. Dla stałej prawdziwej wartości $j$ suma prawdopodobieństw po wszystkich zaszumionych wynikach $i$ musi wynosić $1$. Czyli

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

Macierz bez ujemnych wpisów spełniająca (1) nazywana jest lewostochastyczną. Macierz lewostochastyczna jest też nazywana kolumnowostochastyczną, ponieważ każda z jej kolumn sumuje się do $1$. Eksperymentalnie wyznaczamy przybliżone wartości każdego elementu ${M}_{i,j}$, wielokrotnie przygotowując każdy stan bazowy $|j \rangle$ i obliczając częstości wystąpień próbkowanych bitstringów.

Jeśli eksperyment polega na szacowaniu rozkładu prawdopodobieństwa na wyjściowych bitstringach przez wielokrotne próbkowanie, możemy użyć ${M}$ do mitygacji błędu odczytu na poziomie rozkładu. Pierwszym krokiem jest wielokrotne wykonanie interesującego obwodu, tworząc histogram próbkowanych bitstringów. Znormalizowany histogram to zmierzony rozkład prawdopodobieństwa na $2^n$ możliwych bitstringach, który oznaczamy przez ${\tilde{p}} \in \mathbb{R}^{2^n}$. (Szacowane) prawdopodobieństwo ${{\tilde{p}}}_i$ próbkowania bitstringa $i$ jest równe sumie po wszystkich prawdziwych bitstringach $j$, każdy ważony przez prawdopodobieństwo, że zostanie mylony z $i$. Stwierdzenie to w formie macierzowej brzmi:

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

gdzie ${\vec{p}}$ jest prawdziwym rozkładem. Innymi słowy, błąd odczytu ma efekt pomnożenia idealnego rozkładu bitstringów ${\vec{p}}$ przez macierz przypisań ${M}$, dając obserwowany rozkład ${\tilde{p}}$. Zmierzyliśmy ${\tilde{p}}$ i ${M}$, ale nie mamy bezpośredniego dostępu do ${\vec{p}}$. Zasadniczo uzyskamy prawdziwy rozkład bitstringów dla naszego obwodu, rozwiązując równanie (2) dla ${\vec{p}}$ numerycznie.

Zanim przejdziemy dalej, warto zwrócić uwagę na kilka ważnych cech tego naiwnego podejścia.

• W praktyce równanie (2) nie jest rozwiązywane przez odwrócenie ${M}$. Procedury algebry liniowej w bibliotekach programistycznych stosują metody bardziej stabilne, dokładne i efektywne.
• Szacując ${M}$, zakładaliśmy, że wystąpiły wyłącznie błędy odczytu. W szczególności zakładamy, że nie było błędów przygotowania stanu i pomiaru kwantowego — lub przynajmniej że zostały one w inny sposób zmitigowane. W takim stopniu, w jakim jest to dobre założenie, ${M}$ rzeczywiście reprezentuje wyłącznie błąd odczytu. Ale gdy używamy ${M}$ do korekty zmierzonego rozkładu bitstringów, nie czynimy takiego założenia. W rzeczywistości oczekujemy, że interesujący obwód wprowadzi szumy, na przykład błędy bramek. „Prawdziwy" rozkład nadal zawiera efekty wszelkich błędów, które nie zostały w inny sposób zmitigowane.

Ta metoda, choć użyteczna w pewnych okolicznościach, ma kilka ograniczeń.

Zasoby przestrzeni i czasu potrzebne do oszacowania ${M}$ rosną wykładniczo wraz z $n$:

• Szacowanie ${M}$ i ${\tilde{p}}$ jest obarczone błędem statystycznym wynikającym ze skończonego próbkowania. Szum ten można zminimalizować do dowolnie małej wartości kosztem większej liczby shotów (do skali czasowej dryfujących parametrów sprzętu, które skutkują systematycznymi błędami w ${M}$). Jednak jeśli nie przyjmuje się żadnych założeń dotyczących bitstringów obserwowanych podczas mitygacji, liczba shotów wymagana do oszacowania ${M}$ rośnie co najmniej wykładniczo wraz z $n$.
• ${M}$ jest macierzą $2^n \times 2^n$. Gdy $n>10$, ilość pamięci potrzebna do przechowania ${M}$ jest większa niż pamięć dostępna w mocnym laptopie.

Dalsze ograniczenia to:

• Odtworzony rozkład ${\vec{p}}$ może mieć jedno lub więcej ujemnych prawdopodobieństw (sumując się nadal do jedności). Jednym rozwiązaniem jest minimalizacja $||{M} {\vec{p}} - {\tilde{p}}||^2$ przy ograniczeniu, że każdy element ${\vec{p}}$ jest nieujemny. Jednak czas wykonania takiej metody jest o rzędy wielkości dłuższy niż bezpośrednie rozwiązanie równania (2).
• Ta procedura mitygacji działa na poziomie rozkładu prawdopodobieństwa bitstringów. W szczególności nie może skorygować błędu w pojedynczym obserwowanym bitstringu.

Dodatek M3 do Qiskit: skalowanie do dłuższych bitstringów

Rozwiązanie równania (2) za pomocą standardowych numerycznych procedur algebry liniowej jest ograniczone do bitstringów o długości nie większej niż około 10 bitów. M3 może jednak obsługiwać znacznie dłuższe bitstringi. Dwie kluczowe właściwości M3, które to umożliwiają, to:

• Korelacje błędów odczytu rzędu trzeciego i wyższego wśród zbiorów bitów są uznawane za pomijalnie małe i są ignorowane. Zasadniczo, kosztem większej liczby shotów, można szacować wyższe korelacje.
• Zamiast konstruować ${M}$ wprost, używamy znacznie mniejszej efektywnej macierzy, która rejestruje prawdopodobieństwa wyłącznie dla bitstringów zebranych podczas konstruowania ${\tilde{p}}$.

Na wysokim poziomie procedura działa następująco.

Najpierw konstruujemy bloki budulcowe, z których możemy zbudować uproszczony, efektywny opis ${M}$. Następnie wielokrotnie uruchamiamy interesujący obwód i zbieramy bitstringi, których używamy do konstruowania zarówno ${\tilde{p}}$, jak i — z pomocą bloków budulcowych — efektywnego ${M}$.

Dokładniej:

• Jednokubitowe macierze przypisań są szacowane dla każdego Qubitu. W tym celu wielokrotnie przygotowujemy rejestr Qubitów w stanie zerowym $|0 ... 0 \rangle$, a następnie w stanie jedynkowym $|1 ... 1 \rangle$, i rejestrujemy prawdopodobieństwo, że każdy Qubit zostanie odczytany niepoprawnie.

• Korelacje rzędu trzeciego i wyższe są uznawane za pomijalnie małe i są ignorowane.

  Zamiast tego konstruujemy $n$ macierzy przypisań $2 \times 2$ dla pojedynczych Qubitów oraz $n(n-1)/2$ macierzy przypisań $4 \times 4$ dla par Qubitów. Te jedno- i dwukubitowe macierze przypisań są przechowywane do późniejszego użycia.

• Po wielokrotnym próbkowaniu obwodu w celu konstruowania ${\tilde{p}}$, konstruujemy efektywne przybliżenie ${M}$, używając wyłącznie bitstringów próbkowanych podczas konstruowania ${\tilde{p}}$. Ta efektywna macierz jest budowana z użyciem opisanych wcześniej macierzy jedno- i dwukubitowych. Wymiar liniowy tej macierzy wynosi co najwyżej rzędu liczby shotów użytych podczas konstruowania ${\tilde{p}}$, co jest znacznie mniejsze niż wymiar $2^n$ pełnej macierzy przypisań ${M}$.

Szczegóły techniczne dotyczące M3 można znaleźć w artykule Scalable Mitigation of Measurement Errors on Quantum Computers.

Zastosowanie M3 do algorytmu kwantowego

Zastosujemy mitygację odczytu M3 do problemu ukrytego przesunięcia. Problem ukrytego przesunięcia i ściśle z nim powiązane problemy, takie jak problem ukrytej podgrupy, zostały pierwotnie opracowane w kontekście odporności na błędy (a dokładniej, zanim udowodniono możliwość odpornych na błędy QPU!). Są jednak również badane na dostępnych procesorach. Przykład algorytmicznego wykładniczego przyspieszenia uzyskanego dla wariantu problemu ukrytego przesunięcia na 127-kubitowych QPU IBM® można znaleźć w tym artykule (wersja arXiv).

W poniższym tekście całe działania arytmetyczne są boolowskie. To znaczy, dla $a, b \in \mathbb{Z}_2 = \{0, 1\}$, dodawanie $a + b$ jest funkcją logiczną XOR. Ponadto mnożenie $a \times b$ (lub $a b$) jest funkcją logiczną AND. Dla $x, y \in \{0, 1\}^n$, $x + y$ jest zdefiniowane przez bitowe zastosowanie XOR. Iloczyn skalarny $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$ jest zdefiniowany przez $x \cdot y = \sum_i x_i y_i$.

Operator Hadamarda i transformata Fouriera

W implementacji algorytmów kwantowych bardzo powszechne jest używanie operatora Hadamarda jako transformaty Fouriera. Stany bazy obliczeniowej są niekiedy nazywane stanami klasycznymi. Pozostają one w relacji jeden do jednego z klasycznymi bitstringami. Operator Hadamarda $n$-Qubitowy na stanach klasycznych można traktować jako transformatę Fouriera na boolowskiej hiperkostce:

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

Rozważmy stan ${|{s}\rangle}$ odpowiadający stałemu bitstringowi $s$. Stosując $H^{\otimes n}$ i używając ${\langle {x}|{s}\rangle} = \delta_{x,s}$, widzimy, że transformatę Fouriera ${|{s}\rangle}$ można zapisać jako

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

Operator Hadamarda jest swoją własną odwrotnością, czyli $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$. Tak więc odwrotna transformata Fouriera jest tym samym operatorem, $H^{\otimes n}$. Wprost mamy:

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

Problem ukrytego przesunięcia

Rozważamy prosty przykład problemu ukrytego przesunięcia. Problem polega na identyfikacji stałego przesunięcia na wejściu funkcji. Funkcją, którą rozważamy, jest iloczyn skalarny. Jest to najprostszy element dużej klasy funkcji dopuszczających kwantowe przyspieszenie dla problemu ukrytego przesunięcia za pomocą technik podobnych do tych przedstawionych poniżej.

Niech $x,y \in {\mathbb{Z}_2^m}$ będą bitstringami długości $m$. Definiujemy ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ przez

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

Niech $a,b \in {\mathbb{Z}_2^m}$ będą stałymi bitstringami długości $m$. Definiujemy ponadto $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ przez

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

gdzie $a$ i $b$ są (ukrytymi) parametrami. Dane są nam dwie czarne skrzynki: jedna implementująca $f$, a druga $g$. Zakładamy, że wiemy, że obliczają funkcje zdefiniowane powyżej, z tym że nie znamy ani $a$, ani $b$. Celem jest wyznaczenie ukrytych bitstringów (przesunięć) $a$ i $b$ przez wykonywanie zapytań do $f$ i $g$. Oczywiste jest, że jeśli rozgrywamy tę grę klasycznie, potrzebujemy $O(2m)$ zapytań, aby wyznaczyć $a$ i $b$. Na przykład możemy zapytać $g$ o wszystkie pary ciągów, takie że jeden element pary to same zera, a drugi ma dokładnie jeden element równy $1$. W każdym zapytaniu poznajemy jeden element $a$ lub $b$. Jednak zobaczymy, że jeśli czarne skrzynki są zaimplementowane jako obwody kwantowe, możemy wyznaczyć $a$ i $b$ za pomocą jednego zapytania do każdego z $f$ i $g$.

W kontekście złożoności algorytmicznej czarna skrzynka jest nazywana wyrocznią. Oprócz bycia nieprzezroczystą, wyrocznia ma tę właściwość, że zużywa dane wejściowe i zwraca dane wyjściowe natychmiastowo, nie dodając nic do budżetu złożoności algorytmu, w którym jest osadzona. W rzeczywistości w rozpatrywanym przypadku wyrocznie implementujące $f$ i $g$ okazują się efektywne.

Obwody kwantowe dla $f$ i $g$

Potrzebujemy następujących składników, aby zaimplementować $f$ i $g$ jako obwody kwantowe.

Dla jednobitowych stanów klasycznych ${|{x_1}\rangle}, {|{y_1}\rangle}$, z $x_1,y_1 \in \mathbb{Z}_2$, bramka controlled-$Z$ ${CZ}$ może być zapisana jako

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

Będziemy operować $m$ bramkami CZ, jedną na $(x_1, y_1)$, jedną na $(x_2, y_2)$, i tak dalej, aż do $(x_m, y_m)$. Ten operator nazywamy ${CZ}_{x,y}$.

$U_f = {CZ}_{x,y}$ jest kwantową wersją ${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}.$$

Musimy też zaimplementować przesunięcie bitstringa. Oznaczamy operator na rejestrze $x$ przez $X^{a_1}\cdots X^{a_m}$ jako $X_a$ i analogicznie na rejestrze $y$ przez $X_b = X^{b_1}\cdots X^{b_m}$. Operatory te stosują $X$ wszędzie tam, gdzie pojedynczy bit wynosi $1$, i tożsamość $I$ wszędzie tam, gdzie wynosi $0$. Wtedy mamy

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

Druga czarna skrzynka $g$ jest zaimplementowana przez unitarną $U_g$, daną przez

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

Aby to zobaczyć, stosujemy operatory od prawej do lewej do stanu ${|{x}\rangle}{|{y}\rangle}$. Najpierw

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

Następnie,

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

Na koniec,

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

co jest rzeczywiście kwantową wersją $f(x+a, y+b)$.

Algorytm ukrytego przesunięcia

Teraz łączymy elementy, aby rozwiązać problem ukrytego przesunięcia. Zaczynamy od zastosowania Hadamardów do rejestrów zainicjalizowanych w stanie zerowym.

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

Następnie pytamy wyrocznię $g$, aby uzyskać

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

W ostatniej linii pominęliśmy stały globalny czynnik fazowy $(-1)^{a \cdot b}$ i oznaczamy równość z dokładnością do fazy przez $\approx$. Następnie zastosowanie wyroczni $f$ wprowadza kolejny czynnik $(-1)^{x \cdot y}$, który anuluje już obecny. Mamy wtedy:

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

Ostatnim krokiem jest zastosowanie odwrotnej transformaty Fouriera, $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$, dając w wyniku

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

Obwód jest ukończony. W przypadku braku szumu próbkowanie rejestrów kwantowych zwróci bitstringi $b, a$ z prawdopodobieństwem $1$.

Boolowski iloczyn skalarny jest przykładem tak zwanych funkcji giętych. Nie będziemy tu definiować funkcji giętych, lecz jedynie zaznaczymy, że „są maksymalnie odporne na ataki, które starają się wykorzystać zależność wyjść od pewnej liniowej podprzestrzeni wejść." Cytat pochodzi z artykułu Quantum algorithms for highly non-linear Boolean functions, który podaje efektywne algorytmy ukrytego przesunięcia dla kilku klas funkcji giętych. Algorytm z tego samouczka pojawia się w sekcji 3.1 artykułu.

W bardziej ogólnym przypadku obwód do wyznaczania ukrytego przesunięcia $s \in \mathbb{Z}^n$ to

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

W ogólnym przypadku $f$ i $g$ są funkcjami jednej zmiennej. Nasz przykład iloczynu skalarnego ma tę postać, jeśli pozwolimy $f(x, y) \to f(z)$, gdzie $z$ jest konkatenacją $x$ i $y$, a $s$ jest konkatenacją $a$ i $b$. Ogólny przypadek wymaga dokładnie dwóch wyroczni: jednej dla $g$ i jednej dla $\tilde{f}$, gdzie ta ostatnia jest funkcją zwaną dualną do funkcji giętej $f$. Funkcja iloczynu skalarnego ma właściwość samoodwrotności $\tilde{f}=f$.

W naszym obwodzie dla ukrytego przesunięcia na iloczynie skalarnym pominęliśmy środkową warstwę Hadamardów, która pojawia się w obwodzie dla ogólnego przypadku. Choć w ogólnym przypadku ta warstwa jest konieczna, zaoszczędziliśmy trochę głębokości, pomijając ją, kosztem odrobiny dodatkowego przetwarzania, ponieważ wyjściem jest ${|{b}\rangle}{|{a}\rangle}$ zamiast pożądanego ${|{a}\rangle}{|{b}\rangle}$.

Wymagania

Przed rozpoczęciem tego samouczka upewnij się, że masz zainstalowane następujące elementy:

• Qiskit SDK v2.1 lub nowszy, z obsługą wizualizacji
• Qiskit Runtime v0.41 lub nowszy (pip install qiskit-ibm-runtime)
• Dodatek M3 do Qiskit v3.0 (pip install mthree)

Konfiguracja

# 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

Krok 1: Odwzorowanie klasycznych danych wejściowych na problem kwantowy

Najpierw piszemy funkcje implementujące problem ukrytego przesunięcia jako 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
    )

Zaczniemy od małego przykładu:

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

Krok 2: Optymalizacja obwodów do wykonania na sprzęcie kwantowym

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

Krok 3: Wykonanie obwodów za pomocą prymitywów 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)

Krok 4: Post-processing i zwracanie wyników w formacie klasycznym

W omówieniu teoretycznym powyżej ustaliliśmy, że dla wejścia $ab$ oczekujemy wyjścia $ba$. Dodatkowym utrudnieniem jest to, że w celu uzyskania prostszego (przed transpilacją) obwodu wstawiliśmy wymagane bramki CZ między sąsiadującymi parami qubitów. Odpowiada to przeplataniu ciągów bitów $a$ i $b$ jako $a1 b1 a2 b2 \ldots$. Wyjściowy ciąg $ba$ będzie przeplatany w podobny sposób: $b1 a1 b2 a2 \ldots$. Funkcja unscramble poniżej przekształca wyjściowy ciąg z $b1 a1 b2 a2 \ldots$ na $a1 b1 a2 b2 \ldots$, dzięki czemu ciągi wejściowe i wyjściowe można bezpośrednio porównać.

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

Odległość Hamminga między dwoma ciągami bitów to liczba pozycji, na których bity się różnią.

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

Zanotujmy prawdopodobieństwo najbardziej prawdopodobnego ciągu bitów przed zastosowaniem korekcji błędów odczytu za pomocą M3.

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

Teraz stosujemy korekcję odczytu wyuczoną przez M3 do zliczonych wyników. Funkcja apply_corrections zwraca quasi-rozkład prawdopodobieństwa. Jest to lista obiektów float sumujących się do $1$. Jednak niektóre wartości mogą być ujemne.

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

Porównanie identyfikacji ukrytego ciągu przesunięcia przed i po zastosowaniu korekcji 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! 😊

Wykres skalowania czasu CPU wymaganego przez M3 względem liczby strzałów

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

Interpretacja wykresu

Powyższy wykres pokazuje, że czas potrzebny do zastosowania korekcji M3 skaluje się liniowo względem liczby strzałów.

Skalowanie w górę

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

Widzimy, że poprawny ukryty ciąg przesunięcia został znaleziony. Co więcej, dziewięć następnych najbardziej prawdopodobnych ciągów bitów różni się od niego tylko na jednej pozycji. Zanotujmy najbardziej prawdopodobne prawdopodobieństwo:

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

Wyniki pokazują, że błąd odczytu był dominującym źródłem błędu, a mitygacja M3 okazała się skuteczna.