Более короткие квантовые схемы с помощью приближения однокубитного вентиля

Более короткие квантовые схемы с помощью приближения однокубитного вентиля

Отметка времени: 18 декабря 2023 г., 8:56
Более короткие квантовые схемы с помощью аппроксимации однокубитных вентилей PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

Вадим Ключников1,2, Кристин Лаутер3, Роми Минко4,5, Адам Петцник1и Кристоф Пети6,7

1Microsoft Quantum, Редмонд, Вашингтон, США
2Microsoft Quantum, Торонто, Онтарио, Калифорния
3Facebook AI Research, Сиэтл, Вашингтон, США
4Оксфордский университет, Оксфорд, Великобритания
5Хайльброннский институт математических исследований, Бристольский университет, Бристоль, Великобритания
6Бирмингемский университет, Бирмингем, Великобритания
7Свободный университет Брюсселя, Брюссель, Бельгия

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

Абстрактные

Мы даем новую процедуру аппроксимации общих однокубитных унитарных единиц из конечного универсального набора вентилей, сводя проблему к новой задаче аппроксимации величины, достигая немедленного улучшения длины последовательности в 7/9 раз. Продление работ [28] И [15], мы показываем, что использование вероятностных смесей каналов для решения резервного варианта [13] и задачи аппроксимации величины экономят вдвое затраты на аппроксимацию. В частности, по набору вентилей Клиффорда+$sqrt{mathrm{T}}$ мы достигаем среднего количества вентилей, не относящихся к Клиффорду, $0.23log_2(1/varepsilon)+2.13$ и T-count $0.56log_2(1/varepsilon)+5.3. $ со смешанными запасными аппроксимациями для точности нормы алмаза $varepsilon$.
В этой статье представлен целостный обзор аппроксимации вентилей в дополнение к этим новым открытиям. Мы даем сквозную процедуру аппроксимации вентилей для общих множеств вентилей, связанных с некоторыми кватернионными алгебрами, предоставляя педагогические примеры с использованием обычных отказоустойчивых множеств вентилей (V, Clifford+T и Clifford+$sqrt{mathrm{T}}$). . Мы также предоставляем подробные численные результаты для наборов вентилей Clifford+T и Clifford+$sqrt{mathrm{T}}$. Стремясь сохранить самодостаточность статьи, мы включили обзор соответствующих алгоритмов для перечисления целочисленных точек и решения уравнений относительной нормы. В Приложениях мы приводим ряд дальнейших приложений задач аппроксимации величин, а также улучшенные алгоритмы точного синтеза.

► Данные BibTeX

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

[1] Фрэнк Аруте, Кунал Арья, Райан Бэббуш, Дэйв Бэкон, Джозеф С. Бардин, Рами Барендс, Рупак Бисвас, Серджио Бойшо, Фернандо Г.С.Л. Брандао, Дэвид А. Бьюэлл, Брайан Беркетт, Ю Чен, Цзыджун Чен, Бен Кьяро, Роберто Коллинз, Уильям Кортни, Эндрю Дансуорт, Эдвард Фархи, Брукс Фоксен, Остин Фаулер, Крэйг Гидни, Марисса Джустина, Роб Графф, Кит Герин, Стив Хабеггер, Мэттью П. Харриган, Майкл Дж. Хартманн, Алан Хо, Маркус Хоффманн, Трент Хуанг, Трэвис С. Хамбл, Сергей В. Исаков, Эван Джеффри, Чжан Цзян, Двир Кафри, Константин Кечеджи, Джулиан Келли, Пол В. Климов, Сергей Кныш, Александр Коротков, Федор Кострица, Дэвид Ландхейс, Майк Линдмарк, Эрик Лусеро, Дмитрий Лях, Сальваторе Мандра, Джаррод Р. МакКлин, Мэттью МакИвен, Энтони Мегрант, Сяо Ми, Кристель Михельсен, Масуд Мохсени, Джош Мутус, Офер Нааман, Мэттью Нили, Чарльз Нил, Мерфи Юэжен Ню, Эрик Остби, Андре Петухов, Джон К. Платт, Крис Кинтана, Элеонора Дж. Риффель, Педрам Рушан, Николас С. Рубин, Дэниел Санк, Кевин Дж. Сатцингер, Вадим Смелянский, Кевин Дж. Санг, Мэттью Д. Тревитик, Амит Вайнсенчер, Бенджамин Вильялонга, Теодор Уайт, З. Джейми Яо , Пинг Йе, Адам Зальцман, Хартмут Невен и Джон М. Мартинис, «Квантовое превосходство с использованием программируемого сверхпроводящего процессора», Nature 574, 505-510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] Войцех Банащик «Неравенства для выпуклых тел и полярных обратных решеток в $R^n$» Discrete & Computational Geometry 13, 217–231 (1995).
https: / / doi.org/ 10.1007 / BF02574039

[3] Адриано Баренко, Чарльз Х. Беннетт, Ричард Клив, Дэвид П. ДиВинченцо, Норман Марголус, Питер Шор, Тихо Слиатор, Джон А. Смолин и Харальд Вайнфуртер, «Элементарные вентили для квантовых вычислений», Physical Review A 52, 3457–3467 ( 1995).
https: / / doi.org/ 10.1103 / PhysRevA.52.3457

[4] Андреас Бласс, Алекс Бочаров и Юрий Гуревич, «Оптимальные схемы Паули + V без вспомогательных элементов для осевых вращений», Журнал математической физики 56, 122201 (2015).
https: / / doi.org/ 10.1063 / 1.4936990
Arxiv: 1412.1033

[5] Майкл Беверленд, Эрл Кэмпбелл, Марк Ховард и Вадим Ключников, «Нижние границы неклиффордовых ресурсов для квантовых вычислений», Quantum Science and Technology 5, 035009 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab8963
Arxiv: 1904.01124

[6] Майкл Э. Беверланд, Пракаш Мурали, Маттиас Тройер, Криста М. Своре, Торстен Хефлер, Вадим Ключников, Гуан Хао Лоу, Матиас Соекен, Аарти Сундарам и Александр Васчилло, «Оценка требований для масштабирования до практического квантового преимущества» (2022).
https://​/​doi.org/​10.48550/​arXiv.2211.07629
Arxiv: 2211.07629

[7] Жан Бурген и Алекс Гамбур «Теорема о спектральной щели в SU$(d)$» Журнал Европейского математического общества 14, 1455–1511 (2012).
https: / / doi.org/ 10.4171 / JEMS / 337

[8] Алекс Бочаров, Юрий Гуревич и Криста М. Своре, «Эффективное разложение однокубитных вентилей на V-базисные схемы», Physical Review A 88, 1–13 (2013).
https: / / doi.org/ 10.1103 / PhysRevA.88.012313
Arxiv: 1303.1411

[9] Сергей Бравий и Алексей Китаев «Универсальные квантовые вычисления с идеальными вентилями Клиффорда и шумными вспомогательными устройствами» Физ. Ред. А 71, 022316 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022316

[10] Сергей Бравиян и Роберт Кёниг «Классификация топологически защищенных вентилей для кодов локального стабилизатора» Phys. Преподобный Летт. 110, 170503 (2013).
https: / / doi.org/ 10.1103 / PhysRevLett.110.170503

[11] Майкл Э. Беверланд, Александр Кубица и Криста М. Своре, «Цена универсальности: сравнительное исследование накладных расходов на дистилляцию состояний и переключение кода с помощью цветовых кодов», PRX Quantum 2, 020341 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020341

[12] Алекс Бочаров, Мартин Реттелер и Криста М. Своре, «Эффективный синтез универсальных квантовых схем с повторением до успеха», Physical Review Letters 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502
Arxiv: 1404.5320

[13] Алекс Бочаров, Мартин Реттелер и Криста М. Своре, «Эффективный синтез вероятностных квантовых схем с резервным копированием», Physical Review A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317
Arxiv: 1409.3552

[14] Вера фон Бург, Гуан Хао Лоу, Томас Ханер, Дамиан С. Штайгер, Маркус Райхер, Мартин Реттелер и Маттиас Тройер, «Квантовые вычисления, улучшенный вычислительный катализ», Phys. Ред. Исследования 3, 033055 (2021).
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033055

[15] Эрл Кэмпбелл «Более короткие последовательности вентилей для квантовых вычислений путем смешивания унитарных элементов» Physical Review A 95 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.042306
Arxiv: 1612.02689

[16] Эндрю М. Чайлдс, Юань Су, Мин К. Тран, Натан Вибе и Шучен Чжу, «Теория ошибки Троттера с масштабированием коммутатора», Phys. Ред. X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020

[17] Денис X. Чарльз, Кристин Э. Лаутер и Эял З. Горен, «Криптографические хэш-функции из расширительных графов», Journal of Cryptology 22, 93–113 (2009).
HTTPS: / / doi.org/ 10.1007 / s00145-007-9002-х

[18] Анри Коэн «Продвинутые темы вычислительной теории чисел» Springer New York (2000).
https:/​/​doi.org/​10.1007/​978-1-4419-8489-0

[19] Анри Коэн «Курс вычислительной алгебраической теории чисел» Springer Berlin Heidelberg (1993).
https:/​/​doi.org/​10.1007/​978-3-662-02945-9

[20] Набор данных о более коротких квантовых схемах (2023 г.).
https://azure-quantum-notebooks.azurefd.net/publicdata/shorter-quantum-circuits-dataset.tar

[21] Брайан Истин и Эмануэль Нилл «Ограничения на наборы трансверсально-кодированных квантовых вентилей» Phys. Преподобный Летт. 102, 110502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.110502

[22] Саймон Форест, Дэвид Госсет, Вадим Ключников и Дэвид Маккиннон, «Точный синтез однокубитных унитарных элементов с помощью наборов циклотомных вентилей Клиффорда», Журнал математической физики 56, 082201 (2015).
https: / / doi.org/ 10.1063 / 1.4927100

[23] Дэниел Готтесман и Исаак Л. Чуанг «Демонстрация жизнеспособности универсальных квантовых вычислений с использованием телепортации и однокубитных операций» Nature 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[24] Крейг Гидни и Остин Г. Фаулер «Эффективные фабрики магических состояний с катализируемым преобразованием $|CCZ⟩$ в $2|T⟩$» Quantum 3, 135 (2019).
https:/​/​doi.org/​10.22331/​q-2019-04-30-135

[25] Иоахим фон Цур Гатенанд Юрген Герхард «Современная компьютерная алгебра» Издательство Кембриджского университета (2013).
https: / / doi.org/ 10.1017 / CBO9781139856065

[26] Крейг Гидни «Уменьшение вдвое стоимости квантового сложения» Quantum 2, 74 (2018).
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

[27] Дэвид Госсет, Вадим Ключников, Мишель Моска и Винсент Руссо, «Алгоритм T-подсчета», Quantum Info. Вычислить. 14, 1261–1276 (2014).
https://​/​doi.org/​10.48550/​arXiv.1308.4134

[28] Мэтью Б. Гастингс «Превращение ошибок синтеза вентилей в некогерентные ошибки» Quantum Information and Computation 17, 488–494 (2017).
https://​/​doi.org/​10.48550/​arXiv.1612.01011
Arxiv: 1612.01011

[29] Арам В. Харроу, Бенджамин Рехт и Исаак Л. Чуанг, «Эффективные дискретные приближения квантовых вентилей», Journal of Mathematical Physics 43, 4445–4451 (2002).
https: / / doi.org/ 10.1063 / 1.1495899

[30] Кеннет Айрленд и Майкл Розен «Классическое введение в современную теорию чисел», Springer New York (1990).
https:/​/​doi.org/​10.1007/​978-1-4757-2103-4

[31] Рабан Итен, Роджер Колбек, Иван Кукулян, Джонатан Хоум и Маттиас Кристандл, «Квантовые схемы для изометрий» Phys. Ред. А 93, 032318 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032318

[32] Рабан Итен, Оливер Рирдон-Смит, Эмануэль Мальветти, Лука Мондада, Габриэль Повер, Итан Редмонд, Равджот Сингх Кохли и Роджер Колбек, «Введение в UniversalQCompiler» (2021).
https://​/​doi.org/​10.48550/​arXiv.1904.01072
Arxiv: 1904.01072

[33] Натаниэль Джонстон, Дэвид В. Крибс и Верн И. Полсен, «Вычисление стабилизированных норм для квантовых операций с помощью теории полностью ограниченных карт», Quantum Info. Вычислить. 9, 16–35 (2009).
https://​/​doi.org/​10.48550/​arXiv.0711.3636

[34] Александр Яковлевич Хинчин «Количественная формулировка аппроксимационной теории Кронекера» Известия Российской академии наук. Серия Математическая 12, 113–122 (1948).

[35] В. Ключников, А. Бочаров, М. Реттелер и Дж. Ярд, «Схема аппроксимации унитарных кубитов» (2015).
https://​/​doi.org/​10.48550/​arXiv.1510.03888
Arxiv: 1510.03888

[36] Филип Кэй, Раймонд Лафламм и Мишель Моска, «Введение в квантовые вычисления», Oxford University Press (2006).
https: / / doi.org/ 10.1093 / осо / 9780198570004.001.0001

[37] В. Ключников, Д. Маслов и М. Моска, «Асимптотически оптимальная аппроксимация однокубитных унитарных блоков с помощью Клиффорда и Т-схем с использованием постоянного числа вспомогательных кубитов», Physical Review Letters 110, 190502 (2013).
https: / / doi.org/ 10.1103 / PhysRevLett.110.190502
Arxiv: 1212.0822

[38] Вадим Ключников, Дмитрий Маслов и Мишель Моска, «Быстрый и эффективный точный синтез однокубитных унитарных элементов, генерируемых Клиффордом и Т-гейтами», Quantum Info. Вычислить. 13, 607–630 (2013).
https://​/​doi.org/​10.48550/​arXiv.1206.5236

[39] В. Ключников и Дж. Ярд «Основы точного синтеза» (2015).
https://​/​doi.org/​10.48550/​arXiv.1504.04350
Arxiv: 1504.04350

[40] Гуан Хао Лованд Исаак Л. Чуанг «Оптимальное моделирование гамильтониана посредством квантовой обработки сигналов» Phys. Преподобный Летт. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[41] Франц Леммермейер «Алгоритм Евклида в полях алгебраических чисел» Expositiones Mathematicae 13, 385–416 (1995).

[42] Х. В. Ленстра «Целочисленное программирование с фиксированным числом переменных» Математика исследования операций 8, 538–548 (1983).
https: / / doi.org/ 10.1287 / moor.8.4.538

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

[44] А. К. Ленстра, Х. В. Ленстра и Л. Ловас, “Факторизация полиномов с рациональными коэффициентами”, Mathematische Annalen 261, 515–534 (1982).
https: / / doi.org/ 10.1007 / BF01457454

[45] А. Любоцкий, Р. Филлипс и П. Сарнак, «Графы Рамануджана», Combinatorica 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799

[46] Ишвар Магесан, Джей М. Гамбетта и Джозеф Эмерсон, «Характеристика квантовых вентилей с помощью рандомизированного тестирования» Phys. Ред. A 85, 042311 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.85.042311

[47] Эмануэль Мальветти, Рабан Итен и Роджер Колбек, «Квантовые схемы для разреженных изометрий», Quantum 5, 412 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-412

[48] Майкл А. Нильсен и Исаак Л. Чуанг «Квантовые вычисления и квантовая информация» Cambridge University Press (2012).
https: / / doi.org/ 10.1017 / CBO9780511976667

[49] Блокнот по коротким квантовым схемам (2023 г.).
https:/​/​github.com/​microsoft/​Quantum/​blob/​a57178163b64a060d37603355c8a78571075f679/​samples/​azure-quantum/​shorter-quantum-circuits/​shorter-quantum-circuits-dataset.ipynb

[50] Габриэле Небе, Эрик М. Рейнс и Нил Дж.А. Слоан, «Реальные и комплексные группы Клиффорда», Springer Berlin Heidelberg (2006).
https:/​/​doi.org/​10.1007/​3-540-30731-1_6

[51] Юнсон Нам, Юань Су и Дмитрий Маслов, «Приблизительное квантовое преобразование Фурье с T-вентилями O(n log(n))» npj Quantum Information 6, 26 (2020).
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[52] Кристоф Пети, Кристин Лаутер и Жан-Жак Кискатер, «Полный криптоанализ LPS и хэш-функций Моргенштерна» (2008).
https:/​/​doi.org/​10.1007/​978-3-540-85855-3_18

[53] Эдуардо Карвальо Пинто и Кристоф Пети «Улучшенные алгоритмы поиска пути в графах LPS Раманухана» Журнал математической криптологии 12, 191–202 (2018).
https: / / doi.org/ 10.1515 / jmc-2017-0051

[54] Адам Паецник и Криста М. Своре «Повторяй до успеха: недетерминированное разложение однокубитных унитарных элементов» Quantum Information and Computation 14, 1277–1301 (2014).
https://​/​doi.org/​10.48550/​arXiv.1311.1074
Arxiv: 1311.1074

[55] Ори Парзанчевски и Питер Сарнак «Супер-золотые ворота для PU (2)» Успехи в математике 327, 869–901 (2018) Специальный том в честь Давида Каждана.
https: / / doi.org/ 10.1016 / j.aim.2017.06.022

[56] Нил Дж. Росс «Оптимальная аппроксимация Z-вращений Клиффорда + V без вспомогательных сил» Quantum Info. Вычислить. 15, 932–950 (2015).
https://​/​doi.org/​10.48550/​arXiv.1409.4355

[57] Нил Дж. Россанд Питер Селинджер «Оптимальное безвспомогательное приближение Клиффорда + Т для z-вращений» Quantum Information & Computation 15, 932–950 (2015).
https://​/​doi.org/​10.48550/​arXiv.1403.2975
Arxiv: 1403.2975

[58] Питер Сарнак «Письмо Ааронсону и Поллингтону о теореме Сольвея-Китаева и Золотых воротах, 2015».
http://​/​publications.ias.edu/​sarnak/​paper/​2637

[59] Насер Т. Сардари «Сложность сильного приближения на сфере» Международные уведомления о математических исследованиях 2021, 13839–13866 (2021).
https://doi.org/10.1093/imrn/rnz233

[60] Питер Селинджер «Эффективное приближение Клиффорда + Т однокубитных операторов» Quantum Information & Computation 15, 159–180 (2015).
https://​/​doi.org/​10.48550/​arXiv.1212.6253
Arxiv: 1212.6253

[61] Частное сообщение Закари Стира (2020).

[62] Жан-Пьер Тилишан Жиль Земор «Коллизии хеш-функции графа расширителя LPS» Ежегодная международная конференция по теории и приложениям криптографических методов 254–269 (2008).
https:/​/​doi.org/​10.1007/​978-3-540-78967-3_15

[63] Джон Войт «Алгебры кватернионов» Springer International Publishing (2021).
https:/​/​doi.org/​10.1007/​978-3-030-56694-4

[64] Лоуренс К. Вашингтон «Введение в циклотомные поля» Springer New York (1997).
https:/​/​doi.org/​10.1007/​978-1-4612-1934-7

[65] Джон Уотроус «Теория квантовой информации» Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142

[66] Пол Вебстер и Стивен Д. Бартлетт «Отказоустойчивые квантовые вентили с дефектами в кодах топологических стабилизаторов» Phys. Ред. А 102, 022403 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022403

Цитируется

[1] Дэниел Литински и Наоми Никерсон, «Активный том: архитектура для эффективных отказоустойчивых квантовых компьютеров с ограниченными нелокальными соединениями», Arxiv: 2211.15465, (2022).

[2] Паскаль Басслер, Маттиас Зиппер, Кристофер Цедзих, Маркус Генрих, Патрик Х. Хубер, Михаэль Йоханнинг и Мартин Клиш, «Синтез и компиляция с оптимальными по времени многокубитными вентилями», Квант 7, 984 (2023).

[3] Сейсэки Акибуэ, Го Като и Сейитиро Тани, «Вероятностный унитарный синтез с оптимальной точностью», Arxiv: 2301.06307, (2023).

[4] Томас Лубински, Кассандра Гранаде, Амос Андерсон, Алан Геллер, Мартин Реттелер, Андрей Петренко и Беттина Хайм, «Продвижение гибридных квантово-классических вычислений с выполнением в реальном времени», Границы физики 10, 940293 (2022).

[5] Сейсэки Акибуэ, Го Като и Сейитиро Тани, «Вероятностный синтез состояний на основе оптимального выпуклого приближения», Arxiv: 2303.10860, (2023).

Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2023-12-19 01:59:59). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2023-12-19 01:59:58).

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

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

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