P vs NP และการคำนวณเชิงควอนตัม

เมื่อปีที่แล้วเรามีโอกาสกลับไปคุยกับรุ่นน้องโรงเรียนเรื่องสารสนเทศควอนตัม คุยเรื่องเอนแทงเกิลเมนต์บ้าง เรื่องการแก้ความผิดพลาด (error correction) เชิงควอนตัมบ้าง แต่ไม่ได้คุยเรื่องการคำนวณเชิงควอนตัม(ที่ถูกถาม)เพราะไม่รู้จะอธิบายยังไงให้คนที่ไม่คุ้นทั้งควอนตัมและวิทยาศาสตร์คอมพิวเตอร์เข้าใจ อย่างน้อยสมัยตอนปริญญาตรีเราก็เข้าไม่ถึงมัน ควอนตัมคอมพิวเตอร์แก้ปัญหาอะไรก็ไม่รู้ได้เร็วขึ้น เร็วขึ้นเท่าไรก็ไม่รู้ จนกระทั่งเราเรียนควอนตัมอัลกอริธึม (วิธีที่ควอนตัมคอมพิวเตอร์ใช้แก้ปัญหา) จาก Cristopher Moore ตอนปีหนึ่งเทอมหนึ่งของปริญญาเอก (ซึ่งปัจจุบันเป็นหนึ่งในกรรมการวิทยานิพนธ์ของเรา ไม่แปลกใจที่ approach ในโพสท์นี้ได้รับอิทธิพลจากหนังสือ The Nature of Computation ที่เขาเขียน) และจับกลุ่มกับนักเรียนคนอื่นอ่านเรื่องปัญหาต่างๆในวิทยาศาสตร์คอมพิวเตอร์ระหว่างซัมเมอร์ ถึงจะ appreciate มันได้เต็มที่

เกมและการเดินเล่น

image-koenigsberg2c_map_by_merian-erben_1652

นี่คือหน้าตาของเมือง Königsberg ในศตวรรษที่ 18 (Kaliningrad, รัสเซียในปัจจุบัน) แม่น้ำ Pregel ไหลตัดแยกตัวเมืองเป็นสี่ “เกาะ” ที่เชื่อมกันด้วยสะพานเจ็ดสะพาน (ปัจจุบันเหลือแค่ห้าจากการทิ้งระเบิดสมัยสงครามโลกครั้งที่สอง) เรื่องเล่ามีอยู่ว่าชาวเมืองมักจะใช้เวลาบ่ายวันอาทิตย์เดินข้ามสะพานชมเมือง ทำให้เกิดความสงสัยว่าเป็นไปได้ไหมที่จะข้ามสะพานครบทั้งเจ็ดสะพานโดยไม่ข้ามสะพานใดสะพานหนึ่งมากกว่าหนึ่งครั้ง?

อีกปัญหาที่มีความคล้ายกันมากมาจากเกมที่ชาวไอริช William Rowan Hamilton คิดขึ้นในปี 1857 (คนเดียวกับที่คิด quaternion กับกลศาสตร์ Hamilton ที่คนเรียนฟิสิกส์รู้จักน่ะแหละ) ชื่อว่าเกม Icosian เป็นการหาเส้นทางเดินบนขอบ (ที่เป็นเส้นหนึ่งมิติ ไม่ใช่หน้า) ของรูปเหลี่ยม 12 หน้า (dodecahedron) ที่ผ่านทุกมุมแต่ไม่ผ่านมุมใดมุมหนึ่งมากกว่าหนึ่งครั้ง ซึ่งไม่ต่างกับการหาเส้นทางเดินผ่านทุกเกาะโดยไม่ผ่านเกาะเดิมมากกว่าหนึ่งครั้ง  รูปซ้ายเป็นตัวอย่างของรูปเหลี่ยม 12 หน้า

acprof_9780199233212_graphic_005

รูปขวาคือรูปซ้ายที่ถูกอัดให้แบนเป็นกราฟ (graph) สองมิติ กราฟมีโหนด (vertex หรือจุดยอด) และเส้นเชื่อม (edge) ระหว่างโหนด เกม Icosian ถามหาเส้นทางเดินบนกราฟที่ผ่านทุกๆโหนดแต่ไม่ผ่านโหนดใดโหนดหนึ่งมากกว่าหนึ่งครั้ง ในขณะที่ปัญหาสะพานทั้งเจ็ดของ Königsberg ถามหาเส้นทางเดินบนกราฟด้านล่างที่ผ่านทุกๆเส้นเชื่อมแต่ไม่ผ่านเส้นเชื่อมใดเส้นเชื่อมหนึ่งมากกว่าหนึ่งครั้ง

200px-kc3b6nigsberg_graph-svg

เส้นทางที่เป็นคำตอบของปัญหาแรกถูกเรียกชื่อในภายหลังว่าเส้นทาง Euler (Eulerian path) เพราะ Leonhard Euler ชาวสวิตเซอร์แลนด์ที่ช่วงนั้นทำงานอยู่ที่ Saint Petersburg (เพราะได้รับการชักชวนจาก Daniel Bernoulli เจ้าของหลักการเกี่ยวกับของไหลที่เรียนกันในฟิสิกส์ เพื่อมาแทน Nicolaus Bernoulli ที่ป่วยตาย) สังเกตว่ากราฟจะมีเส้นทาง Euler ก็ต่อเมื่อไม่มีโหนดที่มีเส้นออกจากโหนดเป็นจำนวนคี่ หรือถ้ามีก็มีแค่สองโหนด เพราะการผ่านโหนดใดโหนดหนึ่งโดยไม่เดินซ้ำเส้นทางเดิมจะต้องมีทางเข้าทางหนึ่งกับทางออกทางหนึ่ง แต่โหนดเริ่มต้นไม่ต้องมีทางเข้าและโหนดสุดท้ายไม่ต้องมีทางออก (เหตุผลที่เราบอกก็เพื่อให้พอจะเชื่อได้ว่ามันเป็นจริงเท่านั้น ไม่ใช่การพิสูจน์จริงๆ)

ข้อสังเกตนี้ลึกซึ้งที่ว่ามันไม่ใช่ข้อสังเกตเกี่ยวกับปัญหาสะพานทั้งเจ็ดของ Königsberg เท่านั้นแต่เป็นข้อสังเกตเกี่ยวกับทุกๆกราฟ และข้อสังเกตนี้บอกขั้นตอนการหาคำตอบหรืออัลกอริธึม (algorithm) ที่มีประสิทธิภาพ สิ่งที่เราต้องทำก็แค่นับเส้นเชื่อมที่ออกจากแต่ละโหนด สมมติว่าเราเช็คแต่ละเส้นเชื่อมของแต่ละโหนดได้ในหนึ่งสเต็ปเวลา ถ้าให้ n เป็นจำนวนโหนดและ e เป็นจำนวนเส้น เราจะใช้เวลาอย่างมากแค่ ne < n2  สเต็ป

แต่จนถึงทุกวันนี้ยังไม่มีใครรู้อัลกอริธึมที่หาคำตอบของเกม Icosian (เรียกว่าเส้นทาง Hamilton) อย่างมีประสิทธิภาพในกราฟทั่วไปได้เลย ซึ่งคิดดูแล้วน่าทึ่งเพราะปัญหาของ Hamilton ต่างกับปัญหาของ Euler เพียงแค่การเปลี่ยนเส้นเชื่อมเป็นโหนดเท่านั้นเอง

การโตแบบทวีคูณ

อัลกอริธึมที่ใช้ได้กับทั้งสองปัญหาก็คือลองเดินมันโง่ๆทุกเส้นทางบนกราฟแล้วดูว่ามีเส้นทางที่ต้องการไหม สมมติว่าเราอยู่บน complete graph ที่ทุกโหนดเชื่อมกับทุกโหนด ถ้าให้ n เป็นจำนวนโหนด จำนวนเส้นทางที่ต้องเดินก็โตแบบทวีคูณ (exponential) ใน n คือเป็นเลขยกกำลังที่มีกำลังของ n เป็นกำลัง (กำลังเยอะจัง)

  • ถ้าจะให้เดินไม่ซ้ำโหนดก็เลือกหนึ่งใน n โหนดก่อน ทำให้เหลือ n-1 โหนดที่จะไปได้ในเสต็ปแรก n-2 โหนดที่จะไปได้ในเสต็ปที่สอง… จนครบทุกโหนด ซึ่งให้ n!≈2n log n ด้วยการประมาณ Stirlingที่นักเรียนฟิสิกส์ต้องเคยใช้
  • ถ้าจะให้เดินไม่ซ้ำเส้นก็เลือกหนึ่งใน n โหนดก่อน ประมาณหยาบๆว่าแต่ละสเต็ปมีทางเดินให้เลือก n ทางและ n2 เป็นความยาวของทางเดินที่ยาวที่สุด ทำให้ได้ nn2≈2n2log n ด้วยการประมาณ Stirling

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

  • 1,000,000 เม็ดในช่องที่ 20
  • 1,000,000,000,000 เม็ดในช่องที่ 40
  • 18,000,000,000,000,000,000 เม็ดในช่องสุดท้ายซึ่งตีได้เป็น 460,000,000 ตัน (ถ้าจะเปรียบเทียบก็หนักกว่ามหาพีระมิดแห่งกีซาถึง 70 เท่า)

rice-on-chessboard

บางเวอร์ชันของเรื่องเล่านี้จบลงที่พระราชาสั่งประหารคนผู้นั้นเมื่อรู้ตัวว่าโดนหลอกเข้าให้แล้ว บทเรียนหนึ่งของเรื่องนี้ก็คืออย่าไปกวนตีนคนที่มีอำนาจมากนัก แต่อีกบทเรียนที่สำคัญกว่าสำหรับจุดประสงค์ของบทความนี้ก็คือการโตของตัวเลขแบบทวีคูณนั้นรวดเร็วเกินกว่าที่จะจินตนาการได้  ถึงจะใช้ซูเปอร์คอมพิวเตอร์ที่ทำการคำนวณได้กว่า 1015 สเต็ปในหนึ่งวินาที (petaflop) ก็ยังอาจต้องใช้เวลาเกินอายุปัจจุบันของเอกภพ 13.7 พันล้านปี (ประมาณ 1017 วินาที) ถ้าอัลกอริธึมใช้เวลาเป็นทวีคูณของขนาด n ของปัญหา

runtime_comparison

อัลกอริธึมที่ช้าจึงไม่ใช่แค่ไม่ทันใจ อาจจะไม่ทันโลกแตกด้วยซ้ำ! (ดวงอาทิตย์อยู่ได้อีกแค่ประมาณห้าพันล้านปี)

P vs NP

ก่อนที่ผู้อ่านจะไปคิดค้นอัลกอริธึมแก้เกม Icosian เรามีข่าวดีกับข่าวร้ายจะบอก ข่าวดีก็คือถ้าหาอัลกอริธึมที่มีประสิทธิภาพได้หรือพิสูจน์ได้ว่าไม่มีอัลกอริธึมที่มีประสิทธิภาพจะได้เงินสิบล้านเหรียญสหรัฐทันที ไม่ใช่จากเราเพราะเราไม่มีเงินมากขนาดนั้น แต่จาก Clays Mathematics Institute  เพราะคำตอบของปัญหานี้จะแก้ปัญหา P vs NP ซึ่งเป็นหนึ่งในหกปัญหาแห่งสหัสวรรษ (millennium problems) ที่ยังไม่มีคำตอบ

ปัญหา P vs NP คืออะไร? P คือคลาสของปัญหาที่แก้ได้ในเวลา(จำนวนสเต็ป)ที่เป็นพหุนาม (polynomial) ของ n (เช่น n2, n3 และผลรวมของมัน) ในขณะที่ NP คือคลาสของปัญหาที่เช็คคำตอบได้ในเวลาพหุนาม ทั้งการหาเส้นทาง Euler และ Hamilton เป็นปัญหา NP ถ้ามีคนให้เส้นทางเดินมาเราก็แค่เดินตามและเช็คว่าเดินซ้ำเส้นเชื่อมหรือโหนดเดิมหรือไม่

นักวิทยาศาสตร์คอมพิวเตอร์ถือว่าปัญหาใน P แก้ได้อย่างมีประสิทธิภาพ จริงอยู่ที่ว่าปัญหาที่แก้ได้ในเวลา n1000000 ก็อยู่ใน P เช่นกันแต่ในทางปฏิบัติเรามักจะเจอแต่กำลังน้อยๆ [1] ในขณะที่ไม่มีใครรู้วิธีแก้ปัญหา NP ที่ไม่อยู่ใน P ในกรณีที่แย่ที่สุดได้ดีกว่าการลองเช็คทุกๆคำตอบสักเท่าไร (เราหาเส้นทาง Hamilton ในกราฟของสะพานทั้งเจ็ดของ Königsberg ได้ง่ายๆแต่เราทำอย่างนั้นไม่ได้กับทุกๆกราฟ)

ตั้งแต่ปี 1971 ถึงปัจจุบันเรารู้แล้วว่าปัญหาของ Hamilton และอีกหลายร้อยปัญหาใน NP อย่างการจัดตารางการบิน, การขดตัวของโปรตีน, การแก้ Ising model ในสามมิติ, การพิสูจน์ทฤษฎีบทในคณิตศาสตร์, หรือเกมนินเทนโดจริงๆแล้วเป็นปัญหาเดียวกันหมดเรียกว่าปัญหา NP-complete และถ้าแก้ปัญหานี้ได้ก็จะแก้ปัญหาทุกปัญหาใน NP ได้อย่างมีประสิทธิภาพ (และอาจจะพาให้นักคณิตศาสตร์นักวิทยาศาสตร์ตกงานกันหมด เหลือแต่นักเขียนโปรแกรม)

ยังไม่มีใครสามารถพิสูจน์ได้ว่าปัญหา NP-complete อยู่นอก P และถ้าหาอัลกอริธึมสำหรับปัญหา NP-complete อย่างการหาเส้นทาง Hamilton ที่มีประสิทธิภาพได้ก็แปลว่าไม่มีปัญหาไหนใน NP ที่อยู่นอก P หลายทศวรรษที่ผ่านมาให้กำเนิดกว่าร้อยเปเปอร์ที่พิสูจน์ว่า P=NP หรือ P≠NP แต่ก็ยังไม่มีใครเคลมหนึ่งล้านเหรียญสหรัฐไปได้ เพราะฉะนั้นข่าวร้ายสำหรับคนที่อยากลองแก้ปัญหานี้ก็คือมันอาจจะไม่ใช่ปัญหาเอาไว้แก้เล่นฆ่าเวลาเพราะอาจจะต้องฆ่าไปเป็นทศวรรษ

การคำนวณเชิงควอนตัม

นักวิทยาศาสตร์คอมพิวเตอร์ส่วนใหญ่เชื่อว่า P≠NP เพราะเราไม่เคยแก้ปัญหา NP-complete ได้อย่างมีประสิทธิภาพและไม่เคยเห็นธรรมชาติแก้ปัญหา NP-complete ได้อย่างมีประสิทธิภาพ เราอาจจะคิดว่าแก้ปัญหาการหดตัวของโปรตีนได้โดยการดูโปรตีนจริงๆขดตัว แต่โปรตีนจริงๆก็ขดตัวผิดพลาดได้อย่าง prion ที่ทำให้เกิดโรควัวบ้า หรือมีคนคิดแก้ปัญหา NP-complete โดยการรอให้ระบบฟิสิกส์ตกลงสู่ระดับชั้นพลังงานต่ำสุดซึ่งเราอาจจะคิดว่าก็เป็นพฤติกรรมปกติของระบบฟิสิกส์ก็พบว่าถึงจะเป็นระบบควอนตัมก็ยังต้องรอเป็นเวลาเป็นทวีคูณ ยังไม่มีใครรู้วิธีแก้ปัญหา NP-complete อย่างมีประสิทธิภาพด้วยควอนตัมอัลกอริธึม ยิ่งไปกว่านั้นยังไม่มีใครพิสูจน์ได้ว่าควอนตัมอัลกอริธึมนั้นเร็วกว่าอัลกอริธึมที่เร็วที่สุดโดยไม่เริ่มต้นจากสมมติฐานทำนองเดียวกันกับ P≠NP

(นี่เป็นจุดที่ข่าวควอนตัมคอมพิวเตอร์มักจะพลาด อธิบายความเร็วของควอนตัมอัลกอริธึมจากความสามารถในการลองทุกคำตอบพร้อมๆกัน อีกนิยามหนึ่งของปัญหาในคลาส NP คือปัญหาที่แก้ได้อย่างมีประสิทธิภาพถ้าหากเราสามารถลองทุกคำตอบพร้อมๆกันได้ (การคำนวณแบบ non-deterministic) เป็นที่มาของชื่อ NP: Non-deterministic polynomial-time)

ถ้าควอนตัมอัลกอริธึมแก้ทุกปัญหา NP ไม่ได้แล้วเราจะสนใจมันทำไม? มีหลายเหตุผลที่ทำให้มันน่าสนใจซึ่งเราจะพูดถึงในโพสท์ต่อๆไป เช่น

  1. ควอนตัมอัลกอริธึมของ Lov Grover ช่วยหาคำตอบจากทั้งหมด n คำตอบของปัญหา NP ได้ด้วยเวลา \sqrt{n} ซึ่งไม่ทำให้ P=NP แต่ก็เร็วกว่าอัลกอริธึมธรรมดาซึ่งใช้เวลา n ในกรณีที่แย่ที่สุด
  2. ควอนตัมอัลกอริธึมของ Peter Shor แก้ปัญหาการแยกตัวประกอบและทำลายการเข้ารหัสบัตร ATM ในปัจจุบันซึ่งเป็นปัญหา NP แต่เชื่อว่าไม่ NP-complete ได้อย่างมีประสิทธิภาพในขณะที่ยังไม่มีใครค้นพบอัลกอริธึมธรรมดาที่มีประสิทธิภาพ
  3. Boson Sampling ของ Alex Arkhipov และ Scott Aaronson ใช้ในการประมาณ permanent ของเมทริกซ์ซึ่งเชื่อว่าเป็นปัญหาที่อยู่นอก NP
  4. ควอนตัมคอมพิวเตอร์จำลองระบบฟิสิกส์ได้ทุกระบบที่ใช้ควอนตัมอธิบายได้ นี่เป็นเหตุผลที่นักวิทยาศาสตร์ทั้งฟิสิกส์,เคมี,ชีวะสนใจมากที่สุด

ถ้าเหตุผลเหล่านี้ยังไม่พอก็ยังมีอีกเหตุผล: การเข้าใจควอนตัมอัลกอริธึมคือการเข้าใจความคิดของควอนตัมคอมพิวเตอร์—เข้าใจการคิดแบบควอนตัม

[1] เรามักจะไม่พูดถึงอัลกอริธึมที่ใช้เวลาน้อยกว่า n เพราะนั่นเป็นเวลาที่ต้องใช้ในการอ่านอินพุตของปัญหา ถึงแม้ในความเป็นจริงอัลกอริธึมที่ไม่ต้องอ่านอินพุตทั้งหมด (sublinear algorithm) อย่าง compressed sensing ก็เป็นที่สนใจ ส่วนว่าทำไมใช้พหุนามแทน n เฉยๆก็เพราะอัลกอริธึมที่อาศัยอัลกอริธึมที่ใช้เวลา n เป็น subroutine อาจจะใช้เวลา n2, n3 ได้แต่ก็ยังเป็นพหุนามอยู่ (จริงๆแล้วต้องใช้ Big O notation ถึงจะเข้าใจได้)