ปรับปรุงความซับซ้อนของแบบสอบถามควอนตัมบนอินพุตที่ง่ายขึ้น

ปรับปรุงความซับซ้อนของแบบสอบถามควอนตัมบนอินพุตที่ง่ายขึ้น

ประทับเวลา: 8 เมษายน 2024 11:29 น

โนเอล ที. แอนเดอร์สัน1,เจย์-ยูชอง1, เชลบี คิมเมล1,ดายอนโก2และเซียวฮันเย่1,3

1วิทยาลัยมิดเดิลเบอรี, มิดเดิลเบอรี, เวอร์มอนต์, สหรัฐอเมริกา
2วิทยาลัยวิลเลียมส์, วิลเลียมส์ทาวน์, แมสซาชูเซตส์, สหรัฐอเมริกา
3มหาวิทยาลัยบราวน์, พรอวิเดนซ์, โรดไอแลนด์, สหรัฐอเมริกา

พบบทความนี้ที่น่าสนใจหรือต้องการหารือ? Scite หรือแสดงความคิดเห็นใน SciRate.

นามธรรม

อัลกอริธึมโปรแกรมควอนตัมสแปนสำหรับการประเมินฟังก์ชันบางครั้งอาจลดความซับซ้อนในการสืบค้นเมื่อสัญญาว่าอินพุตมีโครงสร้างบางอย่าง เราออกแบบอัลกอริธึมโปรแกรม span ที่ปรับเปลี่ยนแล้วเพื่อแสดงการปรับปรุงเหล่านี้ยังคงมีอยู่แม้ว่าจะไม่มีสัญญาล่วงหน้าก็ตาม และเราขยายแนวทางนี้ไปสู่ปัญหาทั่วไปของการแปลงสถานะ ในฐานะแอปพลิเคชัน เราได้พิสูจน์ข้อดีของควอนตัมแบบเอกซ์โพเนนเชียลและซูเปอร์พหุโนเมียลในความซับซ้อนของคิวรีโดยเฉลี่ยสำหรับปัญหาการค้นหาต่างๆ โดยสรุปการค้นหาพร้อมคำแนะนำของ Montanaro [Montanaro, TQC 2010]

ปรับปรุงความซับซ้อนในการสืบค้นควอนตัมบนอินพุตที่ง่ายขึ้น PlatoBlockchain Data Intelligence ค้นหาแนวตั้ง AI.

ภาพเด่น: แผนผังการตัดสินใจที่ใช้สร้างหนึ่งในอัลกอริทึมของเรา

สรุปยอดนิยม

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

► ข้อมูล BibTeX

► ข้อมูลอ้างอิง

[1] อันดริส อัมไบนิส และโรนัลด์ เดอ วูล์ฟ ความซับซ้อนในการสืบค้นควอนตัมกรณีเฉลี่ย วารสารฟิสิกส์ A: คณิตศาสตร์และทั่วไป 34(35):6741, 2001. doi:10.1088/​0305-4470/​34/​35/​302.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] โดริต อาฮารอฟ. การคำนวณควอนตัม บทวิจารณ์ประจำปีของ Computational Physics VI, หน้า 259–346, 1999. doi:10.1142/​9789812815569_0007.
https://doi.org/​10.1142/​9789812815569_0007

[3] มิเชล โบเยอร์, ​​จิลส์ บราสซาร์ด, ปีเตอร์ ฮาเยอร์ และอแลง แทปป์ ขอบเขตที่แน่นแฟ้นในการค้นหาควอนตัม ฟอร์ชริตต์ เดอร์ ฟิสิก, 46(4-5):493–505, 1998. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -ป.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[4] อเล็กซานเดอร์ เบลอฟส์. โปรแกรม Span สำหรับฟังก์ชันที่มีใบรับรอง 1 ใบที่มีขนาดคงที่: บทคัดย่อแบบขยาย ใน รายงานการประชุม ACM Symposium ประจำปีครั้งที่สี่สิบสี่ด้านทฤษฎีคอมพิวเตอร์, STOC '12, หน้า 77–84, 2012. doi:10.1145/​2213977.2213985.
https://doi.org/10.1145/​2213977.2213985

[5] จิลส์ บราสซาร์ด, ปีเตอร์ ฮาเยอร์, ​​มิเคเล่ มอสก้า และอแลง แทปป์ การขยายและการประมาณค่าแอมพลิจูดควอนตัม ในการคำนวณและข้อมูลควอนตัม เล่มที่ 305 ของ Contemp คณิตศาสตร์ หน้า 53–74 อาเมอร์. คณิตศาสตร์. Soc., พรอวิเดนซ์, โรดไอแลนด์, 2002. doi:10.1090/​conm/​305/​05215.
https://doi.org/​10.1090/​conm/​305/​05215

[6] กิลส์ บราสซาร์ด, ปีเตอร์ ฮาเยอร์ และอแลง แทปป์ การนับควอนตัม ใน Automata, Languages ​​and Programming, หน้า 820–831, 1998. doi:10.1007/​BFb0055105.
https://doi.org/​10.1007/​BFb0055105

[7] อเล็กซานเดอร์ เบลอฟส์ และเบน ดับเบิลยู. ไรชาร์ด โปรแกรม Span และอัลกอริธึมควอนตัมสำหรับการเชื่อมต่อแบบ st และการตรวจจับกรงเล็บ หมายเหตุการบรรยายในวิทยาการคอมพิวเตอร์ 7501 LNCS:193–204, 2012. doi:10.1007/​978-3-642-33090-2_18.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] อเล็กซานเดอร์ เบลอฟส์ และแอนซิส โรสมานิส ขอบล่างของควอนตัมแน่นหนาสำหรับการนับโดยประมาณด้วยสถานะควอนตัม 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] ซัลมาน เบกี และไลลา ทากาวี การเร่งความเร็วควอนตัมตามแผนผังการตัดสินใจแบบคลาสสิก ควอนตัม 4:241 2020 ดอย:10.22331/​q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] อเล็กซานเดอร์ เบลอฟส์ และ ดูยาล ยอลคู ตั๋วเที่ยวเดียวสู่ลาสเวกัสและศัตรูควอนตัม 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] ริชาร์ด. คลีฟ, อาร์เทอร์. เอเคิร์ต, เคียรา มัคคิอาเวลโล และมิเคเล่ มอสก้า อัลกอริธึมควอนตัมกลับมาอีกครั้ง การดำเนินการของราชสมาคมแห่งลอนดอน ซีรีส์ A: วิทยาศาสตร์คณิตศาสตร์ กายภาพ และวิศวกรรมศาสตร์ 454(1969):339–354, 1998. doi:10.1098/​rspa.1998.0164.
https://doi.org/10.1098/​rspa.1998.0164

[12] อาร์จาน คอร์เนลิสเซน, สเตซีย์ เจฟเฟอรี, มาริส โอโซลส์ และอัลวาโร เปียดราฟิตา โปรแกรมสแปนและความซับซ้อนของเวลาควอนตัม ในการประชุมวิชาการนานาชาติเรื่องรากฐานทางคณิตศาสตร์ของวิทยาการคอมพิวเตอร์ ครั้งที่ 45 (MFCS 2020) Schloss Dagstuhl-Leibniz-Zentrum สำหรับข้อมูล 2020 ดอย:10.4230/​LIPIcs.MFCS.2020.26.
https://doi.org/​10.4230/​LIPIcs.MFCS.2020.26

[13] คริส เคด, แอชลีย์ มอนทานาโร และอเล็กซานเดอร์ เบลอฟส์ อัลกอริธึมควอนตัมที่มีประสิทธิภาพด้านเวลาและพื้นที่สำหรับการตรวจจับวงจรและการทดสอบการแบ่งส่วน ข้อมูลควอนตัมและการคำนวณ 18(1-2):18–50 2018

[14] ไค เดลอเรนโซ, เชลบี คิมเมล และอาร์ ทีล วิตเตอร์ การประยุกต์อัลกอริธึมควอนตัมสำหรับ st-Connectivity ในการประชุมครั้งที่ 14 ว่าด้วยทฤษฎีการคำนวณควอนตัม การสื่อสาร และการเข้ารหัส (TQC 2019) หน้า 6:1–6:14, 2019 doi:10.4230/​LIPIcs.TQC.2019.6.
https://doi.org/​10.4230/​LIPIcs.TQC.2019.6

[15] มิทรี กรินโก, จูเลียน กาคอน, คริสตา ซูฟาล และสเตฟาน เวอร์เนอร์ การประมาณค่าแอมพลิจูดควอนตัมแบบวนซ้ำ npj Quantum Information, 7(1):52, มี.ค. 2021. doi:10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] ลอฟ เค. โกรเวอร์. กลศาสตร์ควอนตัมช่วยในการค้นหาเข็มในกองหญ้า จดหมายทบทวนทางกายภาพ, 79(2):325–328, 1997. doi:10.1103/PhysRevLett.79.325.
https://doi.org/​10.1103/​PhysRevLett.79.325

[17] วาซิลี โฮฟฟ์ดิ้ง. อสมการของความน่าจะเป็นสำหรับผลรวมของตัวแปรสุ่มที่มีขอบเขต วารสารสมาคมสถิติอเมริกัน 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830.
https://doi.org/10.1080/​01621459.1963.10500830

[18] สึโยชิ อิโตะ และสเตซีย์ เจฟเฟอรี่ โปรแกรม Span โดยประมาณ อัลกอริทึม, 81(6):2158–2195, 2019. doi:10.1007/​s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] ไมเคิล จาเร็ต, สเตซีย์ เจฟเฟอรี่, เชลบี คิมเมล และอัลวาโร เปียดราฟิตา อัลกอริธึมควอนตัมสำหรับการเชื่อมต่อและปัญหาที่เกี่ยวข้อง ในการประชุมสัมมนายุโรปเรื่องอัลกอริทึมประจำปีครั้งที่ 26 (ESA 2018) หน้า 49:1–49:13, 2018 doi:10.4230/​LIPIcs.ESA.2018.49
https://​doi.org/​10.4230/​LIPIcs.ESA.2018.49

[20] อเล็กซี่ วาย. คิตาเยฟ. การวัดควอนตัมและปัญหาความคงตัวของอาบีเลียน 1995. arXiv:quant-ph/​9511026.
arXiv:ปริมาณ-ph/9511026

[21] ทรอย ลี, ราจัต มิททัล, เบน ดับเบิลยู. ไรชาร์ด, โรเบิร์ต สปาเลก และมาริโอ เซเกดี ความซับซ้อนของการสืบค้นควอนตัมของการแปลงสถานะ ในปี 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, หน้า 344–353, 2011. doi:10.1109/​FOCS.2011.75.
https://doi.org/​10.1109/​FOCS.2011.75

[22] เฟรเดริก แม็กเนียซ, แอชวิน นายัค, เจเรมี โรแลนด์ และมิโคลส ซานธา ค้นหาผ่าน Quantum Walk วารสารสยามคอมพิวเตอร์, 40(1):142–164, 2011. doi:10.1137/​090745854.
https://doi.org/10.1137/​090745854

[23] แอชลีย์ มอนทานาโร. ค้นหาควอนตัมพร้อมคำแนะนำ ในการประชุมเรื่องการคำนวณควอนตัม การสื่อสาร และการเข้ารหัส หน้า 77–93 สปริงเกอร์ 2010. doi:10.1007/​978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] เบน ดับเบิลยู. ไรชาร์ด. โปรแกรม Span และความซับซ้อนในการสืบค้นควอนตัม: ขอบเขตของฝ่ายตรงข้ามโดยทั่วไปนั้นเกือบจะแน่นหนาสำหรับทุกฟังก์ชันบูลีน IEEE Symposium ประจำปีครั้งที่ 50 เรื่องรากฐานของวิทยาศาสตร์คอมพิวเตอร์ หน้า 544–551, 2009 doi:10.1109/FOCS.2009.55
https://doi.org/​10.1109/​FOCS.2009.55

[25] เบน ดับเบิลยู. ไรชาร์ด. การสะท้อนสำหรับอัลกอริธึมแบบสอบถามควอนตัม ใน รายงานการประชุมสัมมนา ACM-SIAM ประจำปี 2011 เรื่อง Discrete Algorithms, Proceedings หน้า 560–569 2011. ดอย:10.1137/​1.9781611973082.44.
https://doi.org/10.1137/​1.9781611973082.44

[26] ไลลา ทากาวี. อัลกอริธึมควอนตัมแบบง่ายสำหรับปัญหาการระบุ Oracle Quantum Machine Intelligence, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

อ้างโดย

[1] Stacey Jeffery, Shelby Kimmel และ Alvaro Piedrafita, “อัลกอริทึมควอนตัมสำหรับการสุ่มตัวอย่าง Path-Edge”, arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel และ R. Teal Witter, “อัลกอริธึมคิวรีควอนตัมคู่ต่อสู้ที่แข็งแกร่งและมีประสิทธิภาพด้านพื้นที่”, arXiv: 2306.15040, (2023).

การอ้างอิงข้างต้นมาจาก are อบต./นาซ่าโฆษณา (ปรับปรุงล่าสุดสำเร็จ 2024-04-11 15:45:18 น.) รายการอาจไม่สมบูรณ์เนื่องจากผู้จัดพิมพ์บางรายไม่ได้ให้ข้อมูลอ้างอิงที่เหมาะสมและครบถ้วน

On บริการอ้างอิงของ Crossref ไม่พบข้อมูลอ้างอิงงาน (ความพยายามครั้งสุดท้าย 2024-04-11 15:45:17)

บทความนี้เผยแพร่ใน Quantum ภายใต้ the ครีเอทีฟคอมมอนส์แบบแสดงที่มา 4.0 สากล (CC BY 4.0) ใบอนุญาต ลิขสิทธิ์ยังคงอยู่กับผู้ถือลิขสิทธิ์ดั้งเดิม เช่น ผู้เขียนหรือสถาบันของพวกเขา

ประทับเวลา:

เพิ่มเติมจาก วารสารควอนตัม