นักวิทยาศาสตร์ของ NTT กล่าวว่าพวกเขามีวิธีการใหม่ในการตรวจสอบข้อได้เปรียบของควอนตัม

ซันนีเวล แคลิฟอร์เนีย – 26 ตุลาคม 2022 – NTT Research ประกาศว่านักวิทยาศาสตร์จาก ห้องปฏิบัติการเข้ารหัสและความปลอดภัยของข้อมูล (CIS) และเพื่อนร่วมงานจาก ห้องปฏิบัติการสารสนเทศเพื่อสังคมของเอ็นทีที (SIL) ได้เขียนรายงานเกี่ยวกับข้อได้เปรียบเชิงควอนตัม บทความนี้ได้รับเลือกให้นำเสนอในการประชุมประจำปี IEEE Symposium on Foundations of Computer Science (FOCS) ซึ่งจะจัดขึ้นในวันที่ 31 ต.ค. - พ.ย. 3 ในเดนเวอร์

ผู้ร่วมเขียนบทความเรื่อง “ข้อได้เปรียบเชิงควอนตัมที่ตรวจสอบได้โดยไม่มีโครงสร้าง” คือ ดร.ทาคาชิ ยามาคาวะ นักวิจัยดีเด่นของ NTT SIL และ ดร.มาร์ค ซันดรี นักวิทยาศาสตร์อาวุโสใน เอ็นทีที วิจัย ห้องปฏิบัติการซีไอเอส งานนี้ทำในบางส่วนที่มหาวิทยาลัยพรินซ์ตัน ซึ่ง ดร. ยามาคาว่า เป็นนักวิชาการด้านการวิจัยที่มาเยี่ยม และดร. แซนดรียังทำหน้าที่เป็นผู้ช่วยศาสตราจารย์ด้านวิทยาการคอมพิวเตอร์อีกด้วย 

หัวข้อของข้อได้เปรียบของควอนตัม (หรือการเพิ่มความเร็วของควอนตัม) เกี่ยวข้องกับประเภทของปัญหาที่คอมพิวเตอร์ควอนตัมสามารถแก้ไขได้เร็วกว่าคอมพิวเตอร์ทั่วไปหรือไม่ใช่ควอนตัม และเร็วกว่ามากเพียงใด ปัญหาที่เป็นปัญหามักถูกอธิบายเป็นคลาส non-deterministic polynomial-time (NP) ความได้เปรียบจะแปรผันไปมากเพียงใด คอมพิวเตอร์ควอนตัมอาจสามารถแก้ปัญหาบางอย่างได้ภายในหนึ่งนาทีหรือหนึ่งวินาที ซึ่งใช้เวลากับคอมพิวเตอร์แบบคลาสสิกหนึ่งสัปดาห์ หรืออาจใช้เวลาเป็นเลขชี้กำลังอย่างไม่อาจหยั่งรู้ได้ ในบทความนี้ ผู้เขียนกล่าวถึงความท้าทายในการตรวจสอบความเหนือกว่านี้ และดำเนินการอย่างมีประสิทธิภาพ จนถึงปัจจุบัน การสาธิตความได้เปรียบของควอนตัมได้เกี่ยวข้องกับ "โครงสร้าง" ที่สำคัญหรือการสื่อสารไปมาระหว่างสองฝ่ายขึ้นไป ความก้าวหน้าของกระดาษ Yamakawa และ Zhandry คือการแสดงให้เห็นถึงปัญหาที่ยากของ NP ซึ่งการตรวจสอบเป็นไปได้โดยไม่มีโครงสร้าง

"นี่เป็นครั้งแรกที่เราได้เห็นการเร่งความเร็วของควอนตัมแบบเอ็กซ์โปเนนเชียลสำหรับปัญหาการค้นหา NP ซึ่งต้องใช้คำพยากรณ์แบบสุ่มเท่านั้น" ศาสตราจารย์ด้านวิทยาการคอมพิวเตอร์จากมหาวิทยาลัยเทกซัสออสติน ดร. สก็อตต์ แอรอนสัน ผู้ให้ความเห็นเกี่ยวกับเวอร์ชันแรกๆ กล่าว ของบทความระหว่างการประชุมเชิงปฏิบัติการเมื่อวันที่ 13 มิถุนายน พ.ศ. 2022 ที่ Simons Institute for the Theory of Computing โดยต้องการเพียงออราเคิลสุ่ม นั่นคือ กล่องดำตามทฤษฎีที่สร้างคำตอบแบบสุ่มสำหรับแต่ละคำถาม ยามาคาว่าและแซนดรีสร้างปัญหาขึ้นบนสมมติฐานทางคอมพิวเตอร์ที่ไม่มีโครงสร้าง ดังนั้น ปัญหาของพวกเขาจึงสอดคล้องกับฟังก์ชันทางเดียวมากกว่าฟังก์ชันที่มีโครงสร้าง เช่น ที่พบในการเข้ารหัสคีย์สาธารณะ การจัดตำแหน่งทางเดียวนั้นอำนวยความสะดวกในการตรวจสอบอย่างมีประสิทธิภาพ

“เป็นเรื่องน่าตื่นเต้นที่ได้เห็นนักเข้ารหัสลับในเครือ NTT ทำงานร่วมกันในการวิจัยซึ่งได้รับฉลากของ 'ความก้าวหน้า' อีกครั้ง โดยเฉพาะอย่างยิ่งในบทความที่เสริมสร้างความเข้าใจของเราเกี่ยวกับการคำนวณควอนตัม ซึ่งเป็นอีกประเด็นหนึ่งที่เรามุ่งเน้นที่ NTT Research” Kazuhiro Gomi กล่าว , NTT Research ประธานและ CEO. “ขอแสดงความยินดีและขอแสดงความยินดีกับผู้เข้าร่วมทุกคนในการประชุม IEEE อันทรงเกียรตินี้” 

ปัญหาการค้นหา NP ที่ Yamakawa และ Zhandry คิดขึ้นคือปัญหาสองในหนึ่งเดียวที่ทำให้เกิดการค้นหา 1) สตริงสัญลักษณ์ n ที่เป็นคำรหัสของรหัสการแก้ไขข้อผิดพลาดที่กำหนด และ 2) สตริงสัญลักษณ์ n ที่แต่ละ สัญลักษณ์ถูกแมปเป็นศูนย์ภายใต้ออราเคิลสุ่ม แต่ละปัญหาแยกกันเป็นเรื่องง่าย แต่การหาสัญลักษณ์ชุดเดียวที่เป็นทั้ง codeword และ map ให้เป็น XNUMX นั้นยากกว่ามาก อย่างน้อยก็ในเชิงคลาสสิก "ถ้าคุณเป็นควอนตัม คุณสามารถแก้ปัญหานี้ได้ในเวลาพหุนาม" ดร. แซนดรีกล่าว "แต่ถ้าคุณเป็นคนคลาสสิก อย่างน้อยถ้าคุณอยู่ในโมเดลกล่องดำนี้ คุณต้องใช้เวลาเลขชี้กำลัง" ในทางกลับกัน เมื่อพิจารณาถึงวิธีแก้ปัญหาที่เป็นไปได้ การตรวจสอบโดยง่ายด้วยการตรวจสอบว่าแก้ปัญหาแต่ละข้อแยกจากกันหรือไม่ โปรดทราบว่าเนื่องจากเป็นเอกสารสำหรับ FOCS งานนี้จึงเป็นงานพื้นฐานหรือพื้นฐาน ดังที่ได้กล่าวไว้ในคำปราศรัยของ Dr. Aaronson ที่สถาบัน Simons (กล่าวถึงใน NTT Research . ฉบับนี้) บทความบล็อก) อาร์กิวเมนต์ Yamakawa-Zhandry อยู่ในคลาสของการเร่งความเร็วที่สามารถตรวจสอบทางคณิตศาสตร์ได้อย่างง่ายดาย แต่จะไม่แสดงให้เห็นในทางปฏิบัติโดยคอมพิวเตอร์ควอนตัมจริงในเร็วๆ นี้ นอกเหนือจากรูปแบบการตรวจสอบที่ก้าวล้ำแล้ว บทความนี้ยังชี้ให้เห็นสิ่งใหม่เกี่ยวกับขอบเขตของการเพิ่มความเร็วของควอนตัม

“ก่อนงานของเรา เรามีตัวอย่างความได้เปรียบเชิงควอนตัมสำหรับปัญหา NP เช่น แฟคตอริ่ง หรือการค้นหาช่วงเวลาในการตั้งค่ากล่องดำ แต่ปรากฎว่าอัลกอริธึมควอนตัมที่อยู่เบื้องหลังตัวอย่างเหล่านี้โดยพื้นฐานแล้วคือการค้นหาช่วงเวลา แม้ว่าการแสดงวิธีการใช้การค้นหาช่วงเวลากับตัวอย่างเหล่านี้มักจะไม่ใช่เรื่องเล็กน้อย” ดร. แซนดรีกล่าว “เอกสารของเราแสดงให้เห็นว่ามีกรณีที่สองเป็นอย่างน้อย คุณสามารถตีความในแง่ดีว่ามีความหวังว่าข้อได้เปรียบของควอนตัมจะแพร่หลายมากกว่าที่เราคิดไว้ก่อนหน้านี้”

ได้รับการสนับสนุนจากคณะกรรมการด้านเทคนิคของ IEEE Computer Society เกี่ยวกับพื้นฐานทางคณิตศาสตร์ของคอมพิวเตอร์ (TCMF) FOCS เป็นการประชุมชั้นนำในด้านวิทยาการคอมพิวเตอร์เชิงทฤษฎี การเรียกร้องเอกสารสำหรับ FOCS 2022 ซึ่งเป็นงานประชุมประจำปีครั้งที่ 63 ระบุว่าการคำนวณควอนตัมเป็นหนึ่งใน 17 เรื่องทั่วไปที่น่าสนใจ กระดาษ Yamakawa-Zhandry มีกำหนดจะนำเสนอในวันที่ 31 ต.ค. 2022 เวลา 10:15 น. MT หากต้องการเรียนรู้เพิ่มเติมเกี่ยวกับและลงทะเบียนสำหรับงานนี้ โปรดไปที่ โฟกัส 2022 เว็บไซต์.