ทำความเข้าใจความเร็วร้อยล้านเท่าของเครื่องจักร D-Wave

อาจจะพูดได้ว่าเครื่องจักร D-Wave ที่ถูกสร้างมาเพื่อให้เป็นควอนตัมคอมพิวเตอร์เชิงพาณิชย์เครื่องแรกเป็นสาเหตุให้เราเริ่มเขียนบล็อกนี้ขึ้น เพราะก่อนหน้านั้นถึงแม้ว่าทฤษฎีควอนตัมมักจะถูกเข้าใจผิดอยู่แล้วแต่เมื่อมันมาเป็นที่สนใจในวงการเทคโนโลยีก็ยิ่งทำให้จำนวนคนที่เข้าใจผิดมีมากขึ้นไปใหญ่ เร็วๆนี้ Google ได้ออกเปเปอร์

Vasil S. Denchev et al., What is the Computational Value of Finite Range Tunneling?

ซึ่งถูกนำมาเป็นข่าวว่าเครื่องจักร D-Wave (2X) เร็วกว่า PC ถึงร้อยล้านเท่า! ความเร็วนี้มาจากการเปรียบเทียบกับอัลกอริธึมหนึ่งๆเท่านั้นซึ่งข่าวก็พูดถึง แต่ประเด็นที่ไม่ถูกยกขึ้นมาเลยก็คือ มีอัลกอริธึมที่รันได้บน PC ที่เร็วกว่าเครื่องจักร D-Wave ซึ่งทำให้ประโยคที่ว่า “เครื่องจักร D-Wave เร็วกว่า PC” ไม่จริงซะทีเดียว ซึ่งเปเปอร์เองก็บอกว่าสรุปเช่นนั้นไม่ได้เพราะเหตุผลเดียวกันว่ามีอัลกอริธึมบน PC ที่เร็วกว่า สิ่งที่พบได้ในเปเปอร์ก็คือมีปัญหาที่ถูกออกแบบมาเพื่อให้ Simulated Annealing (SA) ติดหล่ม ทีมของ Google ทำการทดลองและได้ผลว่าเครื่องจักร D-Wave แก้ปัญหานี้ได้เร็วกว่า SA และ Quantum Monte Carlo (QMC) ร้อยล้านเท่า โดย speedup อันแรกน่าจะเป็น asymptotic ในขณะที่อันหลังเป็นค่าคงที่ตามภาพ

จาก Vasil S. Denchev et al.

จุดมุ่งหมายของโพสท์นี้คือการอธิบายที่มาที่ไปตามความเข้าใจคร่าวๆของเราว่าทำไม Google ถึงเปรียบเทียบระหว่างสามวิธีนี้, ผลเป็นไปตามที่คาดจากทฤษฎีหรือไม่, และอนาคตของเครื่องจักร D-Wave จะดำเนินไปในทางไหน

ปัญหาที่เครื่องจักร D-Wave ต้องการแก้

คลาสของปัญหาที่ทีมของ Google สนใจคือการหาคำตอบที่ดีที่สุดจากทุกๆคำตอบที่เป็นไปได้ (optimization) ซึ่งเป็นปัญหาที่แพร่หลายมาก ขอเพียงเรามีเซตของสถานะ (ค่าของตัวแปร) และฟังก์ชันของ “ค่าใช้จ่าย” นิยามบนเซตของสถานะ เป้าหมายคือการหาสถานะที่ดีที่สุดโดยนิยามว่าคือสถานะที่ต้องจ่ายน้อยที่สุด ตัวอย่างที่คนน่าจะรู้จักกันมากที่สุดก็เช่นปัญหา Traveling Salesman หาเส้นทางสั้นที่สุดที่จะเดินทางผ่านทุกจุดมุ่งหมายที่ต้องการผ่านซึ่งเป็นปัญหาที่สายการบิน, ขนส่ง, ไปรษณีย์ ฯลฯ ต้องประสบ โดยทั่วไปแล้วไม่มีใครค้นพบอัลกอริธึมที่แก้ปัญหาประเภทนี้ได้อย่างมีประสิทธิภาพถึงแม้จะมีควอนตัมคอมพิวเตอร์ (หลายปัญหาเป็นปัญหา NP-complete) เป้าหมายของทีม Google จึงไม่ใช่การแก้ปัญหาเหล่านี้อย่างมีประสิทธิภาพแต่เป็นการเปรียบเทียบว่าควอนตัมคอมพิวเตอร์แก้ปัญหานี้ได้เร็วกว่าคอมพิวเตอร์ธรรมดาขนาดไหนถึงแม้จะไม่มีประสิทธิภาพทั้งคู่ก็ตาม

ปัญหาทุกปัญหาตามที่นิยามข้างต้นสามารถถูกจำลองโดยระบบฟิสิกส์ได้โดยให้พลังงานเป็นฟังก์ชันค่าใช้จ่ายและใช้ระบบที่แทนค่าของตัวแปร เช่นถ้าแต่ละตัวแปรมีได้สองค่าเราก็ใช้สปิน-1/2 ไม่ต้องตกใจชื่อมัน ขอให้รู้แค่ว่ามัน “ชี้ขึ้น” หรือ “ชี้ลง” ได้ จากนั้นสิ่งที่เราต้องทำก็คือออกแบบผังการเปลี่ยนอุณหภูมิ (annealing schedule) โดยหวังว่าระบบจะหลบหล่มและเข้าสู่ระดับพลังงานที่ต่ำที่สุดได้ ซึ่งในกรณีที่เลวร้ายที่สุดของปัญหา (worst case) ระบบฟิสิกส์เองก็มักจะหาระดับพลังงานต่ำที่สุดของมันไม่เจอเหมือนกัน! จึงใช้ระบบฟิสิกส์ในการแก้ปัญหา NP-complete อย่างมีประสิทธิภาพไม่ได้ (การขดตัวของโปรตีนหรือการฟอร์มตัวของฟองสบู่ก็เหมือนกัน)

ไอเดียของ Quantum Annealing (QA) ก็คือถ้าระบบที่ติดหล่มเป็นระบบควอนตัม มันไม่จำเป็นที่จะต้องกระโดดข้ามกำแพงพลังงานแต่สามารถทะลุผ่านไปได้เลย ซึ่ง Farhi, Goldstone และ Gutmann ได้คำนวณไว้ตั้งแต่ 2002 แล้วว่าหากกำแพงสูงและบาง QA สามารถเร็วกว่า SA แบบเอ็กซ์โพเนนเชียลได้ แต่ยิ่งกำแพงกว้างขึ้นโอกาสที่จะทะลุก็ยิ่งลดลง

ดังนั้นเราสามารถใช้กำแพงพลังงานที่บางและสูงในการแสดง speedup ของเครื่องจักร D-Wave เทียบกับ SA ในการทดลองได้ คำถามก็คือถ้าเมื่อการทดลองสำเร็จ เราจะบอกได้ว่า QA บนเครื่องจักร D-Wave เร็วกว่าอัลกอริธึมดั้งเดิมได้หรือไม่? น่าเสียดายว่าคำตอบในตอนนี้คือไม่ ถ้าอย่างนั้นมีปัญหาอื่นที่ใช้ในการแสดง speedup ของเครื่องจักร D-Wave ได้หรือเปล่า? ไม่มีใครรู้คำตอบ ด้วยเหตุผลดังต่อไปนี้

สิ่งที่เครื่องจักร D-Wave ใช่และไม่ใช่

สมมติว่าใน QA เราไม่ได้ต้องการแค่ให้ระดับพลังงานต่ำสุด encode คำตอบของปัญหา optimization แต่ให้มันเป็นสถานะควอนตัมอะไรก็ได้ (และทำในอุณหภูมิ 0 K!) Aharonov et al. พิสูจน์ใน 2004 ว่าเราจะได้ควอนตัมคอมพิวเตอร์อเนกประสงค์ (adiabatic quantum computer) ที่สามารถรันควอนตัมอัลกอริธึมได้อย่างมีประสิทธิภาพตราบใดก็ตามที่ช่องว่างระหว่างระดับพลังงานเหนือระดับต่ำสุดไม่แคบเกินไป [1] โดยเฉพาะมันจะสามารถรันอัลกอริธึมแยกตัวประกอบที่มีทฤษฎีสนับสนุนว่าเร็วกว่าอัลกอริธึมดั้งเดิมที่ดีที่สุดที่เรารู้แบบเอ็กซ์โพเนนเชียลได้

เครื่องจักร D-Wave ถูกสร้างขึ้นมาเพื่อ QA โดยเฉพาะมาจากการเอาระบบตัวนำยิ่งยวดที่แทนสถานะ “ขึ้น” เมื่อมีกระแสไฟฟ้าไหลในทิศทางหนึ่งและ “ลง” เมื่อไหลอีกทิศทางหนึ่ง หรือเรียกว่า “ฟลักซ์ควอนตัมบิตที่ทำจาก Josephson junction” จากนั้นก็เชื่อมต่อควอนตัมบิตเข้าด้วยกันเป็นกราฟ (หมายถึงเน็ตเวิร์คไม่ไช่กราฟที่พล็อตกัน) ซึ่งแพทเทิร์นการเชื่อมต่อนี้เป็นตัวกำหนดระดับพลังงานที่เราวาดเป็นหุบเขาให้ระบบกระโดดไปมาข้างต้น (Hamiltonian) ด้วยเหตุผลทางวิศวกรรมการจะเชื่อมต่อทุกๆควอนตัมบิตทำได้ยาก D-Wave จึงตกลงใจที่จะทำการเชื่อมต่อที่พวกเขาให้ชื่อว่ากราฟ chimera โดยการแบ่งควอนตัมบิตเป็นกลุ่มๆ กลุ่มละ 8 ควอนตัมบิต ในกลุ่มเดียวกันจะมีการเชื่อมต่อที่หนาแน่นทำให้ควอนตัมบิตใดบิตหนึ่งเปลี่ยนทิศทางเป็นอิสระจากควอนตัมบิตที่เหลือในกลุ่มได้ยาก ข้อจำกัดในการเชื่อมต่อทำให้ Alex Selby เขียนอัลกอริธึมที่เร็วกว่าทั้ง SA, QMC (ด้านล่าง) และเครื่องจักร D-Wave ได้ ซึ่งในขณะที่ทีมของ Google เชื่อว่าอัลกอริธึมนี้จะไม่สามารถใช้ได้กับเครื่องจักร D-Wave รุ่นต่อไป (แต่ไม่ได้วิเคราะห์ในเปเปอร์) Selby ไม่เห็นด้วยและคิดว่าจะต้องมีการเปลี่ยนแปลงการเชื่อมต่อมากกว่านั้นมาก อัลกอริธึมดั้งเดิมจึงจะล้มเหลว

นอกจากนี้ฟลักซ์ควอนตัมบิตที่ทำจาก Josephson junction จำกัด Hamiltonian ที่เลือกได้ให้อยู่ในคลาสที่เรียกว่า stoquastic Hamiltonian คือ Hamiltonian ที่ไม่มี “ปัญหาเครื่องหมาย” (sign problem) ในฟิสิกส์ควอนตัมเรามักจะต้องคำนวณ matrix element ที่มาจาก Hamiltonian เพื่อที่จะอนุมานสมบัติต่างๆของระบบ มีอัลกอริธึมบนคอมพิวเตอร์ธรรมดาชื่อว่า path integral quantum Monte Carlo (เรียกสั้นๆว่า QMC) ที่คำนวณโดยการแปลง matrix element พวกนี้เป็นกระบวนการ stochastic (เลกเชอร์ของ Matthias Troyer อ่านรู้เรื่องดี) แต่ทริคนี้ใช้ไม่ได้เสมอไปโดยเฉพาะบางครั้งก็จะให้ “ความน่าจะเป็น” ที่ไม่ใช่จำนวนจริงบวกออกมา นี่คือปัญหาเครื่องหมายทำให้เราจำลองมันอย่างตรงไปตรงมาบนคอมพิวเตอร์ไม่ได้

ผลที่ตามมาสำหรับ D-Wave ก็คือ

•  Bravyi et al. พิสูจน์ว่าถ้ามีแต่ stoquastic Hamiltonian จะแก้ปัญหาแค่ในคลาส BPP_path ได้อย่างมีประสิทธิภาพซึ่งเชื่อว่าไม่ครอบคลุมคลาส BQP ของปัญหาที่แก้ได้อย่างมีประสิทธิภาพด้วยควอนตัมคอมพิวเตอร์อเนกประสงค์ [2]
• Hamiltonian ที่ stoquastic แปลว่าเรามักจะใช้ QMC ในการจำลองเครื่องจักร D-Wave อย่างมีประสิทธิภาพได้ (แต่ไม่เสมอไป) นี่เป็นเหตุผลหนึ่งที่ทีม Google ใช้ QMC จำลอง QA ได้ด้วยความเร็วที่ต่างกันด้วยแค่ค่าคงที่

จึงไม่มีใครรู้แน่ชัดว่าเครื่องจักร D-Wave จะแสดง speedup จากสมบัติทางควอนตัมได้หรือไม่

อนาคตของเครื่องจักร D-Wave

ถ้าอย่างนั้น D-Wave รุ่นต่อไปจะพัฒนาได้ในทางไหนบ้าง? ลดอุณหภูมิ ปรับปรุงการเชื่อมต่อ(และ error ในการทดลอง) เพื่อที่จะแมปปัญหาในโลกของความเป็นจริงลงในคอมพิวเตอร์ได้ทั้งจำนวนมากขึ้นและมีประสิทธิภาพมากขึ้น ออกนอก stoquastic Hamiltonian แต่ถ้าจะต้องการแสดงให้เห็น speedup เชิงควอนตัม D-Wave มีปัญหาใหญ่กว่านั้นและเป็นปัญหาทางทฤษฎีที่น่าสนใจมาก

ในหมู่นักวิชาการเชื่อกันว่าความอดทนต่อความผิดพลาด (fault tolerance)นั้นจำเป็นอย่างยิ่งในการสเกลควอนตัมคอมพิวเตอร์ให้ใหญ่พอที่จะแสดง speedup เชิงควอนตัมได้และนี่เป็น design choice ที่ D-Wave ไม่ให้ความสำคัญตั้งแต่แรกเริ่มต่างกับ approaches อื่นๆ มีงานวิจัยศึกษาการแก้ความผิดพลาด (error correction) ในโมเดล adiabatic แต่ความผิดพลาดก็ยังเกิดขึ้นได้ในการแก้ความผิดพลาดของการแก้ความผิดพลาดของ… การอดทนต่อความผิดพลาดทำให้คอมพิวเตอร์ยังทำงานต่อไปได้ตราบใดก็ตามที่อัตราการเกิดความผิดพลาดยังต่ำกว่าค่า threshold หนึ่ง ซึ่งการหา threshold ของโมเดล adiabatic ยังเป็นปัญหาปลายเปิด

ปัจจุบันเป็นเวลาที่น่าตื่นเต้นที่บริษัทยักษ์ใหญ่ทั้ง IBM, Intel, Microsoft, Google ระดมทุนวิจัยศึกษาควอนตัมคอมพิวเตอร์ในหลากหลายโมเดล (แม้กระทั่ง topological ที่ได้ชื่อว่า “ทฤษฎีสตริงของควอนตัมคอมพิวติง”!) และไม่มีใครรู้ว่าจะสำเร็จหรือไม่ โมเดลไหนจะชนะ หรือสุดท้ายทุกโมเดลจะอยู่ร่วมกันอย่างมีความสุข เราจะพบว่ามันสวยงามมากถ้าทุกๆโมเดลเป็นไปได้ทั้งหมดเพราะมันสื่อว่าปรากฎการณ์ทางฟิสิกส์ที่หลากหลายและดูแตกต่างกันในทฤษฎีควอนตัมมีสิ่งหนึ่งที่เหมือนกันก็คือพลังในการประมวลผลข้อมูล

[1] ช่องว่างนี้เรียกสั้นๆว่า gap ในที่นี้ไม่แคบเกินไปแปลว่าความกว้างอย่างน้อยต้องสเกลเป็น inverse polynomial ในจำนวนควอนตัมบิต (gap มักจะ inverse exponential สำหรับปัญหา NP-complete) โดยคร่าวๆแล้ว gap เกี่ยวกับเวลาที่ใช้ในการแก้ปัญหาเพราะถ้าช่องว่างเล็กแล้วเรารีบรันอัลกอริธึมระบบจะกระโดดขึ้นไปยังระดับพลังงานที่สูงกว่าได้ ↩

[2] เราคิดว่าเป็นเพราะ BPP_path อยู่ใน Polynomial Hierarchy แต่ BQP อาจจะมีส่วนที่ยื่นออกมาจาก PH (Scott Aaronson พิสูจน์ว่ามี oracle ที่ทำให้ BQP ⊄ BPP_path) ↩