อัลกอริทึมของ Shor

สำหรับโมดูล Qiskit in Classrooms นี้ นักเรียนต้องมีสภาพแวดล้อม Python ที่ใช้งานได้พร้อมแพ็คเกจต่อไปนี้ติดตั้งไว้:

• qiskit v2.1.0 หรือใหม่กว่า
• qiskit-ibm-runtime v0.40.1 หรือใหม่กว่า
• qiskit-aer v0.17.0 หรือใหม่กว่า
• qiskit.visualization
• numpy
• pylatexenc

สำหรับการตั้งค่าและติดตั้งแพ็คเกจข้างต้น ดูคู่มือ ติดตั้ง Qiskit เพื่อรันงานบนคอมพิวเตอร์ควอนตัมจริง นักเรียนต้องสมัครบัญชีกับ IBM Quantum® โดยทำตามขั้นตอนในคู่มือ ตั้งค่าบัญชี IBM Cloud

โมดูลนี้ผ่านการทดสอบและใช้เวลา QPU สามวินาที นี่เป็นเพียงการประมาณการ การใช้งานจริงของคุณอาจแตกต่างกัน

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

บทนำ

ในช่วงต้นทศวรรษ 1990 มีความตื่นเต้นเพิ่มขึ้นเรื่อย ๆ เกี่ยวกับศักยภาพของคอมพิวเตอร์ควอนตัมในการแก้ปัญหาที่ยากสำหรับคอมพิวเตอร์คลาสสิก นักวิทยาศาสตร์คอมพิวเตอร์ที่มีพรสวรรค์บางคนได้คิดค้นอัลกอริทึมที่แสดงให้เห็นถึงพลังของการคอมพิวเตอร์ควอนตัมสำหรับปัญหาเฉพาะกลุ่มที่ถูกสร้างขึ้น แต่ยังไม่มีใครพบ "killer app" ของการคอมพิวเตอร์ควอนตัมที่เดียวที่รับประกันว่าจะปฏิวัติสาขานี้ จนกระทั่งปี 1994 เมื่อ Peter Shor คิดค้นสิ่งที่ตอนนี้เรียกว่าอัลกอริทึมของ Shor สำหรับการแยกตัวประกอบของจำนวนขนาดใหญ่

เป็นที่รู้จักกันดีในเวลานั้นว่าการหาตัวประกอบเฉพาะของจำนวนขนาดใหญ่นั้นยากมากสำหรับคอมพิวเตอร์คลาสสิก อันที่จริง โปรโตคอลความปลอดภัยทางอินเทอร์เน็ตอาศัยความยากนี้ Shor พบวิธีหาตัวประกอบเหล่านี้อย่างมีประสิทธิภาพมากขึ้นแบบเอกซ์โปเนนเชียล โดยโอนขั้นตอนที่ท้าทายกว่าบางส่วนไปยังคอมพิวเตอร์ควอนตัมในอนาคตที่ยังเป็นทฤษฎี

ในโมดูลนี้ เราจะสำรวจอัลกอริทึมของ Shor ก่อนอื่น เราจะให้บริบทเพิ่มเติมเล็กน้อยเกี่ยวกับอัลกอริทึม โดยทำให้ปัญหาที่มันแก้ชัดเจนขึ้นและอธิบายความเกี่ยวข้องกับความปลอดภัยทางไซเบอร์ ต่อไป เราจะให้พื้นฐานเบื้องต้นเกี่ยวกับคณิตศาสตร์มอดูลาร์และวิธีนำไปใช้กับปัญหาการแยกตัวประกอบ โดยแสดงให้เห็นว่าการแยกตัวประกอบลดรูปเป็นปัญหาอีกอย่างที่เรียกว่า "การหาอันดับ" เราจะแสดงให้เห็นว่า Quantum Fourier Transform และ Quantum Phase Estimation ที่เราเรียนรู้ในโมดูลก่อนหน้าเข้ามามีบทบาทอย่างไร และวิธีใช้เพื่อแก้ปัญหาการหาอันดับ

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

ปัญหาการแยกตัวประกอบ

เป้าหมายของปัญหาการแยกตัวประกอบคือการหาตัวประกอบเฉพาะของจำนวน $N$ สำหรับ $N$ บางจำนวน สิ่งนี้ค่อนข้างง่าย ตัวอย่างเช่น ถ้า $N$ เป็นเลขคู่ ตัวประกอบเฉพาะตัวหนึ่งจะเป็น 2 ถ้า $N$ เป็นกำลังของจำนวนเฉพาะ หมายความว่า $N=p^k$ สำหรับจำนวนเฉพาะ $p$ บางจำนวน การหา $p$ ก็ค่อนข้างง่ายเช่นกัน: เราแค่ประมาณรากที่ $k$ ของ $N$ และมองหาจำนวนเฉพาะใกล้เคียงที่อาจเป็น $p$

แต่คอมพิวเตอร์คลาสสิกติดขัดเมื่อ $N$ เป็นเลขคี่และ ไม่ใช่ กำลังของจำนวนเฉพาะ นี่คือกรณีที่อัลกอริทึมของ Shor จัดการ อัลกอริทึมหาตัวประกอบสองตัว $p$ และ $q$ โดยที่ $N=pq$ สามารถนำไปใช้แบบวนซ้ำจนกว่าตัวประกอบทั้งหมดจะเป็นจำนวนเฉพาะ ในส่วนถัดไปเราจะเห็นว่าปัญหานี้จัดการอย่างไร

ความเกี่ยวข้องกับความปลอดภัยทางไซเบอร์

มีรูปแบบการเข้ารหัสหลายอย่างที่สร้างขึ้นจากข้อเท็จจริงที่ว่าการแยกตัวประกอบของจำนวนขนาดใหญ่นั้นยาก รวมถึงหนึ่งที่ใช้กันทั่วไปในปัจจุบัน เรียกว่า RSA ใน RSA กุญแจสาธารณะถูกสร้างขึ้นโดยการคูณจำนวนเฉพาะขนาดใหญ่สองจำนวนเข้าด้วยกันเพื่อได้ $N = p\cdot q$ จากนั้น ทุกคนสามารถใช้กุญแจสาธารณะนี้เพื่อเข้ารหัสข้อมูล แต่เฉพาะผู้ที่มีกุญแจส่วนตัว $p$ และ $q$ เท่านั้นที่สามารถถอดรหัสข้อมูลนั้นได้

ถ้า $N$ แยกตัวประกอบได้ง่าย ทุกคนก็จะสามารถหาได้ว่า $p$ และ $q$ คืออะไรและทำลายการเข้ารหัส แต่มันไม่ใช่อย่างนั้น นี่เป็นปัญหาที่ยากมากอย่างเป็นที่รู้จัก อันที่จริง ตัวประกอบเฉพาะของจำนวนที่เรียกว่า RSA1024 ซึ่งมีความยาว 1024 ตัวเลขฐานสองและ 309 ตัวเลขฐานสิบ ยังไม่ถูกค้นพบ แม้จะมีการเสนอรางวัล $100,000 สำหรับการแยกตัวประกอบตั้งแต่ปี 1991

วิธีแก้ปัญหาของ Shor

ในปี 1994 Peter Shor ตระหนักว่าคอมพิวเตอร์ควอนตัมสามารถแยกตัวประกอบของจำนวนขนาดใหญ่ได้อย่างมีประสิทธิภาพมากกว่าคอมพิวเตอร์คลาสสิกแบบเอกซ์โปเนนเชียล ความคิดเชิงลึกของเขาอาศัยความสัมพันธ์ระหว่างปัญหาการแยกตัวประกอบนี้และ คณิตศาสตร์มอดูลาร์ เราจะผ่านบทเรียนสั้น ๆ เกี่ยวกับคณิตศาสตร์มอดูลาร์ จากนั้นเราจะเห็นว่าเราสามารถใช้สิ่งนี้ในการแยกตัวประกอบ $N$ ได้อย่างไร

คณิตศาสตร์มอดูลาร์

คณิตศาสตร์มอดูลาร์เป็นระบบการนับที่เป็นวงจร หมายความว่าในขณะที่การนับเริ่มต้นในแบบปกติ ด้วยจำนวนเต็ม 0, 1, 2 เป็นต้น ณ จุดใดจุดหนึ่ง หลังจากคาบ $N$ การนับจะเริ่มต้นใหม่ มาดูวิธีการทำงานด้วยตัวอย่าง สมมติว่าคาบของเราคือ 5 เมื่อเรานับถึง 5 แทนที่จะนับ 5 เราจะเริ่มต้นใหม่ที่ 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

นี่เป็นเพราะว่าในโลก "modulo-5" 5 เท่ากับ 0 เราบอกว่า $5\bmod 5 \ = 0$ อันที่จริง พหุคูณทั้งหมดของ 5 จะเท่ากับ $0\bmod 5$

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ จากนั้นคลิกสามเหลี่ยมเพื่อดูคำตอบ

ใช้คณิตศาสตร์มอดูลาร์เพื่อแก้ปัญหาต่อไปนี้:

คุณออกเดินทางบนรถไฟข้ามทวีประยะไกลในเวลา 8 AM รถไฟใช้เวลา 60 ชั่วโมง ตอนที่คุณถึงที่หมายจะเป็นเวลาเท่าไร?

คำตอบ:

คาบคือ 24 เนื่องจากมี 24 ชั่วโมงในหนึ่งวัน ดังนั้น ปัญหานี้สามารถเขียนในรูปคณิตศาสตร์มอดูลาร์ได้เป็น:

$(8+60)\text{mod}(24) = 20$

ดังนั้น คุณจะถึงปลายทางเวลา 20:00 หรือ 8 PM

$\mathbb{Z}_N$ และ $\mathbb{Z}_N^*$

มักมีประโยชน์ในการแนะนำสองเซต $\mathbb{Z}_N$ และ $\mathbb{Z}_N^*$ $\mathbb{Z}_N$ คือเซตของจำนวนที่มีอยู่ในโลก "modulo-$N$" ตัวอย่างเช่น เมื่อเรานับ modulo-5 เซตจะเป็น $\mathbb{Z}_5=\{0,1,2,3,4\}$ อีกตัวอย่าง: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$ เราสามารถทำการบวกและคูณ (modulo $N$) บนสมาชิกใน $\mathbb{Z}_N$ และผลลัพธ์ของแต่ละการดำเนินการก็เป็นสมาชิกใน $\mathbb{Z}_N$ เช่นกัน ทำให้ $\mathbb{Z}_N$ เป็นวัตถุทางคณิตศาสตร์ที่เรียกว่า ring

มีเซตย่อยพิเศษของ $\mathbb{Z}_N$ ที่น่าสนใจเป็นพิเศษสำหรับเราในอัลกอริทึมของ Shor นั่นคือเซตย่อยของจำนวนใน $\mathbb{Z}_N$ โดยที่ greatest common divisor ระหว่างสมาชิกแต่ละตัวและ $N$ คือ 1 ดังนั้นสมาชิกแต่ละตัวเป็น "co-prime" กับ $N$ ถ้าเรานำเซตตัวเลขเหล่านี้มาพร้อมกับการดำเนินการคูณแบบมอดูลาร์ มันก็จะก่อตัวเป็นวัตถุทางคณิตศาสตร์อีกอย่าง เรียกว่า group เราเรียก group นี้ว่า $\mathbb{Z}_N^*$ ปรากฎว่ากับ $\mathbb{Z}_N^*$ (และ finite groups โดยทั่วไป) ถ้าเราเลือกสมาชิกใด ๆ $a \in \mathbb{Z}_N^*$ และคูณ $a$ กับตัวมันเองซ้ำ ๆ เราจะได้จำนวน $1$ เสมอในที่สุด จำนวนครั้งขั้นต่ำที่ต้องคูณ $a$ กับตัวมันเองเพื่อให้ได้ $1$ เรียกว่า อันดับ ของ $a$ ข้อเท็จจริงนี้จะสำคัญมากในการอภิปรายของเราเกี่ยวกับวิธีแยกตัวประกอบจำนวนด้านล่าง

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ จากนั้นคลิกสามเหลี่ยมเพื่อดูคำตอบ

$\mathbb{Z}_{15}^*$ คืออะไร?

คำตอบ:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

เราไม่รวมจำนวนต่อไปนี้:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

อันดับของสมาชิกแต่ละตัวใน $\mathbb{Z}_{15}^*$ คืออะไร?

คำตอบ:

อันดับ $r$ คือจำนวนที่น้อยที่สุดโดยที่ $a^r\text{mod}(15)=1$ สำหรับสมาชิกแต่ละตัว $a$

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

โปรดทราบว่าแม้ว่าเราสามารถหาอันดับของจำนวนใน $\mathbb{Z}_{15}^*$ ได้ แต่นี่ไม่ใช่งานง่ายโดยทั่วไป สำหรับ $N$ ที่ใหญ่กว่า นี่คือหัวใจสำคัญของปัญหาการแยกตัวประกอบและเหตุผลที่เราต้องการคอมพิวเตอร์ควอนตัม เราจะเห็นว่าทำไมเมื่อเราทำงานผ่านส่วนที่เหลือของ notebook

นำคณิตศาสตร์มอดูลาร์ไปใช้กับปัญหาการแยกตัวประกอบ

กุญแจสำคัญในการหาตัวประกอบ $p$ และ $q$ โดยที่ $N=pq$ อยู่ที่การหาจำนวนเต็ม อื่น $x$ โดยที่

$x^2 \equiv 1 \bmod N$ และ $x \not\equiv \pm 1 \bmod N.$

การหา $x$ ช่วยหา $p$ และ $q$ ได้อย่างไร? มาผ่านการอ้างเหตุผลกัน เนื่องจาก $x^2 \equiv 1 \bmod N$ หมายความว่า $x^2 - 1 \equiv 0 \bmod N$ กล่าวอีกนัยหนึ่ง $x^2 - 1$ เป็นพหุคูณของ $N$ ดังนั้น สำหรับจำนวนเต็ม $l$ บางจำนวน

$x^2 - 1 = l N$

เราสามารถแยกตัวประกอบ $x^2 - 1$ เพื่อได้:

$(x+1)(x-1) = l N$

จากสมมติฐานเริ่มต้นของเรา เรารู้ว่า $x \not\equiv \pm 1 \bmod N$ ดังนั้น $N$ ไม่หารลงตัวพอดีสำหรับทั้ง $x+1$ หรือ $x-1$ ดังนั้น ตัวประกอบสองตัวของ $N$ คือ $p$ และ $q$ แต่ละตัวต้องหาร $x-1$ และ $x+1$ ได้ ไม่ว่าจะเป็น $p$ เป็นตัวประกอบของ $x-1$ และ $q$ เป็นตัวประกอบของ $x+1$ หรือในทางกลับกัน ดังนั้น ถ้าเราคำนวณ greatest common divisors (GCDs) ระหว่าง $N$ และทั้ง $x-1$ และ $x+1$ นั่นจะให้ $p$ และ $q$ แก่เรา การคำนวณ GCD ระหว่างตัวเลขสองจำนวนเป็นงานที่ง่ายสำหรับคลาสสิก ซึ่งสามารถทำได้ด้วย อัลกอริทึมของ Euclid เป็นต้น

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ จากนั้นคลิกสามเหลี่ยมเพื่อดูคำตอบ

อาจเป็นเรื่องยากที่จะเข้าใจแต่ละขั้นตอนของตรรกะข้างต้น ดังนั้นลองทำงานผ่านตัวอย่าง ใช้ $N=15$ และ $x=11$ ก่อนอื่น ตรวจสอบว่า $x^2 \equiv 1 \text{mod}(N)$ และ $x \not\equiv \pm 1 \bmod N$ จากนั้นดำเนินการตรวจสอบแต่ละขั้นตอน สุดท้าย คำนวณ $\text{GCD}(11\pm1,15)$ และตรวจสอบว่ามันเป็นตัวประกอบของ $15$

คำตอบ:

$11^2 = 121$ ซึ่งคือ $15*8 + 1$ ดังนั้น $11^2\bmod 15 = 1$ $\checkmark$

$11 - 1 = 10$ ซึ่งไม่เท่ากับ $0\bmod 15$ $\checkmark$

$11 + 1 = 12$ ซึ่งไม่เท่ากับ $0\bmod 15$ $\checkmark$

ตอนนี้ เรารู้ว่า $(x+1)(x-1) = l N$ สำหรับจำนวนเต็ม $l$ บางจำนวน ซึ่งตรวจสอบได้เมื่อเราแทนค่า $x$ และ $N$: $(12)(10) = l 15$ เมื่อ $l = 8$ $\checkmark$

ตอนนี้ เราต้องคำนวณ $\text{GCD}(12,15)$ และ $\text{GCD}(10,15)$

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

ดังนั้น เราพบตัวประกอบของ $15$ แล้ว!

อัลกอริทึม

ตอนนี้ที่เราเห็นว่าการหาจำนวนเต็ม $x$ โดยที่ $x^2 \equiv 1\bmod N$ ช่วยในการแยกตัวประกอบ $N$ ได้อย่างไร เราสามารถผ่านอัลกอริทึมของ Shor ได้ โดยพื้นฐานแล้วมันลดเหลือการหา $x$:

1. เลือกจำนวนเต็มแบบสุ่ม เลือกจำนวนเต็มแบบสุ่ม $a$ โดยที่ $1 < a < N$

• คำนวณ $\text{GCD}(a, N)$ แบบคลาสสิก
  • ถ้า $\text{GCD}(a, N) > 1$ คุณพบตัวประกอบแล้ว หยุด
  • ไม่เช่นนั้น ดำเนินต่อ

2. หาอันดับ $r$ ของ $a$ modulo $N$ หาจำนวนเต็มบวกที่น้อยที่สุด $r$ ที่ตอบสนอง $a^r \equiv 1 \pmod N$

3. ตรวจสอบว่าอันดับเป็นเลขคู่หรือไม่

• ถ้า $r$ เป็นเลขคี่ กลับไปขั้นตอนที่ 1 และเลือก $a$ ใหม่
• ถ้า $r$ เป็นเลขคู่ ดำเนินต่อขั้นตอนที่ 4

4. คำนวณ $x = a^{r/2} \bmod N$

• ตรวจสอบว่า $x \not\equiv 1 \pmod N$ และ $x \not\equiv -1 \pmod N$
  • ถ้า $x \equiv \pm 1 \pmod N$ กลับไปขั้นตอนที่ 1 และเลือก $a$ ใหม่
• ไม่เช่นนั้น คำนวณ gcds เพื่อดึงตัวประกอบ:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

สิ่งเหล่านี้จะเป็นตัวประกอบที่ไม่ตรงไปตรงมาของ $N$

5. แยกตัวประกอบซ้ำถ้าจำเป็น

• ถ้า $p$ และ/หรือ $q$ ไม่ใช่จำนวนเฉพาะ ใช้อัลกอริทึมซ้ำเพื่อแยกตัวประกอบให้สมบูรณ์
• เมื่อตัวประกอบทั้งหมดเป็นจำนวนเฉพาะ การแยกตัวประกอบเสร็จสมบูรณ์

จากขั้นตอนนี้ อาจไม่ชัดเจนว่าทำไมจึงต้องใช้คอมพิวเตอร์ควอนตัม เป็นเพราะขั้นตอนที่ 2 การหาอันดับของ $a$ modulo $N$ เป็นปัญหาที่ยากมากในเชิงคลาสสิก ความซับซ้อนเติบโตแบบเอกซ์โปเนนเชียลตามจำนวน $N$ แต่ด้วยคอมพิวเตอร์ควอนตัม เราแค่ต้องใช้ Quantum Phase Estimation เพื่อแก้มัน ขั้นตอนที่ 4 การหา GCD ของจำนวนสองจำนวน เป็นสิ่งที่ค่อนข้างง่ายในเชิงคลาสสิก ดังนั้น ขั้นตอนเดียวที่ต้องการพลังของคอมพิวเตอร์ควอนตัมจริง ๆ คือขั้นตอนการหาอันดับ เราบอกว่าปัญหาการแยกตัวประกอบ "ลดรูป" เป็นปัญหาการหาอันดับ

ส่วนที่ยาก: การหาอันดับ

ตอนนี้เราจะผ่านวิธีที่เราสามารถใช้คอมพิวเตอร์ควอนตัมในการหาอันดับ ก่อนอื่น มาทำให้ชัดเจนว่าหมายถึงอะไรโดย "อันดับ" แน่นอน ฉันได้บอกคุณแล้วว่าอันดับหมายความว่าอะไรทางคณิตศาสตร์: มันคือจำนวนเต็มบวกแรกที่ไม่ใช่ศูนย์ $r$ โดยที่ $a^r = 1 \pmod N$ แต่มาดูว่าเราสามารถเข้าใจแนวคิดนี้ได้มากขึ้นไหม

สำหรับ $N$ ที่เล็กพอ เราสามารถหาอันดับได้โดยการคำนวณกำลังแต่ละตัวของ $a$ นำ modulus $N$ ของตัวเลขนั้น จากนั้นหยุดเมื่อเราพบกำลัง $r$ ที่ตอบสนอง $a^r = 1 \text{mod}(N)$ นั่นคือสิ่งที่เราทำกับตัวอย่าง $N=15$ ข้างต้น มาดูกราฟบางส่วนของกำลังมอดูลาร์เหล่านี้สำหรับค่าตัวอย่างของ $a$ และ $N$:

สังเกตเห็นอะไรไหม? นี่เป็นฟังก์ชันเป็นคาบ! และอันดับ $r$ เท่ากับคาบ! ดังนั้น การหาอันดับเท่ากับการหาคาบ

คอมพิวเตอร์ควอนตัมเหมาะมากในการหาคาบของฟังก์ชัน สำหรับสิ่งนี้ เราสามารถใช้ subroutine อัลกอริทึมที่เรียกว่า Quantum Phase Estimation เราได้อภิปราย QPE และความสัมพันธ์กับ Quantum Fourier Transform ในโมดูลก่อนหน้า สำหรับการทบทวนโดยละเอียด ไปที่โมดูล QFT หรือบทเรียนของ John Watrous เกี่ยวกับ Quantum Phase Estimation ในคอร์ส Quantum Algorithms ของเขา เราจะผ่านแก่นของขั้นตอนตอนนี้:

ใน Quantum Phase Estimation (QPE) เราเริ่มต้นด้วยยูนิทารี $U$ และ eigenstate ของยูนิทารีนั้น $|\psi\rangle$ จากนั้น เราใช้ QPE เพื่อประมาณ eigenvalue ที่สอดคล้อง ซึ่งเนื่องจากตัวดำเนินการเป็นยูนิทารี จะอยู่ในรูป $e^{2\pi i \theta}$ ดังนั้น การหา eigenvalue เท่ากับการหาค่า $\theta$ ในฟังก์ชันเป็นคาบ Circuit มีลักษณะดังนี้:

ที่จำนวน control qubits (Qubit ควบคุม $m$ ตัวบนสุดในรูปด้านบน) กำหนดความแม่นยำของการประมาณ

ในอัลกอริทึมของ Shor เราใช้ QPE บนตัวดำเนินการยูนิทารี $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

ที่นี่ $|y\rangle$ หมายถึงสถานะฐาน computational ของรีจิสเตอร์ multi-qubit ที่ค่าไบนารีของ Qubit สอดคล้องกับจำนวนเต็ม $y$ ตัวอย่างเช่น ถ้า $N=15$ และ $y = 2$ แล้ว $|y\rangle$ จะแทนด้วยสถานะฐาน four-qubit $|0010\rangle$ เนื่องจากต้องใช้สี่ Qubit เพื่อเข้ารหัสจำนวนถึง 15 (ถ้าแนวคิดนี้ยังไม่คุ้นเคย ดู โมดูล Qiskit in classrooms เบื้องต้น สำหรับการทบทวนการเข้ารหัสไบนารีของสถานะควอนตัม)

ตอนนี้ เราต้องหา eigenstate ของยูนิทารีนี้ ถ้าเราเริ่มในสถานะ $|1\rangle$ เราสามารถเห็นว่าการใช้ $U$ แต่ละครั้งจะคูณสถานะของรีจิสเตอร์ด้วย $a \pmod N$ และหลังจาก $r$ ครั้งเราจะกลับมาที่สถานะ $|1\rangle$ อีกครั้ง ตัวอย่างเช่น $a = 3$ และ $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

ดังนั้น superpositions ของสถานะในวงจรนี้ ($|\psi_j\rangle$) ในรูปแบบ:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

ทั้งหมดเป็น eigenstates ของ $M_a$ (มี eigenstates มากกว่านี้ แต่เราสนใจเฉพาะที่อยู่ในรูปแบบข้างต้น)

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ จากนั้นคลิกสามเหลี่ยมเพื่อดูคำตอบ

หา eigenstate ของยูนิทารีที่สอดคล้องกับ $a=2$ และ $N = 15$

คำตอบ:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

ดังนั้น อันดับ $r=4$ Eigenstates ที่เราสนใจจะเป็น superposition เท่ากันของสถานะทั้งหมดที่วนซ้ำข้างต้น พร้อม phase ต่าง ๆ:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

สมมติว่าเราสามารถ initialize สถานะ Qubit ให้เป็น eigenstates เหล่านี้ตัวหนึ่งได้ (สปอยล์ — เราทำไม่ได้ หรืออย่างน้อยก็ไม่ง่าย เราจะอธิบายว่าทำไมและเราทำอะไรแทนได้ในไม่ช้า) จากนั้นเราสามารถใช้ QPE เพื่อประมาณ eigenvalue ที่สอดคล้อง $\omega_j = e^{2 \pi i \theta_j}$ ที่ $\theta_j = \frac{j}{r}$ จากนั้น เราจะสามารถหาอันดับ $r$ ได้จากสมการง่าย ๆ:

$r = \frac{j}{\theta_j}.$

แต่จำไว้ว่า ฉันบอกว่า QPE ประมาณ $\theta_j$ — ไม่ได้ให้ค่าที่แน่นอน เราต้องการการประมาณที่ดีพอที่จะแยกแยะระหว่าง $r$ และ $r+1$ ยิ่งมี control qubits $m$ มาก การประมาณก็จะดียิ่งขึ้น ในปัญหาท้ายบทเรียน คุณจะถูกขอให้หา $m$ ขั้นต่ำที่ต้องการในการแยกตัวประกอบจำนวน $N$

ตอนนี้ เราต้องแก้ไขปัญหาหนึ่ง คำอธิบายทั้งหมดข้างต้นเกี่ยวกับวิธีหา $r$ เริ่มต้นด้วยการเตรียม eigenstate $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$ แต่เราไม่รู้วิธีทำสิ่งนั้นโดยไม่รู้ $r$ อยู่แล้ว ตรรกะเป็นวงกลม เราต้องการวิธีประมาณ eigenvalue โดยไม่ initialize eigenstate

แทนที่จะเริ่มด้วย eigenstate ของ $M_a$ เราสามารถเตรียม initial state ให้เป็นสถานะ $n$-qubit ที่สอดคล้องกับ $|1\rangle$ ในรูปไบนารี (นั่นคือ $|000...01\rangle$) แม้ว่าสถานะนี้เองไม่ใช่ eigenstate ของ $M_a$ อย่างชัดเจน แต่มันเป็น superposition ของ eigenstates ทั้งหมด $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ จากนั้นคลิกสามเหลี่ยมเพื่อดูคำตอบ

ตรวจสอบว่า $|1\rangle$ เท่ากับ superposition ของ eigenstates ที่คุณหาสำหรับ $N=15$ และ $a=2$ ในคำถามตรวจสอบก่อนหน้า

คำตอบ:

eigenstates ทั้งสี่คือ:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

ดังนั้น

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

สิ่งนี้ช่วยให้เราหาอันดับ $r$ ได้อย่างไร? เนื่องจาก initial state เป็น superposition ของ eigenstates ทั้งหมดในรูปแบบที่ระบุข้างต้น อัลกอริทึม QPE จะประมาณ $\theta_k$ แต่ละตัวที่สอดคล้องกับ eigenstates เหล่านี้พร้อมกัน ดังนั้น การวัด control qubits $m$ ตัวในตอนท้ายจะให้การประมาณค่า $k/r$ ที่ $k \in \{0,1,2,...,r-1\}$ เป็น eigenvalue ที่เลือกแบบสุ่มในแต่ละครั้ง ถ้าเราทำซ้ำ Circuit นี้สองสามครั้งและได้ตัวอย่างสองสามตัวที่มีค่า $k$ ต่างกัน เราจะสามารถหา $r$ ได้อย่างรวดเร็ว

ใช้งานใน Qiskit

ตามที่เราได้กล่าวไว้ก่อนหน้า ฮาร์ดแวร์ของเราไม่ถึงจุดที่เราจะแยกตัวประกอบจำนวนขนาดใหญ่อย่าง RSA1024 ได้ เราจะแยกตัวประกอบจำนวนขนาดเล็กเพื่อแสดงให้เห็นว่าอัลกอริทึมทำงานอย่างไร สำหรับการสาธิตนี้ เราจะใช้เวอร์ชันที่ง่ายกว่าของโค้ดที่นำเสนอใน บทแนะนำอัลกอริทึมของ Shor ถ้าต้องการรายละเอียดเพิ่มเติม โปรดไปที่บทแนะนำ

เราจะรันอัลกอริทึมโดยใช้กรอบการทำงานมาตรฐานของเราสำหรับการแก้ปัญหาควอนตัม เรียกว่ากรอบการทำงาน Qiskit patterns ประกอบด้วยสี่ขั้นตอน:

1. แมปปัญหาของคุณไปยัง Circuit ควอนตัม
2. ปรับ Circuit ให้เหมาะสมสำหรับรันบนฮาร์ดแวร์ควอนตัม
3. รัน Circuit บนคอมพิวเตอร์ควอนตัม
4. ประมวลผลการวัดหลังการทดลอง

1. แมป

มาแยกตัวประกอบ $N=15$ โดยเลือก $a=2$ เป็นจำนวนเต็ม co-prime ของเรา

ก่อนอื่น เราต้องสร้าง Circuit ที่จะใช้งานยูนิทารีการคูณแบบมอดูลาร์ $M_a$ นี่คือส่วนที่ยุ่งยากที่สุดของการใช้งานทั้งหมด และอาจมีค่าใช้จ่ายในการคำนวณสูงมาก ขึ้นอยู่กับวิธีการ สำหรับสิ่งนี้ เราจะโกงนิดหน่อย: เรารู้ว่าเราเริ่มต้นในสถานะ $|1\rangle$ และจากคำถามตรวจสอบก่อนหน้า

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

ดังนั้น เราจะสร้างยูนิทารีที่ทำการดำเนินการที่ถูกต้องกับสี่สถานะนี้ แต่ปล่อยให้สถานะอื่นทั้งหมดไม่เปลี่ยนแปลง นี่คือการโกงเพราะเราใช้ความรู้เกี่ยวกับอันดับของ $2\bmod 15$ เพื่อทำให้ยูนิทารีเรียบง่าย ถ้าเราพยายามแยกตัวประกอบจำนวนที่ตัวประกอบของมันไม่รู้จักจริง ๆ เราจะทำสิ่งนี้ไม่ได้

ตรวจสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดคำตอบของคุณ จากนั้นคลิกสามเหลี่ยมเพื่อดูคำตอบ

ด้วยความรู้ของคุณเกี่ยวกับวิธีที่ตัวดำเนินการ $M_2$ แปลงสถานะข้างต้น สร้างตัวดำเนินการจากชุด SWAP gates ที่สลับสถานะของ Qubit สองตัว (คำใบ้: การเขียนสถานะแต่ละตัว $|i\rangle$ ในรูปไบนารีจะช่วยได้)

คำตอบ:

มาเขียนการกระทำของ $M_2$ บนสถานะในรูปไบนารีใหม่:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

การกระทำแต่ละอย่างสามารถทำได้ด้วย SWAP ง่าย ๆ $M_2|0001\rangle$ ทำได้โดยการสลับสถานะของ Qubit $0$ และ $1$ $M_2|0010\rangle$ ทำได้โดยการสลับสถานะของ Qubit $1$ และ $2$ และต่อไป ดังนั้น เราสามารถแยกย่อยเมทริกซ์ $M_2$ เป็นชุด SWAP gates ต่อไปนี้:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

จำไว้ว่าตัวดำเนินการกระทำจากขวาไปซ้าย มาตรวจสอบว่ามันมีผลที่ต้องการกับสถานะแต่ละตัว:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

ตอนนี้เราสามารถเขียนโค้ด Circuit ที่เทียบเท่ากับตัวดำเนินการนี้ใน Qiskit ได้

ก่อนอื่น เรา import แพ็คเกจที่จำเป็น:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

จากนั้น เราสร้างตัวดำเนินการ $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

อัลกอริทึม QPE ใช้ controlled-$U$ gate ดังนั้น ตอนนี้ที่เรามี Circuit $M_2$ แล้ว เราต้องทำให้มันเป็น Circuit controlled-$M_2$:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

ตอนนี้เรามี controlled-$U$ gate แล้ว แต่เพื่อรันอัลกอริทึม Quantum Phase Estimation เราจะต้องมี controlled-$U^2$, controlled-$U^4$, ขึ้นไปถึง controlled-$U^{2^{m-1}}$ ที่ $m$ คือจำนวน Qubit ที่ใช้ประมาณ phase ยิ่งมี Qubit มาก การประมาณ phase ก็ยิ่งแม่นยำ เราจะใช้ $m=8$ control qubits สำหรับขั้นตอน phase estimation ของเรา ดังนั้น เราต้องการ:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

ที่ดัชนี $k$ ด้วย $0 \le k \le m-1 = 7$ สอดคล้องกับ control qubit ตอนนี้มาคำนวณ $a^{2^k}\bmod N$ สำหรับแต่ละค่าของ $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

เนื่องจาก $a^{2^k} \bmod N = 1$ สำหรับ $k \ge 2$ ตัวดำเนินการทั้งหมดที่สอดคล้อง ($M_8$ ขึ้นไป) เท่ากับ identity ดังนั้น เราต้องสร้างเมทริกซ์อีกตัวหนึ่งเท่านั้น คือ $M_4$

หมายเหตุ: การทำให้เรียบง่ายนี้ใช้ได้ที่นี่เพราะอันดับของ $2 \bmod 15$ คือ $4$ เมื่อ $k=2$ (ดังนั้น $2^k = 4$) ทุกกำลังที่ตามมาของตัวดำเนินการจะเป็น identity โดยทั่วไป สำหรับ $N$ ที่ใหญ่กว่าหรือการเลือก $a$ ที่แตกต่าง คุณไม่สามารถข้ามการสร้างกำลังที่สูงกว่าได้ นี่คือเหตุผลหนึ่งที่ถือว่านี่เป็น ตัวอย่างทดสอบ: จำนวนขนาดเล็กช่วยให้มีทางลัดที่ไม่ได้ผลสำหรับกรณีที่ใหญ่กว่า

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

และเหมือนเดิม เราทำให้มันเป็นตัวดำเนินการ controlled-$M_4$:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

ตอนนี้ เราสามารถรวมทุกอย่างเข้าด้วยกันเพื่อหาอันดับของ $2\bmod 15$ ด้วย Circuit ควอนตัม โดยใช้ phase estimation:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. ปรับให้เหมาะสม

ตอนนี้ที่เราแมป Circuit ของเราแล้ว ขั้นตอนถัดไปคือการปรับให้เหมาะสมสำหรับรันบนคอมพิวเตอร์ควอนตัมเฉพาะ ก่อนอื่นเราต้องโหลด Backend

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

ถ้าคุณไม่มีเวลาเหลืออยู่ในบัญชีหรือต้องการใช้ simulator ด้วยเหตุผลใดก็ตาม คุณสามารถรัน cell ด้านล่างเพื่อตั้งค่า simulator ที่จะจำลองอุปกรณ์ควอนตัมที่เราเลือกข้างต้น:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. รัน

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

เราเห็นยอดสี่ยอดที่ชัดเจนที่ 00000000, 01000000, 10000000, และ 11000000 พร้อมกับ count บางส่วนในสตริงบิตอื่นเนื่องจากสัญญาณรบกวนในคอมพิวเตอร์ควอนตัม เราจะละเลยสิ่งเหล่านี้และเก็บเฉพาะสี่ตัวหลักโดยกำหนด threshold: เฉพาะ count ที่สูงกว่า threshold นี้เท่านั้นที่ถือว่าเป็นสัญญาณจริงที่อยู่เหนือสัญญาณรบกวน

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. ประมวลผลหลังการทดลอง

สำหรับอัลกอริทึมของ Shor อัลกอริทึมส่วนใหญ่จะทำในเชิงคลาสสิก ดังนั้น เราจะใส่ส่วนที่เหลือลงในขั้นตอน "ประมวลผลหลังการทดลอง" หลังจากที่เราได้รับการวัดจากคอมพิวเตอร์ควอนตัม การวัดแต่ละตัวข้างต้นสามารถแปลงเป็นจำนวนเต็มได้ ซึ่งหลังจากหารด้วย $2^m$ แล้ว จะเป็นการประมาณของ $\frac{k}{r}$ ที่ $k$ เป็นตัวสุ่มในแต่ละครั้ง

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

บทสรุป

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

ในขณะที่เรายังห่างไกลจากการใช้อัลกอริทึมนี้ในการแยกตัวประกอบจำนวนอย่าง RSA1024 คอมพิวเตอร์ควอนตัมของเราดีขึ้นทุกวัน และเมื่อถึงขีดจำกัดที่เรียกว่า fault tolerance อัลกอริทึมเช่นนี้จะตามมาในไม่ช้า นี่เป็นเวลาที่น่าตื่นเต้นมากที่จะเรียนรู้เกี่ยวกับการคอมพิวเตอร์ควอนตัม!

ปัญหา

แนวคิดหลัก:

• ระบบการเข้ารหัสสมัยใหม่อาศัยความยากในเชิงคลาสสิกของการแยกตัวประกอบจำนวนเต็มขนาดใหญ่
• คณิตศาสตร์มอดูลาร์ — รวมถึงโครงสร้าง $\mathbb{Z}_N$ และ $\mathbb{Z}_N^*$ — ให้รากฐานทางคณิตศาสตร์สำหรับอัลกอริทึมของ Shor
• ปัญหาการแยกตัวประกอบจำนวนเต็ม $N$ สามารถลดรูปเป็นปัญหาการหาอันดับของจำนวน modulo $N$
• การหาอันดับด้วยควอนตัมใช้เทคนิค quantum phase estimation เพื่อหาคาบของฟังก์ชัน $a^x \mod N$
• อัลกอริทึมของ Shor ประกอบด้วยขั้นตอนการทำงานแบบ classical–quantum hybrid ที่เลือกฐาน ทำ quantum order finding จากนั้นคำนวณตัวประกอบจากผลลัพธ์ในเชิงคลาสสิก

จริง/เท็จ:

1. จ/ผ ประสิทธิภาพของอัลกอริทึมของ Shor คุกคามความปลอดภัยของการเข้ารหัส RSA
2. จ/ผ อัลกอริทึมของ Shor สามารถรันได้อย่างมีประสิทธิภาพบนคอมพิวเตอร์ควอนตัมสมัยใหม่ใด ๆ
3. จ/ผ อัลกอริทึมของ Shor ใช้ quantum phase estimation (QPE) เป็น subroutine หลัก
4. จ/ผ ส่วนคลาสสิกของอัลกอริทึมของ Shor เกี่ยวข้องกับการคำนวณ greatest common divisor (GCD)
5. จ/ผ อัลกอริทึมของ Shor ใช้ได้เฉพาะสำหรับการแยกตัวประกอบของเลขคู่เท่านั้น
6. จ/ผ การรันอัลกอริทึมของ Shor ที่ประสบความสำเร็จรับประกันตัวประกอบที่ถูกต้องเสมอ

คำถามตอบสั้น:

1. ทำไมอัลกอริทึมของ Shor จึงถือว่าเป็นภัยคุกคามในอนาคตต่อการเข้ารหัส RSA?
2. ทำไมการหาคาบหรืออันดับของฟังก์ชัน modular exponential จึงมีประโยชน์ในการแยกตัวประกอบจำนวนในอัลกอริทึมของ Shor?

ปัญหาท้าทาย:

1. เราต้องการ control qubits $m$ จำนวนเท่าใดสำหรับจำนวน $N$ ที่กำหนดที่เราพยายามจะแยกตัวประกอบ เพื่อให้ได้ความแม่นยำใน QPE ที่จำเป็นในการหาค่าที่ถูกต้องของอันดับ $r$?

2. โดยปฏิบัติตามขั้นตอนที่เราอธิบายที่นี่สำหรับการแยกตัวประกอบ 15 ตอนนี้ลองแยกตัวประกอบ 21