ควอนตัมคอมพิวเตอร์กับปัญหา Combinatorial Optimization

มีความเชื่อว่าควอนตัมคอมพิวเตอร์ซึ่งมีคิวบิตที่สามารถอยู่ในสถานะ superposition คือเป็น 0 และ 1 ได้ในเวลาเดียวกัน จะสามารถทำตัวเป็น binary string จำนวน 2^n แบบพร้อมๆ กันและจะสามารถแก้ปัญหาประเภท combinatorial ได้ในพริบตา แต่ความเป็นจริงแม้แต่กับควอนตัมคอมพิวเตอร์เองมันก็ไม่ได้ง่ายขนาดนั้น เรื่องนี้ผมไปลองศึกษาดูแล้วว่ามันทำงานอย่างไร ทำได้ขนาดไหน จึงขอมาเขียนลงบล็อกเพื่อทบทวนให้ตัวเองและมาเล่าสู่กันฟัง ดังนี้

บทนำ
ปัญหา Optimization คือการหาจุดสูงสุดหรือต่ำสุดจากกราฟ Objective Function ซึ่งหากกราฟเป็นฟังค์ชั่นทางคณิตศาสตร์โค้งเว้าสวยงามก็พอมีทางที่จะไต่ความชันกราฟเพื่อไปหาจุดสูงสุดหรือต่ำสุดที่ต้องการได้ แต่หากกราฟเป็นหลุมเป็นบ่อหรือไปเจอปัญหาอย่าง Combinatorial Optimization ซึ่งพื้นที่ค้นหาไม่ใช่เส้นต่อเนื่องและไม่มีความหมายในเชิงปริมาณ เป็นการยากที่จะรู้ได้ว่าจุดที่เราอยู่มันสูงสุดหรือยัง ถ้าขยับต่อไปอีกมันจะสูงขึ้นหรือต่ำลง เราคาดการณ์ไม่ได้นอกจากจะต้องลองขยับดูจริงๆ แค่นั้นยังไม่พอ ปัญหา combinatorial optimization มักจะมาพร้อมกับพื้นที่ค้นหาที่มีอัตราการโตระดับ exponential ขึ้นไป การค้นหาคำตอบทั้งพื้นที่เป็นสิ่งที่เป็นไปไม่ได้ อัลกอริทึมในปัจจุบันล้วนแต่ต้องใช้โชคช่วยไม่ทางใดก็ทางหนึ่ง เช่น Genetic, Swarm, Simulated Annealing


ตัวอย่างพื้นผิว Objective Function ของปัญหา Max-Cut
โจทย์ Optimize ต้องการแบ่งข้างโหนดโดยให้เส้นเชื่อมพาดข้ามฝั่งให้มากที่สุด

ข่าวประเภท pop science มักจะเขียนให้คนเข้าใจว่า เมื่อควอนตัมคอมพิวเตอร์มีคิวบิตที่สามารถแสดงตัวเป็นสถานะจำนวน 2^n ได้พร้อมกัน จะสามารถทดลองและหาคำตอบได้พร้อมกัน นัยว่าจะสามารถ brute force ทะลวงปัญหาได้ในพริบตา แต่ในทางปฏิบัติมันทำอย่างนั้นไม่ได้ เหตุผลก็เพราะ

ประการแรก ต้องดูก่อนว่า objective function ของเราอยู่ที่ไหน ถ้ามันอยู่บนคอมพิวเตอร์คลาสสิกธรรมดา แล้วเราจะเอา superposition ยัดเข้าไปเพื่อหาคำตอบได้อย่างไร superposition จะมีประโยชน์ก็ต่อเมื่อนำไปใช้กับ objective function ที่ยอมรับ superposition ได้เท่านั้น

ประการที่สอง เมื่อเราใส่ input เป็น superposition ให้กับ objective function แบบ superposition แน่นอนว่าผลลัพธ์มันก็ออกมาเป็น superposition คำตอบของเราแทรกตัวอยู่ในนั้นแหละ แต่น่าเศร้าที่เราไม่สามารถดึงมันออกมาได้โดยง่าย นี่จึงเป็นสาเหตุที่ยังต้องมีการวิจัยหาอัลกอริทึมเพื่อที่จะดึงคำตอบที่อยู่ในนั้นออกมา

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

ตอนนี้เรามาดูกันต่อว่าถ้าจะเอาควอนตัมคอมพิวเตอร์มาใช้กับงานแบบนี้ปัจจุบันเขาทำกันอย่างไร

Quantum Simulation
ความจริงแล้วในตอนแรกควอนตัมคอมพิวเตอร์ถูกเสนอให้สร้างขึ้นมาเพื่อแก้ปัญหาทางควอนตัมในธรรมชาติ เช่นการคำนวณอันตรกิริยาในโมเลกุล ซึ่งเมื่อระบบที่สนใจมีขนาดใหญ่ขึ้น ความซับซ้อนในการคำนวณจะเพิ่มขึ้นเป็นทวีคูณจนเกินกำลังคอมพิวเตอร์ธรรมดา นักวิทยาศาตร์จึงมีความคิดว่าถ้าจะคำนวณระบบควอนตัม มันก็ต้องใข้คอมพิวเตอร์ซึ่งคำนวณด้วยวิธีแบบควอนตัม จะเป็นการดีมากหากมี Universal Quantum Computer ที่สามารถโมเดลคุณลักษณะของระบบหรือแฮมิลโตเนียน(Hamiltonian)อย่างไรก็ได้ตามแต่ระบบที่สนใจแล้วทดลองคำนวณพลวัตดู เรียกว่าเป็นการจำลองระบบควอนตัมหรือ Quantum Simulation

เรื่องมันเริ่มสนุกขึ้นเมื่อพบว่าหากสามารถสร้างควอนตัมคอมพิวเตอร์ได้จริง มันจะไม่เพียงเอามาใช้จำลองระบบควอนตัมได้เท่านั้น แต่มันยังสามารถรันอัลกอริทึมบางอย่างได้เร็วกว่าคอมพิวเตอร์ธรรมดา เช่น การแยกตัวประกอบเลขจำนวนเต็ม (Shor’s algorithm) หรือการค้นหาข้อมูล (Grover’s algorithm)

ปัญหา NP อย่าง combinatorial optimization ก็เข้าข่ายงานนี้ด้วย โดยแนวคิดหลักในการแก้ปัญหานี้ก็คือ

  1. จำเป็นต้อง encode Objective Function (Cost Function) เป็น Hamiltonian
  2. จากนั้นค้นหา Eigenstate ที่ระดับพลังงานต่ำที่สุด
  3. ที่จุดนั้นเมื่อวัดค่าแล้วจะมีโอกาสพบคำตอบที่ใกล้เคียงกับค่า Optimum มากที่สุด

กล่าวคือเป็นนำเอาพื้นผิว landscape ของปัญหา optimization มาจำลองด้วย hamiltonian แล้วค้นหาก้นบ่อโดยการค้นหา ground state ของระบบ
(ถ้ายังไม่รู้ว่า Hamiltonian หรือ Eigenstate คืออะไร แวะไปอ่านโพสนี้ก่อนได้ครับ)
หลักการมีสั้นๆ แค่นี้ แต่ตอนทำจริงกลับเป็นเรื่องยาก เพราะอยู่ๆ เราจะพาระบบเข้าไปที่ ground state ได้อย่างไร?

Adiabatic Theorem
อะเดียบาติก(Adiabatic) แปลตรงตัวแปลว่าไม่มีอะไรผ่าน ในทางอุณหพลศาสตร์ อะเดียบาติกหมายถึงไม่มีการส่งผ่านความร้อนเข้าหรือออกจากระบบ ในทางควอนตัม อะเดียบาติกหมายถึงไม่มีการผ่านระดับพลังงาน
ทฤษฎี Adiabatic ในกลศาสตร์ควอนตัมกล่าวไว้ว่า หากมีระบบอะไรซักอย่างอยู่ในสถานะไอเกน เช่นที่ ground state ถ้าเราค่อยๆ ปรับ Hamiltonian อย่างช้าๆ ระบบจะยังคงอยู่ในสถานะไอเกนที่ ground state ใน Hamiltonian ใหม่ด้วยเช่นกัน นั่นคือไม่มีการเปลี่ยนแปลงระดับพลังงาน

อารมณ์เดียวกับการเล่นเกม Quantum Moves (เกมใน Play Store)

ถ้าเราค่อยๆ ย้ายบ่อศักย์ (เปลี่ยน Hamiltonian) ช้าๆ ระบบจะยังคง Eigenstate อยู่ได้

ถ้าเราทะเล่อทะล่าย้ายบ่อศักย์ พลังงานส่วนเกินที่เพิ่มขึ้นทำให้ Eigenstate เสียไป

ดังนั้นแนวทางการแก้ปัญหา Optimization ก็คือ ให้ตั้งต้นสร้าง Hamiltonian ที่มีสถานะไอเกนที่ง่ายที่สุด เช่น landsacpe ราบเรียบ ซึ่งจะมีสถานะไอเกนเป็น superposition กระจายความน่าจะเป็นเท่าๆ กันหมดทั้งพื้นที่ จากนั้นให้ค่อยๆ interpolate Hamiltonian ของโจทย์ optimization ที่ต้องการใส่เข้าไป สุดท้ายแล้วระบบควรจะต้องคงอยู่ที่ ground state ซึ่งความน่าจะเป็นจะมาหนาแน่นอยู่บริเวณสถานะที่เป็นคำตอบของการ optimize

H(t) = (1-\frac{t}{T})H_B + \frac{t}{T}H_P

Hamiltonian ณ ขณะหนึ่ง เกิดจาก Hamiltonian ตั้งต้น HB
ค่อยๆ interpolate กับ Hamiltonian ของโจทย์ที่ต้องการ HP

 

การเปลี่ยน Hamiltonian (เส้นสีเทา) ที่ราบเรียบให้เป็น Hamiltonian ตามโจทย์ optimization อย่างช้าๆ
หากตั้งต้นด้วยสถานะ ground state ก็ควรจะจบด้วยสถานะ ground state เช่นกัน

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

QA – Quantum Annealing
ด้วยหลักการเดียวกับ Adiabatic Theorem ข้างต้นคือค่อยๆ สร้างพื้นผิว Hamiltonian ของปัญหาขึ้นมาจากพื้นผิวราบเรียบ แต่ Quantum Annealing จะเริ่มต้นด้วยสถานะควอนตัมที่มีความผันผวนมากที่สุด(แทนที่จะเป็น ground state)แล้วค่อยลดพลังงานลง จนระดับพลังงานต่ำสุดตอนที่พื้นผิวของปัญหาปรากฏขึ้นอย่างเต็มที่ คล้ายกับอัลกอริทึม Simulated Annealing ที่ใส่ความผันผวนเข้าในระบบให้มากที่สุดเพื่อกระจายการค้นหาแล้วค่อยลดความผันผวนลง

สิ่งที่ quantum annealing ทำได้มากกว่า simulated annealing ก็เป็นไปตามความต่างระหว่างกลศาสตร์คลาสสิกกับกลศาสตร์ควอนตัม คือสถานะควอนตัมจะมีความสามารถในการ “ทะลุกำแพงปัญหา” หรือที่เรียกว่า quantum tunneling ได้ ทำให้มีความสามารถในการหนีออกจาก “ก้นบ่อปลอม” หรือ local minima ได้ดีกว่า หากเจอกำแพงที่มีความชันมากๆ


ภาพซ้ายเปรียบเปรยให้เห็นว่า Simulated Annealing จะใส่ความผันผวนให้วัตถุมีความสามารถในการกระโดดเพื่อหาก้นบ่อ
ภาพขวาคือ Quantum Annealing ก็ทำงานลักษณะเดียวกัน แต่วัตถุควอนตัมจะมีความสามารถในการทะลุกำแพงปัญหา

เครื่องจักรที่บริษัท D-Wave สร้างขึ้น คือเครื่องสำหรับทำ quantum annealing แบบนี้ ซึ่งนักวิชาการส่วนหนึ่งไม่ค่อยชอบ เพราะเป็นวิธีที่ไม่ได้มีความพยายามสร้างความแม่นยำในสถานะควอนตัมเลย และไม่ได้มีการพิสูจน์ประสิทธิภาพแต่อย่างใด นอกจากนี้แล้ว hamiltonian ที่จะผูกขึ้นบนเครื่องของ D-Wave ได้ ก็ต้อง map ให้เป็นโจทย์ QUBO (Quadratic Unconstrained Binary Optimization) เท่านั้น มันจึงยังไม่จัดว่าเป็น universal quantum computer อย่างเต็มตัว

VQE – Variational Quantum Eigensolver
เป็นอัลกอริทึมในการหา Eigenstate ต่ำที่สุด ซึ่งมีที่มาจากวิธีการประมาณค่าสถานะพื้นในกลศาสตร์ควอนตัม อัลกอริทึมนี้มีการทำงานแบบผสม (hybrid) ระหว่างคอมพิวเตอร์ธรรมดาและควอนตัมคอมพิวเตอร์ ในปัจจุบันที่ควอนตัมคอมพิวเตอร์ยังอยู่ในช่วงเตาะแตะ เมื่อเรายังไม่สามารถรันควอนตัมอัลกอริทึมยาวๆ ได้ เราจึงต้องใช้คอมพิวเตอร์ธรรมดาเป็นโครงหลัก แล้วเรียกใช้ควอนตัมคอมพิวเตอร์ในบางจุดเป็นช่วงสั้นๆ

หลักการค้นหา eigenstate ของ VQE คือเปลี่ยนโดเมนค้นหาจากสถานะควอนตัมให้กลายเป็นตัวแปร parameter ตามจำนวนแกนหลัก (basis) นำ parameter ไปสร้างสถานะควอนตัมสำหรับเดินหาคำตอบ(เรียกเท่ห์ๆ ว่า Ansatz) แล้ววัดค่าเฉลี่ยพลังงานหรือที่เรียกว่าค่าคาดหวัง(Expectation Value) ใช้เป็นค่า cost function การทำแบบนี้จะสามารถใช้ optimization algorithm แบบคลาสสิกธรรมดา ค้นหา parameter ที่จะนำไปสู่ eigenstate ที่ระดับพลังงานต่ำที่สุดได้

สรุปชัดๆ อีกทีคือ

  1. กำหนด parameter มุมเริ่มต้น \vec{\theta} ตามจำนวนของแกนหลัก
  2. สร้าง ansatz ซึ่งเป็นสถานะควอนตัมที่จะแปรตาม parameter มุม \Psi(\vec{\theta})   (ทำบนควอนตัมคอมพิวเตอร์)
  3. นำสถานะควอนตัมนั้นไปผ่าน hamiltonian ของโจทย์และวัดค่าคาดหวัง \langle \Psi(\vec{\theta}) | H_p | \Psi(\vec{\theta}) \rangle   (ทำบนควอนตัมคอมพิวเตอร์)
  4. ใช้อัลกอริทึมแบบคลาสสิกในการคำนวณ parameter ใหม่ เพื่อ minimize ค่าคาดหวัง
  5. ทำซ้ำตั้งแต่ข้อ 2-5 จนกว่าจะพอใจ
  6. สุดท้ายนำ parameter ไปสร้างสถานะควอนตัมและวัดผล (measure) หลายๆ ครั้ง ก็จะมีโอกาสพบคำตอบที่ใกล้เคียง optimum (ทำบนควอนตัมคอมพิวเตอร์)

ภาพ optimization surface จาก Wikipedia (ซึ่งไม่เกี่ยวข้องกับฟังค์ชันค่าคาดหวังแต่อย่างใด แต่มันสวยดี)
ผู้เขียนเพียงต้องการจะสื่อว่า VQE เปลี่ยนโจทย์ให้กลายเป็นการ optimize ค่าคาดหวังบนพื้นผิวของ parameter มุม

 

QAOA – Quantum Approximate Optimization Algorithm
อีกหนึ่งอัลกอริทึมที่กำลังถูกกล่าวถึงมากขึ้น และบริษัท Rigetti ก็ได้นำมาทำเป็น showcase สาธิตการทำงานกับควอนตัมคอมพิวเตอร์ของตนเอง QAOA เป็นอัลกอริทึมที่รวมข้อดีของ Adiabatic และ VQE เข้าด้วยกัน กล่าวคือมันใช้หลักการปรับ Hamiltonian ขณะที่พยายามกดระบบให้อยู่ในสถานะที่พลังงานต่ำ แต่ก็เป็นอัลกอริทึมแบบ hybrid ที่ไม่จำเป็นต้องทำงานบนควอนตัมคอมพิวเตอร์ยาวๆ ก็ได้

ด้วยหลักการเดียวกับ Adiabatic Theorem คือให้ระบบเริ่มต้นด้วย Hamiltonian ที่ราบเรียบ ค่อยๆ ให้มันเปลี่ยนแปลงตามเวลา และจบด้วย Hamiltonian ของโจทย์ แต่เราจะสนใจการเปลี่ยนแปลงของสถานะควอนตัมมากกว่าตัวแฮมิลโตเนียน โดยจะมีการทำ parameter ของมุมขึ้นมาในลักษณะเดียวกับ VQE แล้วนำสถานะควอนตัมนั้นมาผ่าน Operation ซึ่งจะวิวัฒน์ (Evolve) สถานะควอนตัมนั้นตามคุณลักษณะของ Hamiltonian ณ step นั้น


แฮมิลโตเนียนตั้งตัน HB คือ superposition ราบเรียบเต็มพื้นที่
ตัวอย่างนี้นำไปผ่านการวิวัฒน์ 2 step เพื่อเข้าสู่แฮมิลโตเนียน HP ของโจทย์ที่ต้องการ
  1. ดูตามภาพทางซ้ายสุด เราจะเตรียม superposition โดยการนำสถานะ “ศูนย์” ไปผ่านเกต Hadamard (H ตัวนี้ไม่ได้หมายถึง Hamiltonian นะ) ณ จุดนี้เท่ากับเราก็จะมีแฮมิลโตเนียน HB ตั้งต้นที่เป็นพื้นผิวราบเรียบ
  2. ตัวอย่างนี้เราจะวิวัฒน์ 2 step (จริงๆ จะซอยมากกว่านี้ก็ได้ ยิ่งละเอียดผลลัพธ์ยิ่งแม่น แต่ก็จะทำงานช้าลง) ในแต่ละ step เราต้องการให้เข้าสู่แฮมิลโตเนียนที่มีค่าก้ำกึ่งระหว่าง HB และ HP
  3. ในอัลกอริทึมนี้กำหนดให้ Unitary Operator ที่จะวิวัฒน์ดังกล่าว มีค่าซึ่งเกิดจากแฮมิลโตเนียน HB กับมุม β และแฮมิลโตเนียน HP กับมุม γ
    U(H_t) = \text{exp}(-iH_{B}\beta_t)\text{exp}(-iH_{P}\gamma_t)
    ฟังค์ชั่นนี้มีที่มาจาก Trotter decomposition และ Schrödinger equation (ที่เฌอปรางยังออกปากว่ายาก)

  4. ปัญหาคือเราไม่รู้ว่ามุม β และ γ ในแต่ละ step มีค่าเท่าไหร่ ซึ่งตรงนี้ก็ต้องเอาวิธีของ VQE มาใช้ คือตั้ง ansatz ขึ้นมาแล้ว optimize หาค่ามุมที่จะให้ค่าเฉลี่ยพลังงานต่ำที่สุด เป็นการกดระบบให้อยู่ในสถานะที่พลังงานต่ำอยู่ทุก step
  5. เมื่อวิวัฒน์ไปจนเข้าสู่แฮมิลโตเนียนสุดท้าย ก็ถือได้ว่าเรามีสถานะไอเกนที่ต่ำที่สุดแล้ว ก็นำสถานะนั้นไปวัดค่าเพื่อหาคำตอบต่อไป

บทส่งท้าย
ก็พอจะเห็นได้ว่า แม้ว่าควอนตัมคอมพิวเตอร์จะมี parallelism ที่มีพลังคำนวณมหาศาล แต่มันไม่ได้เกิดมาเพื่องาน Optimization เลย ด้วยเทคนิคทั้งหลายทั้งปวง เราก็ทำได้แค่ “มีโอกาส” วัดค่าที่ “ใกล้เคียง” กับค่า optimum เท่านั้น ไม่มีอะไรการันตีได้เลยว่าจะสามารถหาค่า optimum ได้ในเวลาที่เหมาะสม อัลกอริทึมส่วนใหญ่ก็ออกตัวว่ามันแค่ Approximate เพื่อหา good solution ไม่ใช่ best solution โดยส่วนตัวผมว่างานที่ดูจะมีอนาคตสำหรับควอนตัมคอมพิวเตอร์จริงๆ น่าจะเป็นเรื่อง Quantum Simulation (งาน Chemistry, Material) หรือเป็นตัวช่วยคำนวณ Linear Systems (งาน Machine Learning) หรือ Integer Factoring (งาน Breaking Cryptography) มากกว่างาน Optimization แต่อย่างว่า เราเพิ่งจะก้าวเข้าสู่ยุคเริ่มต้นของควอนตัมคอมพิวเตอร์ อะไรจะรอเราอยู่ข้างหน้าบ้างก็สุดจะคาดเดา

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

 
Link แนะนำ

Advertisements

One Response to “ควอนตัมคอมพิวเตอร์กับปัญหา Combinatorial Optimization”

  1. เรื่องของควอนตัมแฮมิลโตเนียนและสถานะไอเกน | Panya's Blog: Programmer Thoughts Says:

    […] ควอนตัมคอมพิวเตอร์กับปัญหา Combinatorial Optimiz… […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: