การลดความผิดพลาดในการอ่านค่าสำหรับ Sampler primitive โดยใช้ M3

ประมาณการการใช้งาน: ไม่ถึงหนึ่งนาทีบนโปรเซสเซอร์ Heron r2 (หมายเหตุ: นี่เป็นเพียงการประมาณเท่านั้น เวลาที่ใช้จริงอาจแตกต่างกัน)

พื้นหลัง

ต่างจาก Estimator primitive ตรงที่ Sampler primitive ไม่มีการรองรับการลดความผิดพลาดในตัว วิธีการหลายอย่างที่ Estimator รองรับนั้นออกแบบมาเฉพาะสำหรับค่าความคาดหวัง จึงไม่สามารถนำมาใช้กับ Sampler primitive ได้ ข้อยกเว้นคือการลดความผิดพลาดในการอ่านค่า ซึ่งเป็นวิธีที่มีประสิทธิภาพสูงและนำมาใช้กับ Sampler primitive ได้เช่นกัน

M3 Qiskit addon นำเสนอวิธีที่มีประสิทธิภาพในการลดความผิดพลาดในการอ่านค่า บทช่วยสอนนี้จะอธิบายวิธีใช้ M3 Qiskit addon เพื่อลดความผิดพลาดในการอ่านค่าสำหรับ Sampler primitive

ความผิดพลาดในการอ่านค่าคืออะไร?

ก่อนการวัดผล สถานะของ Qubit register จะถูกอธิบายด้วยซูเปอร์โพซิชันของ computational basis states หรือด้วย density matrix การวัด Qubit register ลงใน classical bit register จะดำเนินการเป็นสองขั้นตอน ขั้นตอนแรกคือการวัดเชิงควอนตัมที่แท้จริง ซึ่งหมายความว่าสถานะของ Qubit register จะถูกโปรเจกต์ไปยัง basis state เดียวที่ระบุด้วย สตริงของ $1$ และ $0$ ขั้นตอนที่สองคือการอ่านสตริงบิตที่ระบุ basis state นี้ แล้วเขียนลงในหน่วยความจำคอมพิวเตอร์แบบคลาสสิก เราเรียกขั้นตอนนี้ว่า readout ปรากฏว่าขั้นตอนที่สอง (readout) มีความผิดพลาดมากกว่าขั้นตอนแรก (การโปรเจกต์ไปยัง basis states) สิ่งนี้สมเหตุสมผลเมื่อนึกว่า readout ต้องตรวจจับ สถานะควอนตัมในระดับจุลภาค แล้วขยายมันขึ้นมาสู่ระดับมหภาค โดย readout resonator จะเชื่อมต่อกับ (transmon) Qubit ทำให้เกิดการเปลี่ยนความถี่เล็กน้อยมาก จากนั้นพัลส์ไมโครเวฟ จะสะท้อนออกจาก resonator แล้วได้รับการเปลี่ยนแปลงเล็กน้อยใน คุณสมบัติของมัน จากนั้นพัลส์ที่สะท้อนกลับมาจะถูกขยายและวิเคราะห์ นี่เป็นกระบวนการที่ละเอียดอ่อน และอยู่ภายใต้ความผิดพลาดหลายประเภท

ประเด็นสำคัญคือ แม้ทั้งการวัดเชิงควอนตัมและ readout จะเกิดความผิดพลาดได้ แต่ อย่างหลังเป็นต้นเหตุของความผิดพลาดหลัก ที่เรียกว่า readout error ซึ่งเป็นสิ่งที่เราโฟกัสในบทช่วยสอนนี้

พื้นหลังทางทฤษฎี

หาก sampled bitstring (ที่จัดเก็บในหน่วยความจำแบบคลาสสิก) แตกต่างจาก bitstring ที่ระบุ สถานะควอนตัมที่ถูกโปรเจกต์ เราเรียกว่าเกิด readout error ขึ้น ความผิดพลาดเหล่านี้พบว่าเป็นแบบสุ่มและไม่สัมพันธ์กันระหว่างแต่ละ sample การสร้างแบบจำลอง readout error ว่าเป็น noisy classical channel นั้นพบว่ามีประโยชน์มาก นั่นคือ สำหรับทุกคู่ของ bitstrings $i$ และ $j$ จะมีความน่าจะเป็นคงที่ที่ค่าจริงของ $j$ จะถูก อ่านผิดเป็น $i$

โดยเฉพาะอย่างยิ่ง สำหรับทุกคู่ของ bitstrings $(i, j)$ จะมีความน่าจะเป็น (แบบเงื่อนไข) ${M}_{i,j}$ ที่ $i$ จะถูกอ่าน เมื่อค่าจริงคือ $j$ นั่นคือ

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

โดยที่ $n$ คือจำนวนบิตใน readout register เพื่อให้ชัดเจน เราสมมติว่า $i$ เป็นจำนวนเต็มในระบบทศนิยมที่การแทนค่าทวิภาคของมันคือ bitstring ที่ใช้ระบุ computational basis states เราเรียกเมทริกซ์ขนาด $2^n \times 2^n$ ${M}$ ว่า assignment matrix สำหรับค่าจริงที่ $j$ คงที่ การบวกความน่าจะเป็นทุกผลลัพธ์ที่มีสัญญาณรบกวน $i$ ต้องได้ $1$ นั่นคือ

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

เมทริกซ์ที่ไม่มีค่าลบและเป็นไปตาม (1) เรียกว่า left-stochastic เมทริกซ์ left-stochastic เรียกอีกอย่างว่า column-stochastic เพราะแต่ละคอลัมน์บวกได้ $1$ เราหาค่าประมาณของแต่ละสมาชิก ${M}_{i,j}$ จากการทดลองโดย เตรียม basis state $|j \rangle$ ซ้ำๆ แล้วคำนวณความถี่ ของการปรากฏของ sampled bitstrings

หากการทดลองหนึ่งเกี่ยวข้องกับการประมาณการกระจายความน่าจะเป็นบน output bitstrings โดยการสุ่มซ้ำๆ เราสามารถใช้ ${M}$ เพื่อลด readout error ในระดับของการกระจาย ขั้นตอนแรกคือการรัน Circuit ที่สนใจซ้ำๆ หลายครั้ง เพื่อสร้าง histogram ของ sampled bitstrings histogram ที่ normalize แล้วคือการกระจายความน่าจะเป็นที่วัดได้บน $2^n$ bitstrings ที่เป็นไปได้ ซึ่งเราแทนด้วย ${\tilde{p}} \in \mathbb{R}^{2^n}$ ความน่าจะเป็น (ที่ประมาณ) ${{\tilde{p}}}_i$ ของการ sample bitstring $i$ เท่ากับผลรวมของ true bitstrings $j$ ทั้งหมด แต่ละอันถ่วงน้ำหนักด้วย ความน่าจะเป็นที่มันจะถูกเข้าใจผิดว่าเป็น $i$ ข้อความนี้ในรูปแบบเมทริกซ์คือ

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

โดยที่ ${\vec{p}}$ คือการกระจายที่แท้จริง กล่าวอีกนัยหนึ่ง readout error มีผลคูณ การกระจายในอุดมคติของ bitstrings ${\vec{p}}$ ด้วย assignment matrix ${M}$ เพื่อ สร้างการกระจายที่สังเกตได้ ${\tilde{p}}$ เราวัด ${\tilde{p}}$ และ ${M}$ แล้ว แต่ไม่มีทางเข้าถึง ${\vec{p}}$ โดยตรง โดยหลักการ เราจะ ได้การกระจายที่แท้จริงของ bitstrings สำหรับ Circuit ของเรา โดยการแก้สมการ (2) หา ${\vec{p}}$ เชิงตัวเลข

ก่อนที่จะไปต่อ มีข้อสังเกตสำคัญบางประการของแนวทางเบื้องต้นนี้

• ในทางปฏิบัติ สมการ (2) ไม่ได้แก้โดยการ invert ${M}$ ขั้นตอนวิธีพีชคณิตเชิงเส้นใน ไลบรารีซอฟต์แวร์ใช้วิธีที่มีเสถียรภาพ แม่นยำ และมีประสิทธิภาพมากกว่า
• เมื่อประมาณค่า ${M}$ เราสมมติว่ามีเฉพาะ readout error เกิดขึ้นเท่านั้น โดยเฉพาะอย่างยิ่ง เราสมมติว่าไม่มีความผิดพลาดในการเตรียมสถานะและการวัดเชิงควอนตัม — หรืออย่างน้อยก็ได้รับการแก้ไขแล้ว ในกรณีที่สมมติฐานนี้ดี ${M}$ จะแทน เฉพาะ readout error เท่านั้น แต่เมื่อเรา ใช้ ${M}$ เพื่อแก้ไขการกระจายที่วัดได้ บน bitstrings เราไม่ได้ตั้งสมมติฐานเช่นนั้น จริงๆ แล้ว เราคาดว่า Circuit ที่น่าสนใจ จะนำเข้าสัญญาณรบกวน เช่น gate errors การกระจาย "ที่แท้จริง" ยังคงรวมผลกระทบจากความผิดพลาดที่ไม่ได้รับการแก้ไขอื่นๆ

วิธีนี้แม้จะมีประโยชน์ในบางสถานการณ์ แต่ก็มีข้อจำกัดบางประการ

ทรัพยากรด้านพื้นที่และเวลาที่ต้องการในการประมาณค่า ${M}$ เพิ่มขึ้นแบบเอ็กซ์โพเนนเชียลตาม $n$:

• การประมาณค่า ${M}$ และ ${\tilde{p}}$ ขึ้นอยู่กับความผิดพลาดทางสถิติจากการ sampling จำนวนจำกัด สัญญาณรบกวนนี้สามารถลดให้เล็กน้อยได้ตามต้องการ โดยแลกกับ shots มากขึ้น (จนถึงช่วงเวลาที่พารามิเตอร์ฮาร์ดแวร์เปลี่ยนแปลง ซึ่งส่งผลให้เกิดความผิดพลาดเชิงระบบใน ${M}$) อย่างไรก็ตาม หากไม่มีการสมมติฐานเกี่ยวกับ bitstrings ที่สังเกตได้ เมื่อทำการลดความผิดพลาด จำนวน shots ที่ต้องการเพื่อประมาณค่า ${M}$ จะเพิ่มขึ้น อย่างน้อยแบบเอ็กซ์โพเนนเชียลตาม $n$
• ${M}$ คือเมทริกซ์ขนาด $2^n \times 2^n$ เมื่อ $n>10$ ปริมาณหน่วยความจำที่ต้องการในการจัดเก็บ ${M}$ จะมากกว่าหน่วยความจำที่มีในแล็ปท็อปประสิทธิภาพสูง

ข้อจำกัดเพิ่มเติม:

• การกระจายที่กู้คืนมา ${\vec{p}}$ อาจมี ความน่าจะเป็นติดลบหนึ่งรายการขึ้นไป (ขณะที่ยังบวกได้หนึ่ง) วิธีแก้ทางหนึ่ง คือการ minimize $||{M} {\vec{p}} - {\tilde{p}}||^2$ โดยมีเงื่อนไขว่า แต่ละสมาชิกใน ${\vec{p}}$ ต้องไม่ติดลบ อย่างไรก็ตาม runtime ของวิธีดังกล่าว ยาวนานกว่าการแก้สมการ (2) โดยตรงถึงหลายอันดับ
• ขั้นตอนการลดความผิดพลาดนี้ทำงานในระดับการกระจายความน่าจะเป็น บน bitstrings โดยเฉพาะอย่างยิ่ง มันไม่สามารถแก้ไขความผิดพลาดใน bitstring แต่ละตัวที่สังเกตได้

Qiskit M3 addon: การปรับขนาดสำหรับ bitstrings ที่ยาวขึ้น

การแก้สมการ (2) โดยใช้ขั้นตอนวิธีพีชคณิตเชิงเส้นมาตรฐานนั้นจำกัดอยู่ที่ bitstrings ที่ยาวไม่เกินประมาณ 10 บิต อย่างไรก็ตาม M3 สามารถจัดการกับ bitstrings ที่ยาวกว่ามากได้ คุณสมบัติสำคัญสองประการของ M3 ที่ทำให้เป็นไปได้คือ:

• สหสัมพันธ์ใน readout error ลำดับที่สามขึ้นไประหว่างกลุ่มของบิต ถูกสมมติว่าไม่มีนัยสำคัญและละเว้น ในทางหลักการ หากแลกกับ shots มากขึ้น ก็สามารถประมาณสหสัมพันธ์ที่สูงกว่าได้เช่นกัน
• แทนที่จะสร้าง ${M}$ อย่างชัดเจน เราใช้เมทริกซ์ effective ที่มีขนาดเล็กกว่ามาก ซึ่งบันทึก ความน่าจะเป็นเฉพาะสำหรับ bitstrings ที่เก็บรวบรวมเมื่อสร้าง ${\tilde{p}}$

ในระดับสูง ขั้นตอนการทำงานมีดังนี้

ขั้นแรก เราสร้าง building blocks ที่จะนำมาใช้สร้างคำอธิบาย effective ที่เรียบง่ายของ ${M}$ จากนั้น เราเรียกใช้ Circuit ที่สนใจซ้ำๆ และเก็บ bitstrings ที่ใช้ในการสร้าง ทั้ง ${\tilde{p}}$ และด้วยความช่วยเหลือจาก building blocks สร้าง ${M}$ effective

โดยละเอียดกว่านั้น:

• Single-qubit assignment matrices จะถูกประมาณสำหรับแต่ละ Qubit เพื่อทำเช่นนี้ เราเตรียม Qubit register ในสถานะ all-zero $|0 ... 0 \rangle$ แล้วในสถานะ all-one $|1 ... 1 \rangle$ ซ้ำๆ และบันทึกความน่าจะเป็นสำหรับแต่ละ Qubit ที่จะถูกอ่านผิด

• สหสัมพันธ์ลำดับที่สามขึ้นไปถูกสมมติว่าไม่มีนัยสำคัญและละเว้น

  แทนที่เราสร้าง $2 \times 2$ single-qubit assignment matrices จำนวน $n$ อัน และ $4 \times 4$ two-qubit assignment matrices จำนวน $n(n-1)/2$ อัน one- และ two-qubit assignment matrices เหล่านี้จะถูกจัดเก็บ ไว้ใช้ในภายหลัง

• หลังจาก sampling Circuit ซ้ำๆ เพื่อสร้าง ${\tilde{p}}$, เราสร้างการประมาณ effective ของ ${M}$ โดยใช้เฉพาะ bitstrings ที่ถูก sample เมื่อสร้าง ${\tilde{p}}$ เมทริกซ์ effective นี้ สร้างจาก single- และ two-qubit matrices ที่อธิบายไว้ในหัวข้อก่อนหน้า มิติเชิงเส้นของเมทริกซ์นี้อยู่ในระดับของจำนวน shots ที่ใช้สร้าง ${\tilde{p}}$ ซึ่งเล็กกว่า มิติ $2^n$ ของ assignment matrix ${M}$ เต็มๆ มาก

สำหรับรายละเอียดทางเทคนิคของ M3 คุณสามารถอ่านได้ใน Scalable Mitigation of Measurement Errors on Quantum Computers

การประยุกต์ใช้ M3 กับ quantum algorithm

เราจะนำ M3's readout mitigation มาใช้กับ hidden shift problem ซึ่ง hidden shift problem และปัญหาที่ใกล้เคียงกัน เช่น hidden subgroup problem ถูกคิดค้นขึ้นในบริบทของ fault-tolerant (แม่นยำกว่านั้น ก่อนที่ fault-tolerant QPUs จะถูกพิสูจน์ว่าเป็นไปได้!) แต่ก็ถูกศึกษาด้วย processor ที่มีอยู่เช่นกัน ตัวอย่างของ algorithmic exponential speedup ที่ได้รับสำหรับตัวแปรหนึ่งของ hidden shift problem บน 127-qubit IBM® QPUs สามารถหาได้ใน บทความนี้ (arXiv version)

ในส่วนต่อไป เลขคณิตทั้งหมดเป็น Boolean นั่นคือ สำหรับ $a, b \in \mathbb{Z}_2 = \{0, 1\}$ การบวก $a + b$ คือฟังก์ชัน XOR เชิงตรรกะ ยิ่งไปกว่านั้น การคูณ $a \times b$ (หรือ $a b$) คือฟังก์ชัน AND เชิงตรรกะ สำหรับ $x, y \in \{0, 1\}^n$, $x + y$ ถูกนิยามโดยการประยุกต์ XOR แบบ bitwise dot product $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$ ถูกนิยามโดย $x \cdot y = \sum_i x_i y_i$

Hadamard operator และ Fourier transform

ในการสร้าง quantum algorithms การใช้ Hadamard operator เป็น Fourier transform นั้นพบได้ทั่วไปมาก computational basis states บางครั้งเรียกว่า classical states ซึ่งมีความสัมพันธ์แบบหนึ่งต่อหนึ่ง กับ classical bitstrings $n$-Qubit Hadamard operator บน classical states สามารถมองได้ว่าเป็น Fourier transform บน Boolean hypercube:

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

พิจารณาสถานะ ${|{s}\rangle}$ ที่สอดคล้องกับ bitstring $s$ ที่คงที่ เมื่อประยุกต์ $H^{\otimes n}$ และใช้ ${\langle {x}|{s}\rangle} = \delta_{x,s}$, เราจะเห็นว่า Fourier transform ของ ${|{s}\rangle}$ สามารถเขียนได้เป็น

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

Hadamard เป็น inverse ของตัวเอง นั่นคือ $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$ ดังนั้น inverse Fourier transform คือ operator เดิม $H^{\otimes n}$ โดยชัดเจน เรามี

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

Hidden shift problem

เราพิจารณาตัวอย่างง่ายๆ ของ hidden shift problem ปัญหาคือการระบุ constant shift ใน input ของฟังก์ชัน ฟังก์ชันที่เราพิจารณาคือ dot product ซึ่งเป็นสมาชิกที่ง่ายที่สุด ของฟังก์ชันกลุ่มใหญ่ที่ยอมรับ quantum speedup สำหรับ hidden shift problem ผ่านเทคนิคที่คล้ายกับที่นำเสนอด้านล่าง

ให้ $x,y \in {\mathbb{Z}_2^m}$ เป็น bitstrings ที่มีความยาว $m$ เรานิยาม ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ โดย

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

ให้ $a,b \in {\mathbb{Z}_2^m}$ เป็น bitstrings ที่คงที่ยาว $m$ เรายังนิยาม $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ โดย

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

โดยที่ $a$ และ $b$ เป็นพารามิเตอร์ที่ซ่อนอยู่ เราได้รับ black boxes สองอัน อันหนึ่ง implement $f$ และอีกอันหนึ่ง $g$ เราสมมติว่าเรารู้ว่ามันคำนวณฟังก์ชันที่นิยามข้างต้น ยกเว้นเราไม่รู้ ทั้ง $a$ และ $b$ เกมคือการหา hidden bitstrings (shifts) $a$ และ $b$ โดยการ query $f$ และ $g$ ชัดเจนว่าหากเราเล่นเกมแบบ classical เราต้องการ $O(2m)$ queries เพื่อหา $a$ และ $b$ ตัวอย่างเช่น เราสามารถ query $g$ ด้วยทุกคู่ของสตริงที่มีองค์ประกอบหนึ่งของคู่เป็น all zeros และอีกองค์ประกอบหนึ่งมีเพียงองค์ประกอบเดียวที่ตั้งเป็น $1$ ในแต่ละ query เราจะเรียนรู้องค์ประกอบหนึ่งของ $a$ หรือ $b$ อย่างไรก็ตาม เราจะเห็นว่า หาก black boxes ถูก implement เป็น quantum circuits เราสามารถ หา $a$ และ $b$ ด้วย query เดียวต่อ $f$ และ $g$

ในบริบทของ algorithmic complexity, black box เรียกว่า oracle นอกจากจะทึบแสงแล้ว oracle ยังมีคุณสมบัติที่รับ input และ ให้ output ทันที โดยไม่เพิ่มอะไรในงบประมาณความซับซ้อนของ algorithm ที่มันฝังอยู่ ในความเป็นจริง ในกรณีนี้ oracles ที่ implement $f$ และ $g$ จะเห็นว่ามีประสิทธิภาพ

Quantum circuits สำหรับ $f$ และ $g$

เราต้องการส่วนประกอบต่อไปนี้เพื่อ implement $f$ และ $g$ เป็น quantum circuits

สำหรับ single-qubit classical states ${|{x_1}\rangle}, {|{y_1}\rangle}$, โดยที่ $x_1,y_1 \in \mathbb{Z}_2$, controlled-$Z$ Gate ${CZ}$ สามารถเขียนได้เป็น

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

เราจะดำเนินการด้วย $m$ CZ gates หนึ่งอันบน $(x_1, y_1)$ และหนึ่งอันบน $(x_2, y_2)$ และต่อไปจนถึง $(x_m, y_m)$ เราเรียก operator นี้ว่า ${CZ}_{x,y}$

$U_f = {CZ}_{x,y}$ คือเวอร์ชันควอนตัมของ ${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}.$$

เราต้องการ implement bitstring shift ด้วย เราแทน operator บน $x$ register $X^{a_1}\cdots X^{a_m}$ ด้วย $X_a$ และในทำนองเดียวกันบน $y$ register $X_b = X^{b_1}\cdots X^{b_m}$ operators เหล่านี้ใช้ $X$ ตรงที่บิตเดียวเป็น $1$ และ identity $I$ ตรงที่เป็น $0$ แล้วเรามี

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

black box ที่สอง $g$ ถูก implement โดย unitary $U_g$ ซึ่งได้จาก

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

เพื่อดูสิ่งนี้ เราประยุกต์ operators จากขวาไปซ้ายกับสถานะ ${|{x}\rangle}{|{y}\rangle}$ ขั้นแรก

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

จากนั้น

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

สุดท้าย

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

ซึ่งก็คือเวอร์ชันควอนตัมของ $f(x+a, y+b)$

Hidden shift algorithm

ตอนนี้เราจะนำชิ้นส่วนต่างๆ มาประกอบกันเพื่อแก้ hidden shift problem เราเริ่มด้วยการใช้ Hadamards กับ registers ที่ initialize ไว้ที่สถานะ all-zero

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

จากนั้น เรา query oracle $g$ เพื่อได้

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

ในบรรทัดสุดท้าย เราละ constant global phase factor $(-1)^{a \cdot b}$ ออก และแทน equality จนถึง phase ด้วย $\approx$ จากนั้น การใช้ oracle $f$ จะนำตัวคูณอีก $(-1)^{x \cdot y}$ เข้ามา ซึ่งยกเลิกกับตัวที่มีอยู่แล้ว แล้วเรามี:

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

ขั้นตอนสุดท้ายคือการใช้ inverse Fourier transform, $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$, ซึ่งได้ผลลัพธ์

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

Circuit เสร็จสมบูรณ์แล้ว ในกรณีที่ไม่มีสัญญาณรบกวน การ sampling quantum registers จะ คืนค่า bitstrings $b, a$ ด้วยความน่าจะเป็น $1$

Boolean inner product เป็นตัวอย่างของฟังก์ชันที่เรียกว่า bent functions เราจะไม่นิยาม bent functions ที่นี่ แต่เพียงแต่สังเกตว่าพวกมัน "มีความต้านทานสูงสุดต่อการโจมตีที่พยายามใช้ประโยชน์จากการพึ่งพา ของ outputs ต่อ linear subspace ของ inputs" คำพูดนี้มาจากบทความ Quantum algorithms for highly non-linear Boolean functions ซึ่ง ให้ hidden shift algorithms ที่มีประสิทธิภาพสำหรับฟังก์ชัน bent หลายกลุ่ม algorithm ในบทช่วยสอนนี้ปรากฏในหัวข้อ 3.1 ของบทความ

ในกรณีทั่วไปยิ่งขึ้น Circuit สำหรับการหา hidden shift $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}.$$

ในกรณีทั่วไป $f$ และ $g$ เป็นฟังก์ชันของตัวแปรเดียว ตัวอย่าง inner product ของเรามีรูปแบบนี้หากเราให้ $f(x, y) \to f(z)$, โดยที่ $z$ เท่ากับการเชื่อมต่อของ $x$ และ $y$ และ $s$ เท่ากับการเชื่อมต่อ ของ $a$ และ $b$ กรณีทั่วไปต้องการ oracles พอดีสองตัว: หนึ่ง oracle สำหรับ $g$ และหนึ่งสำหรับ $\tilde{f}$, โดยที่ฟังก์ชันหลังนี้รู้จักในชื่อ dual ของ bent function $f$ ฟังก์ชัน inner product มีคุณสมบัติ self-dual $\tilde{f}=f$

ใน Circuit ของเราสำหรับ hidden shift บน inner product เราละชั้นกลางของ Hadamards ที่ปรากฏใน Circuit สำหรับกรณีทั่วไปออก แม้ว่าในกรณีทั่วไป ชั้นนี้จำเป็น แต่เราประหยัด depth ได้บ้างโดยละมันออก ที่แลกกับ การ post-processing เล็กน้อย เพราะ output คือ ${|{b}\rangle}{|{a}\rangle}$ แทนที่จะเป็น ${|{a}\rangle}{|{b}\rangle}$ ตามต้องการ

ข้อกำหนด

ก่อนเริ่มบทช่วยสอนนี้ ให้ตรวจสอบว่าคุณติดตั้งสิ่งต่อไปนี้แล้ว:

• Qiskit SDK v2.1 หรือใหม่กว่า พร้อมรองรับ visualization
• Qiskit Runtime v0.41 หรือใหม่กว่า (pip install qiskit-ibm-runtime)
• M3 Qiskit addon v3.0 (pip install mthree)

การตั้งค่า

# 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

ขั้นตอนที่ 1: แมป input แบบ classical ไปยังปัญหาเชิงควอนตัม

ก่อนอื่น เราจะเขียนฟังก์ชันเพื่อ implement ปัญหา hidden shift ในรูปแบบ 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
    )

เริ่มต้นด้วยตัวอย่างขนาดเล็กก่อน:

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

ขั้นตอนที่ 2: ปรับแต่ง Circuit เพื่อรันบน quantum hardware

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

ขั้นตอนที่ 3: รัน Circuit ด้วย Qiskit primitives

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

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

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

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

    return mit, qubit_mapping

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

ขั้นตอนที่ 4: ประมวลผลและแสดงผลในรูปแบบคลาสสิก

ในการอภิปรายเชิงทฤษฎีข้างต้น เราพบว่าสำหรับอินพุต $ab$ เราคาดว่าจะได้เอาต์พุตเป็น $ba$ ความซับซ้อนเพิ่มเติมคือ เพื่อให้ Circuit (ก่อน transpile) ง่ายขึ้น เราได้แทรก CZ Gate ที่จำเป็นระหว่างคู่ Qubit ที่อยู่ติดกัน ซึ่งเท่ากับการสลับ bitstring $a$ และ $b$ เป็น $a1 b1 a2 b2 \ldots$ สตริงเอาต์พุต $ba$ จะถูกสลับในลักษณะเดียวกัน: $b1 a1 b2 a2 \ldots$ ฟังก์ชัน unscramble ด้านล่าง แปลงสตริงเอาต์พุตจาก $b1 a1 b2 a2 \ldots$ เป็น $a1 b1 a2 b2 \ldots$ เพื่อให้สามารถเปรียบเทียบสตริงอินพุตและเอาต์พุตได้โดยตรง

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

ระยะทาง Hamming ระหว่าง bitstring สองอัน คือจำนวนตำแหน่งที่บิตแตกต่างกัน

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

มาบันทึกความน่าจะเป็นของ bitstring ที่น่าจะเป็นไปได้มากที่สุดก่อนที่จะใช้การลด readout error ด้วย M3

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

ตอนนี้เราใช้การแก้ไข readout ที่ M3 เรียนรู้มาปรับปรุง counts ฟังก์ชัน apply_corrections คืนค่าการแจกแจงความน่าจะเป็นแบบ quasi ซึ่งเป็นรายการออบเจ็กต์ float ที่รวมกันได้ $1$ แต่บางค่าอาจเป็นลบได้

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

เปรียบเทียบการระบุ hidden shift string ก่อนและหลังใช้การแก้ไข 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! 😊

พล็อตการใช้เวลา CPU ของ M3 ตามจำนวน shots

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

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

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

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

การแปลผลกราฟ

กราฟข้างต้นแสดงให้เห็นว่าเวลาที่ต้องใช้ในการแก้ไข M3 เพิ่มขึ้นแบบเชิงเส้นตามจำนวน shots

ขยายขนาดขึ้น

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

เราจะเห็นว่าสามารถค้นหา hidden shift string ที่ถูกต้องได้ นอกจากนี้ bitstring ที่น่าจะเป็นไปได้มากที่สุดเก้าอันดับถัดไปผิดพลาดเพียงตำแหน่งเดียวเท่านั้น บันทึกความน่าจะเป็นที่น่าจะเป็นไปได้มากที่สุด:

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