Быстрое моделирование планарных схем Клиффорда

Быстрое моделирование планарных схем Клиффорда

Отметка времени: 12 февраля 2024 г., 10:28 AM

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

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

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

Абстрактные

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

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

Быстрое моделирование планарных схем Клиффорда PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

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

[Встраиваемое содержимое]

► Данные BibTeX

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

[1] Фрэнк Аруте, Кунал Арья, Райан Бэббуш, Дэйв Бэкон, Джозеф С. Бардин, Рами Барендс, Рупак Бисвас, Серджио Бойшо, Фернандо Г.С.Л. Брандао, Дэвид А. Бьюэлл и др. «Квантовое превосходство с помощью программируемого сверхпроводящего процессора». Природа 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] Мэтью Д. Рид, Леонардо ДиКарло, Саймон Э. Нигг, Луян Сан, Луиджи Фрунцио, Стивен М. Гирвин и Роберт Дж. Шёлкопф. «Реализация трехкубитной квантовой коррекции ошибок с помощью сверхпроводящих схем». Природа 482, 382–385 (2012).
https: / / doi.org/ 10.1038 / nature10786

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

[5] Ниссим Офек, Андрей Петренко, Рейньер Хирес, Филип Рейнхольд, Заки Легтас, Брайан Влатакис, Йехан Лю, Луиджи Фрунцио, С.М. Гирвин, Лян Цзян и др. «Продление срока службы квантового бита с исправлением ошибок в сверхпроводящих цепях». Природа 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] Майкл Дж. Бремнер, Ричард Джоза и Дэн Дж. Шепард. «Классическое моделирование коммутирующих квантовых вычислений предполагает коллапс полиномиальной иерархии». Труды Королевского общества A: Математические, физические и технические науки 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] Скотт Ааронсон и Дэниел Готтесман. «Улучшенное моделирование схем стабилизаторов». Physical Review A 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] Сергей Бравый, Дэвид Госсет, Роберт Кениг и Марко Томамичел. «Квантовое преимущество с шумными мелкими схемами». Физика природы, страницы 1–6 (2020).
HTTPS: / / doi.org/ 10.1038 / s41567-020-0948-г

[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 по численному анализу 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. ИИЭР (2010).
https: / / doi.org/ 10.1109 / FOCS.2010.28

[29] Ричард Дж. Липтон и Роберт Эндре Тарьян. «Теорема о сепараторе для плоских графов». SIAM Journal по прикладной математике 36, 177–189 (1979).
https: / / doi.org/ 10.1137 / 0136016

[30] Скотт Ааронсон и Лицзе Чен. «Теоретико-сложные основы экспериментов по квантовому превосходству». На 32-й конференции по сложности вычислений (CCC 2017). Замок Дагштуль-Лейбниц-Центр информатики (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] Сергей Бравый, Грэм Смит и Джон Смолин. «Торговля классическими и квантовыми вычислительными ресурсами». Физическое обозрение Х 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 августа 31 г.

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

[42] Оскар Х. Ибарра, Шломо Моран и Роджер Хуэй. «Обобщение алгоритма быстрого разложения матрицы LUP и его применения». Журнал алгоритмов 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] Майкл Т. Гудрич. «Плоские разделители и триангуляция параллельных многоугольников». Журнал компьютерных и системных наук 51, 374–389 (1995).
https: / / doi.org/ 10.1006 / jcss.1995.1076

[45] Йерун Деэн и Барт Де Мур. «Группа Клиффорда, состояния стабилизатора, линейные и квадратичные операции над $mathrm{GF}$(2)». Физическое обозрение А 68, 042318 (2003).
https: / / doi.org/ 10.1103 / PhysRevA.68.042318

[46] Саймон Андерс и Ганс Дж. Бригель. «Быстрое моделирование схем стабилизатора с использованием представления графических состояний». Физическое обозрение А 73, 022334 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022334

[47] Сергей Бравый. Личное общение, 2017 (2017).

[48] Маартен Ван ден Нест, Йерун Дехан и Барт Де Мур. «Графическое описание действия локальных преобразований Клиффорда на состояния графа». Физическое обозрение А 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] Шихао Чжан, Цзячэн Бао, Ифань Сунь, Ливчжоу Ли, Хоуджун Сунь и Сяндун Чжан, «Высокопроизводительная параллельная классическая схема для моделирования мелких квантовых схем», Arxiv: 2103.00693, (2021).

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

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2024-02-13 03:31:02).

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

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

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