QAOA ระดับ utility scale

ดูวิดีโอเกี่ยวกับ QAOA ระดับ utility scale จาก Olivia Lanes หรือเปิดวิดีโอในหน้าต่างแยกบน YouTube.

ภาพรวมบทเรียน:

จนถึงตอนนี้ในคอร์สนี้ เราหวังว่าเราให้รากฐานที่มั่นคงของกรอบงานและเครื่องมือที่จำเป็นในการแก้ปัญหา utility-scale บนคอมพิวเตอร์ควอนตัม ตอนนี้ เราจะได้เห็นเครื่องมือเหล่านี้ในการทำงานในที่สุด

ในบทเรียนนี้ เราจะลงมือกับตัวอย่าง utility-scale ของปัญหา Max-Cut ซึ่งเป็นปัญหาที่มีชื่อเสียงในทฤษฎีกราฟเกี่ยวกับวิธีแบ่งกราฟออกเป็นสองส่วนอย่างเหมาะสมที่สุด เราจะเริ่มด้วยกราฟ 5 node ง่าย ๆ เพื่อสร้างสัญชาตญาณว่าคอมพิวเตอร์ควอนตัมช่วยเราแก้ปัญหาได้อย่างไร จากนั้นนำไปใช้กับเวอร์ชัน utility-scale ของปัญหา

บทเรียนนี้จะเป็นภาพรวมกว้าง ๆ ของวิธีการที่เราใช้แก้ปัญหานี้ ไม่ใช่การแนะนำ code สำหรับบทเรียนนี้ มีtutorial พร้อม code จริงที่คุณสามารถรันเพื่อแก้ปัญหา Max-Cut บนคอมพิวเตอร์ควอนตัม

ปัญหา

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

สาม use case ที่เราเชื่อมั่นมากที่สุดในการสำรวจคือ:

1. การจำลองธรรมชาติ
2. การประมวลผลข้อมูลที่มีโครงสร้างซับซ้อน
3. การปรับให้เหมาะสม

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

ปัญหาการปรับให้เหมาะสมที่น่าสนใจในวันนี้เรียกว่า Max-Cut ซึ่งเราจะแก้โดยใช้อัลกอริทึมที่เรียกว่า Quantum Approximate Optimization Algorithm (QAOA)

Max-Cut คืออะไร?

เราเริ่มต้นด้วยกราฟ ซึ่งประกอบด้วยชุดของ vertex (หรือ node) บางส่วนเชื่อมต่อด้วย edge ในปัญหานี้ เราถูกถามให้แบ่ง node ของกราฟออกเป็นสอง subset โดย "ตัด" edge ที่เชื่อมต่อพวกมัน เราต้องการหา partition ที่สูงสุดจำนวน edge ที่ถูกตัดในลักษณะนี้ ด้วยเหตุนี้จึงชื่อ "Max-Cut"

ตัวอย่างเช่น รูปด้านบนแสดงกราฟ 5 node พร้อมโซลูชัน Max-cut ทางขวา มันตัดผ่าน 5 edge ซึ่งเป็นดีที่สุดเท่าที่ทำได้กับกราฟนี้

เพราะกราฟ 5 node มีขนาดเล็กมาก จึงไม่ยากนักที่จะหา Max-Cut ในหัวหรือโดยการลอง cut สองสามครั้งบนกระดาษ แต่คุณอาจจินตนาการได้ว่าปัญหาจะยากขึ้นเรื่อย ๆ เมื่อจำนวน vertex เพิ่มขึ้น ส่วนหนึ่งเพราะจำนวน cut ที่เป็นไปได้ที่ต้องพิจารณาเพิ่มขึ้นแบบเลขชี้กำลังในจำนวน node และที่จุดหนึ่ง สิ่งนี้กลายเป็นยากแม้แต่สำหรับ supercomputer ด้วยอัลกอริทึมคลาสสิกที่รู้จัก

เราต้องการวิธีแก้ปัญหา Max-Cut สำหรับกราฟที่ใหญ่กว่าและซับซ้อนกว่าเหล่านี้ เพราะปัญหามีการประยุกต์ใช้จริงมากมาย รวมถึงการตรวจจับการฉ้อโกงในด้านการเงิน graph clustering การออกแบบเครือข่าย และการวิเคราะห์โซเชียลมีเดีย Max-Cut มักพบเป็น subproblem ภายในวิธีการเฉพาะต่อปัญหาขนาดใหญ่ ดังนั้นจึงพบบ่อยกว่าที่เราอาจคิดในเบื้องต้น

โซลูชัน

ตอนนี้ เราจะผ่านวิธีการที่เราใช้แก้ปัญหา Max-Cut บนคอมพิวเตอร์ควอนตัม เราจะทำสิ่งนี้กับกราฟ 5 node ง่าย ๆ คุณสามารถทำตามโดยใช้ python notebook tutorial หลังจากตัวอย่างง่ายนั้น tutorial จะแนะนำคุณผ่านตัวอย่าง utility-scale ของปัญหา

ขั้นตอนแรกคือการสร้างกราฟของเราโดยกำหนดจำนวน node และ edge ที่เชื่อมต่อ node สอง node คุณสามารถทำสิ่งนี้โดยการ import package ที่เรียกว่า rustworkx ดังที่แสดงใน tutorial ผลลัพธ์จะเป็นกราฟที่มีลักษณะเช่นนี้:

เราจะใช้กรอบงาน Qiskit patterns เพื่อหาโซลูชัน Max-Cut สำหรับกราฟนี้บนคอมพิวเตอร์ควอนตัมของเรา

Map

เราต้อง map ปัญหาสู่คอมพิวเตอร์ควอนตัมของเรา เพื่อทำสิ่งนี้ ขอสังเกตก่อนว่าการสูงสุดจำนวนการตัดในกราฟสามารถเขียนทางคณิตศาสตร์เป็น:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

โดยที่ $i$ และ $j$ คือ node ในกราฟ และ $x_i$ และ $x_j$ เป็น 0 หรือ 1 ขึ้นอยู่กับว่า node แต่ละตัวอยู่ฝั่งใดของ partition (กลุ่มหนึ่งติดฉลาก "0" และอีกกลุ่มหนึ่งติดฉลาก "1") เมื่อ $x_i$ และ $x_j$ อยู่ฝั่งเดียวกันของ partition นิพจน์ในผลรวมเท่ากับศูนย์ เมื่ออยู่คนละฝั่ง ดังนั้นมีการตัดระหว่างพวกมัน นิพจน์เท่ากับหนึ่ง ดังนั้นการสูงสุดจำนวนการตัดจะสูงสุดผลรวม

เรายังสามารถพลิกสิ่งนี้และค้นหาค่าต่ำสุดโดยการคูณค่าแต่ละตัวด้วยลบหนึ่ง

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

ตอนนี้เราพร้อมที่จะ map แล้ว อาจเป็นเรื่องที่น่ากลัวเล็กน้อยที่จะคิดถึงวิธีไปจากกราฟที่เราเพิ่งวาดสู่ quantum circuit แต่เราจะทำทีละขั้นตอน

จำไว้ว่า เราจะพยายามแก้ Max-Cut โดยใช้ QAOA ในวิธีการ QAOA ในที่สุดเราต้องการ operator (หรืออีกนัยหนึ่ง Hamiltonian) ที่จะใช้แสดง cost function ของ hybrid algorithm รวมถึง parametrized circuit (ansatz) ที่เราใช้แสดงโซลูชันที่เป็นไปได้สำหรับปัญหา

QUBO

เราสามารถสุ่มตัวอย่างจาก candidate solution เหล่านี้และประเมินพวกมันโดยใช้ cost function เพื่อทำสิ่งนี้ เราใช้ประโยชน์จากชุดของการกำหนดสูตรใหม่ทางคณิตศาสตร์ รวมถึงสัญกรณ์ Quadratic Unconstrained Binary Optimization หรือ QUBO สั้น ๆ ซึ่งเป็นวิธีที่มีประโยชน์ในการเข้ารหัสปัญหา combinatorial optimization ใน QUBO เราต้องการหา:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

โดยที่ $Q$ เป็น matrix $n\times n$ ของจำนวนจริง $n$ สอดคล้องกับจำนวน node ในกราฟของเรา ที่นี่คือ 5

เพื่อใช้ QAOA เราต้องกำหนดสูตรปัญหาของเราเป็น Hamiltonian ซึ่งเป็นฟังก์ชันหรือ matrix ที่แสดงถึงพลังงานรวมของระบบ โดยเฉพาะ เราต้องการสร้าง cost function Hamiltonian ที่มีคุณสมบัติว่า ground state สอดคล้องกับค่าต่ำสุดของฟังก์ชัน ดังนั้น เพื่อแก้ปัญหาการปรับให้เหมาะสมของเรา เราจะพยายามเตรียม ground state ของ $H$ บนคอมพิวเตอร์ควอนตัม จากนั้นการสุ่มตัวอย่างจากสถานะนี้จะให้โซลูชันสำหรับ $\min 𝑓(𝑥)$ ด้วยความน่าจะเป็นสูง

การ Mapping สู่ cost function Hamiltonian

ปรากฏว่า เราโชคดี เพราะปัญหา QUBO เกี่ยวข้องอย่างมากและจริง ๆ แล้วเทียบเท่าทางการคำนวณกับ Hamiltonian ที่มีชื่อเสียงและแพร่หลายที่สุดตัวหนึ่งในฟิสิกส์: Ising Hamiltonian

เพื่อเขียนปัญหา QUBO เป็น Ising Hamiltonian สิ่งที่เราต้องทำคือเปลี่ยนตัวแปรง่าย ๆ:

$$x_i = \frac{1-z_i}{2}.$$

เราจะไม่ผ่านขั้นตอนทั้งหมดที่นี่ แต่มีการอธิบายใน notebook ที่แนบ ในที่สุด การหาค่าต่ำสุดของนิพจน์ QUBO เหมือนกับการหาค่าต่ำสุดของนิพจน์นี้:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

เขียนใหม่เล็กน้อยและเรามี cost function Hamiltonian ที่ค่าต่ำสุดของนิพจน์แสดงถึง ground state Z คือ Pauli Z operator และ $b$ คือ real scalar coefficient:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

ตอนนี้ที่เรามี Hamiltonian แล้ว เราต้องเขียนมันใหม่ในแง่ของ two-local Pauli ZZ operator ที่เราสามารถแปลงได้ง่ายเป็น two-qubit Gate ใน quantum circuit ของเรา เราจะได้รับออบเจ็กต์หกตัว หรือ Pauli string โดยแต่ละตัวสอดคล้องกับแต่ละ edge หกตัวในกราฟ องค์ประกอบทั้ง 5 ในสตริงแต่ละตัวแสดงถึงการดำเนินการบน node ซึ่งเป็น identity ถ้า node ไม่เชื่อมต่อกับ edge เฉพาะนั้น และ Pauli Z operator ถ้าเชื่อมต่อ ใน Qiskit bitstring ที่แสดง Qubit ถูก index ย้อนกลับ ตัวอย่างเช่น edge ระหว่าง node 0 และ 1 ถูกเข้ารหัสเป็น IIIZZ และ edge ระหว่าง 2 และ 4 ถูกเข้ารหัสเป็น ZIZII

สร้าง quantum circuit

ด้วย Hamiltonian ที่เขียนในแง่ของ Pauli operator เราพร้อมที่จะสร้าง quantum circuit ซึ่งช่วยให้เราสุ่มตัวอย่างโซลูชันที่ดีโดยใช้คอมพิวเตอร์ควอนตัม:

อัลกอริทึม QAOA ได้รับแรงบันดาลใจจาก Adiabatic Theorem ซึ่งระบุว่าหากเราเริ่มใน ground state ของ time-dependent Hamiltonian หาก Hamiltonian วิวัฒนาการช้าพอ และให้เวลาเพียงพอ สถานะสุดท้ายจะเป็น ground state ของ Hamiltonian สุดท้าย QAOA สามารถคิดได้ว่าเป็นเวอร์ชัน discrete, trotterized ของ Quantum Adiabatic Algorithm ที่แต่ละ trotter step แสดงถึง layer ของอัลกอริทึม QAOA แทนที่จะวิวัฒนาการจากสถานะหนึ่งไปอีกสถานะ ในแต่ละ layer เราจะสลับไปมาระหว่าง cost function Hamiltonian และ "mixer" Hamiltonian ที่เรียกว่า ซึ่งเราจะครอบคลุมในบทเรียนนี้ในภายหลัง

ข้อดีของ QAOA คือเร็วกว่า quantum adiabatic algorithm แต่คืนโซลูชันโดยประมาณแทนที่จะเป็นผลที่เหมาะสมที่สุด ในขีดจำกัดที่จำนวน layer ไปถึงอนันต์ QAOA บรรจบสู่กรณี QAA แต่แน่นอนสิ่งนี้มีค่าใช้จ่ายในการคำนวณสูงมาก

เพื่อสร้าง quantum circuit ของเรา เราจะใช้ alternating operator ที่พารามิเตอร์โดย $\gamma$ และ $\beta$ ซึ่งจะแสดงถึง discretization ของการวิวัฒนาการตามเวลา

ดังนั้น สามส่วนหลักของ QAOA circuit คือ:

1. initial trial state สีเทา ซึ่งเป็น ground state ของ mixer ที่สร้างโดยการใช้ Hadamard Gate กับทุก Qubit
2. cost function evolution ที่เราได้พูดถึงก่อนหน้านี้ สีม่วงเข้ม
3. การวิวัฒนาการภายใต้ mixer Hamiltonian ที่เรายังไม่ได้ครอบคลุม สีม่วงอ่อน

Hamiltonian เริ่มต้นของเราเรียกว่า Mixer เพราะ ground state ของมันคือ superposition ของ bitstring ที่เป็นไปได้ทั้งหมดที่น่าสนใจ: ด้วยเหตุนี้จึงบังคับส่วนผสมของโซลูชันที่เป็นไปได้ทั้งหมดตั้งแต่แรก

Mixer Hamiltonian คือผลรวมง่าย ๆ ของการดำเนินการ Pauli-X บนแต่ละ node ของกราฟ Qiskit ช่วยให้คุณใช้ mixer operator ที่กำหนดเองที่แตกต่างได้หากต้องการ แต่เราจะใช้อันมาตรฐานที่นี่ อีกครั้ง คุณสามารถเห็นว่าด้วย Qiskit งานจำนวนมากถูกนำออกไปสำหรับเรา ทำให้การหา mixer Hamiltonian และ starting state เป็นเรื่องเล็กน้อย งานเดียวที่เราต้องทำคือการหา cost function

แต่ละ iteration ของ operator เหล่านี้เรียกว่า layer layer เหล่านี้สามารถมองได้เป็น discretization ของการวิวัฒนาการตามเวลาของระบบดังที่อธิบายไว้ก่อนหน้า รูปแบบสลับกันมาจาก trotter decomposition และประมาณฟังก์ชัน exponential ของ matrix ที่ไม่ commute โดยทั่วไป ยิ่งเรารวม layer หรือ step มากขึ้น เราจะยิ่งใกล้เคียงกับการวิวัฒนาการตามเวลาต่อเนื่อง เหมือนใน QAA ดังนั้นในทางทฤษฎี ผลลัพธ์จะยิ่งแม่นยำมากขึ้น แต่สำหรับตัวอย่างนี้ เราจะเริ่มด้วยการสุ่มตัวอย่างเพียง layer เดียว จำไว้ว่า ทั้ง cost function Hamiltonian และ mixer มีพารามิเตอร์ เรายังต้องหาค่าที่เหมาะสมสำหรับ $\gamma$ และ $\beta$

Optimize

แม้ว่า circuit ที่เราเพิ่งสร้างดูค่อนข้างง่ายและมีประโยชน์ในการสร้างความเข้าใจเชิงสัญชาตญาณ แต่จำไว้ว่า quantum chip ไม่เข้าใจว่า QAOA Gate คืออะไร เราต้องแปลงสิ่งนี้เป็นชุดของ single- และ two-qubit "native" Gate ที่สามารถดำเนินการได้โดยตรงบนฮาร์ดแวร์ Native Gate คือ Gate ที่สามารถดำเนินการได้โดยตรงบน Qubit Circuit ดังกล่าวถือว่าเขียนใน Instruction Set Architecture (ISA) ของ backend

ไลบรารี Qiskit มีชุดของ transpilation pass ที่รองรับ circuit transformation หลากหลาย เราต้องการให้แน่ใจว่า circuit ได้รับการปรับให้เหมาะสมสำหรับวัตถุประสงค์ของเรา

ระลึกจากบทเรียนก่อนหน้าของเราว่ากระบวนการ transpilation เกี่ยวข้องกับขั้นตอนหลายอย่าง:

• การ mapping เริ่มต้นของ Qubit ใน circuit (กล่าวคือ decision variable) สู่ physical Qubit บนอุปกรณ์
• การ unroll ของ instruction ใน quantum circuit เป็น hardware native instruction ที่ backend เข้าใจ
• การ routing ของ Qubit ใน circuit ที่มีปฏิกิริยากันสู่ physical Qubit ที่อยู่ติดกัน

และดังเช่นเคย รายละเอียดเพิ่มเติมเกี่ยวกับสิ่งนี้สามารถพบได้ในเอกสาร

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

ส่ง backend ที่คุณเลือกผ่านฟังก์ชัน transpiler และระบุ optimization level ใน tutorial คุณจะเลือก level 3 ซึ่งเป็น level สูงสุดและละเอียดถี่ถ้วนที่สุด

และด้วยสิ่งนั้น เรามี transpiled circuit ที่พร้อมจะรันบนฮาร์ดแวร์!

Execute

จนถึงตอนนี้ เรา transpile circuit โดยปล่อย parameter gamma และ beta ไว้คนเดียว แต่เราไม่สามารถรัน circuit โดยไม่ระบุพารามิเตอร์เหล่านี้ได้จริง ๆ ในขั้นตอนการทำงาน QAOA parameter QAOA ที่เหมาะสมถูกพบใน iterative optimization loop ที่เรารันชุดของการประเมิน circuit แล้วใช้ classical optimizer เพื่อหาพารามิเตอร์ $\beta$ และ $\gamma$ ที่เหมาะสม อย่างไรก็ตาม เราต้องเริ่มที่ไหนสักแห่ง ดังนั้นเราทำการเดาเริ่มต้น $\gamma=\pi/2$ และ $\beta=\pi$

Execution Mode

ตอนนี้ เราเกือบพร้อมที่จะรัน circuit แล้ว แต่ก่อนอื่น สำคัญที่จะสังเกตว่าคุณสามารถส่ง job ได้หลายวิธีซึ่งเรียกว่า execution mode

• Job mode: การร้องขอ primitive เดียวของ Estimator หรือ Sampler โดยไม่มี context manager Circuit และ input ถูกบรรจุเป็น primitive unified bloc (PUB) และส่งเป็น execution task บนคอมพิวเตอร์ควอนตัม

• Batch mode: multi-job manager สำหรับการรันการทดลองที่ประกอบด้วยชุดของ job อิสระอย่างมีประสิทธิภาพ ใช้ batch mode เพื่อส่ง primitive job หลายตัวพร้อมกัน

• Session mode: หน้าต่างเฉพาะสำหรับการรัน multi-job workload วิธีนี้ช่วยให้ผู้ใช้สามารถทดลองกับ variational algorithm ในลักษณะที่คาดเดาได้มากขึ้น และแม้แต่รันการทดลองหลาย ๆ อย่างพร้อมกัน โดยใช้ประโยชน์จาก parallelism ใน stack ใช้ session สำหรับ iterative workload หรือการทดลองที่ต้องการ dedicated access ดู Run jobs in a session สำหรับตัวอย่าง

สำหรับการทดลอง QAOA session จะเป็นตัวเลือกที่ดีหากคุณมีสิทธิ์เข้าถึง เนื่องจากเราต้องสุ่มตัวอย่าง circuit หลาย ๆ ครั้งด้วยค่าพารามิเตอร์ต่าง ๆ เพื่อหาค่าที่เหมาะสม

กลับสู่ปัญหาการปรับให้เหมาะสม เราต้องหาค่าของ gamma และ beta ที่ดีกว่าการเดาแรกของเรา เราจะทำสิ่งนี้โดยการเสียบ cost function ของเราและการเดาเริ่มต้นเหล่านี้เข้าสู่ scipy optimizer COBYLA

ที่นี่คุณสามารถเห็นค่าของ cost function ตลอด iteration ต่าง ๆ มันเริ่มแปลก ๆ เล็กน้อยและขึ้นลง แต่จากนั้นก็ตกลงสู่ค่าต่ำ เราจะใช้ค่าที่ scipy พบที่สอดคล้องกับการประเมิน cost function ที่ต่ำสุด

ตอนนี้ที่เราสามารถลด cost function โดยการหาค่าพารามิเตอร์ที่ดีกว่า เราจะรัน circuit ของเราโดยใช้ค่าใหม่ที่เราพบสำหรับ gamma และ beta ฉันแสดงค่าเฉพาะที่ฉันใช้ที่นี่ แต่จำไว้ว่าเมื่อคุณลองด้วยตัวเองหรือแม้แต่รัน notebook tutorial เดิมซ้ำ ค่าเหล่านี้อาจเปลี่ยนแปลงเล็กน้อย ตอนนี้เราจะรัน circuit ที่ปรับให้เหมาะสมด้วยค่าเหล่านี้และหา candidate solution สำหรับปัญหา Max-Cut ของเรา

ในขั้นตอน post-processing เราจะวิเคราะห์ข้อมูลและแสดงผลลัพธ์เหล่านี้เพื่อดูว่าอัลกอริทึมควอนตัมของเราพบโซลูชันที่ถูกต้องหรือไม่

Post-process

ตอนนี้มาพล็อต histogram ของข้อมูลเพื่อดูโซลูชันสุดท้าย:

Bit string แสดงถึงวิธีที่ node แต่ละตัวถูก partition เป็นสองกลุ่ม (ติดฉลาก "0" และ "1") โดย cut ควรมีสี่โซลูชันที่ให้ค่าสูงสุดของ edge ที่ถูกตัด สี่อันเหล่านี้แสดงเป็นสีม่วง คุณสามารถเห็นทันทีว่า 4 โซลูชันมีความน่าจะเป็นมากกว่าอย่างอื่น ๆ bit string ที่สูงสุดและมีความน่าจะเป็นมากที่สุดคือ 0,1,0,1,1 (จำไว้ว่าลำดับของ Qubit ถูกย้อนกลับในกราฟ bitstring!)

จากกราฟนี้ เราสามารถใช้ bitstring ที่น่าจะเป็นที่สุดและแสดงมันเป็นกราฟที่ถูก partition พร้อมการตัดผ่าน 5 edge:

ดังนั้น นี่เป็น Max-Cut solution จริง ๆ แต่ไม่ใช่อันเดียว! เนื่องจากสมมาตรของกราฟนี้ มีโซลูชันที่ถูกต้องหลายอย่าง แทนที่จะมี node 0 และ 3 อยู่ภายใน cut เราสามารถมี node 2 และ 4 แทน คุณสามารถเห็นว่าฉันต้องทำแค่หมุน cut เพื่อรวม node ใหม่เหล่านี้ จำนวน edge ที่ถูกตัดยังคง 5 ปรากฏว่ามี max cut solution สี่อย่าง เนื่องจากแต่ละโซลูชันสองอย่างที่เราสังเกตยังมี "คู่ตรงข้าม" ที่ node สีม่วงเป็นสีเทาและ node สีเทาเป็นสีม่วง ดังนั้น cut ยังคงเดิม แต่แต่ละ node สลับไปฝั่งตรงข้ามของ partition อย่างมีประสิทธิภาพ

มาดู histogram และโซลูชันที่น่าจะเป็นที่สุดสี่อย่างอีกสักครู่ ตามหลักการแล้ว พวกมันควรเป็นแต่ละโซลูชัน Max-Cut จริงสี่อย่าง ปัญหาคืออัลกอริทึมไม่ได้ระบุโซลูชันที่สี่และสุดท้ายว่าเป็นหนึ่งใน 4 คำตอบที่น่าจะเป็นที่สุด มันเป็นอันดับห้าที่น่าจะเป็น โซลูชันที่สี่ที่อัลกอริทึมระบุไม่ถูกต้อง หากคุณวาดมัน คุณจะเห็นว่าโซลูชันมีเพียง 4 cut

แต่จำไว้: นี่เป็นอัลกอริทึมโดยประมาณ มันไม่ผิดพลาดได้และไม่ถูกต้อง 100% ของเวลา คุณต้องใช้ความรู้และความเข้าใจของตัวเองเพื่อตรวจสอบโซลูชัน

ข้อผิดพลาดนี้อาจเกิดจากหลายแหล่ง:

1. อาจเป็นลักษณะโดยประมาณของอัลกอริทึมเอง และจำนวน layer น้อยที่ฉันใช้
2. อาจเป็น finite sampling error ซึ่งสามารถลดได้หากฉันเพิ่มจำนวน shot ในการทดลอง
3. อาจเป็น readout error เนื่องจากโซลูชันที่สี่จริงต่างกันเพียง bit เดียว

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

อย่างไรก็ตาม อย่าลืมว่ามี bitstring 32 อันที่เป็นไปได้ และโซลูชันจริงสี่อย่างอยู่ในห้า candidate ที่ดีที่สุด และเราใช้เพียงสอง layer ในการหาสิ่งนี้ โดยทั่วไป หากเราต้องการเพิ่มโอกาสในการหา Max-Cut ที่ดีที่สุดทุกครั้ง เราสามารถเพิ่มความลึก layer ได้ มีความซับซ้อนบางอย่างในเรื่องนี้ แต่นั่นสำหรับบทเรียนต่อมา

ในระดับ utility scale

ตอนนี้ที่คุณได้ลิ้มรสกระบวนการแก้ปัญหา Max-Cut ขนาดเล็กบนคอมพิวเตอร์ควอนตัมแล้ว ฉันท้าให้คุณทำในระดับ scale ทำตามtutorial ที่ลิงก์ไว้เพื่อดูว่าคุณสามารถได้กี่ cut ในกราฟ 125 node