ในปี 1994 นักคณิตศาสตร์คนหนึ่งค้นพบวิธีทำให้คอมพิวเตอร์ควอนตัมทำสิ่งที่คอมพิวเตอร์คลาสสิกธรรมดาไม่สามารถทำได้ งานวิจัยเผยให้เห็นว่า โดยหลักการแล้ว เครื่องจักรที่ตามกฎของกลศาสตร์ควอนตัมสามารถแยกปัจจัยจำนวนมากออกเป็นปัจจัยสำคัญได้อย่างมีประสิทธิภาพ ซึ่งเป็นงานที่ยากสำหรับคอมพิวเตอร์คลาสสิกจนเป็นพื้นฐานสำหรับความปลอดภัยทางอินเทอร์เน็ตส่วนใหญ่ในปัจจุบัน
การเพิ่มขึ้นของการมองโลกในแง่ดีตามมา บางที นักวิจัยคิดว่า เราสามารถประดิษฐ์อัลกอริทึมควอนตัม ที่สามารถแก้ปัญหาต่างๆ ได้มากมาย
แต่ความคืบหน้าหยุดชะงัก “มันเป็นเส้นทางที่ไม่ค่อยดีนัก” . กล่าว Ryan O'Donnell ของมหาวิทยาลัยคาร์เนกี้ เมลลอน “ผู้คนก็แบบว่า 'นี่น่าทึ่งมาก ฉันแน่ใจว่าเราจะได้อัลกอริธึมที่น่าอัศจรรย์ทุกประเภท' ไม่." นักวิทยาศาสตร์ค้นพบการเร่งความเร็วอย่างมากสำหรับปัญหาประเภทแคบๆ เดียวจากภายในชุดมาตรฐาน เรียกว่า นพซึ่งหมายความว่าพวกเขามีโซลูชันที่ตรวจสอบได้มีประสิทธิภาพ เช่น แฟคตอริ่ง
เป็นเช่นนี้มาเกือบสามทศวรรษแล้ว จากนั้นในเดือนเมษายน นักวิจัย คิดค้น เป็นปัญหารูปแบบใหม่โดยพื้นฐานที่คอมพิวเตอร์ควอนตัมควรจะสามารถแก้ปัญหาได้เร็วกว่าปัญหาทั่วไปแบบทวีคูณ มันเกี่ยวข้องกับการคำนวณอินพุตของกระบวนการทางคณิตศาสตร์ที่ซับซ้อน โดยอิงจากผลลัพธ์ที่สับสนเท่านั้น ไม่ว่าปัญหาจะเกิดขึ้นเพียงลำพังหรือเป็นปัญหาแรกในพรมแดนใหม่ของปัญหาอื่น ๆ อีกมากมายนั้นยังไม่เป็นที่แน่ชัด
“มีความรู้สึกตื่นเต้น” . กล่าว วิโนดไวกุลธนนักวิทยาศาสตร์คอมพิวเตอร์ที่สถาบันเทคโนโลยีแมสซาชูเซตส์ “หลายคนกำลังคิดว่ามีอะไรอีกบ้าง”
นักวิทยาศาสตร์คอมพิวเตอร์พยายามทำความเข้าใจว่าคอมพิวเตอร์ควอนตัมทำอะไรได้ดีกว่าโดยศึกษาแบบจำลองทางคณิตศาสตร์ที่เป็นตัวแทนของพวกมัน บ่อยครั้งที่พวกเขาจินตนาการถึงแบบจำลองของคอมพิวเตอร์ควอนตัมหรือคลาสสิกที่จับคู่กับเครื่องคำนวณในอุดมคติที่เรียกว่าออราเคิล Oracles เป็นเหมือนฟังก์ชันทางคณิตศาสตร์อย่างง่ายหรือโปรแกรมคอมพิวเตอร์ โดยรับอินพุตและแยกเอาต์พุตที่กำหนดไว้ล่วงหน้า พวกเขาอาจมีพฤติกรรมสุ่ม โดยแสดง "ใช่" หากอินพุตอยู่ในช่วงสุ่ม (เช่น 12 ถึง 67) และ "ไม่" หากไม่เป็นเช่นนั้น หรืออาจเป็นแบบเป็นระยะๆ เพื่อให้อินพุตระหว่าง 1 ถึง 10 คืนค่า "ใช่" 11 ถึง 20 ให้ "ไม่ใช่" 21 ถึง 30 ให้ผลลัพธ์ "ใช่" อีกครั้ง เป็นต้น
สมมุติว่าคุณมีออราเคิลเป็นระยะตัวหนึ่งและคุณไม่รู้ช่วงเวลานั้น สิ่งที่คุณทำได้คือป้อนตัวเลขและดูสิ่งที่ส่งออก ด้วยข้อจำกัดเหล่านั้น คอมพิวเตอร์สามารถหาช่วงเวลาได้เร็วแค่ไหน? ในปี 1993 แดเนียล ไซมอน ที่มหาวิทยาลัยมอนทรีออล พบว่าอัลกอริธึมควอนตัมสามารถคำนวณคำตอบของปัญหาที่เกี่ยวข้องอย่างใกล้ชิดได้เร็วกว่าอัลกอริธึมทั่วไปแบบทวีคูณ
ผลลัพธ์ที่ได้ทำให้ไซมอนสามารถกำหนดหนึ่งในคำแนะนำแรกๆ ที่คาดว่าจะมีความเหนือกว่าอย่างมากสำหรับคอมพิวเตอร์ควอนตัม แต่เมื่อเขาส่งบทความไปยังการประชุมชั้นนำ มันถูกปฏิเสธ อย่างไรก็ตาม บทความนี้ได้ให้ความสนใจสมาชิกรุ่นน้องของคณะกรรมการโปรแกรมการประชุม — ปีเตอร์ ชอร์ซึ่งตอนนั้นอยู่ที่ Bell Laboratories ในรัฐนิวเจอร์ซีย์ Shor พบว่าเขาสามารถปรับอัลกอริธึมของ Simon เพื่อคำนวณระยะเวลาของ oracle ได้ หากมี จากนั้นเขาก็ตระหนักว่าเขาสามารถปรับอัลกอริธึมได้อีกครั้ง เพื่อแก้สมการที่มีพฤติกรรมคล้ายกับออราเคิลแบบคาบ ซึ่งก็คือสมการที่อธิบายแฟคตอริ่งซึ่งเป็นคาบ
ผลงานของ Shor เป็นประวัติศาสตร์ อัลกอริธึมควอนตัมที่เขาค้นพบสามารถลดจำนวนมหาศาลลงในปัจจัยเฉพาะที่เป็นส่วนประกอบได้อย่างรวดเร็ว ซึ่งไม่มีอัลกอริธึมแบบคลาสสิกที่รู้จักสามารถทำได้ ในปีถัดมา นักวิจัยได้ค้นพบอัลกอริธึมควอนตัมที่มีประสิทธิภาพอื่นๆ บางส่วน เช่น อัลกอริธึมของ Shor แม้จะให้ความได้เปรียบแบบทวีคูณ แต่ก็ไม่มีใครพิสูจน์ความได้เปรียบเชิงควอนตัมอย่างมากในปัญหา NP ที่ไม่ได้เป็นระยะๆ ได้
การขาดความก้าวหน้านี้ทำให้นักวิทยาศาสตร์คอมพิวเตอร์สองคน สกอตต์ อารอนสัน แห่งมหาวิทยาลัยเท็กซัส ออสติน และ อันดริส อัมไบนิส ของมหาวิทยาลัยลัตเวียเพื่อทำการสังเกตการณ์ การพิสูจน์ความได้เปรียบของควอนตัมมักขึ้นอยู่กับคำพยากรณ์ที่มีโครงสร้างที่ไม่สุ่มเช่นระยะ ในปี 2009 พวกเขา คาดคะเน ว่าจะไม่มีการเร่งความเร็วอย่างมากในปัญหา NP ที่สุ่มหรือไม่มีโครงสร้าง ไม่มีใครสามารถหาข้อยกเว้นได้
การคาดเดาของพวกเขาผูกมัดพลังของคอมพิวเตอร์ควอนตัม แต่มันกล่าวเพียงว่าไม่มีการเร่งความเร็วอย่างมากสำหรับปัญหา NP ที่ไม่มีโครงสร้างเฉพาะประเภท - ผู้ที่มีคำตอบใช่หรือไม่มี หากปัญหาเกี่ยวข้องกับการหาคำตอบเชิงปริมาณที่เฉพาะเจาะจงมากขึ้น ซึ่งเรียกว่าปัญหาการค้นหา การคาดเดาก็ใช้ไม่ได้
ด้วยเหตุนี้ นักวิจัย ทาคาชิ ยามาคาวะ ของ NTT Social Informatics Laboratories และ มาร์ค แซนดรี ของ NTT Research และ Princeton University ตัดสินใจทดลองกับปัญหาการค้นหาที่เฉพาะเจาะจง ซึ่งเปิดตัวในปี 2005 โดย โอเดด เรเจฟ.
ลองนึกภาพชุดใบพัดสภาพอากาศที่ชี้ไปในทิศทางเดียวกัน ให้แต่ละคนดันวัด แล้วปล่อยให้ลมแรงพัดมามีอิทธิพลต่อทิศทางของพวกเขา Regev ต้องการกำหนดตามทิศทางสุดท้ายของพวกเขาซึ่งพวกเขาทั้งหมดชี้ไปในตอนแรก ปัญหาเช่นนี้จึงถูกเรียกว่า “การเรียนรู้โดยผิดพลาด” เพราะการผลักและลมกระทำเหมือนเป็นที่มาของความผิดพลาดแบบสุ่มในทิศทางเดิม มีหลักฐานว่าการแก้ปัญหาทั้งอัลกอริธึมคลาสสิกและควอนตัมเป็นเรื่องยาก
Yamakawa และ Zhandry ปรับแต่งการตั้งค่า พวกเขาปรับเปลี่ยนความแข็งแกร่งของหมัดเริ่มต้นเหล่านั้น ทำให้คาดเดาได้มากขึ้น พวกเขายังทำให้ลมถูกกำหนดโดยคำทำนายที่สุ่มขึ้นเพื่อให้มันสุ่มมากขึ้นในบางกรณีแต่ก็อยู่เฉยๆอย่างสมบูรณ์ในผู้อื่น
ด้วยการปรับเปลี่ยนเหล่านี้ นักวิจัยได้ค้นพบว่าอัลกอริธึมควอนตัมสามารถค้นหาทิศทางเริ่มต้นได้อย่างมีประสิทธิภาพ พวกเขายังพิสูจน์ด้วยว่าอัลกอริธึมแบบคลาสสิกใด ๆ จะต้องช้าลงด้วยปัจจัยเลขชี้กำลัง เช่นเดียวกับ Shor พวกเขาปรับอัลกอริทึมเพื่อแก้ปัญหาในเวอร์ชันจริง ซึ่งจะแทนที่ oracle ด้วยสมการทางคณิตศาสตร์ที่แท้จริง
นักวิทยาศาสตร์คอมพิวเตอร์ยังคงทำงานเพื่อทำความเข้าใจและสร้างปัญหา Vaikuntanathan เปรียบเทียบกับรูปแบบอื่นที่เกิดขึ้นเมื่อทำการบีบอัดข้อมูล: เมื่อข้อมูลถูกบีบอัดลง บิตสองบิตสามารถถูกบีบลงในที่เดียวกันโดยไม่ได้ตั้งใจและเขียนทับได้ ปัญหาในการทำนายการชนกันล่วงหน้า เพื่อที่คุณจะหลีกเลี่ยงได้นั้น มีความคล้ายคลึงอยู่บ้าง “นั่นเป็นปัญหาประเภทหนึ่งซึ่งโดยทั่วไปแล้วจะมีลักษณะเช่นนี้” เขากล่าว “บางทีปัญหาเหล่านี้สามารถแก้ไขได้อย่างควอนตัม”
มีความหวังว่าปัญหาที่ไม่มีโครงสร้างเช่นปัญหาใหม่อาจแก้ไขได้แม้ในคอมพิวเตอร์ควอนตัมเวอร์ชันที่เพิ่งเริ่มต้นในปัจจุบัน ดังนั้นจึงเป็นช่องทางในการทดสอบ แนวคิดก็คือปัญหาที่ไม่มีโครงสร้างอาจใช้ทรัพยากรในการเขียนโปรแกรมน้อยลง หรือไวต่อสัญญาณรบกวนน้อยลง เนื่องจากปัญหาเหล่านี้สุ่มแล้ว แต่จนถึงตอนนี้ ปัญหาใหม่ยังคงปรากฏว่าขั้นสูงเกินกว่าที่คอมพิวเตอร์ควอนตัมที่มีอยู่จะแก้ไขได้ “มันเป็นปัญหาที่แปลก ฉันไม่ได้คิดที่จะกำหนดมัน” Aaronson กล่าว “แต่เมื่อมองย้อนกลับไป มันมีคุณสมบัติที่ดีมาก”
ผลที่ได้คือตัวอย่างแรกของความได้เปรียบเชิงควอนตัมอย่างมากในปัญหา NP ที่ไม่มีโครงสร้าง จะมีปัญหาอื่นอีกมากมายที่โลกควอนตัมเปลี่ยนจากที่แก้ไม่ได้จริงเป็นแก้ปัญหาไม่ได้? ตอนนี้มีเหตุผลมากขึ้นที่จะคิดอย่างนั้น
O'Donnell กล่าวว่า "มันค่อนข้างพลิกกลับความเชื่อของเราเกี่ยวกับปัญหาประเภทใดที่คอมพิวเตอร์ควอนตัมสามารถทำได้" O'Donnell กล่าว
