Быстрое квантовое разделение цепей с рандомизированными измерениями

Быстрое квантовое разделение цепей с рандомизированными измерениями

Отметка времени: 2 марта 2023 г., 11:42
Исходный узел: 1990460

Ангус Лоу1,2, Матия Медвидович1,3,4, Энтони Хейс1, Ли Дж. О'Риордан1, Томас Р. Бромли1, Хуан Мигель Аррасола1и Натан Киллоран1

1Занаду, Торонто, Онтарио, M5G 2C8, Канада
2Центр теоретической физики Массачусетского технологического института, Кембридж, Массачусетс, 02139, США
3Центр вычислительной квантовой физики, Институт Флэтайрон, Нью-Йорк, NY, 10010, США
4Факультет физики, Колумбийский университет, Нью-Йорк, 10027, США

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

Абстрактные

Мы предлагаем новый метод увеличения объема квантовых вычислений за пределы количества физических кубитов, доступных на одном устройстве. Это достигается путем случайной вставки каналов измерения и подготовки для выражения выходного состояния большой схемы в виде разделимого состояния на разных устройствах. В нашем методе используются рандомизированные измерения, в результате чего накладные расходы выборки составляют $widetilde{O}(4^k / varepsilon ^2)$, где $varepsilon $ — точность вычислений, а $k$ — количество параллельных проводов, которые «вырезать», чтобы получить меньшие подсхемы. Мы также показываем теоретико-информационную нижнюю границу $Omega(2^k / varepsilon ^2)$ для любой сопоставимой процедуры. Мы используем наши методы, чтобы показать, что схемы в алгоритме квантовой приближенной оптимизации (QAOA) с $p$ запутывающими слоями могут быть смоделированы схемами на части исходного числа кубитов с накладными расходами, которые составляют примерно $2^{O(pkappa) }$, где $kappa$ — размер известного сбалансированного разделителя вершин графа, кодирующего задачу оптимизации. Мы получаем числовые доказательства практического ускорения, используя наш метод, примененный к QAOA, по сравнению с предыдущей работой. Наконец, мы исследуем практическую осуществимость применения процедуры размыкания цепей к крупномасштабным задачам QAOA на кластеризованных графах с использованием симулятора кубитов за 30$ для оценки вариационной энергии задачи с кубитами за 129$, а также выполнения задачи с кубитами за 62$. -оптимизация кубитов.

► Данные BibTeX

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

[1] https://​/​github.com/​XanaduAI/​randomized-measurements-circuit-cutting (2022 г.).
https://​/​github.com/​XanaduAI/​рандомизированные-измерения-схемы-резки

[2] Скотт Ааронсон и Дэниел Готтесман «Улучшенное моделирование схем стабилизатора» Phys. Ред. А 70, 052328 (2004 г.).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] Дж. Аврон, Офер Каспер и Илан Розен, «Квантовое преимущество и уменьшение шума в распределенных квантовых вычислениях», Phys. Ред. А 104, 052404 (2021 г.).
https: / / doi.org/ 10.1103 / PhysRevA.104.052404

[4] Томас Эйрал, Франсуа-Мари Ле Режан, Зейн Салим, Юрий Алексеев и Мартин Сухара, «Квантовое разделение и вычисления: демонстрация оборудования и шумное моделирование», Ежегодный симпозиум IEEE Computer Society 2020 по СБИС (ISVLSI) 138–140 (2020).
https://​/​doi.org/​10.1109/​ISVLSI49217.2020.00034

[5] Ф. Барратт, Джеймс Дборин, Матиас Бал, Вид Стоевич, Фрэнк Поллманн и А. Г. Грин, «Параллельное квантовое моделирование больших систем на небольших компьютерах NISQ», npj Quantum Information 7, 79 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00420-3

[6] Вилле Бергхольм, Джош Исаак, Мария Шульд, Кристиан Гоголин, Шахнаваз Ахмед, Вишну Аджит, М. Сохаиб Алам, Гильермо Алонсо-Линахе, Б. АкашНараянан, Али Асади, Хуан Мигель Арразола, Уткарш Азад, Сэм Бэннинг, Карстен Бланк, Томас Р. Бромли, Бенджамин А. Кордье, Джек Серони, Ален Дельгадо, Оливия Ди Маттео, Аминтор Душко, Таня Гарг, Диего Гуала, Энтони Хейс, Райан Хилл, Аруса Иджаз, Теодор Исакссон, Дэвид Иттах, Соран Джахангири, Пратик Джейн, Эдвард Цзян, Анкит Ханделвал, Корбиниан Коттманн, Роберт А. Лэнг, Кристина Ли, Томас Локе, Ангус Лоу, Кери Маккирнан, Йоханнес Якоб Мейер, Дж. А. Монтаньес-Баррера, Ромен Мойярд, Зеюе Ню, Ли Джеймс О'Риордан, Стивен Оуд, Ашиш Паниграхи, Пак Че-Юн, Даниэль Полатайко, Николас Кесада, Чейз Робертс, Нахум Са, Исидор Шох, Борун Ши, Шули Шу, Сукин Сим, Аршприт Сингх, Ингрид Страндберг, Джей Сони, Антал Сава, Слиман Табет, Родриго А. Варгас-Эрнандес , Тревор Винсент, Никола Витуччи, Морис Вебер, Дэвид Вирикс, Роланд Вир Сема, Мориц Уиллманн, Винсент Вонг, Шаомин Чжан и Натан Киллоран, «PennyLane: автоматическое дифференцирование гибридных квантово-классических вычислений» (2018).
https://​/​doi.org/​10.48550/​ARXIV.1811.04968
https: / / arxiv.org/ абс / 1811.04968

[7] Сергей Бравиян и Дэвид Госсет «Улучшенное классическое моделирование квантовых цепей, в которых доминирует Клиффорд Гейтс» Phys. Преподобный Летт. 116, 250501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.116.250501

[8] Сергей Бравый, Дэвид Госсет и Рамис Мовассаг, «Классические алгоритмы для квантовых средних значений» Nature Physics 17, 337–341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

[9] Сергей Бравый, Грэм Смит и Джон А. Смолин, «Торговля классическими и квантовыми вычислительными ресурсами» Phys. Ред. X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[10] Сергей Бравый, Александр Клиш, Роберт Кениг и Юджин Тан, «Препятствия для вариационной квантовой оптимизации из-за защиты симметрии» Phys. Преподобный Летт. 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[11] Сергей Бравый, Дэн Браун, Падраик Калпин, Эрл Кэмпбелл, Дэвид Госсет и Марк Ховард, «Моделирование квантовых схем с помощью разложения стабилизатора низкого ранга», Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Тханг Нгуен Буян и Курт Джонс «Поиск хороших приближенных вершин и реберных разделов является NP-трудным» Письма по обработке информации 42, 153–159 (1992).
https:/​/​doi.org/​10.1016/​0020-0190(92)90140-Q
https://​/​www.sciencedirect.com/​science/​article/​pii/​002001909290140Q

[13] Франческо Бушеми и Ниланджана Датта «Квантовая емкость каналов с произвольно коррелированным шумом» IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https: / / doi.org/ 10.1109 / TIT.2009.2039166

[14] Сенруи Чен, Вэньцзюнь Юй, Пей Цзэн и Стивен Т. Фламмиа, «Надежная оценка теней» PRX Quantum 2, 030348 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.030348

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

[16] Томас М. Ковер и Джой А. Томас «Элементы теории информации» Уайли (2005).
https://​/​doi.org/​10.1002/​047174882x

[17] Ведран Дунько, Йимин Ге и Дж. Игнасио Чирак, «Ускорение вычислений с использованием небольших квантовых устройств», Phys. Преподобный Летт. 121, 250501 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.250501

[18] Андреас Эльбен, Стивен Т. Фламмиа, Синь-Юань Хуанг, Ричард Куенг, Джон Прескилл, Бенуа Вермерш и Питер Золлер, «Инструментарий для рандомизированных измерений» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.11374
https: / / arxiv.org/ абс / 2203.11374

[19] Лео Фанг, Андреас Хен, Харун Байрактар ​​и Сэм Стэнвик, «NVIDIA/cuQuantum: cuQuantum v22.05.0» (2022 г.).
https: / / doi.org/ 10.5281 / zenodo.6574510

[20] Роберт М. Фано «Передача информации: статистическая теория коммуникаций» MIT Press (1966).

[21] Эдвард Фархи, Дэвид Гамарник и Сэм Гутманн, «Алгоритму квантовой приближенной оптимизации необходимо видеть весь график: типичный случай» (2020).
https://​/​doi.org/​10.48550/​ARXIV.2004.09002
https: / / arxiv.org/ абс / 2004.09002

[22] Эдвард Фархи, Дэвид Гамарник и Сэм Гутманн, «Алгоритм квантовой приближенной оптимизации должен видеть весь график: примеры наихудшего случая» (2020).
https://​/​doi.org/​10.48550/​ARXIV.2005.08747
https: / / arxiv.org/ абс / 2005.08747

[23] Эдвард Фархи, Джеффри Голдстоун и Сэм Гутманн, «Алгоритм квантовой приближенной оптимизации» (2014).
https://​/​doi.org/​10.48550/​ARXIV.1411.4028
https: / / arxiv.org/ абс / 1411.4028

[24] Эдвард Фархи, Джеффри Голдстоун и Сэм Гутманн, «Алгоритм квантовой приближенной оптимизации, примененный к проблеме ограниченных вхождений» (2014).
https://​/​doi.org/​10.48550/​ARXIV.1412.6062
https: / / arxiv.org/ абс / 1412.6062

[25] Эдвард Фархианд Арам У. Хэрроу «Квантовое превосходство с помощью алгоритма квантовой приближенной оптимизации» (2016).
https://​/​doi.org/​10.48550/​ARXIV.1602.07674
https: / / arxiv.org/ абс / 1602.07674

[26] Уриэль Фейдж, Мохаммад Таги Хаджиагайи и Джеймс Р. Ли, «Улучшенные алгоритмы аппроксимации для разделителей вершин минимального веса», SIAM Journal on Computing 38, 629–657 (2008).
https: / / doi.org/ 10.1137 / 05064299X

[27] Джонни Грей и Стефанос Куртис «Сужение гипероптимизированной тензорной сети» Quantum 5, 410 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-410

[28] М. Гуцэ, Дж. Кан, Р. Куенг и Дж. А. Тропп, «Томография быстрого состояния с оптимальными границами ошибок», Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111

[29] Чонван Хаах, Арам В. Харроу, Чжэнфэн Цзи, Сяоди Ву и Ненгкун Ю, «Оптимальная выборочная томография квантовых состояний» IEEE Transactions on Information Theory 63, 5628–5641 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2719044

[30] Стюарт Хэдфилд, Чжихуи Ван, Брайан О'Горман, Элеонора Г. Риффель, Давиде Вентурелли и Рупак Бисвас, «От квантового приближенного алгоритма оптимизации к квантовому переменному оператору анзаца» Алгоритмы 12 (2019).
https: / / doi.org/ 10.3390 / a12020034
https:/​/​www.mdpi.com/​1999-4893/​12/​2/​34

[31] Майкл Городецкий, Питер В. Шор и Мэри Бет Рускай, «Каналы, разрушающие запутанность», обзоры по математической физике 15, 629–641 (2003).
https: / / doi.org/ 10.1142 / S0129055X03001709

[32] Синь-Юань Хуанг, Ричард Куенг и Джон Прескилл, «Предсказание многих свойств квантовой системы на основе очень небольшого числа измерений» Nature Physics 16, 1050–1057 (2020).
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[33] Уильям Хаггинс, Пиюш Патил, Брэдли Митчелл, К. Биргитта Уэйли и Э. Майлз Стауденмайр, «На пути к квантовому машинному обучению с тензорными сетями», Quantum Science and Technology 4, 024001 (2019).
https: / / doi.org/ 10.1088 / 2058-9565 / aaea94

[34] Ричард Куен и Дэвид Гросс «Состояния стабилизатора кубитов представляют собой сложные проективные 3-схемы» (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02767
https: / / arxiv.org/ абс / 1510.02767

[35] Джунде Ли, Махабубул Алам и Сваруп Гош, «Крупномасштабная квантовая приближенная оптимизация с помощью принципа «разделяй и властвуй»» (2021).
https://​/​doi.org/​10.48550/​ARXIV.2102.13288
https: / / arxiv.org/ абс / 2102.13288

[36] Сет Ллойд, Мария Шульд, Аруса Иджаз, Джош Исаак и Натан Киллоран, «Квантовые вложения для машинного обучения» (2020).
https://​/​doi.org/​10.48550/​ARXIV.2001.03622
https: / / arxiv.org/ абс / 2001.03622

[37] Ангус Лоуэ и Эшвин Наяк «Нижние границы для изучения квантовых состояний с однократными измерениями» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.14438
https: / / arxiv.org/ абс / 2207.14438

[38] Даниил Лыков, Джонатан Вурц, Коди Пул, Марк Саффман, Том Ноэль и Юрий Алексеев, «Пороги частоты дискретизации для квантового преимущества алгоритма квантовой приближенной оптимизации» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2206.03579
https: / / arxiv.org/ абс / 2206.03579

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

[40] Саймон С. Маршалл, Каспер Гюрик и Ведран Дунько, «Многомерное квантовое машинное обучение с помощью небольших квантовых компьютеров» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.13739
https: / / arxiv.org/ абс / 2203.13739

[41] Матия Медвидович и Джузеппе Карлео «Классическое вариационное моделирование алгоритма квантовой приближенной оптимизации» npj Quantum Information 7 (2021).
HTTPS: / / doi.org/ 10.1038 / s41534-021-00440-г

[42] Косуке Митараи и Кейсуке Фуджи «Построение виртуального двухкубитного вентиля путем выборки операций с одним кубитом» New Journal of Physics 23, 023021 (2021).
https://​/​doi.org/​10.1088/​1367-2630/​abd7bc

[43] Косуке Митараи и Кейсуке Фуджи «Накладные расходы на моделирование нелокального канала с локальными каналами с помощью квазивероятностной выборки» Quantum 5, 388 (2021).
https:/​/​doi.org/​10.22331/​q-2021-01-28-388

[44] Филипп Мориц, Роберт Нишихара, Стефани Ванг, Алексей Туманов, Ричард Лио, Эрик Лян, Мелих Элибол, Зонхэн Ян, Уильям Пол, Майкл И. Джордан и Ион Стойка, «Ray: распределенная платформа для новых приложений ИИ» (2017 г.) .
https://​/​doi.org/​10.48550/​ARXIV.1712.05889
https: / / arxiv.org/ абс / 1712.05889

[45] Хакоп Пашаян, Джоэл Дж. Уоллман и Стивен Д. Бартлетт, «Оценка вероятностей результатов квантовых цепей с использованием квазивероятностей», Phys. Преподобный Летт. 115, 070501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.115.070501

[46] Тяньи Пэн, Арам В. Хэрроу, Марис Озолс и Сяоди Ву, «Моделирование больших квантовых схем на маленьком квантовом компьютере», Physical Review Letters 125 (2020).
https: / / doi.org/ 10.1103 / physrevlett.125.150504

[47] Майкл А. Перлин, Зейн Х. Салим, Мартин Сучара и Джеймс С. Осборн, «Квантовая схема разрезания с помощью томографии максимального правдоподобия», npj Quantum Information 7 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00390-6

[48] Альберто Перуццо, Джаррод МакКлин, Питер Шадболт, Ман-Хонг Юнг, Сяо-Ци Чжоу, Питер Дж. Лав, Алан Аспуру-Гузик и Джереми Л. О'Брайен, «Решатель вариационных собственных значений на фотонном квантовом процессоре» Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

[49] Кристоф Пивето и Дэвид Саттер «Схема вязания с классической коммуникацией» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2205.00016
https: / / arxiv.org/ абс / 2205.00016

[50] Зейн Х. Салим, Тиг Томеш, Майкл А. Перлин, Пранав Гокхале и Мартин Сучара, «Квантовое разделяй и властвуй для комбинаторной оптимизации и распределенных вычислений» (2021).
Arxiv: 2107.07532

[51] Игал Сасон и Серхио Верду «$f$-дивергентные неравенства» IEEE Transactions on Information Theory 62, 5973–6006 (2016).
https: / / doi.org/ 10.1109 / TIT.2016.2603151

[52] Мария Шульд, Алекс Бочаров, Криста М. Своре и Натан Вибе, «Схемоцентрические квантовые классификаторы» Physical Review A 101 (2020).
https: / / doi.org/ 10.1103 / physreva.101.032308

[53] Мария Шульд, Вилле Бергхольм, Кристиан Гоголин, Джош Изаак и Натан Киллоран, «Оценка аналитических градиентов на квантовом оборудовании» Phys. Ред. A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[54] Айк Шукурян, Торстен Уайлд, Аксель Ауветер и Арндт Боде, «Прогнозирование энергии и энергопотребления сильно и слабо масштабируемых высокопроизводительных приложений» Supercomputing Frontiers and Innovations 1, 20–41 (2014).
https://​/​doi.org/​10.14529/​jsfi140202

[55] Вэй Танган и Маргарет Мартоноси «ScaleQC: масштабируемая платформа для гибридных вычислений на квантовых и классических процессорах» (2022 г.).
https://​/​doi.org/​10.48550/​ARXIV.2207.00933
https: / / arxiv.org/ абс / 2207.00933

[56] Эвут Ван Ден Берг «Простой метод выборки случайных операторов Клиффорда», Международная конференция IEEE по квантовым вычислениям и инженерии (QCE), 2021 г., 54–59 (2021 г.).
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[57] Чжихуэй Ван, Стюарт Хэдфилд, Чжан Цзян и Элеонора Г. Риффель, «Алгоритм квантовой приближенной оптимизации для MaxCut: фермионный взгляд» Phys. Ред. А 97, 022304 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022304

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

[59] Зак Уэбб «Группа Клиффорда образует единый 3-дизайн» (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02769
https: / / arxiv.org/ абс / 1510.02769

[60] Роланд Виерсема, Леонардо Герини, Хуан Фелипе Карраскилья и Леандро Аолита, «Связность цепей повышается за счет квантово-классически-квантовых интерфейсов» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.04984
https: / / arxiv.org/ абс / 2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao и You Zhou, «Квантовое моделирование с гибридными тензорными сетями», Phys. Преподобный Летт. 127, 040501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.040501

[62] Huangjun Zhu «Многокубитные группы Клиффорда представляют собой унитарные 3-схемы» Phys. Ред. А 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Цитируется

[1] Лиранде Пира и Крис Ферри, «Приглашение к распределенным квантовым нейронным сетям», Arxiv: 2211.07056, (2022).

[2] Лукас Бреннер, Кристоф Пивето и Дэвид Саттер, «Оптимальное перерезание провода с помощью классической коммуникации», Arxiv: 2302.03366, (2023).

[3] Мэтью ДеКросс, Эли Чертков, Меган Кохаген и Майкл Фосс-Фейг, «Компиляция повторного использования кубита с измерением и сбросом в середине схемы», Arxiv: 2210.08039, (2022).

[4] Кристиан Уфрехт, Манираман Периясами, Себастьян Рич, Даниэль Д. Шерер, Аксель Плинге и Кристофер Мучлер, «Вырезание квантовых вентилей с множественным управлением с помощью исчисления ZX», Arxiv: 2302.00387, (2023).

[5] Марвин Бехтольд, Джоанна Барзен, Франк Лейманн, Александр Мандл, Джулиан Обст, Феликс Тругер и Бенджамин Ведер, «Исследование эффекта отсечения цепи в QAOA для задачи MaxCut на устройствах NISQ», Arxiv: 2302.01792, (2023).

[6] Ритаджит Маджумдар и Кристофер Дж. Вуд, «Устранение ошибок квантовой схемы», Arxiv: 2211.13431, (2022).

[7] Даниэль Т. Чен, Зейн Х. Салим и Майкл А. Перлин, «Квантовое разделение и властвие для классических теней», Arxiv: 2212.00761, (2022).

[8] Гидеон Учехара, Тор М. Аамодт и Оливия Ди Маттео, «Оптимизация отключения цепи на основе вращения», Arxiv: 2211.07358, (2022).

[9] Карлос А. Риофрио, Оливер Митевски, Кейтлин Джонс, Флориан Креллнер, Александр Вучкович, Джозеф Доетч, Йоханнес Клепш, Томас Эмер и Андре Луков, «Характеристика производительности квантовых генеративных моделей», Arxiv: 2301.09363, (2023).

[10] Диего Гуала, Шаомин Чжан, Эстер Крус, Карлос А. Риофрио, Йоханнес Клепш и Хуан Мигель Аррасола, «Практический обзор классификации изображений с помощью квантовых схем с вариационной тензорной сетью», Arxiv: 2209.11058, (2022).

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

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2023-03-03 16:49:00).

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

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

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