1Школа математики Бристольского университета. n.linden@bristol.ac.uk
2QuSoft, CWI и Университет Амстердама, Нидерланды. rdewolf@cwi.nl
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Квантовое преобразование Фурье (QFT) является ключевым примитивом для квантовых вычислений, который обычно используется в качестве подпрограммы в более крупных вычислениях, например, для оценки фазы. Таким образом, мы можем иметь небольшой контроль над состоянием, которое вводится в КТП. Таким образом, при реализации хорошей КТП мы можем предположить, что она должна хорошо работать при произвольных входных состояниях. $Проверка$ этого наихудшего случая правильного поведения КТП-реализации была бы экспоненциально сложной (по количеству кубитов) в целом, что вызывает опасения, что такая проверка будет невозможна на практике на любой системе полезного размера. В этой статье мы показываем, что на самом деле нам нужна только хорошая производительность QFT в $среднем$-$случайе, чтобы достичь хорошей производительности $худшего$-$случая$ для ключевых задач — оценки фазы, определения периода и оценки амплитуды. . Далее мы даем очень эффективную процедуру для проверки требуемого поведения КТП в среднем случае.
Популярное резюме
► Данные BibTeX
► Рекомендации
[1] Скотт Ааронсон и Патрик Ралл. Квантовый приближенный счет, упрощенный. В материалах 3-го симпозиума по простоте алгоритмов (SOSA), страницы 24–32, 2020 г. arXiv:1908.10846.
https: / / doi.org/ 10.1137 / 1.9781611976014.5
Arxiv: 1908.10846
[2] Чарльз Х. Беннет, Итан Бернштейн, Жиль Брассар и Умеш Вазирани. Сильные и слабые стороны квантовых вычислений. SIAM Journal on Computing, 26 (5): 1510–1523, 1997. Quant-ph / 9701001.
https: / / doi.org/ 10.1137 / S0097539796300933
Arxiv: колич-фот / 9701001
[3] Жиль Брассар, Питер Хёйер, Мишель Моска и Ален Тапп. Квантовое усиление и оценка амплитуды. В квантовых вычислениях и квантовой информации: том тысячелетия, том 305 из серии AMS Contemporary Mathematics Series, страницы 53–74. 2002. квант-ph / 0005055.
HTTPS: / / doi.org/ 10.1090 / conm / 305/05215
Arxiv: колич-фот / 0005055
[4] Чи-Фанг Чен и Фернандо ГСЛ Брандао. Концентрация для ошибки рысака. arXiv: 2111.05324, 9 ноября 2021 г.
https:///doi.org/10.48550/arXiv.2111.05324
Arxiv: 2111.05324
[5] Ричард Клив, Артур Экерт, Кьяра Маккиавелло и Микеле Моска. Новый взгляд на квантовые алгоритмы. В Proceedings of the Royal Society of London, том A454, страницы 339–354, 1998. quant-ph/9708016.
https: / / doi.org/ 10.1098 / rspa.1998.0164
Arxiv: колич-фот / 9708016
[6] Дон Копперсмит. Приближенное преобразование Фурье, полезное в квантовом факторинге. Отчет IBM Research № RC19642, quant-ph/0201067, 1994.
https:///doi.org/10.48550/arXiv.quant-ph/0201067
Arxiv: колич-фот / 0201067
[7] Маркус да Силва, Оливер Лэндон-Кардинал и Дэвид Пулен. Практическая характеристика квантовых устройств без томографии. Письма о физическом обзоре, 107:210404, 2011. arXiv:1104.3835.
https: / / doi.org/ 10.1103 / PhysRevLett.107.210404
Arxiv: 1104.3835
[8] Йенс Эйзерт, Доминик Ханглитер, Натан Уок, Инго Рот, Дамиан Маркхэм, Рея Парех, Улисс Шабо и Эльхам Кашефи. Квантовая сертификация и бенчмаркинг. Nature Reviews Physics, 2:382–390, 2020. arXiv:1910.06343.
https://doi.org/10.1038/s42254-020-0186-4
Arxiv: 1910.06343
[9] Стивен Т. Фламмиа и И-Кай Лю. Прямая оценка точности по нескольким измерениям Паули. Письма о физическом обзоре, 106:230501, 2011. arXiv:1104.4695.
https: / / doi.org/ 10.1103 / PhysRevLett.106.230501
Arxiv: 1104.4695
[10] Андраш Гильен, Шринивасан Аруначалам и Натан Вибе. Оптимизация алгоритмов квантовой оптимизации за счет более быстрого вычисления квантового градиента. В материалах 30-й конференции ACM-SIAM SODA, страницы 1425–1444, 2019 г. arXiv:1711.00465.
https: / / doi.org/ 10.1137 / 1.9781611975482.87
Arxiv: 1711.00465
[11] Лов К. Гровер. Быстрый квантово-механический алгоритм поиска в базе данных. В Proceedings of 28th ACM STOC, страницы 212–219, 1996. quant-ph/9605043.
https: / / doi.org/ 10.1145 / 237814.237866
Arxiv: колич-фот / 9605043
[12] Андраш Гильен, Юань Су, Гуан Хао Лоу и Натан Вибе. Квантовое преобразование сингулярных значений и не только: экспоненциальные улучшения квантовой матричной арифметики. В материалах 51-го заседания ACM STOC, страницы 193–204, 2019 г. arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
Arxiv: 1806.01838
[13] Стивен П. Джордан. Быстрый квантовый алгоритм для численной оценки градиента. Physical Review Letters, 95:050501, 2005. quant-ph/0405146.
https: / / doi.org/ 10.1103 / PhysRevLett.95.050501
Arxiv: колич-фот / 0405146
[14] Алексей Ю. Китаев. Квантовые измерения и проблема абелева стабилизатора. quant-ph/9511026, 12 ноября 1995 г.
https:///doi.org/10.48550/arXiv.quant-ph/9511026
Arxiv: колич-фот / 9511026
[15] Ноа Линден и Рональд де Вольф. Облегченное обнаружение небольшого количества больших ошибок в квантовой схеме. Quantum, 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] Джон М. Мартин, Зейн М. Росси, Эндрю К. Тан и Исаак Л. Чуанг. Великое объединение квантовых алгоритмов. PRX Quantum, 2:040203, 2021. arXiv.2105.02859.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[18] Майкл А. Нильсен и Исаак Л. Чуанг. Квантовые вычисления и квантовая информация. Издательство Кембриджского университета, 2000.
https: / / doi.org/ 10.1017 / CBO9780511976667
[19] Патрик Ролл. Более быстрые когерентные квантовые алгоритмы для оценки фазы, энергии и амплитуды. Quantum, 5(566), 2021. arXiv:2103.09717.
https://doi.org/10.22331/q-2021-10-19-566
Arxiv: 2103.09717
[20] Питер В. Шор. Полиномиальные алгоритмы простой факторизации и дискретного логарифмирования на квантовом компьютере. SIAM Journal on Computing, 26(5):1484–1509, 1997. Более ранняя версия в FOCS'94. квант-ф/9508027.
https: / / doi.org/ 10.1137 / S0097539795293172
Arxiv: колич-фот / 9508027
[21] Ци Чжао, Ю Чжоу, Александр Ф. Шоу, Тонъян Ли и Эндрю М. Чайлдс. Гамильтоново моделирование со случайными входными данными. arXiv: 2111.04773, 8 ноября 2021 г.
https:///doi.org/10.48550/arXiv.2111.04773
Arxiv: 2111.04773
Цитируется
[1] Джоран ван Апелдорн, Арьян Корнелиссен, Андраш Гильен и Джакомо Нанницини, «Квантовая томография с использованием унитарных единиц государственной подготовки», Arxiv: 2207.08800.
Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2022-12-08 04:24:57). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.
On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2022-12-08 04:24:56).
Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
