通过更简单的输入提高了量子查询复杂性

通过更简单的输入提高了量子查询复杂性

时间戳记：8年2024月11日上午29:XNUMX

诺埃尔·T·安德森1, 郑在宇1, 谢尔比·金梅尔1, 高多妍2、叶晓涵1,3

1米德尔伯里学院，米德尔伯里，佛蒙特州，美国
2威廉姆斯学院，美国马萨诸塞州威廉斯敦
3布朗大学，美国罗德岛州普罗维登斯

觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.

抽象

当承诺输入具有一定的结构时，用于函数评估的量子跨度程序算法有时会降低查询复杂性。我们设计了一种修改后的跨度程序算法，以表明即使没有提前承诺，这些改进仍然存在，并且我们将这种方法扩展到更普遍的状态转换问题。作为一个应用，我们证明了几个搜索问题的平均查询复杂度上的指数和超多项式量子优势，概括了 Montanaro 的搜索建议 [Montanaro, TQC 2010]。

在更简单的输入上提高量子查询复杂性 PlatoBlockchain 数据智能。垂直搜索。人工智能。

特色图片：用于创建我们的算法之一的决策树。

热门摘要

我们期望量子算法像经典算法一样，在更简单的输入上运行得更快。例如，如果您正在无序列表中搜索某个项目，并且该项目有许多副本，那么我们预计，与只有一个标记项目时相比，在这种情况下量子算法应该运行得更快，即使不知道提前的目标项目数量。事实上，对于搜索问题，如何在更简单的输入上获得这样的优势是已知的。然而，当没有明显的方法来标记计算何时运行足够长的时间时，将这种想法推广到搜索之外的问题是具有挑战性的。我们修改了查询模型中的几个流行的算法框架，以创建标志来提醒我们计算是否运行了足够长的时间，使我们能够在更简单的输入上尽早结束算法，而无需提前知道实例是简单还是困难。作为一个应用程序，给定问题的简单输入和困难输入的分布，我们可以分析平均查询复杂性。我们表明，搜索问题的输入的某些分布比经典算法产生更大的平均量子查询优势。

►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] 多里特·阿哈罗诺夫量子计算。计算物理学年度评论 VI，第 259–346 页，1999 年。doi:10.1142/​9789812815569_0007。
https：/ / doi.org/ 10.1142 / 9789812815569_0007

[3] 米歇尔·博耶、吉尔斯·布拉萨德、彼得·霍耶和阿兰·塔普。量子搜索的严格界限。 Fortschritte der Physik, 46(4-5):493–505, 1998. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -P。
<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] 亚历山大·贝洛夫斯。具有恒定大小的 1 证书的函数的 Span 程序：扩展摘要。第四十四届 ACM 计算理论年度研讨会论文集，STOC '12，第 77-84 页，2012 年。doi:10.1145/​2213977.2213985。
https：/ / doi.org/10.1145/ 2213977.2213985

[5] 吉尔斯·布拉萨德、彼得·霍耶、米歇尔·莫斯卡和阿兰·塔普。量子幅度放大和估计。在《量子计算和信息》中，《Contemp》第 305 卷。数学，第 53-74 页。阿米尔。数学。 Soc.，普罗维登斯，罗德岛州，2002 年。doi:10.1090/​conm/​305/​05215。
https：/ ‐ / doi.org/10.1090/conm/305/05215

[6] 吉尔斯·布拉萨德、彼得·霍耶和阿兰·塔普。量子计数。 《自动机》，语言和编程，第 820–831 页，1998 年。doi:10.1007/BFb0055105。
https：/ / doi.org/ 10.1007 / BFb0055105

[7] 亚历山大·贝洛夫斯 (Aleksandrs Belovs) 和本·W·赖查特 (Ben W. Reichardt)。用于 ST 连接和爪检测的 Span 程序和量子算法。计算机科学讲义，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。doi:10.22331/q-2020-03-02-241。
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] 亚历山大·贝洛夫斯 (Aleksandrs Belovs) 和杜亚尔·约尔库 (Duyal Yolcu)。前往拉斯维加斯和量子对手的单程票。 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] Arjan Cornelissen、Stacey Jeffery、Maris Ozols 和 Alvaro Piedrafita。跨度程序和量子时间复杂度。第 45 届计算机科学数学基础国际研讨会 (MFCS 2020)。 Schloss Dagstuhl-Leibniz-Zentrum für Informatik，2020。doi:10.4230/​LIPIcs.MFCS.2020.26。
https：///doi.org/10.4230/LIPIcs.MFCS.2020.26

[13] 克里斯·凯德、阿什利·蒙塔纳罗和亚历山大·贝洛夫斯。用于检测循环和测试二分性的时间和空间高效的量子算法。量子信息与计算，18（1-2）：18–50，2018。

[14] 凯·德洛伦佐、谢尔比·金梅尔和 R.蒂尔·维特。量子算法在 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 量子信息，7(1):52，2021 年 10.1038 月。doi:41534/​s021-00379-1-XNUMX。
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] 洛夫·K·格罗弗。量子力学有助于大海捞针。物理评论快报，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] 伊藤刚和史黛西·杰弗里。近似跨度程序。算法，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：quant-ph / 9511026

[21] 特洛伊·李、拉贾特·米塔尔、本·W·雷查特、罗伯特·斯帕莱克和马里奥·塞格迪。状态转换的量子查询复杂性。 2011 年 IEEE 第 52 届计算机科学基础年度研讨会，第 344-353 页，2011 年。doi:10.1109/​FOCS.2011.75。
https：///doi.org/10.1109/FOCS.2011.75

[22] 弗雷德里克·马格尼兹、阿什温·纳亚克、杰雷米·罗兰和米克洛斯·桑塔。通过 Quantum Walk 搜索。 SIAM 计算杂志，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] 本·W·雷查特 (Ben W. Reichardt)跨度程序和量子查询复杂性：对于每个布尔函数，一般对手的界限几乎都是严格的。第 50 届 IEEE 计算机科学基础研讨会，第 544-551 页，2009 年。doi:10.1109/​FOCS.2009.55。
https：///doi.org/10.1109/FOCS.2009.55

[25] 本·W·雷查特 (Ben W. Reichardt)量子查询算法的思考。 2011 年年度 ACM-SIAM 离散算法研讨会论文集，论文集，第 560-569 页。 2011.doi:10.1137/​1.9781611973082.44。
https：/ / doi.org/10.1137/ 1.9781611973082.44

[26] 莱拉·塔加维。预言机识别问题的简化量子算法。量子机器智能，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，“路径边缘采样的量子算法”， 的arXiv：2303.03319, (2023).

[2] Michael Czekanski、Shelby Kimmel 和 R. Teal Witter，“稳健且空间高效的双对抗量子查询算法”， 的arXiv：2306.15040, (2023).

以上引用来自 SAO / NASA广告 （最近成功更新为2024-04-11 15:45:18）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。

On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2024-04-11 15:45:17）。

该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。

时间戳记：

更多来自 量子杂志