Mitigace chyb při čtení pro primitiv Sampler pomocí M3

Odhadovaná spotřeba: méně než jedna minuta na procesoru Heron r2 (POZNÁMKA: Jde pouze o odhad. Skutečná doba běhu se může lišit.)

Pozadí

Na rozdíl od primitivu Estimator nemá primitiv Sampler vestavěnou podporu pro mitigaci chyb. Několik metod podporovaných Estimatorem je specificky navrženo pro střední hodnoty (expectation values), a proto se na primitiv Sampler nevztahují. Výjimkou je mitigace chyb při čtení, což je vysoce účinná metoda použitelná i pro primitiv Sampler.

Addon M3 pro Qiskit implementuje efektivní metodu mitigace chyb při čtení. Tento tutoriál vysvětluje, jak pomocí addonu M3 pro Qiskit mitigovat chyby při čtení u primitivu Sampler.

Co jsou chyby při čtení?

Těsně před měřením je stav qubitového registru popsán superpozicí výpočetních bázových stavů, nebo hustotní maticí. Měření qubitového registru do klasického bitového registru pak probíhá ve dvou krocích. Nejprve proběhne samotné kvantové měření. To znamená, že stav qubitového registru je promítnut na jediný bázový stav charakterizovaný řetězcem $1$ a $0$. Druhý krok spočívá ve čtení bitového řetězce charakterizujícího tento bázový stav a jeho zápisu do paměti klasického počítače. Tento krok nazýváme readout (čtení). Ukazuje se, že druhý krok (čtení) vnáší více chyb než první krok (promítnutí na bázové stavy). Dává to smysl, když si uvědomíš, že čtení vyžaduje detekci mikroskopického kvantového stavu a jeho zesílení do makroskopické oblasti. K (transmonovému) qubitu je připojen čtecí rezonátor, který tak zažívá velmi malý frekvenční posun. Na rezonátor je pak odražen mikrovlnný puls, který zase zažívá malé změny svých vlastností. Odražený puls je pak zesílen a analyzován. Jde o jemný proces náchylný k celé řadě chyb.

Důležité je, že ačkoli jsou kvantové měření i čtení náchylné k chybám, druhé z nich vnáší dominantní chybu, nazývanou chyba při čtení, a ta je předmětem tohoto tutoriálu.

Teoretické pozadí

Pokud se vzorkovaný bitový řetězec (uložený v klasické paměti) liší od bitového řetězce charakterizujícího promítnutý kvantový stav, říkáme, že došlo k chybě při čtení. Tyto chyby jsou pozorovány jako náhodné a nekorelované od vzorku k vzorku. Ukázalo se jako užitečné modelovat chybu při čtení jako zašuměný klasický kanál. To znamená, že pro každý pár bitových řetězců $i$ a $j$ existuje pevná pravděpodobnost, že skutečná hodnota $j$ bude nesprávně přečtena jako $i$.

Přesněji řečeno, pro každý pár bitových řetězců $(i, j)$ existuje (podmíněná) pravděpodobnost ${M}_{i,j}$, že je přečteno $i$, pokud je skutečná hodnota $j.$ To jest,

$${M}_{i,j} = \Pr(\text{čtená hodnota je } i | \text{skutečná hodnota je } j) \text{ pro } i,j \in (0,...,2^n - 1), \tag{1}$$

kde $n$ je počet bitů v čtecím registru. Pro konkrétnost předpokládáme, že $i$ je desetinné celé číslo, jehož binární reprezentace je bitový řetězec označující výpočetní bázové stavy. Matici $2^n \times 2^n$ ${M}$ nazýváme přiřazovací maticí (assignment matrix). Pro pevnou skutečnou hodnotu $j$ musí součet pravděpodobnosti přes všechny zašuměné výsledky $i$ dát $1$. To jest

$$\sum_{i=0}^{2^n - 1} {M}_{i,j} = 1 \text{ pro všechna } j$$

Matice bez záporných prvků splňující (1) se nazývá levostochastická. Levostochastická matice se také nazývá sloupcově stochastická, protože každý z jejích sloupců se sčítá na $1$. Přibližné hodnoty každého prvku ${M}_{i,j}$ experimentálně zjišťujeme opakovanou přípravou každého bázového stavu $|j \rangle$ a výpočtem frekvencí výskytu vzorkovaných bitových řetězců.

Pokud experiment zahrnuje odhadování rozdělení pravděpodobnosti přes výstupní bitové řetězce opakovaným vzorkováním, pak můžeme ${M}$ použít k mitigaci chyb při čtení na úrovni rozdělení. Prvním krokem je opakované spuštění fixního obvodu zájmu, čímž vytvoříme histogram vzorkovaných bitových řetězců. Normalizovaný histogram je naměřené rozdělení pravděpodobnosti přes $2^n$ možných bitových řetězců, které označíme ${\tilde{p}} \in \mathbb{R}^{2^n}$. (Odhadovaná) pravděpodobnost ${{\tilde{p}}}_i$ vzorkování bitového řetězce $i$ se rovná součtu přes všechny skutečné bitové řetězce $j$, každý vážený pravděpodobností, že bude zaměněn za $i$. Toto tvrzení v maticovém tvaru je

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

kde ${\vec{p}}$ je skutečné rozdělení. Jinými slovy, chyba při čtení má účinek násobení ideálního rozdělení přes bitové řetězce ${\vec{p}}$ přiřazovací maticí ${M}$, čímž vznikne pozorované rozdělení ${\tilde{p}}$. Měřili jsme ${\tilde{p}}$ a ${M}$, ale nemáme přímý přístup k ${\vec{p}}$. V principu získáme skutečné rozdělení bitových řetězců pro náš obvod číselným řešením rovnice (2) pro ${\vec{p}}$.

Než budeme pokračovat, stojí za zmínku některé důležité vlastnosti tohoto naivního přístupu.

• V praxi se rovnice (2) neřeší inverzí ${M}$. Rutiny lineární algebry v softwarových knihovnách používají metody, které jsou stabilnější, přesnější a efektivnější.
• Při odhadování ${M}$ jsme předpokládali, že docházelo pouze k chybám při čtení. Zejména předpokládáme, že nedocházelo k chybám přípravy stavu a kvantového měření — nebo přinejmenším, že byly jinak mitigovány. Do té míry, do jaké je to dobrý předpoklad, ${M}$ skutečně reprezentuje pouze chybu při čtení. Ale když ${M}$ používáme ke korekci naměřeného rozdělení přes bitové řetězce, takový předpoklad neděláme. Ve skutečnosti očekáváme, že zajímavý obvod vnese šum, například chyby Gate. „Skutečné" rozdělení stále zahrnuje efekty z jakýchkoli chyb, které nebyly jinak mitigovány.

Tato metoda je sice za určitých okolností užitečná, trpí však několika omezeními.

Prostorové a časové zdroje potřebné k odhadnutí ${M}$ rostou exponenciálně s $n$:

• Odhadování ${M}$ a ${\tilde{p}}$ podléhá statistické chybě způsobené konečným vzorkováním. Tento šum lze libovolně zmenšit za cenu více shotů (až do časové škály driftování hardwarových parametrů, které vedou k systematickým chybám v ${M}$). Pokud však nejsou učiněny žádné předpoklady o bitových řetězcích pozorovaných při provádění mitigace, počet shotů potřebný k odhadnutí ${M}$ roste přinejmenším exponenciálně s $n$.
• ${M}$ je matice $2^n \times 2^n$. Když $n>10$, množství paměti potřebné k uložení ${M}$ přesahuje paměť dostupnou ve výkonném laptopu.

Dalšími omezeními jsou:

• Obnovené rozdělení ${\vec{p}}$ může mít jednu nebo více záporných pravděpodobností (přičemž jejich součet je stále jedna). Jedním řešením je minimalizovat $||{M} {\vec{p}} - {\tilde{p}}||^2$ s podmínkou, že každý prvek ${\vec{p}}$ je nezáporný. Doba běhu takové metody je však o řády magnitudy delší než přímé řešení rovnice (2).
• Tento postup mitigace pracuje na úrovni rozdělení pravděpodobnosti přes bitové řetězce. Zejména nemůže opravit chybu v individuálním pozorovaném bitovém řetězci.

Addon M3 pro Qiskit: Škálování na delší bitové řetězce

Řešení rovnice (2) pomocí standardních numerických rutin lineární algebry je omezeno na bitové řetězce ne delší než přibližně 10 bitů. M3 však zvládne mnohem delší bitové řetězce. Dvě klíčové vlastnosti M3, které to umožňují, jsou:

• Korelace chyb při čtení třetího a vyššího řádu mezi kolekcemi bitů se předpokládají jako zanedbatelné a jsou ignorovány. V principu by bylo možné za cenu více shotů odhadnout i vyšší korelace.
• Místo explicitního konstruování ${M}$ používáme mnohem menší efektivní matici, která zaznamenává pravděpodobnosti pouze pro bitové řetězce shromážděné při konstrukci ${\tilde{p}}$.

Na vysoké úrovni postup funguje takto.

Nejprve konstruujeme stavební bloky, ze kterých lze sestavit zjednodušený, efektivní popis ${M}$. Poté opakovaně spouštíme obvod zájmu a shromažďujeme bitové řetězce, které použijeme ke konstrukci jak ${\tilde{p}}$, tak s pomocí stavebních bloků i efektivního ${M}$.

Přesněji řečeno,

• Pro každý qubit jsou odhadnuty jednoqubitové přiřazovací matice. Za tímto účelem opakovaně připravíme qubitový registr v stavu samých nul $|0 ... 0 \rangle$ a poté v stavu samých jedniček $|1 ... 1 \rangle$ a zaznamenáme pravděpodobnost, že každý qubit bude přečten nesprávně.

• Korelace třetího a vyššího řádu se předpokládají jako zanedbatelné a jsou ignorovány.

  Místo toho konstruujeme $n$ jednoqubitových přiřazovacích matic $2 \times 2$ a $n(n-1)/2$ dvouqubitových přiřazovacích matic $4 \times 4$. Tyto jedno- a dvouqubitové přiřazovací matice jsou uloženy pro pozdější použití.

• Po opakovaném vzorkování obvodu ke konstrukci ${\tilde{p}}$ sestavíme efektivní aproximaci ${M}$ s využitím pouze bitových řetězců vzorkovaných při konstrukci ${\tilde{p}}$. Tato efektivní matice je postavena pomocí jedno- a dvouqubitových matic popsaných v předchozím bodu. Lineární rozměr této matice je nejvýše řádu počtu shotů použitých při konstrukci ${\tilde{p}}$, což je mnohem menší než rozměr $2^n$ plné přiřazovací matice ${M}$.

Technické podrobnosti o M3 najdeš v Scalable Mitigation of Measurement Errors on Quantum Computers.

Aplikace M3 na kvantový algoritmus

Mitigaci čtení M3 aplikujeme na problém skrytého posunu (hidden shift problem). Problém skrytého posunu a s ním úzce související problémy, jako je problém skryté podgrupy, byly původně koncipovány v nastavení odolném vůči chybám (přesněji řečeno před tím, než bylo prokázáno, že odolné QPU jsou možné!). Studují se však i na dostupných procesorech. Příklad algoritmického exponenciálního zrychlení dosaženého pro variantu problému skrytého posunu na 127qubitových IBM® QPU lze nalézt v tomto článku (verze na arXiv).

V následujícím textu je veškerá aritmetika Booleovská. To znamená, že pro $a, b \in \mathbb{Z}_2 = \{0, 1\}$ je sčítání $a + b$ logická funkce XOR. Dále násobení $a \times b$ (nebo $a b$) je logická funkce AND. Pro $x, y \in \{0, 1\}^n$ je $x + y$ definováno po bitech aplikací XOR. Skalární součin $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$ je definován jako $x \cdot y = \sum_i x_i y_i$.

Hadamardův operátor a Fourierova transformace

Při implementaci kvantových algoritmů je velmi časté použití Hadamardova operátoru jako Fourierovy transformace. Výpočetní bázové stavy se někdy nazývají klasické stavy. Stojí v vztahu jedna ku jedné s klasickými bitovými řetězci. $n$-qubitový Hadamardův operátor na klasické stavy lze chápat jako Fourierovu transformaci na Booleovské hyperkrychli:

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

Uvažujme stav ${|{s}\rangle}$ odpovídající pevnému bitovému řetězci $s$. Aplikací $H^{\otimes n}$ a využitím ${\langle {x}|{s}\rangle} = \delta_{x,s}$ vidíme, že Fourierovu transformaci ${|{s}\rangle}$ lze zapsat jako

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

Hadamard je svou vlastní inverzí, to jest, $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$. Inverzní Fourierova transformace je tedy stejný operátor, $H^{\otimes n}$. Explicitně máme,

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

Problém skrytého posunu

Uvažujeme jednoduchý příklad problému skrytého posunu. Úlohou je identifikovat konstantní posun na vstupu funkce. Funkce, kterou uvažujeme, je skalární součin. Je nejjednodušším členem velké třídy funkcí, které připouštějí kvantové zrychlení pro problém skrytého posunu pomocí technik podobných těm níže uvedeným.

Nechť $x,y \in {\mathbb{Z}_2^m}$ jsou bitové řetězce délky $m$. Definujeme ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ jako

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

Nechť $a,b \in {\mathbb{Z}_2^m}$ jsou pevné bitové řetězce délky $m$. Dále definujeme $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ jako

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

kde $a$ a $b$ jsou (skryté) parametry. Dostaneme dva černé boxy, jeden implementující $f$ a druhý $g$. Předpokládáme, že víme, že počítají výše definované funkce, avšak neznáme ani $a$ ani $b$. Cílem hry je určit skryté bitové řetězce (posuny) $a$ a $b$ dotazy na $f$ a $g$. Je zřejmé, že hrajeme-li hru klasicky, potřebujeme $O(2m)$ dotazů k určení $a$ a $b$. Například se můžeme dotazovat $g$ se všemi páry řetězců takovými, že jeden prvek páru je samé nuly a druhý prvek má právě jeden prvek nastavený na $1$. Každým dotazem se dozvíme jeden prvek buď $a$ nebo $b$. Uvidíme však, že jsou-li černé boxy implementovány jako kvantové Circuit, lze $a$ a $b$ určit jediným dotazem na každý z $f$ a $g$.

V kontextu algoritmické složitosti se černý box nazývá orákulum. Orákulum je kromě své neprůhlednosti charakterizováno tím, že konzumuje vstup a produkuje výstup okamžitě, přičemž nepřidává nic k rozpočtu složitosti algoritmu, ve kterém je obsaženo. Ve skutečnosti, v daném případě, orákula implementující $f$ a $g$ se ukážou jako efektivní.

Kvantové Circuit pro $f$ a $g$

K implementaci $f$ a $g$ jako kvantových Circuit potřebujeme následující ingredience.

Pro jednoqubitové klasické stavy ${|{x_1}\rangle}, {|{y_1}\rangle}$, kde $x_1,y_1 \in \mathbb{Z}_2$, Gate controlled-$Z$ ${CZ}$ lze zapsat jako

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

Budeme operovat s $m$ Gate CZ, jednou na $(x_1, y_1)$, jednou na $(x_2, y_2)$ a tak dále až po $(x_m, y_m)$. Tento operátor nazýváme ${CZ}_{x,y}$.

$U_f = {CZ}_{x,y}$ je kvantová verze ${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}.$$

Potřebujeme také implementovat posun bitového řetězce. Operátor na registru $x$ označíme $X^{a_1}\cdots X^{a_m}$ jako $X_a$ a obdobně na registru $y$ $X_b = X^{b_1}\cdots X^{b_m}$. Tyto operátory aplikují $X$ všude, kde je jeden bit $1$, a identitu $I$ všude, kde je $0$. Pak máme

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

Druhý černý box $g$ je implementován unitárním operátorem $U_g$, daným jako

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

Abychom to ověřili, aplikujeme operátory zprava doleva na stav ${|{x}\rangle}{|{y}\rangle}$. Nejprve

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

Pak,

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

Nakonec,

$$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ž je skutečně kvantová verze $f(x+a, y+b)$.

Algoritmus skrytého posunu

Nyní skládáme díly dohromady, abychom vyřešili problém skrytého posunu. Začneme aplikací Hadamardů na registry inicializované do stavu samých nul.

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

Dále se dotážeme orákula $g$ a dostaneme

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

Na posledním řádku jsme vynechali konstantní globální fázový faktor $(-1)^{a \cdot b}$ a rovnost až na fázi označujeme $\approx$. Dále aplikace orákula $f$ zavádí další faktor $(-1)^{x \cdot y}$, který ruší ten již přítomný. Pak máme:

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

Posledním krokem je aplikace inverzní Fourierovy transformace, $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$, čímž dostaneme

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

Circuit je hotový. Při absenci šumu vzorkování kvantových registrů vrátí bitové řetězce $b, a$ s pravděpodobností $1$.

Booleovský vnitřní součin je příkladem takzvaných ohnutých funkcí (bent functions). Ohnuté funkce zde nebudeme definovat, pouze poznamenáme, že „jsou maximálně odolné vůči útokům, které se snaží využít závislost výstupů na nějakém lineárním podprostoru vstupů." Tento citát pochází z článku Quantum algorithms for highly non-linear Boolean functions, který podává efektivní algoritmy skrytého posunu pro několik tříd ohnutých funkcí. Algoritmus v tomto tutoriálu se nachází v sekci 3.1 článku.

V obecnějším případě je Circuit pro hledání skrytého posunu $s \in \mathbb{Z}^n$

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

V obecném případě jsou $f$ a $g$ funkce jedné proměnné. Náš příklad vnitřního součinu má tuto formu, pokud položíme $f(x, y) \to f(z)$, kde $z$ je konkatenace $x$ a $y$ a $s$ je konkatenace $a$ a $b$. Obecný případ vyžaduje přesně dvě orákula: jedno pro $g$ a jedno pro $\tilde{f}$, kde druhé je funkce známá jako duál ohnuté funkce $f$. Funkce vnitřního součinu má samoduální vlastnost $\tilde{f}=f$.

V našem Circuit pro skrytý posun na vnitřním součinu jsme vynechali střední vrstvu Hadamardů, která se v Circuit pro obecný případ objevuje. I když je v obecném případě tato vrstva nutná, ušetřili jsme trochu hloubky jejím vynecháním za cenu mírného post-processingu, protože výstup je ${|{b}\rangle}{|{a}\rangle}$ místo žádaného ${|{a}\rangle}{|{b}\rangle}$.

Požadavky

Než začneš s tímto tutoriálem, ujisti se, že máš nainstalováno následující:

• Qiskit SDK v2.1 nebo novější s podporou vizualizace
• Qiskit Runtime v0.41 nebo novější (pip install qiskit-ibm-runtime)
• Addon M3 pro Qiskit v3.0 (pip install mthree)

Nastavení

# 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: Namapuj klasické vstupy na kvantový problém

Nejprve napišme funkce pro implementaci problému skrytého posunu 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
    )

Začneme malým příkladem:

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: Optimalizuj Circuit pro spuštění na kvantovém hardwaru

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: Spusť Circuit pomocí primitiv 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 a vrácení výsledků v klasickém formátu

Ve výše uvedené teoretické diskusi jsme určili, že pro vstup $ab$ očekáváme výstup $ba$. Další komplikací je, že kvůli jednodušším (předtranspilovaným) obvodům jsme vložili potřebné brány CZ mezi sousední páry qubitů. To odpovídá prokládání bitových řetězců $a$ a $b$ jako $a1 b1 a2 b2 \ldots$. Výstupní řetězec $ba$ bude proložen podobným způsobem: $b1 a1 b2 a2 \ldots$. Funkce unscramble níže transformuje výstupní řetězec z $b1 a1 b2 a2 \ldots$ na $a1 b1 a2 b2 \ldots$, takže vstupní a výstupní řetězce lze přímo porovnat.

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

Hammingova vzdálenost dvou bitových řetězců je počet indexů, na kterých se bity liší.

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

Zaznamenáme pravděpodobnost nejpravděpodobnějšího bitového řetězce před aplikací mitigace chyb čtení pomocí M3.

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

Nyní aplikujeme korekci čtení naučenou pomocí M3 na počty měření. Funkce apply_corrections vrací kvázi-pravděpodobnostní rozdělení. Jedná se o seznam objektů float, jejichž součet je $1$. Některé hodnoty však mohou být záporné.

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

Porovnání identifikace skrytého posuvného řetězce před a po aplikaci korekce 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! 😊

Jak čas CPU potřebný pro M3 roste s počtem měření

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

Interpretace grafu

Graf výše ukazuje, že čas potřebný k aplikaci korekce M3 roste lineárně s počtem měření.

Škálování nahoru

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

Vidíme, že správný skrytý posunovací řetězec byl nalezen. Navíc devět dalších nejpravděpodobnějších bitových řetězců se liší pouze v jedné pozici. Zaznamenej nejpravděpodobnější pravděpodobnost:

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

Výsledky ukazují, že chyba čtení byla dominantním zdrojem chyby a mitigation M3 byla účinná.