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

Отметка времени: 13 октября 2022 г., 11:24
Исходный узел: 1724475

Николаос Кукулекидис1, Хёкджун Квон1,2, Хеджон Х. Джи3, Дэвид Дженнингс1,4и М.С. Ким1

1Департамент физики, Имперский колледж Лондона, Лондон SW7 2AZ, Великобритания
2Корейский институт перспективных исследований, Сеул, 02455, Корея
3Факультет вычислительной техники Имперского колледжа Лондона, Лондон SW7 2AZ, Великобритания
4Школа физики и астрономии, Университет Лидса, Лидс, LS2 9JT, Великобритания

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

Абстрактные

Оценка вероятности результата с помощью классических методов является важной задачей для проверки устройств квантовых вычислений. Вероятности результата любой квантовой схемы можно оценить с помощью выборки Монте-Карло, где количество отрицательностей, присутствующих в представлении кадра схемы, количественно определяет накладные расходы на количество выборок, необходимых для достижения определенной точности. В этой статье мы предлагаем две классические подпрограммы: слияние вентилей схемы и оптимизацию кадра, которые оптимизируют представление схемы для уменьшения накладных расходов на выборку. Мы показываем, что время выполнения обеих подпрограмм полиномиально масштабируется по размеру схемы и глубине вентиля. Наши методы применимы к общим схемам, независимо от генерирующих наборов вентилей, размерностей кудитов и выбранных фреймовых представлений для компонентов схемы. Мы численно продемонстрировали, что наши методы обеспечивают улучшенное масштабирование накладных расходов на отрицательные значения для всех протестированных случаев случайных схем со случайными вентилями Клиффорда+$T$ и Хаара, и что производительность наших методов выгодно отличается от предыдущих квазивероятностных симуляторов по количеству не-Клиффордовые ворота увеличиваются.

Рекомендованное изображение: набросок нашей программы на игрушечной трассе. Первый шаг (а) $rightarrow$ (б) — это слияние вентилей, здесь реализованное с $n = 2$. Ворота, имеющие общие входные и выходные провода, соединяются схематически, как показано на рисунке. Второй шаг (b) $rightarrow$ (c) — это оптимизация кадра, здесь реализованная с $ell= 2$ в блоке $B$, содержащем три объединенных вентиля. В результате оптимизации получаются обновленные кадры $G_4, G_7$, тогда как остальные кадры, соединяющие блок $B$ с остальными компонентами схемы, остаются неизменными в этом цикле оптимизации.

Популярное резюме

Ожидается, что квантовые компьютеры обеспечат значительное ускорение по сравнению с классическими вычислениями для определенных задач. Определение набора вычислительных задач, которые можно ускорить с помощью квантовых компьютеров, — общеизвестно сложный вопрос. Естественный подход к созданию этого набора состоит в изучении того, насколько хорошо классические компьютеры могут моделировать эти задачи. Большое семейство таких классических симуляторов основано на представлении задач в виде случайных процессов, которые вероятностно распространяют входное состояние. Квантовые задачи содержат отрицательные вероятности, которые в принципе требуют экспоненциального времени выполнения для классического моделирования. В этой работе мы представляем эффективную оптимизацию классической стратегии моделирования, которая минимизирует отрицательные вероятности, возникающие в процессе. Наши результаты имеют практическое значение, поскольку они обеспечивают более быстрый способ моделирования квантовых компьютеров, а на фундаментальном уровне они исследуют степень, в которой отрицательные вероятности являются индикатором неклассической физики.

► Данные BibTeX

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

[1] Р. П. Фейнман, Международный журнал теоретической физики 21, 467 (1982).
https: / / doi.org/ 10.1007 / BF02650179

[2] Дж. Прескилл, «Квантовые вычисления 40 лет спустя» (2021), arXiv:2106.10522.
Arxiv: 2106.10522

[3] Р. Йожа и М. В. ден Нест, Quantum Inf. Вычислить. 14, 633 (2014).

[4] Д.Е. Кох, Quantum Info. Вычислить. 17, 262–282 (2017).

[5] С. Ааронсон, А. Буланд, Г. Куперберг и С. Мехрабан (Ассоциация вычислительной техники, Нью-Йорк, Нью-Йорк, США, 2017) с. 317–327.

[6] М. Хебенстрейт, Р. Йожа, Б. Краус и С. Стрелчук, Phys. Ред. А 102, 052604 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.052604

[7] М. Йоганатан, Р. Джожа и С. Стрельчук, Труды Королевского общества A: Математические, физические и технические науки 475, 20180427 (2019).
https: / / doi.org/ 10.1098 / rspa.2018.0427

[8] С. Ааронсон и А. Архипов, «Вычислительная сложность линейной оптики», (2010), arXiv:1011.3245.
Arxiv: 1011.3245

[9] М. Дж. Бремнер, Р. Джожа и Д. Д. Шепард, Труды Королевского общества A: Математические, физические и технические науки 467, 459 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

[10] T. Morimae, K. Fujii, and JF Fitzsimons, Phys. Преподобный Летт. 112, 130502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.130502

[11] М. Дж. Бремнер, А. Монтанаро и Дж. Шепард, Phys. Преподобный Летт. 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

[12] Х. Гао, С.-Т. Ван и Л.-М. Дуань, физ. Преподобный Летт. 118, 040502 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.040502

[13] Дж. Бермеджо-Вега, Д. Ханглейтер, М. Шварц, Р. Рауссендорф и Дж. Эйсерт, Phys. Ред. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010

[14] К. Фуджи, Х. Кобаяши, Т. Моримаэ, Х. Нисимура, С. Тамате и С. Тани, Phys. Преподобный Летт. 120, 200502 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.120.200502

[15] А. Буланд, Дж. Фицсаймонс и Д. Е. Кох (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, 2018).

[16] С. Бойшо, С.В. Исаков, В.Н. Смелянский, Р. Бэббуш, Н. Дин, З. Цзян, М.Дж. Бремнер, Дж.М. Мартинис, Х. Невен, Nature Physics 14, 595 (2018).
HTTPS: / / doi.org/ 10.1038 / s41567-018-0124-х

[17] Х. Пашаян, С.Д. Бартлетт и Д. Гросс, Quantum 4, 223 (2020).
https:/​/​doi.org/​10.22331/​q-2020-01-13-223

[18] LG Valiant, SIAM Journal по вычислительной технике 31, 1229 (2002).
https: / / doi.org/ 10.1137 / S0097539700377025

[19] Б. М. Терхал и Д. П. Ди Винченцо, Phys. Rev. A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325

[20] Бартлет С.Д., Сандерс Б.С., Браунштейн С.Л., Немото К. // Phys. Преподобный Летт. 88, 097904 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.097904

[21] С. Ааронсон и Д. Готтесман, Phys. Ред. А 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[22] Д. Гросс, С.Т. Фламмия и Дж. Эйсерт, Phys. Преподобный Летт. 102, 190501 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.190501

[23] DJ Brod, Phys. Rev. A 93, 062332 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.062332

[24] Т. Хауг и М. С. Ким, «Масштабируемые меры магии для квантовых компьютеров» (2022).
https://​/​doi.org/​10.48550/​ARXIV.2204.10061

[25] Х.-С. Чжун, Х. Ван, Ю.-Х. Дэн, М.-К. Чен, Л.-К. Пэн, Ю.-Х. Луо, Дж. Цинь, Д. Ву, С. Дин, Ю. Ху и др., Science 370, 1460–1463 (2020).
https: / / doi.org/ 10.1126 / science.abe8770

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

[27] Х. Берниен, С. Шварц, А. Кислинг, Х. Левин, А. Омран, Х. Пихлер, С. Чой, А. С. Зибров, М. Эндрес, М. Грейнер и др., Nature 551, 579–584 (2017).
https: / / doi.org/ 10.1038 / nature24622

[28] К. Нил, П. Рушан, К. Кечеджи, С. Бойшо, С. В. Исаков, В. Смелянский, А. Мегрант, Б. Кьяро, А. Дансуорт, К. Арья и др., Science 360, 195–199 (2018).
https: / / doi.org/ 10.1126 / science.aao4309

[29] Дж. П. Бонилла Атаидес, Д. К. Такетт, С. Д. Бартлетт, С. Т. Фламмия и Б. Дж. Браун, Nature Communications 12, 2172 (2021).
https:/​/​doi.org/​10.1038/​s41467-021-22274-1

[30] С. Бравий, С. Шелдон, А. Кандала, Д.С. Маккей и Дж.М. Гамбетта, Phys. Ред. А 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

[31] А. Кандала, К. Темме, А. Д. Корколес, А. Меззакапо, Дж. М. Чоу и Дж. М. Гамбетта, Nature 567, 491 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1040-7

[32] S. Endo, SC Benjamin, and Y. Li, Phys. Ред. X 8, 031027 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.031027

[33] K. Temme, S. Bravyi, and JM Gambetta, Phys. Преподобный Летт. 119, 180509 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.180509

[34] Дж. Прескилл, Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[35] А. В. Харроу и А. Монтанаро, Nature 549, 203 (2017).
https: / / doi.org/ 10.1038 / nature23458

[36] Беннинк Р.С., Феррагут Э.М., Хамбл Т.С., Ласка Дж.А., Нутаро Дж.Дж., Плешкох М.Г., Пусер Р.С., Phys. Ред. А 95, 062337 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062337

[37] В. Вейтч, К. Ферри, Д. Гросс и Дж. Эмерсон, New Journal of Physics 14, 113011 (2012).
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​113011

[38] Д. Готтесман, в Энциклопедии математической физики под редакцией Ж.-П. Франсуаза, Г.Л. Набер и Т.С. Цун (Academic Press, Оксфорд, 2006), стр. 196–201.
https:/​/​doi.org/​10.1016/​B0-12-512666-2/​00273-X

[39] Х. Пашаян, О. Рирдон-Смит, К. Корзеква и С.Д. Бартлетт, «Быстрая оценка вероятностей результата для квантовых схем», (2021), arXiv:2101.12223.
https: / / doi.org/ 10.1103 / PRXQuantum.3.020361
Arxiv: 2101.12223

[40] Дж. Р. Седдон, Б. Регула, Х. Пашаян, Ю. Оуян и Э. Т. Кэмпбелл, PRX Quantum 2, 010345 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.010345

[41] С. Бравый, Д. Госсет, Phys. Преподобный Летт. 116, 250501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.116.250501

[42] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset и M. Howard, Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[43] S. Bravyi, G. Smith, JA Smolin, Phys. Ред. X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[44] Х. Кассим, Дж. Дж. Уоллман и Дж. Эмерсон, Quantum 3, 170 (2019).
https:/​/​doi.org/​10.22331/​q-2019-08-05-170

[45] Ю. Хуанг и П. Лав, Phys. Ред. А 99, 052307 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.052307

[46] Л. Коча и М. Саровар, Phys. Ред. А 103, 022603 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.022603

[47] А. Киссинджер, Дж. ван де Ветеринг и Р. Вилмарт, «Классическое моделирование квантовых схем с частичным и графическим разложением стабилизатора», (2022), arXiv:2202.09202.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2022.5
Arxiv: 2202.09202

[48] Х. Кассим, Х. Пашаян и Д. Госсет, Quantum 5, 606 (2021).
https:/​/​doi.org/​10.22331/​q-2021-12-20-606

[49] H. Pashayan, JJ Wallman, and SD Bartlett, Phys. Преподобный Летт. 115, 070501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.115.070501

[50] Д. Штальке, Phys. Ред. А 90, 022302 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.022302

[51] П. Ралл, Д. Лян, Дж. Кук и В. Кречмер, Phys. Ред. А 99, 062337 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.062337

[52] Дж. Р. Седдон и Э. Т. Кэмпбелл, Труды Королевского общества A: Математические, физические и инженерные науки 475, 20190251 (2019).
https: / / doi.org/ 10.1098 / rspa.2019.0251

[53] К. Ферри и Дж. Эмерсон, Журнал физики A: Mathematical and Theoretical 41, 352001 (2008).
https:/​/​doi.org/​10.1088/​1751-8113/​41/​35/​352001

[54] К. Ферри и Дж. Эмерсон, New Journal of Physics 11, 063040 (2009).
https:/​/​doi.org/​10.1088/​1367-2630/​11/​6/​063040

[55] Д. Гросс, Журнал математической физики 47, 122107 (2006).
https: / / doi.org/ 10.1063 / 1.2393152

[56] М. Руцци, М. А. Марчиолли и Д. Галетти, Журнал физики A: Mathematical and General 38, 6239 (2005).
https:/​/​doi.org/​10.1088/​0305-4470/​38/​27/​010

[57] М. А. Марчиолли, М. Руцци и Д. Галетти, Phys. Ред. А 72, 042308 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.72.042308

[58] Д. С. Франса, С. Стрелчук и М. Студзинский, Phys. Преподобный Летт. 126, 210502 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.210502

[59] М. Ховард и Э. Кэмпбелл, Phys. Преподобный Летт. 118, 090501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.090501

[60] М. Генрих и Д. Гросс, Quantum 3, 132 (2019).
https:/​/​doi.org/​10.22331/​q-2019-04-08-132

[61] S. Rahimi-Keshari, TC Ralph и CM Caves, Phys. Ред. X 6, 021039 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021039

[62] A. Mari и J. Eisert, Phys. Преподобный Летт. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503

[63] Р. Рауссендорф, Д. Е. Браун, Н. Дельфосс, К. Окей и Дж. Бермеджо-Вега, Physical Review A 95, 052334 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.052334

[64] К. Джонс, Phys. Ред. А 87, 022328 (2013).
https: / / doi.org/ 10.1103 / PhysRevA.87.022328

[65] DJ Wales и JPK Doye, Журнал физической химии A 101, 5111–5116 (1997).
https: / / doi.org/ 10.1021 / jp970984n

[66] MSA и др., «Qiskit: платформа с открытым исходным кодом для квантовых вычислений» (2021).
https: / / doi.org/ 10.5281 / zenodo.2573505

[67] М. Сересо, А. Аррасмит, Р. Бэббуш, С. К. Бенджамин, С. Эндо, К. Фуджи, Дж. Р. МакКлин, К. Митараи, К. Юань, Л. Чинсио и П. Дж. Коулз, Nature Reviews Physics 3, 625 (2021 г.) ).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

Цитируется

[1] Тобиас Хауг и Лоренцо Пироли, «Количественная нестабилизация состояний матричного произведения», Arxiv: 2207.13076.

[2] Тобиас Хауг и М.С. Ким, «Масштабируемые меры магии для квантовых компьютеров», Arxiv: 2204.10061.

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

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2022-10-16 15:41:38).

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

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

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