Коротші квантові ланцюги через апроксимацію однокубітового вентиля

Коротші квантові ланцюги через апроксимацію однокубітового вентиля

Коротші квантові схеми через апроксимацію однокубітового вентиля PlatoBlockchain Data Intelligence. Вертикальний пошук. Ai.

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

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

Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.

абстрактний

Ми пропонуємо нову процедуру апроксимації загальних однокубітових унітарних одиниць із кінцевого набору універсальних воріт, зводячи проблему до нової проблеми апроксимації величини, досягаючи негайного покращення довжини послідовності в 7/9 разів. Розширення робіт [28] І [15], ми показуємо, що використання імовірнісних сумішей каналів для вирішення резервного [13] і проблеми апроксимації величини економлять у два рази витрати на апроксимацію. Зокрема, за набором вентилів Кліффорда+$sqrt{mathrm{T}}$ ми досягаємо середнього числа некліффордівських воріт $0.23log_2(1/варепсилон)+2.13$ і T-рахунку $0.56log_2(1/варепсилон)+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$” Дискретна та обчислювальна геометрія 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] Андреас Бласс, Алекс Бочаров і Юрій Гуревич, «Оптимальні контури Pauli+V без допоміжних елементів для осьових обертань» Journal of Mathematical Physics 56, 122201 (2015).
https: / / doi.org/ 10.1063 / 1.4936990
arXiv: 1412.1033

[5] Майкл Беверленд, Ерл Кемпбелл, Марк Ховард і Вадим Ключніков, «Нижні межі некліффордівських ресурсів для квантових обчислень» Квантова наука та технологія 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] Jean Bourgainand Alex Gamburd “A Spectral Gap Theorem in SU$(d)$” Journal of the European Mathematical Society 14, 1455–1511 (2012).
https://​/​doi.org/​10.4171/​JEMS/​337

[8] Алекс Бочаров, Юрій Гуревич і Кріста М. Своре, «Ефективна декомпозиція однокубітових вентилів на V базисні схеми», Фізичний огляд A 88, 1–13 (2013).
https: / / doi.org/ 10.1103 / PhysRevA.88.012313
arXiv: 1303.1411

[9] Сергій Брав’ян та Олексій Китаєв “Універсальне квантове обчислення з ідеальними вентилями Кліффорда та зашумленими анцилами” Phys. Rev. A 71, 022316 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022316

[10] Sergey Bravyiand Robert König “Класифікація топологічно захищених вентилів для локальних кодів стабілізації” 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] Алекс Бочаров, Мартін Роттлер і Кріста М. Своре, «Ефективний синтез універсальних повторюваних до успіху квантових ланцюгів» Фізичні оглядові листи 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502
arXiv: 1404.5320

[13] Алекс Бочаров, Мартін Роттлер і Кріста М. Своре, «Ефективний синтез ймовірнісних квантових схем із резервним відключенням» Фізичний огляд 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. Чарльз, Крістін Е. Лаутер та Еял З. Горен, «Криптографічні хеш-функції з розширювальних графів» Журнал криптології 22, 93–113 (2009).
https: / / doi.org/ 10.1007 / s00145-007-9002-x

[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] Bryan Eastinand Emanuel Knill “Restrictions on Transversal Encoded Quantum Gate Sets” 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⟩$» Квант 3, 135 (2019).
https:/​/​doi.org/​10.22331/​q-2019-04-30-135

[25] Joachim von zur Gathenand Jürgen Gerhard “Modern Computer Algebra” Cambridge University Press (2013).
https://​/​doi.org/​10.1017/​CBO9781139856065

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

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

[28] Метью Б. Гастінгс «Перетворення помилок синтезу вентиля в некогерентні помилки» Квантова інформація та обчислення 17, 488–494 (2017).
https://​/​doi.org/​10.48550/​arXiv.1612.01011
arXiv: 1612.01011

[29] Арам В. Харроу, Бенджамін Рехт та Ісаак Л. Чуанг, “Ефективні дискретні апроксимації квантових воріт” Журнал математичної фізики 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. Rev. A 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] Натаніель Джонстон, Девід В. Крібс і Верн І. Полсен, «Обчислення стабілізованих норм для квантових операцій за допомогою теорії повністю обмежених карт» Квантова інформація. обчис. 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/​oso/​9780198570004.001.0001

[37] В. Ключніков, Д. Маслов і М. Моска, «Асимптотично оптимальне наближення однокубітних унітарних елементів схемами Кліффорда і Т з використанням постійної кількості допоміжних кубітів» Фізичні оглядові листи 110, 190502 (2013).
https: / / doi.org/ 10.1103 / PhysRevLett.110.190502
arXiv: 1212.0822

[38] Вадим Ключніков, Дмитро Маслов і Мікеле Моска, «Швидкий і ефективний точний синтез однокубітних унітарних систем, створених Кліффордом і Т. Гейтсом» Квантова інформація. обчис. 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] Guang Hao Low і Isaac L. Chuang “Оптимальне гамільтонівське моделювання за допомогою квантової обробки сигналів” 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] Даніель Літінскі «Гра поверхневих кодів: великомасштабні квантові обчислення з ґратковою хірургією» Квант 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] A. Lubotzky, R. Phillips і P. Sarnak, “Ramanujan graphs” Combinatorica 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799

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

[47] Емануель Мальветті, Рабан Ітен і Роджер Колбек, «Квантові схеми для розріджених ізометрій» Квант 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] Габріеле Небе, Ерік М. Рейнс і Ніл Дж.А. Sloane, “Real and Complex Clifford Groups” Springer Berlin Heidelberg (2006).
https:/​/​doi.org/​10.1007/​3-540-30731-1_6

[51] Юнсон Нам, Юань Су та Дмитро Маслов, «Наближене квантове перетворення Фур’є з O(n log(n)) T гейтами» npj Квантова інформація 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] Eduardo Carvalho Pinto and Christophe Petit “Better path-finding algorithms in LPS Ramanujan graphs” Journal of Mathematical Cryptology 12, 191–202 (2018).
https://​/​doi.org/​10.1515/​jmc-2017-0051

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

[55] Орі Парзанчевський і Пітер Сарнак «Super-Golden-Gates for PU(2)» Advances in Mathematics 327, 869–901 (2018) Спеціальний том на честь Девіда Каждана.
https://​/​doi.org/​10.1016/​j.aim.2017.06.022

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

[57] Ніл Дж. Россан Пітер Селінджер «Оптимальне наближення Clifford+T для z-обертання без допоміжних елементів» Квантова інформація та обчислення 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] Пітер Селінгер «Ефективна апроксимація однокубітових операторів Clifford+T» Квантова інформація та обчислення 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] Джон Войт «Quaternion Algebras» 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] Пол Вебстер і Стівен Д. Бартлетт «Відмовостійкі квантові вентилі з дефектами в кодах топологічного стабілізатора» Фіз. Rev. A 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).

Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2023-12-19 01:59:59). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2023-12-19 01:59:58).

Часова мітка:

Більше від Квантовий журнал