Repetition codes

เราจะเริ่มบทเรียนด้วยการพูดถึง repetition codes Repetition codes ไม่ได้ป้องกันสารสนเทศควอนตัมจากข้อผิดพลาดทุกประเภทที่อาจเกิดขึ้นบน Qubit แต่ก็เป็นพื้นฐานสำหรับ 9-qubit Shor code ที่เราจะเห็นในบทเรียนถัดไป และยังมีประโยชน์สำหรับอธิบายหลักการพื้นฐานของ error correction

การเข้ารหัสและถอดรหัสแบบคลาสสิก

Repetition codes เป็นตัวอย่างพื้นฐานที่สุดของ error correcting codes แนวคิดคือเราสามารถป้องกันบิตจากข้อผิดพลาดได้โดยการทำซ้ำแต่ละบิตตามจำนวนที่กำหนด

โดยเฉพาะอย่างยิ่ง เริ่มต้นพิจารณา 3-bit repetition code ในบริบทของสารสนเทศคลาสสิกก่อน code นี้เข้ารหัสบิตหนึ่งบิตเป็นสามบิตโดยทำซ้ำบิตสามครั้ง ดังนั้น $0$ เข้ารหัสเป็น $000$ และ $1$ เข้ารหัสเป็น $111$

$$\begin{aligned} 0 & \mapsto 000\\ 1 & \mapsto 111 \end{aligned}$$

ถ้าไม่มีอะไรผิดพลาด เราสามารถแยกแยะสองความเป็นไปได้สำหรับบิตเดิมจากการเข้ารหัสได้อย่างชัดเจน ประเด็นสำคัญคือถ้ามีข้อผิดพลาดและบิตหนึ่งในสามพลิก นั่นคือ 0 เปลี่ยนเป็น 1 หรือ 1 เปลี่ยนเป็น 0 เราก็ยังสามารถหาบิตเดิมได้โดยดูว่าค่าไบนารีใดปรากฏสองครั้ง หรือเทียบเท่า เราสามารถ ถอดรหัส โดยคำนวณค่าส่วนใหญ่ (ค่าไบนารีที่ปรากฏบ่อยที่สุด)

$$a b c \mapsto \operatorname{majority}(a,b,c)$$

แน่นอนว่าถ้า 2 หรือ 3 บิตของการเข้ารหัสพลิก การถอดรหัสจะไม่ทำงานถูกต้องและจะได้บิตที่ผิด แต่ถ้าพลิกไม่เกิน 1 ใน 3 บิต การถอดรหัสจะถูกต้อง นี่เป็นคุณสมบัติทั่วไปของ error correcting codes: อาจช่วยแก้ข้อผิดพลาดได้ แต่เฉพาะเมื่อไม่มีข้อผิดพลาดมากเกินไปเท่านั้น

การลดสัญญาณรบกวนสำหรับ binary symmetric channel

ตัวอย่างของสถานการณ์ที่สามารถลดโอกาสเกิดข้อผิดพลาดโดยใช้ repetition code สมมติว่าเป้าหมายของเราคือสื่อสารบิตเดียวไปยังผู้รับสมมุติ และเราส่งบิตผ่าน binary symmetric channel ที่พลิกแต่ละบิตที่ส่งผ่านอย่างอิสระด้วยความน่าจะเป็น $p$ กล่าวคือ ด้วยความน่าจะเป็น $1-p$ ผู้รับจะได้รับบิตที่ส่ง แต่ด้วยความน่าจะเป็น $p$ บิตพลิกและผู้รับได้รับค่าบิตตรงข้าม

ดังนั้น ถ้าเราไม่ใช้ 3-bit repetition code และส่งบิตที่ต้องการโดยตรงผ่าน channel ผู้รับจะได้รับบิตที่ผิดด้วยความน่าจะเป็น $p$ ในทางกลับกัน ถ้าเราเข้ารหัสบิตที่ต้องการส่งโดยใช้ 3-bit repetition code ก่อน แล้วส่งแต่ละบิตในสามบิตของการเข้ารหัสผ่าน channel แต่ละบิตก็จะพลิกอย่างอิสระด้วยความน่าจะเป็น $p$ โอกาสเกิด bit-flip สูงขึ้นเพราะตอนนี้มีสามบิตที่อาจพลิกแทนที่จะเป็นหนึ่ง แต่ถ้าไม่เกินหนึ่งบิตพลิก ผู้รับจะถอดรหัสได้ถูกต้อง ข้อผิดพลาดจึงยังคงอยู่หลังการถอดรหัสเฉพาะเมื่อสองบิตขึ้นไปพลิกระหว่างการส่ง

ความน่าจะเป็นที่สองบิตพลิกระหว่างการส่งคือ $3p^2(1-p)$ ซึ่งคือ $p^2(1-p)$ สำหรับแต่ละสามตัวเลือกสำหรับบิตที่ไม่พลิก ในขณะที่ความน่าจะเป็นที่บิตทั้งสามพลิกคือ $p^3$ ความน่าจะเป็นรวมของการพลิกสองหรือสามบิตจึงเป็น

$$3 p^2 (1 - p) + p^3 = 3 p^2 - 2 p^3.$$

สำหรับค่า $p$ ที่น้อยกว่าหนึ่งในสอง ผลลัพธ์นี้ทำให้ความน่าจะเป็นที่ผู้รับจะได้รับบิตที่ผิดลดลง ยังคงมีโอกาสเกิดข้อผิดพลาดในกรณีนี้ แต่ code ลด ความน่าจะเป็น (สำหรับค่า $p$ มากกว่า หนึ่งในสอง ในทางกลับกัน code จะ เพิ่ม ความน่าจะเป็นที่ผู้รับจะได้รับบิตที่ผิด)

การเข้ารหัส Qubit

3-bit repetition code เป็น classical error correcting code แต่เราสามารถพิจารณาได้ว่าจะเกิดอะไรขึ้นถ้าลองใช้มันเพื่อป้องกัน Qubit จากข้อผิดพลาด ดังที่เราจะเห็น มันไม่ใช่ quantum error correcting code ที่น่าประทับใจมากนัก เพราะมันทำให้ข้อผิดพลาดบางอย่างน่าจะเป็นมากขึ้น อย่างไรก็ตาม มันเป็นก้าวแรกสู่ Shor code และจะเป็นประโยชน์สำหรับเราในแง่การสอน

ให้ชัดเจนว่า เมื่อเราอ้างถึง 3-bit repetition code ที่ใช้สำหรับ Qubit เราหมายถึงการเข้ารหัส Qubit ที่ สถานะฐานมาตรฐาน ถูกทำซ้ำสามครั้ง ทำให้ state vector ของ Qubit เดียวถูกเข้ารหัสดังนี้

$$\alpha \vert 0\rangle + \beta \vert 1\rangle \mapsto \alpha \vert 000\rangle + \beta \vert 111\rangle$$

การเข้ารหัสนี้สามารถ implement ได้ง่ายโดย quantum circuit ต่อไปนี้ ซึ่งใช้ workspace qubits ที่ initialize แล้วสองตัวและ controlled-NOT gates สองตัว

สังเกตว่าโดยเฉพาะอย่างยิ่ง การเข้ารหัสนี้ไม่เหมือนกับการทำซ้ำสถานะควอนตัมสามครั้ง เช่น state vector ของ Qubit ที่กำหนดถูกเข้ารหัสเป็น $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle$ การเข้ารหัสแบบนั้นไม่สามารถ implement ได้สำหรับสถานะควอนตัมที่ไม่รู้จัก $\vert\psi\rangle$ ตาม no cloning theorem

ข้อผิดพลาดแบบ bit-flip

สมมติว่าข้อผิดพลาดเกิดขึ้นหลังจากการเข้ารหัสได้ดำเนินการแล้ว โดยเฉพาะอย่างยิ่ง สมมติว่า $X$ gate หรือกล่าวอีกนัยหนึ่งคือ bit-flip เกิดขึ้นบน Qubit ตัวใดตัวหนึ่ง ตัวอย่างเช่น ถ้า Qubit ตรงกลางประสบ bit-flip สถานะของ Qubit ทั้งสามจะถูก transform เป็นสถานะนี้:

$$\alpha \vert 010\rangle + \beta \vert 101\rangle.$$

แน่นอนว่านี่ไม่ใช่ข้อผิดพลาดประเภทเดียวที่อาจเกิดขึ้น — และก็สมเหตุสมผลที่จะตั้งคำถามถึงการสมมติว่าข้อผิดพลาดอยู่ในรูปแบบของการดำเนินการยูนิทารีที่สมบูรณ์แบบ เราจะกลับมาพิจารณาประเด็นเหล่านี้ในส่วนสุดท้ายของบทเรียน และตอนนี้เราสามารถมองข้อผิดพลาดในรูปแบบนี้ว่าเป็นเพียงหนึ่งในประเภทข้อผิดพลาดที่เป็นไปได้ (แม้ว่าจะสำคัญพื้นฐาน)

เราสามารถเห็นได้ชัดเจนจากนิพจน์ทางคณิตศาสตร์ของสถานะข้างต้นว่าบิตกลางคือบิตที่แตกต่างภายในแต่ละ ket แต่สมมติว่าเรามีสาม Qubit อยู่ในมือและไม่รู้สถานะ ถ้าเราสงสัยว่าอาจเกิด bit-flip วิธีหนึ่งในการตรวจสอบว่าบิตพลิกคือการวัดในฐานมาตรฐาน ซึ่งในกรณีนี้จะทำให้เราเห็น $010$ หรือ $101$ ด้วยความน่าจะเป็น $\vert\alpha\vert^2$ และ $\vert\beta\vert^2$ ตามลำดับ ในทั้งสองกรณี ข้อสรุปของเราคือบิตกลางพลิก — แต่น่าเสียดายที่เราจะสูญเสียสถานะควอนตัมเดิม $\alpha\vert 0\rangle + \beta \vert 1\rangle$ นี่คือสถานะที่เราพยายามป้องกัน ดังนั้นการวัดในฐานมาตรฐานจึงเป็นตัวเลือกที่ไม่น่าพอใจ

สิ่งที่เราทำแทนได้คือใช้ quantum circuit ต่อไปนี้ โดยป้อนสถานะที่เข้ารหัสเข้าไปในสาม Qubit บน Circuit นี้วัด parity ของสถานะฐานมาตรฐานของสอง Qubit บนและสอง Qubit ล่างของการเข้ารหัสสาม Qubit อย่างไม่ทำลาย

ภายใต้สมมติฐานที่ว่าพลิกไม่เกินหนึ่งบิต สามารถสรุปได้อย่างง่ายดายจากผลการวัดว่า bit-flip เกิดขึ้นที่ใด (หรือไม่มี) โดยเฉพาะอย่างยิ่ง ดังที่แผนภาพ circuit สี่อันต่อไปนี้แสดง ผลการวัด $00$ บ่งบอกว่าไม่มี bit-flip เกิดขึ้น ในขณะที่สามความเป็นไปได้อื่นบ่งบอกว่า Qubit ใดประสบ bit-flip

สิ่งสำคัญคือสถานะของสาม Qubit บนไม่ collapse ในทุกกรณี ซึ่งทำให้เราสามารถแก้ไข bit-flip error ได้ถ้ามีเกิดขึ้น — โดยง่าย ๆ ใช้ bit-flip เดิมอีกครั้งด้วย $X$ gate ตารางต่อไปนี้สรุปสถานะที่เราได้จากการพลิกไม่เกินหนึ่งบิต ผลการวัด (ที่เรียกว่า ซินโดรม ในบริบทของ error correction) และการแก้ไขที่จำเป็นเพื่อกลับสู่การเข้ารหัสเดิม

สถานะ	ซินโดรม	การแก้ไข
$\alpha\vert 000\rangle + \beta \vert 111\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert 001\rangle + \beta \vert 110\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes X$
$\alpha\vert 010\rangle + \beta \vert 101\rangle$	$11$	$\mathbb{I}\otimes X\otimes\mathbb{I}$
$\alpha\vert 100\rangle + \beta \vert 011\rangle$	$10$	$X\otimes\mathbb{I}\otimes\mathbb{I}$

อีกครั้ง เราพิจารณาเฉพาะกรณีที่พลิกไม่เกินหนึ่งบิต สิ่งนี้จะไม่ทำงานถูกต้องถ้าพลิกสองหรือสามบิต และเรายังไม่ได้พิจารณาข้อผิดพลาดอื่น ๆ นอกจาก bit-flips

ข้อผิดพลาดแบบ phase-flip

ในโลกควอนตัม bit-flip errors ไม่ใช่ข้อผิดพลาดเดียวที่ต้องกังวล ตัวอย่างเช่น เรายังต้องกังวลเกี่ยวกับ phase-flip errors ซึ่งอธิบายด้วย $Z$ gates ในแนวเดียวกับ bit-flip errors เราสามารถคิดถึง phase-flip errors ว่าเป็นเพียงความเป็นไปได้อีกอย่างหนึ่งสำหรับข้อผิดพลาดที่อาจส่งผลต่อ Qubit

อย่างไรก็ตาม ดังที่เราจะเห็นในส่วนสุดท้ายของบทเรียน ซึ่งพูดถึง การแยกประเภทของข้อผิดพลาด สำหรับ quantum error correcting codes การมุ่งเน้นที่ bit-flip errors และ phase-flip errors จึงมีเหตุผลที่ดี โดยเฉพาะอย่างยิ่ง ความสามารถในการแก้ bit-flip error, phase-flip error หรือทั้งสองข้อผิดพลาดพร้อมกัน จะหมายถึงความสามารถในการแก้ข้อผิดพลาดควอนตัมแบบสุ่มบน Qubit เดียวโดยอัตโนมัติ

น่าเสียดายที่ 3-bit repetition code ไม่ป้องกัน phase-flips เลย ตัวอย่างเช่น สมมติว่า qubit state $\alpha\vert 0\rangle + \beta\vert 1\rangle$ ถูกเข้ารหัสโดยใช้ 3-bit repetition code และเกิด phase-flip error บน Qubit กลาง ผลลัพธ์คือสถานะ

$$(\mathbb{I} \otimes Z \otimes \mathbb{I}) ( \alpha \vert 000\rangle + \beta \vert 111\rangle) = \alpha \vert 000\rangle - \beta \vert 111\rangle,$$

ซึ่งเป็นสถานะที่เราได้จากการเข้ารหัส qubit state $\alpha\vert 0\rangle - \beta\vert 1\rangle$ นั่นเอง จริง ๆ แล้ว phase-flip error บน Qubit ใดก็ตามในสามตัวของการเข้ารหัสมีผลเดียวกัน ซึ่งเทียบเท่ากับ phase-flip error ที่เกิดขึ้นบน Qubit เดิมก่อนการเข้ารหัส ภายใต้สมมติฐานที่ว่าสถานะควอนตัมเดิมเป็นสถานะที่ไม่รู้จัก จึงไม่มีทางตรวจจับว่าเกิดข้อผิดพลาดขึ้น เพราะสถานะที่ได้เป็นการเข้ารหัสที่ถูกต้องของ qubit state อื่น โดยเฉพาะอย่างยิ่ง การรัน error detection circuit ก่อนหน้านี้บนสถานะ $\alpha \vert 000\rangle - \beta \vert 111\rangle$ จะให้ซินโดรม $00$ อย่างแน่นอน ซึ่งบ่งบอกผิดว่าไม่มีข้อผิดพลาดเกิดขึ้น

ในขณะเดียวกัน ตอนนี้มีสาม Qubit แทนที่จะเป็นหนึ่งที่อาจประสบ phase-flip errors ดังนั้น ในสถานการณ์ที่สมมติว่า phase-flip errors เกิดขึ้นอย่างอิสระบนแต่ละ Qubit ด้วยความน่าจะเป็นไม่เป็นศูนย์ $p$ (คล้ายกับ binary symmetric channel ยกเว้นเป็น phase-flips แทน bit-flips) code นี้จะเพิ่มความน่าจะเป็นของ phase-flip error หลังถอดรหัสสำหรับค่า $p$ ที่น้อย ให้แม่นยำยิ่งขึ้น เราจะได้ phase-flip error บน Qubit เดิมหลังถอดรหัสเมื่อมี phase-flip errors จำนวนคี่บนสาม Qubit ของการเข้ารหัส ซึ่งเกิดขึ้นด้วยความน่าจะเป็น

$$3 p (1 - p)^2 + p^3.$$

ค่านี้มากกว่า $p$ เมื่อ $0<p<1/2$ ดังนั้น code จะเพิ่มความน่าจะเป็นของ phase-flip error สำหรับค่า $p$ ในช่วงนี้

Modified repetition code สำหรับ phase-flip errors

เราสังเกตว่า 3-bit repetition code ไม่ใส่ใจ phase-flip errors เลย ดังนั้นดูเหมือนจะไม่มีประโยชน์สำหรับจัดการกับข้อผิดพลาดประเภทนี้ อย่างไรก็ตาม เราสามารถปรับแต่ง 3-bit repetition code อย่างง่ายดายเพื่อให้มันตรวจจับ phase-flip errors ได้ การปรับแต่งนี้จะทำให้ code ไม่ใส่ใจ bit-flip errors — แต่ดังที่เราจะเห็นในส่วนถัดไป เราสามารถรวม 3-bit repetition code เข้ากับเวอร์ชัน modified นี้เพื่อให้ได้ Shor code ซึ่งสามารถแก้ทั้ง bit-flip และ phase-flip errors ได้

นี่คือเวอร์ชัน modified ของ encoding circuit จากข้างต้น ซึ่งจะสามารถตรวจจับ phase-flip errors ได้ การปรับแต่งง่ายมาก: เราเพียงแต่ใช้ Hadamard gate กับแต่ละ Qubit หลังจากทำ controlled-NOT gates สองตัว

Hadamard gate แปลงสถานะ $\vert 0\rangle$ เป็นสถานะ $\vert + \rangle$ และสถานะ $\vert 1\rangle$ เป็นสถานะ $\vert - \rangle$ ดังนั้นผลสุทธิคือ qubit state เดียว $\alpha\vert 0\rangle + \beta \vert 1\rangle$ ถูกเข้ารหัสเป็น

$$\alpha \vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-} \rangle$$

โดยที่ $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ และ $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle$

phase-flip error หรือเทียบเท่า $Z$ gate จะพลิกระหว่างสถานะ $\vert + \rangle$ และ $\vert - \rangle$ ดังนั้นการเข้ารหัสนี้จะมีประโยชน์สำหรับตรวจจับ (และแก้ไข) phase-flip errors โดยเฉพาะอย่างยิ่ง error-detection circuit ก่อนหน้าสามารถปรับแต่งได้ดังนี้

กล่าวเป็นคำพูด เราใช้ circuit จากก่อนหน้าและเพียงแต่ใส่ Hadamard gates บนสาม Qubit บนทั้งที่จุดเริ่มต้นและจุดสิ้นสุด แนวคิดคือ Hadamard gates สามตัวแรก transform สถานะ $\vert + \rangle$ และ $\vert - \rangle$ กลับเป็นสถานะ $\vert 0\rangle$ และ $\vert 1\rangle$ การตรวจสอบ parity เดิมเกิดขึ้น แล้วชั้น Hadamard gates ชั้นที่สอง transform สถานะกลับเป็นสถานะ $\vert + \rangle$ และ $\vert - \rangle$ เพื่อให้เรากู้คืนการเข้ารหัส สำหรับอ้างอิงในอนาคต ขอสังเกตว่า phase-flip detection circuit นี้สามารถทำให้ง่ายขึ้นได้ดังนี้

แผนภาพ circuit สี่อันต่อไปนี้อธิบายว่าเวอร์ชัน modified ของ 3-bit repetition code ของเรา รวมถึงขั้นตอนการเข้ารหัสและขั้นตอนการตรวจจับข้อผิดพลาด ทำงานอย่างไรเมื่อมี phase-flip error ไม่เกินหนึ่งอัน พฤติกรรมคล้ายกับ ordinary 3-bit repetition code สำหรับ bit-flips

นี่คือตารางที่คล้ายกับตารางจากข้างต้น คราวนี้พิจารณาความเป็นไปได้ของ phase-flip error ไม่เกินหนึ่งอัน

สถานะ	ซินโดรม	การแก้ไข
$\alpha\vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-}\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert {+}\,{+}\,{-}\rangle + \beta \vert {-}\,{-}\,{+}\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes Z$
$\alpha\vert {+}\,{-}\,{+}\rangle + \beta \vert {-}\,{+}\,{-}\rangle$	$11$	$\mathbb{I}\otimes Z\otimes\mathbb{I}$
$\alpha\vert {-}\,{+}\,{+} \rangle + \beta \vert {+}\,{-}\,{-}\rangle$	$10$	$Z\otimes\mathbb{I}\otimes\mathbb{I}$

น่าเสียดายที่เวอร์ชัน modified ของ 3-bit repetition code นี้ไม่สามารถแก้ bit-flip errors ได้อีกต่อไป อย่างไรก็ตาม ยังไม่สิ้นหวัง ดังที่แนะนำไว้ก่อนหน้า เราจะสามารถรวม code ทั้งสองที่เพิ่งเห็นเป็น code เดียว — 9-qubit Shor code — ที่สามารถแก้ทั้ง bit-flip และ phase-flip errors และแน่นอน ข้อผิดพลาดใด ๆ บน Qubit เดียวได้