เมื่อไรที่ระบบควอนตัมจำลองได้ยาก? : ดีไซน์การทดลอง quantum supremacy [draft]

เมื่อฟิสิกส์เจอกับวิทยาศาสตร์คอมพิวเตอร์

ด้วยเหตุผลทั้งหลายทั้งปวง คอมพิวเตอร์ธรรมดาจะไม่ถูกแทนที่ด้วยคอมพิวเตอร์ควอนตัมหรอก ในอนาคตเราจะมีคอมพิวเตอร์ควอนตัมไว้เพื่อช่วยแก้ปัญหาเฉพาะอย่างที่คอมพิวเตอร์ธรรมดาแก้ได้ยาก อย่างทอล์คของ Patrick Coles ในงานประชุม QHack 2021 ของ Xanadu ที่ผมเพิ่งดูพูดถึงหลักการดีไซน์ variational quantum algorithms (VQA) สำหรับหาพารามิเตอร์ $\theta$ ที่ optimize cost function ตัว cost function อาจจะคำนวณได้ยาก เราก็ให้คอมพิวเตอร์ควอนตัมคำนวณ cost function ที่พารามิเตอร์ค่าใดค่าหนึ่ง (กำหนดวิธี initialize พารามิเตอร์มาสักวิธี) จากนั้นก็นำไปป้อนให้คอมพิวเตอร์ธรรมดาเพื่อ optimize ค่าพารามิเตอร์ เพื่อเอามาป้อนกลับให้คอมพิวเตอร์ควอนตัมวนลูปไปเรื่อยๆ

graph LR; qc(Quantum computer:
Efficiently compute
the cost function)-->cc(Classical computer:
Optimize $\theta$); cc-->qc;

Patrick Coles บอกว่าวิธีนี้เป็นไอเดียที่ดีถ้าเรารู้ว่าการคำนวณตัว cost function ทำได้ง่ายบนคอมพิวเตอร์ควอนตัมแต่ยากบนคอมพิวเตอร์ธรรมดา ปกติแล้ว cost function ใน VQA เป็น (linear combination ของ) ค่าคาดหมาย (expected value) ของ observable $O$

\[\bra{\psi_{\rm in}}U\dgg(\theta) O U(\theta)\ket{\psi_{\rm in}}\]

ที่หาได้จากการสุ่มค่า $O$ จากเอาท์พุตของวงจรควอนตัม (quantum circuit) $U(\theta)$ หลายๆครั้งซึ่ง without loss of generality ถือได้ว่าเท่ากับการสุ่มตัวอย่างจากการแจกแจงความน่าจะเป็น

\[p_{\x}(U(\theta)) = |\av{\x|U(\theta)|\psi_{\rm in}}|^2\]

ที่จะเห็นบิตสตริง $\x \in \{0,1\}^k$ จากการวัด $k$ คิวบิตใน computational basis ($k$ อาจจะน้อยกว่าจำนวนคิวบิตทั้งหมด) ดังนั้น cost function ที่ “ง่าย” หมายความว่าเรามีอัลกอริธึมที่รับ $\theta$ เป็นอินพุตแล้วสุ่มบิตสตริงเอาท์พุต $\x$ ด้วยความน่าจะเป็น $p_{\x}(U(\theta))$ ได้อย่างมีประสิทธิภาพเมื่อเทียบกับปริมาณทรัพยากรที่ใช้เช่นหน่วยความจำหรือเวลา เราเรียกว่าอัลกอริธึมนี้ “จำลอง” (simulate) เซตของของวงจรควอนตัม $U(\theta)$ อัลกอริธึมตัวนี้บนคอมพิวเตอร์ควอนตัมก็คือตัววงจร $U(\theta)$ เอง (ซึ่งต้องประมวล (compile) เป็นเกตพื้นฐานได้อย่างมีประสิทธิภาพและวงจรไม่ลึกเกินไปคือจำนวนเกตเป็น polynomial ของจำนวนคิวบิต) เดี๋ยวเราจะมาถกเถียงกันว่านิยามการจำลองแบบนี้สมเหตุสมผลหรือไม่ นอกจากนี้ในความเป็นจริงทั้งคอมพิวเตอร์ควอนตัมและคอมพิวเตอร์ธรรมดาที่ทำการจำลองจะต้องมี noise ซึ่งเดี๋ยวก็จะพูดถึงเช่นกัน

แต่เราจะรู้ได้อย่างไรว่าวงจรควอนตัมไหนจำลองได้ยากบนคอมพิวเตอร์ธรรมดา? การจะบอกว่าปัญหาใดปัญหาหนึ่งยากเราจะต้องตัดความเป็นไปได้ทั้งหมด (rule out) ของอัลกอริธึมที่มีประสิทธิภาพรวมถึงอัลกอริธึมที่ยังไม่เคยมีใครค้นพบด้วย เป็นสาเหตุเดียวกับที่ทำให้ P $\neq$ NP พิสูจน์ได้ยากเพราะจะต้อง rule out ทุกอัลกอริธึมที่จะแก้ปัญหา NP-complete ได้อย่างมีประสิทธิภาพ ในเปเปอร์ VQA สำหรับการประมวลเกตควอนตัมของ Patrick Coles เขาพิสูจน์ความยากตรงนี้โดยการโยง cost function ของเขากับผลการคำนวณของโมเดล One Clean Qubit ซึ่งเชื่อว่าจำลองได้ยาก แต่นี่ก็เป็นแค่การขยับคำอธิบายไปอีกขั้้นเท่านั้นเอง “เชื่อว่าจำลองได้ยาก” ในที่นี้หมายความว่าอะไร?

“ความเชื่อ” ในที่นี้คือข้อสันนิษฐานที่มีความเป็นไปได้ (plausible conjecture) ใน complexity theory ทำนอง P $\neq$ NP ที่ทำให้เราสามารถ rule out การจำลองวงจรควอนตัมบนคอมพิวเตอร์ธรรมดาได้โดยไม่ rule out อัลกอริธึมควอนตัมไปด้วย ¹ แต่ในความเป็นจริงคอมพิวเตอร์ควอนตัมที่ไม่ fault-tolerant ก็ต้องมี noise ทำให้อัลกอริธึมจำลองไม่ต้องแม่นยำมากก็ได้ สิ่งที่น่าทึ่งคือเปเปอร์ Boson Sampling บอกว่าเรายังมีโอกาสที่จะ rule out อัลกอริธึมที่ไม่แม่นยำนี้ได้ Breakthrough นี้เปิดประตูสู่ความเป็นไปได้ของการทำการทดลองเพื่อพิสูจน์ quantum supremacy ² ที่เคยเขียนไปในบล็อกนี้ตอนที่กูเกิ้ลประกาศผลการทดลอง Random Circuit Sampling 53 คิวบิต

โพสท์นี้เราจะว่าด้วยการดีไซน์การทดลอง quantum supremacy ที่ผมขอแบ่งเป็นห้าขั้นตอน

0. เลือกเซตของวงจรควอนตัม $\{U\}$ ที่ยังไม่มีใครรู้ว่าจำลองยังไงบนคอมพิวเตอร์ธรรมดา
1. โชว์ว่ามี $p_{\x}(U)$ ที่ประมาณค่าได้ “ยาก” (อัลกอริธึมที่ประมาณ $p_{\x}(U)$ ได้ทุกๆ instance จะแก้ทุกปัญหา #P ได้)
2. โชว์ว่า $p_{\x}(U)$ ประมาณค่าได้ “ยากโดยเฉลี่ย” (อัลกอริธึมที่ประมาณ $p_{\x}(U)$ ได้ใน instance ส่วนใหญ่จะแก้ทุกปัญหา #P ได้)
3. โชว์สิ่งที่เรียกว่า anti-concentration
4. (ไม่จำเป็น) เสนอวิธีเช็คว่าการทดลอง implement สิ่งที่เราต้องการให้มันทำจริงหรือไม่

ในหนึ่งปีสิ้นโลก (2020) ที่ผ่านมา ผมเข้าใจเรื่องนี้มากขึ้นจากการทำงาน quantum supremacy ในระบบ driven many-body ร่วมกับกลุ่มของ Dimitris Angelakis (สิงคโปร์) กับเสนอการทดลองใหม่ชื่อว่า Fermion Sampling ซึ่งรวมเอาข้อดีของ Boson Sampling กับ Random Circuit Sampling เข้าไว้ด้วยกัน

post-selection argument และอัลกอริธึมการนับโดยประมาณ (approximate counting) ของ Stockmeyer

จากที่ไม่รู้ว่าไม่รู้อะไร จนเริ่มเห็น subtlety จากการฟังทอล์ค (บ่อยๆ ทั้งรอบซ้อมรอบจริง) ของเพื่อนนักศึกษาปริญญาเอก ‪Gopikrishnan Muraleedharan‬ กับ Jacob Miller ที่ New Mexico จนกระทั่งปีที่แล้วที่ได้ร่วมทำงานเกี่ยวกับ quantum supremacy ใน driven many-body systems กับกลุ่มของ Dimitris Angelakis (สิงคโปร์) และเป็นส่วนหนึ่งของทีมของ Michał Oszmaniec (โปแลนด์) ที่นำเสนอการทดลอง quantum supremacy ใหม่เรีบกว่า Fermion Sampling โดยเฉพาะเปเปอร์สุดท้าย เรา close the gap เหมือนที่ eisert ทำแต่ใช้เทคนิตคนละอย่าง thanks to Movassagh ที่เป็นเทคนิคที่นักฟิสิกส์ใช้ได้ ลีกรุ๊ป

ไม่มีใตรที่เป็นนักวิทย์คอม (อาจจะยกเว้น Mauro ที่กำลังเรียนปริญญาเอกกับ Mick Bremner)

Mathematical physicist และ relativist Robert Geroch (เขาเขียนหนังสือ computational complexity สำหรับฟิสิกส์ด้วย มี quote แบบนี้ในเล่มนั้นรึเปล่า?)

[T]he mathematics one needs for theoretical physics can often be mastered simply by making a sufficient effort. This activity is quite different from, and far more straightforward than, the originality and creativity needed in physics itself.

• Harrow and Montanaro, Quantum computational supremacy, Nature (2017) รีวิว post-selection argument
• Pashayan, Bartlett and Gross, From estimation of quantum probabilities to simulation of quantum circuits, Quantum (2020) นิยามต่างๆ ของการจำลองและรีวิว Stockmeyer

• Hangleiter, Sampling and the complexity of nature, PhD Thesis, Freie Universität Berlin (2020)

• Arora and Barak, Computation Complexity: A Modern Approach (2007)

Noisy IQP

Power of data in QML

Quantum supremacy กับกาน้ำชา

proposing quantum experiments that can’t be done classically. The goal of chasing after quantum supremacy has been criticized on several grounds So i want to first argue why proving hardness is interesting nonetheless.

นักคณิตศาสตร์ Richard E. Borcherds วิจารณ์ด้วย “teapot test”

Aaronson, Why philosphers should care about computational complexity, Computability: Gödel, Turing, Church, and beyond (2012)

What needs to be proven (to get a paper published), Why they are evidence that the sampling is hard for classical computers (breakthrough pioneered by Terhal and DiVincenzo, and Aaronson and Arkhipov), and how to prove them even if you’re not a computer scientist. For the latter, I need to tell you first what you have to prove.

Back to VQA, the cost function that we’re often interested in like $\av{H}$ can’t be estimated in one shot and is only obtained by sampling. Thus, if there is a classical device that lets us sample exactly from the output distribution similar to that of the quantum device, the classical device can solve exactly the same problem that the quantum device can.

อีกนิยามของการจำลอง: คำนวณ vs สุ่มตัวอย่าง

ถ้าเราต้องการเห็น task ที่คอมพิวเตอร์ควอนตัม

ถ้าเราอยากพิสูจน์ quantum supremacy ของปัญหา

\[p_{\x}(U) = |\av{\x|U|\psi_{\rm in}}|^2\]

0. เลือกโมเดลของการสุ่ม
1. โชว์ว่ามี $p_x(U)$ ที่ประมาณค่าได้ยาก (อัลกอริธึมที่ประมาณ $p_x(U)$ ได้ทุกๆ instance จะแก้ทุกปัญหา $\shap$ ได้)
2. โชว์ว่า $p_x(U)$ ประมาณค่าได้ยาก “โดยเฉลี่ย” (อัลกอริธึมที่ประมาณ $p_x(U)$ ได้ใน instance ส่วนใหญ่จะแก้ทุกปัญหา $\shap$ ได้)
3. โชว์สมบัติของ ensemble ของ $p_x(U)$ ที่เรียกว่า anti-concentration

บาลานซ์ระหว่างความง่ายกับความยาก

• ความน่าจะเป็นไม่กระจุกอยู่ที่ผลการวัดส่วนน้อยมากเกินไป
• วงจรควอนตัมมีจำนวนพารามิเตอร์ไม่มากจนเกินไป
  • พารามิเตอร์มีค่าต่อเนื่อง (continuous)

  การ rule out การจำลองทำได้โดยตั้งอยู่บนข้อสันนิษฐานที่เป็นไปได้ (plausible conjecture) ทางความซับซ้อนเชิงการคำนวณ โดยปกติเราลือกจะ rule out ได้สองทาง โดยประมาณ (approximate sampling) จากการแจกแจง $q(U)$

  • Relative error $\eta \ge 0$ สำหรับทุกๆ บิตสตริง $\x$
  \[|p_{\x}(U)-q_{\x}(U)| \le \eta p_{\x}(U),\]
  • Additive error $\epsilon > 0$
  \[\sum_{\x}|p_{\x}(U)-q_{\x}(U)| \le \epsilon\]

ก่อนอื่นต้องทำความเข้าใจ

1. Terhal and DiVincenzo, Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games (2004) และ Bremner, Jozsa and Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy (2010) Result ของโมเดล DQC1 ก็เข้าใจว่าเป็นแบบนี้ ↩

2. ในเวทีนานาชาติมักจะใช้คำอื่นเช่น quantum advantage แทนด้วยเหตุผลว่าคำว่า supremacy มี connotation ทางลบทางประวัติศาสตร์จากอคติเหยียดคนผิวสี white supremacy ↩