Pengurangan ralat bacaan untuk primitif Sampler menggunakan M3

Anggaran penggunaan: kurang daripada satu minit pada pemproses Heron r2 (NOTA: Ini adalah anggaran sahaja. Masa jalan anda mungkin berbeza.)

Latar Belakang

Berbeza dengan primitif Estimator, primitif Sampler tidak mempunyai sokongan terbina dalam untuk pengurangan ralat. Beberapa kaedah yang disokong oleh Estimator direka khusus untuk nilai jangkaan, dan oleh itu tidak boleh digunakan pada primitif Sampler. Satu pengecualian ialah pengurangan ralat bacaan, iaitu kaedah yang sangat berkesan dan juga boleh digunakan pada primitif Sampler.

Addon M3 Qiskit melaksanakan kaedah yang cekap untuk pengurangan ralat bacaan. Tutorial ini menerangkan cara menggunakan addon M3 Qiskit untuk mengurangkan ralat bacaan bagi primitif Sampler.

Apakah ralat bacaan?

Sejurus sebelum pengukuran, keadaan daftar qubit diterangkan oleh superposisi keadaan asas pengiraan, atau oleh matriks ketumpatan. Pengukuran daftar qubit ke dalam daftar bit klasik kemudian berjalan dalam dua langkah. Pertama, pengukuran kuantum yang sebenar dilakukan. Ini bermakna keadaan daftar qubit diunjur ke satu keadaan asas tunggal yang dicirikan oleh rentetan $1$ dan $0$. Langkah kedua terdiri daripada membaca rentetan bit yang mencirikan keadaan asas ini dan menulisnya ke dalam memori komputer klasik. Kita memanggil langkah ini bacaan. Ternyata langkah kedua (bacaan) menanggung lebih banyak ralat berbanding langkah pertama (unjuran ke keadaan asas). Ini masuk akal apabila anda ingat bahawa bacaan memerlukan pengesanan keadaan kuantum mikroskopik dan memperkuatnya ke alam makroskopik. Resonator bacaan digandingkan dengan qubit (transmon), lalu mengalami anjakan frekuensi yang sangat kecil. Denyut gelombang mikro kemudian dipantulkan daripada resonator, seterusnya mengalami perubahan kecil dalam ciri-cirinya. Denyut yang dipantulkan kemudian diperkuat dan dianalisis. Ini adalah proses yang halus dan terdedah kepada pelbagai ralat.

Perkara penting ialah, walaupun pengukuran kuantum dan bacaan kedua-duanya tertakluk kepada ralat, yang terakhir menanggung ralat yang dominan, dipanggil ralat bacaan, yang menjadi fokus dalam tutorial ini.

Latar belakang teori

Jika rentetan bit yang disampel (disimpan dalam memori klasik) berbeza daripada rentetan bit yang mencirikan keadaan kuantum yang diunjur, kita mengatakan bahawa ralat bacaan telah berlaku. Ralat ini diperhatikan sebagai rawak dan tidak berkorelasi dari sampel ke sampel. Terbukti berguna untuk memodelkan ralat bacaan sebagai saluran klasik bergangguan. Iaitu, bagi setiap pasangan rentetan bit $i$ dan $j$, terdapat kebarangkalian tetap bahawa nilai sebenar $j$ akan dibaca secara silap sebagai $i$.

Lebih tepat lagi, bagi setiap pasangan rentetan bit $(i, j)$, terdapat kebarangkalian (bersyarat) ${M}_{i,j}$ bahawa $i$ dibaca, dengan syarat nilai sebenarnya ialah $j.$ Iaitu,

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

di mana $n$ ialah bilangan bit dalam daftar bacaan. Untuk konkrit, kita andaikan bahawa $i$ ialah integer perpuluhan yang perwakilan binarinya ialah rentetan bit yang melabelkan keadaan asas pengiraan. Kita memanggil matriks $2^n \times 2^n$ ${M}$ sebagai matriks penugasan. Untuk nilai sebenar $j$ yang tetap, menjumlahkan kebarangkalian ke atas semua hasil bergangguan $i$ mesti menghasilkan $1$. Iaitu

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

Matriks tanpa entri negatif yang memenuhi (1) dipanggil stokastik-kiri. Matriks stokastik-kiri juga dipanggil stokastik-lajur kerana setiap lajurnya berjumlah $1$. Kita menentukan nilai anggaran bagi setiap elemen ${M}_{i,j}$ secara eksperimen dengan berulang kali menyediakan setiap keadaan asas $|j \rangle$ dan kemudian mengira kekerapan kemunculan rentetan bit yang disampel.

Jika eksperimen melibatkan penganggaran taburan kebarangkalian ke atas rentetan bit output melalui pensampelan berulang, maka kita boleh menggunakan ${M}$ untuk mengurangkan ralat bacaan pada tahap taburan. Langkah pertama ialah mengulangi litar tetap yang diminati beberapa kali, mencipta histogram rentetan bit yang disampel. Histogram yang dinormalkan ialah taburan kebarangkalian yang diukur ke atas $2^n$ rentetan bit yang mungkin, yang kita nyatakan sebagai ${\tilde{p}} \in \mathbb{R}^{2^n}$. Kebarangkalian (anggaran) ${{\tilde{p}}}_i$ bagi pensampelan rentetan bit $i$ bersamaan dengan jumlah ke atas semua rentetan bit sebenar $j$, setiap satu diberi berat oleh kebarangkalian bahawa ia disalah baca sebagai $i$. Pernyataan ini dalam bentuk matriks ialah

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

di mana ${\vec{p}}$ ialah taburan sebenar. Dengan kata lain, ralat bacaan mempunyai kesan menggandakan taburan ideal ke atas rentetan bit ${\vec{p}}$ dengan matriks penugasan ${M}$ untuk menghasilkan taburan yang diperhatikan ${\tilde{p}}$. Kita telah mengukur ${\tilde{p}}$ dan ${M}$, tetapi tidak mempunyai akses langsung kepada ${\vec{p}}$. Pada prinsipnya, kita akan mendapatkan taburan sebenar rentetan bit untuk litar kita dengan menyelesaikan persamaan (2) untuk ${\vec{p}}$ secara berangka.

Sebelum kita teruskan, ada baiknya menyebut beberapa ciri penting pendekatan naif ini.

• Dalam amalan, persamaan (2) tidak diselesaikan dengan mengsongsangkan ${M}$. Rutin aljabar linear dalam perpustakaan perisian menggunakan kaedah yang lebih stabil, tepat, dan cekap.
• Ketika menganggar ${M}$, kita andaikan bahawa hanya ralat bacaan yang berlaku. Khususnya, kita andaikan tiada ralat penyediaan keadaan dan pengukuran kuantum — atau sekurang-kurangnya ia telah dikurangkan. Setakat andaian ini tepat, ${M}$ sebenarnya hanya mewakili ralat bacaan sahaja. Tetapi apabila kita menggunakan ${M}$ untuk membetulkan taburan yang diukur ke atas rentetan bit, kita tidak membuat andaian sedemikian. Malah, kita menjangkakan litar yang menarik akan memperkenalkan gangguan, contohnya, ralat gate. Taburan "sebenar" masih termasuk kesan daripada sebarang ralat yang tidak dikurangkan.

Kaedah ini, walaupun berguna dalam beberapa keadaan, mempunyai beberapa had.

Sumber ruang dan masa yang diperlukan untuk menganggar ${M}$ meningkat secara eksponen dalam $n$:

• Penganggar ${M}$ dan ${\tilde{p}}$ tertakluk kepada ralat statistik akibat pensampelan terhingga. Gangguan ini boleh dikecilkan sesuka hati dengan kos lebih banyak tembakan (sehingga skala masa parameter perkakasan yang hanyut yang mengakibatkan ralat sistematik dalam ${M}$). Walau bagaimanapun, jika tiada andaian dibuat tentang rentetan bit yang diperhatikan ketika melakukan pengurangan, bilangan tembakan yang diperlukan untuk menganggar ${M}$ meningkat sekurang-kurangnya secara eksponen dalam $n$.
• ${M}$ ialah matriks $2^n \times 2^n$. Apabila $n>10$, jumlah memori yang diperlukan untuk menyimpan ${M}$ adalah lebih besar daripada memori yang tersedia dalam komputer riba berkuasa.

Had selanjutnya ialah:

• Taburan yang dipulihkan ${\vec{p}}$ mungkin mempunyai satu atau lebih kebarangkalian negatif (walaupun masih berjumlah satu). Satu penyelesaian ialah meminimumkan $||{M} {\vec{p}} - {\tilde{p}}||^2$ tertakluk kepada kekangan bahawa setiap entri dalam ${\vec{p}}$ adalah tidak negatif. Walau bagaimanapun, masa jalan kaedah sedemikian adalah magnitud berkali lebih lama berbanding menyelesaikan persamaan (2) secara langsung.
• Prosedur pengurangan ini beroperasi pada tahap taburan kebarangkalian ke atas rentetan bit. Khususnya, ia tidak boleh membetulkan ralat dalam satu rentetan bit yang diperhatikan secara individu.

Addon M3 Qiskit: Skalaan kepada rentetan bit yang lebih panjang

Menyelesaikan persamaan (2) menggunakan rutin aljabar linear berangka standard terhad kepada rentetan bit yang tidak lebih panjang daripada kira-kira 10 bit. Namun begitu, M3 boleh mengendalikan rentetan bit yang jauh lebih panjang. Dua sifat utama M3 yang membolehkan ini ialah:

• Korelasi dalam ralat bacaan tertib tiga dan ke atas dalam kalangan koleksi bit dianggap boleh diabaikan dan diabaikan. Pada prinsipnya, dengan kos lebih banyak tembakan, korelasi yang lebih tinggi juga boleh dianggarkan.
• Daripada membina ${M}$ secara eksplisit, kita menggunakan matriks efektif yang jauh lebih kecil yang merekod kebarangkalian hanya untuk rentetan bit yang dikumpulkan semasa membina ${\tilde{p}}$.

Secara umum, prosedur ini berfungsi seperti berikut.

Pertama, kita membina blok binaan yang boleh kita gunakan untuk membina penerangan yang disederhanakan dan efektif bagi ${M}$. Kemudian, kita menjalankan litar yang diminati berulang kali dan mengumpulkan rentetan bit yang kita gunakan untuk membina kedua-dua ${\tilde{p}}$ dan, dengan bantuan blok binaan, ${M}$ yang efektif.

Lebih tepat lagi,

• Matriks penugasan satu qubit dianggarkan untuk setiap qubit. Untuk melakukan ini, kita berulang kali menyediakan daftar qubit dalam keadaan semua-sifar $|0 ... 0 \rangle$ dan kemudian dalam keadaan semua-satu $|1 ... 1 \rangle$, dan merekod kebarangkalian bagi setiap qubit yang dibaca secara silap.

• Korelasi tertib tiga dan ke atas dianggap boleh diabaikan dan diabaikan.

  Sebaliknya kita membina bilangan $n$ matriks penugasan satu qubit $2 \times 2$, dan bilangan $n(n-1)/2$ matriks penugasan dua qubit $4 \times 4$. Matriks penugasan satu dan dua qubit ini disimpan untuk kegunaan kemudian.

• Selepas berulang kali mengambil sampel litar untuk membina ${\tilde{p}}$, kita membina anggaran efektif bagi ${M}$ menggunakan hanya rentetan bit yang disampel semasa membina ${\tilde{p}}$. Matriks efektif ini dibina menggunakan matriks satu dan dua qubit yang diterangkan dalam item sebelumnya. Dimensi linear matriks ini adalah paling banyak setaraf dengan bilangan tembakan yang digunakan dalam membina ${\tilde{p}}$, yang jauh lebih kecil daripada dimensi $2^n$ matriks penugasan penuh ${M}$.

Untuk perincian teknikal tentang M3, anda boleh merujuk kepada Scalable Mitigation of Measurement Errors on Quantum Computers.

Penggunaan M3 pada algoritma kuantum

Kita akan menggunakan pengurangan bacaan M3 pada masalah anjakan tersembunyi. Masalah anjakan tersembunyi, dan masalah yang berkaitan rapat seperti masalah subkumpulan tersembunyi, pada mulanya difikirkan dalam tetapan toleran ralat (lebih tepat lagi, sebelum QPU toleran ralat terbukti boleh dilaksanakan!). Tetapi ia turut dikaji dengan pemproses yang ada kini. Contoh kelebihan eksponen algoritma yang diperoleh untuk varian masalah anjakan tersembunyi pada QPU IBM® 127 qubit boleh dijumpai dalam kertas kerja ini (versi arXiv).

Dalam perbincangan berikut, semua aritmetik adalah Boolean. Iaitu, untuk $a, b \in \mathbb{Z}_2 = \{0, 1\}$, penambahan, $a + b$ ialah fungsi XOR logik. Selanjutnya, pendaraban $a \times b$ (atau $a b$) ialah fungsi AND logik. Untuk $x, y \in \{0, 1\}^n$, $x + y$ ditakrifkan oleh penerapan XOR secara bitwise. Hasil darab titik $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$ ditakrifkan oleh $x \cdot y = \sum_i x_i y_i$.

Operator Hadamard dan jelmaan Fourier

Dalam melaksanakan algoritma kuantum, sangat lazim menggunakan operator Hadamard sebagai jelmaan Fourier. Keadaan asas pengiraan kadang-kadang dipanggil keadaan klasik. Ia mempunyai hubungan satu-dengan-satu dengan rentetan bit klasik. Operator Hadamard $n$-qubit pada keadaan klasik boleh dilihat sebagai jelmaan Fourier pada hiperlobus 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}|}.$$

Pertimbangkan keadaan ${|{s}\rangle}$ yang sepadan dengan rentetan bit tetap $s$. Menggunakan $H^{\otimes n}$, dan menggunakan ${\langle {x}|{s}\rangle} = \delta_{x,s}$, kita lihat bahawa jelmaan Fourier bagi ${|{s}\rangle}$ boleh ditulis sebagai

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

Hadamard adalah songsangan dirinya sendiri, iaitu, $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$. Jadi, jelmaan Fourier songsangan ialah operator yang sama, $H^{\otimes n}$. Secara eksplisit, kita ada,

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

Masalah anjakan tersembunyi

Kita pertimbangkan contoh mudah masalah anjakan tersembunyi. Masalahnya ialah mengenal pasti anjakan malar dalam input kepada fungsi. Fungsi yang kita pertimbangkan ialah hasil darab titik. Ia adalah ahli paling mudah daripada kelas fungsi besar yang mengakui kelebihan kuantum untuk masalah anjakan tersembunyi melalui teknik yang serupa dengan yang dibentangkan di bawah.

Biarkan $x,y \in {\mathbb{Z}_2^m}$ ialah rentetan bit berpanjang $m$. Kita takrifkan ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ sebagai

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

Biarkan $a,b \in {\mathbb{Z}_2^m}$ ialah rentetan bit tetap berpanjang $m$. Kita selanjutnya takrifkan $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ sebagai

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

di mana $a$ dan $b$ adalah parameter (tersembunyi). Kita diberi dua kotak hitam, satu melaksanakan $f$, dan satu lagi $g$. Kita andaikan bahawa kita tahu mereka mengira fungsi yang ditakrifkan di atas, kecuali kita tidak tahu $a$ mahupun $b$. Permainannya ialah menentukan rentetan bit tersembunyi (anjakan) $a$ dan $b$ dengan membuat pertanyaan kepada $f$ dan $g$. Jelas bahawa jika kita bermain permainan ini secara klasik, kita memerlukan $O(2m)$ pertanyaan untuk menentukan $a$ dan $b$. Sebagai contoh, kita boleh bertanya kepada $g$ dengan semua pasangan rentetan sedemikian sehingga satu elemen pasangan adalah semua sifar, dan elemen lain mempunyai tepat satu elemen ditetapkan kepada $1$. Pada setiap pertanyaan, kita mempelajari satu elemen sama ada $a$ atau $b$. Walau bagaimanapun, kita akan lihat bahawa, jika kotak hitam dilaksanakan sebagai litar kuantum, kita boleh menentukan $a$ dan $b$ dengan satu pertanyaan kepada setiap daripada $f$ dan $g$.

Dalam konteks kerumitan algoritma, kotak hitam dipanggil oracle. Selain daripada menjadi legap, oracle mempunyai sifat bahawa ia menggunakan input dan menghasilkan output dengan serta-merta, tanpa menambah apa-apa kepada belanjawan kerumitan algoritma yang di dalamnya ia tertanam. Malah, dalam kes yang sedang diperkatakan ini, oracle yang melaksanakan $f$ dan $g$ akan dilihat cekap.

Litar kuantum untuk $f$ dan $g$

Kita memerlukan bahan-bahan berikut untuk melaksanakan $f$ dan $g$ sebagai litar kuantum.

Untuk keadaan klasik satu qubit ${|{x_1}\rangle}, {|{y_1}\rangle}$, dengan $x_1,y_1 \in \mathbb{Z}_2$, gate controlled-$Z$ ${CZ}$ boleh ditulis sebagai

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

Kita akan beroperasi dengan $m$ gate CZ, satu pada $(x_1, y_1)$, dan satu pada $(x_2, y_2)$, dan seterusnya, melalui $(x_m, y_m)$. Kita memanggil operator ini ${CZ}_{x,y}$.

$U_f = {CZ}_{x,y}$ ialah versi kuantum bagi ${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}.$$

Kita juga perlu melaksanakan anjakan rentetan bit. Kita nyatakan operator pada daftar $x$ sebagai $X^{a_1}\cdots X^{a_m}$ dengan $X_a$ dan begitu juga pada daftar $y$ $X_b = X^{b_1}\cdots X^{b_m}$. Operator-operator ini menggunakan $X$ di mana bit tunggal ialah $1$, dan identiti $I$ di mana ia ialah $0$. Maka kita ada

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

Kotak hitam kedua $g$ dilaksanakan oleh uniti $U_g$, diberikan oleh

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

Untuk memahami ini, kita gunakan operator dari kanan ke kiri pada keadaan ${|{x}\rangle}{|{y}\rangle}$. Pertama

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

Kemudian,

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

Akhirnya,

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

yang memang merupakan versi kuantum bagi $f(x+a, y+b)$.

Algoritma anjakan tersembunyi

Kini kita gabungkan semua kepingan untuk menyelesaikan masalah anjakan tersembunyi. Kita mulakan dengan menggunakan Hadamard pada daftar yang dimulakan ke keadaan semua-sifar.

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

Seterusnya, kita bertanya oracle $g$ untuk tiba di

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

Dalam baris terakhir, kita diabaikan faktor fasa global malar $(-1)^{a \cdot b}$, dan nyatakan kesamaan sehingga fasa dengan $\approx$. Seterusnya, menggunakan oracle $f$ memperkenalkan satu lagi faktor $(-1)^{x \cdot y}$, membatalkan yang sudah ada. Kita kemudian ada:

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

Langkah terakhir ialah menggunakan jelmaan Fourier songsangan, $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$, menghasilkan

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

Litar selesai. Tanpa gangguan, pensampelan daftar kuantum akan mengembalikan rentetan bit $b, a$ dengan kebarangkalian $1$.

Hasil darab dalam Boolean ialah contoh fungsi yang dipanggil fungsi bengkok. Kita tidak akan mentakrifkan fungsi bengkok di sini tetapi hanya menyebut bahawa ia "sangat tahan terhadap serangan yang cuba mengeksploitasi kebergantungan output pada beberapa subruang linear input." Petikan ini daripada artikel Quantum algorithms for highly non-linear Boolean functions, yang memberikan algoritma anjakan tersembunyi yang cekap untuk beberapa kelas fungsi bengkok. Algoritma dalam tutorial ini muncul dalam Bahagian 3.1 artikel.

Dalam kes yang lebih umum, litar untuk mencari anjakan tersembunyi $s \in \mathbb{Z}^n$ ialah

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

Dalam kes umum, $f$ dan $g$ ialah fungsi satu pemboleh ubah. Contoh hasil darab dalam kita mempunyai bentuk ini jika kita biarkan $f(x, y) \to f(z)$, dengan $z$ sama dengan gabungan $x$ dan $y$, dan $s$ sama dengan gabungan $a$ dan $b$. Kes umum memerlukan tepat dua oracle: Satu oracle untuk $g$ dan satu untuk $\tilde{f}$, di mana yang terakhir ialah fungsi yang dikenali sebagai dual fungsi bengkok $f$. Fungsi hasil darab dalam mempunyai sifat dwi-diri $\tilde{f}=f$.

Dalam litar kita untuk anjakan tersembunyi pada hasil darab dalam, kita tidak menyertakan lapisan tengah Hadamard yang muncul dalam litar untuk kes umum. Walaupun dalam kes umum lapisan ini perlu, kita menjimatkan sedikit kedalaman dengan tidak menyertakannya, dengan kos sedikit pasca-pemprosesan kerana outputnya ialah ${|{b}\rangle}{|{a}\rangle}$ dan bukannya yang diinginkan ${|{a}\rangle}{|{b}\rangle}$.

Keperluan

Sebelum memulakan tutorial ini, pastikan anda telah memasang perkara berikut:

• Qiskit SDK v2.1 atau lebih baru, dengan sokongan visualisasi
• Qiskit Runtime v0.41 atau lebih baru (pip install qiskit-ibm-runtime)
• Addon M3 Qiskit v3.0 (pip install mthree)

Persediaan

# 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

Langkah 1: Petakan input klasik kepada masalah kuantum

Pertama, kita tulis fungsi untuk melaksanakan masalah anjakan tersembunyi sebagai 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
    )

Mari mulakan dengan contoh kecil:

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

Langkah 2: Optimumkan litar untuk pelaksanaan perkakasan kuantum

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

Langkah 3: Laksanakan litar menggunakan primitif 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)

Langkah 4: Pasca-proses dan kembalikan keputusan dalam format klasik

Dalam perbincangan teori di atas, kita telah menentukan bahawa untuk input $ab$, kita menjangkakan output $ba$. Satu komplikasi tambahan ialah, untuk mempunyai litar yang lebih mudah (sebelum transpilasi), kita memasukkan gate CZ yang diperlukan antara pasangan qubit bersebelahan. Ini bersamaan dengan menyusun rentetan bit $a$ dan $b$ sebagai $a1 b1 a2 b2 \ldots$. Rentetan output $ba$ akan disusun dengan cara yang serupa: $b1 a1 b2 a2 \ldots$. Fungsi unscramble di bawah mengubah rentetan output dari $b1 a1 b2 a2 \ldots$ ke $a1 b1 a2 b2 \ldots$ supaya rentetan input dan output boleh dibandingkan secara langsung.

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

Jarak Hamming antara dua rentetan bit ialah bilangan indeks di mana bit berbeza.

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

Mari rekodkan kebarangkalian rentetan bit yang paling mungkin sebelum menggunakan pengurangan ralat bacaan dengan M3.

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

Kini kita gunakan pembetulan bacaan yang dipelajari oleh M3 pada kiraan. Fungsi apply_corrections mengembalikan taburan kuasi-kebarangkalian. Ini ialah senarai objek float yang berjumlah $1$. Tetapi beberapa nilai mungkin negatif.

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

Bandingkan pengenalpastian rentetan bit anjakan tersembunyi sebelum dan selepas menggunakan pembetulan 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! 😊

Plot bagaimana masa CPU yang diperlukan oleh M3 berskala dengan bilangan tembakan

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

Mentafsir plot

Plot di atas menunjukkan bahawa masa yang diperlukan untuk menggunakan pembetulan M3 berskala secara linear dengan bilangan tembakan.

Skalaan ke atas

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

Kita lihat bahawa rentetan bit anjakan tersembunyi yang betul ditemui. Selanjutnya, sembilan rentetan bit yang paling mungkin seterusnya silap hanya pada satu kedudukan. Rekodkan kebarangkalian yang paling mungkin:

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