Швидке моделювання планарних кіл Кліффорда

Швидке моделювання планарних кіл Кліффорда

Мітка часу: 12 лютого 2024 10:28

Девід Госсет1,2,3, Даніель Грір1,4,5, Алекс Керцнер1,2і Люк Шеффер1,2,6

1Інститут квантових обчислень, Університет Ватерлоо, Канада
2Відділ комбінаторики та оптимізації, Університет Ватерлоо, Канада
3Інститут теоретичної фізики Периметр, Ватерлоо, Канада
4Школа інформатики Черітон, Університет Ватерлоо, Канада
5Департамент комп’ютерних наук та інженерії та Департамент математики Каліфорнійського університету, Сан-Дієго, США
6Об’єднаний центр квантової інформації та комп’ютерних наук, Коледж Парк, Меріленд, США

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

абстрактний

Загальну квантову схему можна моделювати класично в експоненціальному часі. Якщо він має планарний макет, тоді алгоритм скорочення тензорної мережі, створений Марковом і Ши, має експоненціальний час виконання, виражений у квадратному корені його розміру, або, загалом, експоненціальний у ширині дерева основного графіка. Окремо Готтесман і Нілл показали, що якщо всі ворота обмежені Кліффордовими, то існує поліноміальне моделювання часу. Ми поєднуємо ці дві ідеї та показуємо, що ширину дерева та планарність можна використати для покращення моделювання схеми Кліффорда. Наш основний результат — це класичний алгоритм із асимптотичним масштабуванням часу виконання як $ n^{omega/2}$ $lt$ $n^{1.19}$, який бере вибірку з вихідного розподілу, отриманого шляхом вимірювання всіх $n$ кубітів стану плоского графа у заданих базах Паулі. Тут $omega$ — показник множення матриці. Ми також надаємо класичний алгоритм з тим самим асимптотичним часом виконання, який бере вибірку з розподілу виходу будь-якої схеми Кліффорда постійної глибини в плоскій геометрії. Наша робота вдосконалює відомі класичні алгоритми з кубічним часом виконання.

Ключовим компонентом є відображення, яке, враховуючи деревоподібну декомпозицію деякого графа $G$, створює схему Кліффорда зі структурою, що відображає розкладання дерева та емулює вимірювання відповідного стану графа. Ми надаємо класичну симуляцію цієї схеми з часом виконання, вказаним вище для планарних графів, а також $nt^{omega-1}$, де $t$ — це ширина розкладання дерева. Наш алгоритм містить дві підпрограми, які можуть представляти незалежний інтерес. Перший — це версія матриці-множення-часу моделювання Готтесмана-Нілла вимірювання мультикубітів на станах стабілізатора. Другий — це новий класичний алгоритм для розв’язання симетричних лінійних систем над $mathbb{F}_2$ у плоскій геометрії, що розширює попередні роботи, які застосовувалися лише до неособливих лінійних систем у аналогічних умовах.

Fast simulation of planar Clifford circuits PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Рекомендоване зображення: за годинниковою стрілкою зліва: графік, гарна декомпозиція дерева та схема, яка готує відповідний стан графіка.

[Вбудоване вміст]

► Дані BibTeX

► Список літератури

[1] Френк Аруте, Кунал Ар’я, Раян Беббуш, Дейв Бекон, Джозеф С. Бардін, Рамі Барендс, Рупак Бісвас, Серхіо Бойшо, Фернандо Дж. С. Л. Брандао, Девід А. Буелл та ін. «Квантова перевага за допомогою програмованого надпровідного процесора». Nature 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] «Квантова документація IBM». https://​/​docs.quantum.ibm.com/​run.
https://​/​docs.quantum.ibm.com/​run

[3] Меттью Д. Рід, Леонардо ДіКарло, Саймон Е. Нігг, Луян Сан, Луїджі Фрунзіо, Стівен М. Гірвін і Роберт Дж. Шолкопф. «Реалізація трикубітової квантової корекції помилок за допомогою надпровідних схем». Nature 482, 382–385 (2012).
https: / / doi.org/ 10.1038 / nature10786

[4] Антоніо Д Корколес, Ісвар Магесан, Шрікант Дж. Срінівасан, Ендрю В. Кросс, Матіас Штеффен, Джей М. Гамбетта та Джеррі М. Чоу. «Демонстрація квантового коду виявлення помилок з використанням квадратної решітки з чотирьох надпровідних кубітів». Nature Communications 6, 1–10 (2015).
https: / / doi.org/ 10.1038 / ncomms7979

[5] Нісім Офек, Андрій Петренко, Райньєр Херес, Філіп Рейнхолд, Закі Легхтас, Браян Властакіс, Єхан Лю, Луїджі Фрунзіо, С. М. Гірвін, Лян Цзян та ін. «Збільшення терміну служби квантового біта з корекцією помилок у надпровідних схемах». Nature 536, 441–445 (2016).
https: / / doi.org/ 10.1038 / nature18949

[6] Ігор Л Марков і Яоюнь Ши. «Моделювання квантових обчислень шляхом скорочення тензорних мереж». SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[7] Серхіо Бойхо, Сергій В Ісаков, Вадим Н Смілянський та Хартмут Невен. «Моделювання квантових схем малої глибини як складних неорієнтованих графічних моделей» (2017).

[8] Сергій Бравий, Ден Браун, Падрейк Келпін, Ерл Кемпбелл, Девід Госсет і Марк Ховард. “Моделювання квантових ланцюгів шляхом розкладання стабілізатора низького рангу”. Квант 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[9] Едвін Педно, Джон А. Ганнелс, Джакомо Наннічіні, Ліор Хореш, Томас Магерляйн, Едгар Соломонік, Ерік В. Дрегер, Ерік Т. Холланд і Роберт Вісніфф. «Подолання 49-кубітового бар’єру в моделюванні квантових схем» (2017).

[10] Едвін Педно, Джон Ганнелс, Джакомо Наннічіні, Ліор Хореш і Роберт Вісніфф. «Використання вторинного сховища для моделювання глибоких 54-кубітних схем Sycamore» (2019).

[11] Боаз Барак, Чі-Нін Чоу та Сюнь Гао. «Підробний лінійний крос-ентропійний бенчмаркінг у дрібних квантових схемах» (2020).

[12] Барбара М. Терхал і Девід П. ДіВінченцо. «Адаптивне квантове обчислення, квантові схеми постійної глибини та ігри Артура-Мерліна» (2002).

[13] Майкл Бремнер, Річард Джоза та Ден Шеперд. «Класичне моделювання комутуючих квантових обчислень передбачає колапс поліноміальної ієрархії». Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459–472 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

[14] Скотт Ааронсон і Алекс Архіпов. “Обчислювальна складність лінійної оптики”. У матеріалах сорок третього щорічного симпозіуму ACM з теорії обчислень. Сторінки 333–342. (2011).
https: / / doi.org/ 10.1145 / 1993636.1993682

[15] Даніель Готтесман. “Подання Гейзенберга квантових комп’ютерів” (1998).

[16] Сергій Бравий і Девід Госсет. «Покращене класичне моделювання квантових схем, де домінують ворота Кліффорда». Фізичні оглядові листи 116, 250501 (2016).
https://​/​doi.org/​10.1103/​physrevlett.116.250501

[17] Скотт Ааронсон і Деніел Готтесман. «Покращене моделювання схем стабілізатора». Фізичний огляд А 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[18] Сергій Бравий, Девід Госсет і Роберт Кеніг. «Квантова перевага з неглибокими ланцюгами». Наука 362, 308–311 (2018).
https://​/​doi.org/​10.1126/​science.aar3106

[19] Адам Бене Воттс, Робін Котарі, Люк Шеффер і Авішай Тал. «Експоненціальне розділення між неглибокими квантовими ланцюгами та необмеженими неглибокими класичними ланцюгами». У матеріалах 51-го щорічного симпозіуму ACM SIGACT з теорії обчислень. Сторінки 515–526. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316404

[20] Деніел Грієр і Люк Шеффер. «Інтерактивні мілкі схеми Кліффорда: квантова перевага проти $mathsf{NC}^1$ і далі». У матеріалах 52-го щорічного симпозіуму ACM SIGACT з теорії обчислень. Сторінки 875–888. (2020).
https: / / doi.org/ 10.1145 / 3357713.3384332

[21] Сергій Бравий, Девід Госсет, Роберт Кеніг і Марко Томамічел. «Квантова перевага з шумними неглибокими ланцюгами». Nature PhysicsPages 1–6 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[22] Роберт Рауссендорф і Ханс Брігель. «Односторонній квантовий комп’ютер». Physical Review Letters 86, 5188 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[23] Джош Алман і Вірджинія Василевська Вільямс. «Удосконалений лазерний метод і швидше множення матриць» (2020).

[24] Чаовен Гуань і Кеннет В. Ріган. «Стабілізаторні схеми, квадратичні форми та ранг обчислювальної матриці» (2019).

[25] Деніел Грієр і Люк Шеффер. “gridCHP++, ліцензія Apache версії 2.0”. https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0.
https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0

[26] Алан Джордж. “Вкладене розсічення регулярної кінцево-елементної сітки”. SIAM Journal on Numerical Analysis 10, 345–363 (1973).
https: / / doi.org/ 10.1137 / 0710032

[27] Річард Ліптон, Дональд Роуз і Роберт Ендре Тар'ян. «Узагальнене вкладене розтин». Журнал SIAM про чисельний аналіз 16, 346–358 (1979).
https: / / doi.org/ 10.1137 / 0716027

[28] Нога Алон і Рафаель Юстер. “Розв’язування лінійних систем за допомогою вкладеного розрізу”. У 2010 р. 51-й щорічний симпозіум IEEE з основ комп’ютерних наук. Сторінки 225–234. IEEE (2010).
https://​/​doi.org/​10.1109/​FOCS.2010.28

[29] Річард Дж. Ліптон і Роберт Ендре Тар'ян. “Теорема про розділення плоских графів”. SIAM Journal on Applied Mathematics 36, 177–189 (1979).
https: / / doi.org/ 10.1137 / 0136016

[30] Скотт Ааронсон і Ліцзі Чен. “Теоретико-комплексні основи експериментів з квантовою перевагою”. На 32-й Конференції з обчислювальної складності (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017).

[31] Цзяньсінь Чен, Фан Чжан, Чапджін Хуан, Майкл Ньюман і Яоюнь Ши. «Класичне моделювання квантових схем середнього розміру» (2018).

[32] Бенджамін Віллалонга, Дмитро Лях, Серхіо Бойшо, Хартмут Невен, Тревіс Хамбл, Рупак Бісвас, Елеонора Ріффель, Алан Хо та Сальваторе Мандра. «Встановлення кордону квантової переваги за допомогою симуляції 281 пфлоп/с». Квантова наука та технологія 5, 034003 (2020).
https://​/​doi.org/​10.1088/​2058-9565/​ab7eeb

[33] Стефан Арнборг, Дерек Дж. Корнейл та Анджей Проскуровський. “Складність знаходження вкладень у $k$-дерево”. Журнал SIAM про алгебраїчні дискретні методи 8, 277–284 (1987).
https: / / doi.org/ 10.1137 / 0608024

[34] Х. Л. Бодлендер. «Туристичний путівник по лісовій широті». Acta Cybernetica 11, 1–21 (1993).

[35] Ганс Л. Бодлендер, Пол Гроонас Дранге, Маркус С. Дрегі, Федір В. Фомін, Даніель Локштанов і Міхал Піліпчук. “$c^kn$ 5-апроксимаційний алгоритм для ширини дерева”. SIAM Journal on Computing 45, 317–378 (2016).
https: / / doi.org/ 10.1137 / 130947374

[36] Сергій Бравий, Грем Сміт і Джон Смолін. «Торгівля класичними та квантовими обчислювальними ресурсами». Physical Review X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[37] М Ван ден Нест. «Класичне моделювання квантових обчислень, теорема Готтесмана-Нілла та трохи більше» (2008).

[38] Алекс Керцнер. «Моделювання Кліффорда: методи та застосування». Магістерська робота. Університет Ватерлоо. (2021).

[39] Карстен Дамм. “Проблеми завершено для $oplus{L}$”. Юрген Дассов і Йозеф Келемен, редактори, Аспекти та перспективи теоретичної інформатики. Сторінки 130–137. Берлін, Гейдельберг (1990). Шпрінгер Берлін Гейдельберг.
https:/​/​doi.org/​10.1016/​0020-0190(90)90150-V

[40] Девід Еппштейн (2007). commons.wikimedia.org/​wiki/​Файл:Tree_decomposition.svg, доступ 08.

[41] Ханс Л. Бодлендер і Тон Клокс. «Кращі алгоритми для ширини шляху та ширини дерева графіків». В автоматах, мовах і програмуванні: 18-й міжнародний колоквіум, Мадрид, Іспанія, 8–12 липня 1991 р. Матеріали 18. Сторінки 544–555. Springer (1991).
https:/​/​doi.org/​10.1007/​3-540-54233-7_162

[42] Оскар Ібарра, Шломо Моран і Роджер Хуей. «Узагальнення швидкого алгоритму декомпозиції матриці LUP і додатків». Journal of Algorithms 3, 45–56 (1982).
https:/​/​doi.org/​10.1016/​0196-6774(82)90007-4

[43] Аді Бен-Ісраель і Томас Н. Гревіль. “Узагальнені обернені: теорія та застосування”. Том 15. Springer Science & Business Media. (2003).
https://​/​doi.org/​10.1007/​b97366

[44] Майкл Т Гудріч. «Площинні роздільники та тріангуляція паралельних полігонів». Journal of Computer and System Sciences 51, 374–389 (1995).
https://​/​doi.org/​10.1006/​jcss.1995.1076

[45] Йерун Дехане та Барт Де Мур. “Група Кліффорда, стани стабілізатора, лінійні та квадратичні операції над $mathrm{GF}$(2)”. Physical Review A 68, 042318 (2003).
https: / / doi.org/ 10.1103 / PhysRevA.68.042318

[46] Саймон Андерс і Ганс Брігель. “Швидка симуляція схем стабілізатора з використанням представлення стану графа”. Physical Review A 73, 022334 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022334

[47] Сергій Бравий. Особисте спілкування, 2017 (2017).

[48] Маартен Ван ден Нест, Єрун Дехане та Барт Де Мур. “Графічний опис дії локальних перетворень Кліффорда на стани графа”. Physical Review A 69, 022316 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.69.022316

Цитується

[1] Тревіс Л. Шолтен, Карл Дж. Вільямс, Дастін Муді, Мікеле Моска, Вільям Герлі, Вільям Дж. Зенг, Матіас Тройєр і Джей М. Гамбетта, «Оцінка переваг і ризиків квантових комп’ютерів», arXiv: 2401.16317, (2024).

[2] Лоренцо Леоне, Сальваторе Ф. Е. Олів’єро, Сет Ллойд і Аліосія Хамма, «Навчання ефективних декодерів для квазіхаотичних квантових скремблерів», arXiv: 2212.11338, (2022).

[3] Райан Л. Манн, «Моделювання квантових обчислень за допомогою поліномів Тутте», npj Квантова інформація 7, 141 (2021).

[4] Сахар Аталла, Майкл Гарн, Санія Євтіч, Юкуан Тао та Шашанк Вірмані, «Ефективне класичне моделювання квантових схем стану кластера з альтернативними входами», arXiv: 2201.07655, (2022).

[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun і Xiangdong Zhang, «Високопродуктивна паралельна класична схема для моделювання неглибоких квантових схем», arXiv: 2103.00693, (2021).

Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2024-02-13 03:31:05). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2024-02-13 03:31:02).

Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.

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

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