1布里斯托大学数学学院。 n.linden@bristol.ac.uk
2QuSoft、CWI 和荷兰阿姆斯特丹大学。 rdewolf@cwi.nl
觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.
抽象
量子傅立叶变换 (QFT) 是量子计算的关键原语，通常用作较大计算中的子例程，例如用于相位估计。 因此，我们可能无法控制输入到 QFT 的状态。 因此，在实现良好的 QFT 时，我们可以想象它需要在任意输入状态下表现良好。 $验证$ QFT 实现的这种最坏情况下的正确行为通常会呈指数级增加（在量子位的数量上），这引起了人们的担忧，即这种验证在任何有用大小的系统上实际上都是不可能的。 在本文中，我们表明，事实上，我们只需要 QFT 具有良好的 $average$-$case$ 性能，即可在关键任务（相位估计、周期查找和振幅估计）中实现良好的 $worst$-$case$ 性能. 此外，我们提供了一个非常有效的程序来验证 QFT 所需的平均情况行为。
热门摘要
►BibTeX数据
►参考
[1] 斯科特·阿伦森和帕特里克·拉尔。 量子近似计数，简化。 在第三届算法简单性研讨会论文集 (SOSA) 中，第 3–24 页，32 年。arXiv:2020。
https：/ / doi.org/10.1137/ 1.9781611976014.5
的arXiv：1908.10846
[2] Charles H. Bennett，Ethan Bernstein，Gilles Brassard和Umesh Vazirani。 量子计算的优缺点。 SIAM计算杂志，26（5）：1510-1523，1997.quant-ph / 9701001。
https：/ / doi.org/ 10.1137 / S0097539796300933
arXiv：quant-ph / 9701001
[3] Gilles Brassard，PeterHøyer，Michele Mosca和Alain Tapp。 量子幅度放大和估计。 在“量子计算和量子信息：千年卷”中，AMS当代数学丛书第305卷，第53-74页。 2002.Quant-ph / 0005055。
https：/ ‐ / doi.org/10.1090/conm/305/05215
arXiv：quant-ph / 0005055
[4] Chi-Fang Chen 和 Fernando GSL Brandão。 Trotter 错误的浓度。 arXiv:2111.05324，9 年 2021 月 XNUMX 日。
https://doi.org/10.48550/arXiv.2111.05324
的arXiv：2111.05324
[5] Richard Cleve、Artur Ekert、Chiara Macchiavello 和 Michele Mosca。 重温量子算法。 在伦敦皇家学会会刊，A454 卷，第 339–354 页，1998 年。quant-ph/9708016。
https：/ / doi.org/ 10.1098 / rspa.1998.0164
arXiv：quant-ph / 9708016
[6] 唐·科珀史密斯。 在量子分解中有用的近似傅里叶变换。 IBM 研究报告编号 RC19642，quant-ph/ 0201067，1994。
https://doi.org/10.48550/arXiv.quant-ph/0201067
arXiv：quant-ph / 0201067
[7] Marcus da Silva、Oliver Landon-Cardinal 和 David Poulin。 没有层析成像的量子器件的实际表征。 物理评论快报，107：210404，2011 年。arXiv：1104.3835。
https：/ / doi.org/ 10.1103 / PhysRevLett.107.210404
的arXiv：1104.3835
[8] Jens Eisert、Dominik Hangeiter、Nathan Walk、Ingo Roth、Damian Markham、Rhea Parekh、Ulysse Chabaud 和 Elham Kashefi。 量子认证和基准测试。 Nature Reviews Physics, 2:382–390, 2020. arXiv:1910.06343。
https://doi.org/10.1038/s42254-020-0186-4
的arXiv：1910.06343
[9] Steven T. Flammia 和 Yi-Kai Liu。 来自少量 Pauli 测量的直接保真度估计。 物理评论快报，106：230501，2011 年。arXiv：1104.4695。
https：/ / doi.org/ 10.1103 / PhysRevLett.106.230501
的arXiv：1104.4695
[10] András Gilyén、Srinivasan Arunachalam 和 Nathan Wiebe。 通过更快的量子梯度计算来优化量子优化算法。 在第 30 届 ACM-SIAM SODA 会议记录中，第 1425-1444 页，2019 年。arXiv：1711.00465。
https：/ / doi.org/10.1137/ 1.9781611975482.87
的arXiv：1711.00465
[11] 洛夫·K·格罗弗。 一种用于数据库搜索的快速量子力学算法。 在第 28 届 ACM STOC 会议记录中，第 212–219 页，1996 年。quant-ph/ 9605043。
https：/ / doi.org/10.1145/ 237814.237866
arXiv：quant-ph / 9605043
[12] András Gilyén、Yuan Su、Guang Hao Low 和 Nathan Wiebe。 量子奇异值变换及以后：量子矩阵算法的指数改进。 在第 51 届 ACM STOC 会议记录中，第 193–204 页，2019 年。arXiv:1806.01838。
https：/ / doi.org/10.1145/ 3313276.3316366
的arXiv：1806.01838
[13] 斯蒂芬·P·乔丹。 用于数值梯度估计的快速量子算法。 Physical Review Letters, 95:050501, 2005. quant-ph/ 0405146。
https：/ / doi.org/ 10.1103 / PhysRevLett.95.050501
arXiv：quant-ph / 0405146
[14] 阿列克谢于。 基塔耶夫。 量子测量和阿贝尔稳定器问题。 quant-ph/9511026，12 年 1995 月 XNUMX 日。
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv：quant-ph / 9511026
[15] 诺亚·林登和罗纳德·德沃尔夫。 对量子电路中少量大错误的轻量级检测。 量子, 5(436), 2021.arXiv:2009.08840。
https://doi.org/10.22331/q-2021-04-20-436
的arXiv：2009.08840
[16] 乌尔米拉·马哈德夫。 量子计算的经典验证。 在第 59 届 IEEE FOCS 会议记录中，第 259–267 页，2018 年。arXiv:1804.01082。
https：///doi.org/10.1109/FOCS.2018.00033
的arXiv：1804.01082
[17] John M. Martyn、Zane M. Rossi、Andrew K. Tan 和 Isaac L. Chuang。 量子算法的大统一。 PRX 量子，2：040203，2021 年。arXiv.2105.02859。
https：/ / doi.org/ 10.1103 / PRXQuantum.2.040203
[18] Michael A. Nielsen 和 Isaac L. Chuang。 量子计算和量子信息。 剑桥大学出版社，2000 年。
https：/ / doi.org/ 10.1017 / CBO9780511976667
[19] 帕特里克·拉尔。 用于相位、能量和振幅估计的更快的相干量子算法。 量子，5(566)，2021 年。arXiv：2103.09717。
https://doi.org/10.22331/q-2021-10-19-566
的arXiv：2103.09717
[20] 彼得·W·肖尔。 用于量子计算机上素数分解和离散对数的多项式时间算法。 SIAM Journal on Computing，26(5):1484–1509, 1997。FOCS'94 的早期版本。 定量 ph/ 9508027.
https：/ / doi.org/ 10.1137 / S0097539795293172
arXiv：quant-ph / 9508027
[21] Qi Zhao、You Zhou、Alexander F. Shaw、Tongyang Li 和 Andrew M. Childs。 具有随机输入的哈密顿模拟。 arXiv:2111.04773，8 年 2021 月 XNUMX 日。
https://doi.org/10.48550/arXiv.2111.04773
的arXiv：2111.04773
被引用
[1] Joran van Apeldoorn、Arjan Cornelissen、András Gilyén 和 Giacomo Nannicini，“使用状态准备酉体的量子断层扫描”， 的arXiv：2207.08800.
以上引用来自 SAO / NASA广告 （最近成功更新为2022-12-08 04:24:57）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。
On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2022-12-08 04:24:56）。
该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。
