Ускорение квантовых алгоритмов с помощью предварительных вычислений

Ускорение квантовых алгоритмов с помощью предварительных вычислений

Отметка времени: 22 февраля 2024 г., 8:10 AM
Ускорение квантовых алгоритмов с помощью предварительных вычислений PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

Уильям Дж. Хаггинс и Джаррод Р. МакКлин

Google Quantum AI, Венеция, Калифорния, США

Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.

Абстрактные

Реальные приложения вычислений могут быть чрезвычайно чувствительны ко времени. Было бы полезно, если бы мы могли ускорить выполнение таких задач, выполняя часть работы заранее. Руководствуясь этим, мы предлагаем модель стоимости квантовых алгоритмов, которая допускает квантовые предварительные вычисления; т. е. для полиномиального количества «бесплатных» вычислений до того, как входные данные для алгоритма будут полностью определены, а также методы их использования. Мы анализируем два семейства унитарных систем, которые асимптотически более эффективно реализовать в этой модели затрат, чем в стандартной. Первый пример квантовых предварительных вычислений, основанный на возведении матрицы плотности в степень, может предложить экспоненциальное преимущество при определенных условиях. Во втором примере используется вариант телепортации ворот для достижения квадратичного преимущества по сравнению с прямой реализацией унитарных единиц. Эти примеры намекают на то, что квантовые предварительные вычисления могут открыть новую арену для поиска квантовых преимуществ.

► Данные BibTeX

► Рекомендации

[1] С Ааронсон. Ограничения квантовых советов и односторонней связи. В материалах. 19-я ежегодная конференция IEEE по сложности вычислений, 2004 г., страницы 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Скотт Ааронсон и Андрис Амбайнис. Форреляция. В материалах сорок седьмого ежегодного симпозиума ACM по теории вычислений, STOC '15, страницы 307–316, Нью-Йорк, штат Нью-Йорк, США, 14 июня 2015 г. ACM. ISBN 9781450335362/​10.1145.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Скотт Ааронсон и Гай Н. Ротблюм. Бережное измерение квантовых состояний и дифференциальная конфиденциальность. 18 апреля 2019 г. URL http://arxiv.org/abs/1904.08747.
Arxiv: 1904.08747

[4] Райан Бэббуш, Джаррод Р. МакКлин, Майкл Ньюман, Крейг Гидни, Серхио Бойшо и Хартмут Невен. Сосредоточьтесь не только на квадратичном ускорении, чтобы получить квантовое преимущество с коррекцией ошибок. Квант PRX, 2 (1): 010103, 29 марта 2021 г. ISSN 2691-3399. 10.1103/​prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Дэниел Дж Бернштейн и Таня Ланге. Неоднородные трещины в бетоне: сила свободных предварительных вычислений. В книге «Достижения в криптологии – ASIACRYPT 2013», конспекты лекций по информатике, страницы 321–340. Springer Berlin Heidelberg, Берлин, Гейдельберг, 2013. ISBN 9783642420443,9783642420450. 10.1007/​978-3-642-42045-0_17.
https:/​/​doi.org/​10.1007/​978-3-642-42045-0_17

[6] Доминик Берри, Крейг Гидни, Марио Мотта, Джаррод Р. МакКлин и Райан Бэббуш. Кубитизация квантовой химии с произвольным базисом с использованием разреженности и факторизации низкого ранга. 6 февраля 2019 г. URL https://doi.org/10.22331/q-2019-12-02-208.
https:/​/​doi.org/​10.22331/​q-2019-12-02-208

[7] Джейкоб Биамонте, Питер Виттек, Никола Панкотти, Патрик Ребентрост, Натан Вибе и Сет Ллойд. Квантовое машинное обучение. Nature, 549 (7671): 195–202, сентябрь 2017 г. ISSN 0028-0836,1476-4687. 10.1038/nature23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Сергей Бравый и Алексей Китаев. Универсальные квантовые вычисления с идеальными вентилями Клиффорда и шумными помощниками. Физ. Ред. А, 71 (2): 022316, 22 февраля 2005 г. ISSN 1050-2947,1094-1622. 10.1103/физрева.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Сергей Бравый и Дмитрий Маслов. Схемы без Адамара раскрывают структуру группы Клиффорда. IEEE Транс. Инф. Теория, 67 (7): 4546–4563, июль 2021 г. ISSN 0018-9448,1557-9654. 10.1109/тит.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Эрл Т. Кэмпбелл и Джо О'Горман. Эффективный подход «магического состояния» к поворотам на малые углы. 14 марта 2016 г. URL https://doi.org/10.1088/2058-9565/1/1/015007.
https:/​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007

[11] Ситан Чен, Джордан Котлер, Синь-Юань Хуан и Джерри Ли. Экспоненциальное разделение между обучением с квантовой памятью и без нее. В 2021 году пройдет 62-й ежегодный симпозиум IEEE по основам информатики (FOCS). IEEE, февраль 2022 г. 10.1109/​focs52979.2021.00063.
https://​/​doi.org/​10.1109/​focs52979.2021.00063

[12] Эндрю М. Чайлдс, Робин Котари и Роландо Д. Сомма. Квантовый алгоритм для систем линейных уравнений с экспоненциально улучшенной зависимостью от точности. SIAM J. Comput., 46 (6): 1920–1950, 1 января 2017 г. ISSN 0097-5397. 10.1137/16М1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[13] Н. Коди Джонс, Джеймс Д. Уитфилд, Питер Л. МакМахон, Ман-Хонг Юнг, Родни Ван Метер, Алан Аспуру-Гузик и Ёсихиса Ямамото. Ускоренное моделирование квантовой химии на отказоустойчивых квантовых компьютерах. New J. Phys., 14 (11): 115023, 27 ноября 2012 г. ISSN 1367-2630. 10.1088/1367-2630/14/11/115023.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​115023

[14] Педро К.С. Коста, Донг Ан, Юваль Р. Сандерс, Юань Су, Райан Бэббуш и Доминик В. Берри. Оптимальный масштабирующий решатель квантовых линейных систем с помощью дискретной адиабатической теоремы. Квант PRX, 3 (4): 040303, 7 октября 2022 г. ISSN 2691-3399. 10.1103/​prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Джордан Котлер, Синь-Юань Хуан и Джаррод Р. МакКлин. Возвращаясь к деквантованию и квантовому преимуществу в задачах обучения. 1 декабря 2021 г. URL http://arxiv.org/abs/2112.00811.
Arxiv: 2112.00811

[16] Шон Икс Куи, Дэниел Готтесман и Анируд Кришна. Диагональные ворота в иерархии Клиффорда. Физ. Ред. А, 95 (1), 26 января 2017 г. ISSN 2469-9926,2469-9934. 10.1103/физрева.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Эдвард Фархи, Джеффри Голдстоун и Сэм Гутманн. Алгоритм квантовой аппроксимационной оптимизации. 14 ноября 2014 г. URL http://arxiv.org/abs/1411.4028.
Arxiv: 1411.4028

[18] Остин Дж. Фаулер. Оптимальные по времени квантовые вычисления. 17 октября 2012 г. URL http://arxiv.org/abs/1210.4626.
Arxiv: 1210.4626

[19] Севаг Гарибян и Франсуа Ле Галль. Деквантование квантового сингулярного преобразования: сложность и приложения к квантовой химии и квантовой гипотезе PCP. В материалах 54-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2022, страницы 19–32, Нью-Йорк, штат Нью-Йорк, США, 9 июня 2022 г. ACM. ISBN 9781450392648/​10.1145.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Крейг Гидни и Мартин Экеро. Как разложить 2048-битные целые числа RSA за 8 часов, используя 20 миллионов шумных кубитов. Quantum, 5 (433): 433, 15 апреля 2021 г. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https:/​/​doi.org/​10.22331/​q-2021-04-15-433

[21] Крейг Гидни и Остин Дж. Фаулер. Гибкая компоновка вычислений поверхностного кода с использованием состояний AutoCCZ. 21 мая 2019 г. URL http://arxiv.org/abs/1905.08916.
Arxiv: 1905.08916

[22] Андраш Гильен и Александр Поремба. Улучшенные квантовые алгоритмы оценки точности. 29 марта 2022 г. URL http://arxiv.org/abs/2203.15993.
Arxiv: 2203.15993

[23] Дэниел Готтесман и Исаак Л. Чуанг. Квантовая телепортация — универсальный вычислительный примитив. 2 августа 1999 г. URL https://doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / 46503

[24] Лео Грейди и Али Кемаль Синоп. Быстрая аппроксимационная сегментация случайных блуждающих с использованием предварительного вычисления собственного вектора. На конференции IEEE 2008 г. по компьютерному зрению и распознаванию образов, страницы 1–8. IEEE, июнь 2008 г. ISBN 9781424422425. 10.1109/​cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

[25] Лов К. Гровер. Быстрый квантовомеханический алгоритм поиска в базе данных. В материалах двадцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '96, STOC '96, страницы 212–219, Нью-Йорк, Нью-Йорк, США, 1996. ACM Press. ISBN 9780897917858/​10.1145.
https: / / doi.org/ 10.1145 / 237814.237866

[26] Арам В. Харроу, Авинатан хасидим и Сет Ллойд. Квантовый алгоритм для линейных систем уравнений. Физ. Rev. Lett., 103 (15): 150502, 9 октября 2009 г. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[27] Синь-Юань Хуанг, Майкл Бротон, Джордан Котлер, Ситан Чен, Джерри Ли, Масуд Мохсени, Хартмут Невен, Райан Бэббуш, Ричард Куенг, Джон Прескилл и Джаррод Р. МакКлин. Квантовое преимущество в обучении на экспериментах. Science, 376 (6598): 1182–1186, 10 июня 2022 г. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https://​/​doi.org/​10.1126/​science.abn7293

[28] Коди Джонс. Протоколы дистилляции состояний Фурье в квантовых вычислениях. 12 марта 2013 г. URL http://arxiv.org/abs/1303.3066.
Arxiv: 1303.3066

[29] Джон Каллохер. Квантовое преимущество для естественной проблемы потоковой передачи. В 2021 году 62-й ежегодный симпозиум IEEE по основам информатики (FOCS), страницы 897–908. IEEE, февраль 2022 г. 10.1109/​focs52979.2021.00091.
https://​/​doi.org/​10.1109/​focs52979.2021.00091

[30] Ричард М. Карп и Ричард Дж. Липтон. Некоторые связи между неоднородными и однородными классами сложности. В материалах двенадцатого ежегодного симпозиума ACM по теории вычислений - STOC '80, STOC '80, страницы 302–309, Нью-Йорк, Нью-Йорк, США, 28 апреля 1980 г. ACM Press. ISBN 9780897910170/​10.1145.
https: / / doi.org/ 10.1145 / 800141.804678

[31] Шелби Киммел, Седрик Йен-Ю Линь, Гуан Хао Лоу, Марис Озолс и Теодор Дж. Йодер. Гамильтоновое моделирование с оптимальной сложностью выборки. Npj Quantum Inf., 3 (1): 1–7, 30 марта 2017 г. ISSN 2056-6387,2056-6387. 10.1038/s41534-017-0013-7.
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[32] Франсуа Ле Галль. Экспоненциальное разделение сложности квантового и классического онлайн-пространства. В материалах восемнадцатого ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах, SPAA '06, страницы 67–73, Нью-Йорк, штат Нью-Йорк, США, 30 июля 2006 г. ACM. ISBN 9781595934529. 10.1145/​1148109.1148119.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Линь Линь и Юй Тонг. Оптимальная фильтрация квантовых собственных состояний на основе полинома с применением к решению квантовых линейных систем. Quantum, 4 (361): 361, 11 ноября 2020 г. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

[34] Дэниел Литински. Магическая государственная дистилляция: не так дорого, как вы думаете. Квантум, 3 (205): 205, 2 декабря 2019а. ISSN 2521-327Х. 10.22331/q-2019-12-02-205.
https:/​/​doi.org/​10.22331/​q-2019-12-02-205

[35] Дэниел Литински. Игра поверхностных кодов: крупномасштабные квантовые вычисления с решеточной хирургией. Квантум, 3 (128): 128, 5 марта 2019 г.б. ISSN 2521-327Х. 10.22331/q-2019-03-05-128.
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[36] Сет Ллойд, Масуд Мохсени и Патрик Ребентрост. Квантовый анализ главных компонент. Нат. Phys., 10 (9): 631–633, 27 сентября 2014 г. ISSN 1745-2473,1745-2481. 10.1038/nphys3029.
https: / / doi.org/ 10.1038 / nphys3029

[37] Джон М. Мартин, Зейн М. Росси, Эндрю К. Тан и Исаак Л. Чуанг. Великое объединение квантовых алгоритмов. Квант PRX, 2 (4): 040203, 3 декабря 2021 г. ISSN 2691-3399. 10.1103/​prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Иман Марвиан и Сет Ллойд. Универсальный квантовый эмулятор. 8 июня 2016 г. URL http://arxiv.org/abs/1606.02734.
Arxiv: 1606.02734

[39] Ф. Моцой, депутат Кайхер и ФК Вильгельм. Линейная и логарифмическая временные композиции квантовых операторов многих тел. Физ. Rev. Lett., 119 (16): 160503, 20 октября 2017 г. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Майкл А. Нильсен. Оптические квантовые вычисления с использованием состояний кластера. Физ. Rev. Lett., 93 (4): 040503, 23 июля 2004 г. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.93.040503.
https: / / doi.org/ 10.1103 / PhysRevLett.93.040503

[41] Брайан О'Горман, Уильям Дж. Хаггинс, Элеонора Дж. Риффель и К. Биргитта Уэйли. Обобщенные сети обмена для краткосрочных квантовых вычислений. 13 мая 2019 г. URL http://arxiv.org/abs/1905.05118.
Arxiv: 1905.05118

[42] Пол Фам и Криста М. Своре. Двумерная квантовая архитектура ближайшего соседа для учета полилогарифмической глубины. 2 июля 27 г. URL http://arxiv.org/abs/2012.
Arxiv: 1207.6655

[43] Р. Рауссендорф и Х. Дж. Бригель. Односторонний квантовый компьютер. Физ. Rev. Lett., 86 (22): 5188–5191, 28 мая 2001 г. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.86.5188.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[44] Юваль Р. Сандерс, Доминик В. Берри, Педро К.С. Коста, Луис В. Тесслер, Натан Вибе, Крейг Гидни, Хартмут Невен и Райан Бэббуш. Составление отказоустойчивых квантовых эвристик для комбинаторной оптимизации. Квант PRX, 1 (2): 020312, 9 ноября 2020 г. ISSN 2691-3399. 10.1103/​prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Дэн Шепард и Майкл Дж. Бремнер. Временно неструктурированные квантовые вычисления. Учеб. Математика. Физ. англ. Sci., 465 (2105): 1413–1439, 8 мая 2009 г. ISSN 1364-5021,1471-2946. 10.1098/rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

[46] Питер-Пайк Слоан, Ян Каутц и Джон Снайдер. Предварительно рассчитанная передача излучения для рендеринга в реальном времени в условиях динамичного низкочастотного освещения. В материалах 29-й ежегодной конференции по компьютерной графике и интерактивным технологиям, SIGGRAPH '02, страницы 527–536, Нью-Йорк, штат Нью-Йорк, США, 1 июля 2002 г. ACM. ISBN 9781581135213/​10.1145.
https: / / doi.org/ 10.1145 / 566570.566612

[47] Джеймс Э. Смит. Исследование стратегий прогнозирования ветвей. За 25 лет международных симпозиумов по компьютерной архитектуре (избранные статьи), ISCA '98, страницы 202–215, Нью-Йорк, штат Нью-Йорк, США, 1 августа 1998 г. ACM. ISBN 9781581130584/​10.1145.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Роландо Д. Сомма и Йигит Субаши. Сложность проверки квантового состояния в задаче квантовых линейных систем. Квант PRX, 2 (1): 010315, 27 января 2021 г. ISSN 2691-3399. 10.1103/​prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Барбара М Терхал. Квантовая коррекция ошибок для квантовой памяти. Преподобный Мод. Phys., 87 (2): 307–346, 7 апреля 2015 г. ISSN 0034-6861,1539-0756. 10.1103/revmodphys.87.307.
https: / / doi.org/ 10.1103 / revmodphys.87.307

[50] Синьлань Чжоу, Дебби В. Люн и Исаак Л. Чуанг. Методология построения квантовых логических вентилей. Физ. Ред. А, 62 (5), 18 октября 2000 г. ISSN 1050-2947,1094-1622. 10.1103/физрева.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Цитируется

[1] Дар Гилбоа и Джаррод Р. МакКлин, «Преимущество экспоненциальной квантовой коммуникации в распределенном обучении», Arxiv: 2310.07136, (2023).

[2] Пабло Родригес-Граса, Рубен Ибаррондо, Хавьер Гонсалес-Конде, Юэ Бан, Патрик Ребентрост и Микель Санс, «Квантовое аппроксимированное возведение в степень матрицы плотности с помощью клонирования», Arxiv: 2311.11751, (2023).

Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2024-02-22 13:13:08). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.

Не удалось получить Перекрестная ссылка на данные во время последней попытки 2024-02-22 13:13:06: Не удалось получить цитируемые данные для 10.22331 / q-2024-02-22-1264 от Crossref. Это нормально, если DOI был зарегистрирован недавно.

Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.

Отметка времени:

Больше от Квантовый журнал