Оптимальные по времени многокубитные вентили: сложность, эффективная эвристика и границы времени вентиля

Оптимальные по времени многокубитные вентили: сложность, эффективная эвристика и границы времени вентиля

Отметка времени: 13 марта 2024 г., 8:59
Оптимальные по времени многокубитные вентили: сложность, эффективная эвристика и границы времени вентиля PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

Паскаль Басслер1, Маркус Генрих1и Мартин Клиш2

1Институт теоретической физики Университета Генриха Гейне, Дюссельдорф, Германия
2Институт квантовых технологий и квантовой оптимизации, Гамбургский технологический университет, Германия

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

Абстрактные

Многокубитные запутанные взаимодействия естественным образом возникают на некоторых платформах квантовых вычислений и обещают преимущества по сравнению с традиционными двухкубитными вентилями. В частности, фиксированное многокубитное взаимодействие типа Изинга вместе с однокубитными X-гейтами может быть использовано для синтеза глобальных ZZ-гейтов (GZZ-гейтов). В этой работе мы впервые показываем, что синтез таких квантовых вентилей, оптимальных по времени, является NP-трудным. Во-вторых, мы предоставляем явные конструкции специальных быстродействующих многокубитных вентилей. Они имеют постоянное время вентиля и могут быть реализованы с помощью линейного множества слоев X-затвора. В-третьих, мы разрабатываем эвристический алгоритм с полиномиальным временем выполнения для синтеза быстрых многокубитных вентилей. В-четвертых, мы получаем нижнюю и верхнюю границы оптимального времени открытия GZZ. Основываясь на явных конструкциях вентилей GZZ и численных исследованиях, мы предполагаем, что любой вентиль GZZ может быть выполнен за время O($n$) для $n$ кубитов. Наш алгоритм эвристического синтеза приводит к времени открытия GZZ с аналогичным масштабированием, что является оптимальным в этом смысле. Мы ожидаем, что наш эффективный синтез быстрых многокубитных вентилей позволит быстрее и, следовательно, более устойчиво к ошибкам выполнять квантовые алгоритмы.

► Данные BibTeX

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

[1] X. Wang, A. Sørensen, K. Mølmer, Многобитовые вентили для квантовых вычислений, Phys. Преподобный Летт. 86, 3907 (2001), arXiv:quant-ph/​0012055.
https: / / doi.org/ 10.1103 / PhysRevLett.86.3907
Arxiv: колич-фот / 0012055

[2] Т. Монц, П. Шиндлер, Дж. Т. Баррейро, М. Чвалла, Д. Нигг, В. А. Койш, М. Харландер, В. Гензель, М. Хеннрих и Р. Блатт, 14-кубитная запутанность: Создание и когерентность, Phys. Преподобный Летт. 106, 130506 (2011), архив: 1009.6126.
https: / / doi.org/ 10.1103 / PhysRevLett.106.130506
Arxiv: 1009.6126

[3] М. Кьергаард, М. Е. Шварц, Й. Браумюллер, П. Кранц, Дж. И.-Й. Ван, С. Густавссон и В.Д. Оливер, Сверхпроводящие кубиты: текущее состояние дел, Annual Review of Condensed Matter Physics 11, 369 (2020), arXiv:1905.13641.
https: / / doi.org/ 10.1146 / annurev-conmatphys-031119-050605
Arxiv: 1905.13641

[4] К. Фиггатт, А. Острандер, Н. М. Линке, К. А. Ландсман, Д. Чжу, Д. Маслов и К. Монро, Параллельные операции запутывания на универсальном квантовом компьютере с ионной ловушкой, Nature 572, 368 (2019), arXiv: 1810.11948 .
https:/​/​doi.org/​10.1038/​s41586-019-1427-5
Arxiv: 1810.11948

[5] Ю. Лу, С. Чжан, К. Чжан, В. Чен, Ю. Шен, Ж. Чжан, Ж.-Н. Чжан и К. Ким, Масштабируемые глобальные ворота запутанности на произвольных ионных кубитах, Nature 572, 363 (2019), arXiv:1901.03508.
https:/​/​doi.org/​10.1038/​s41586-019-1428-4
Arxiv: 1901.03508

[6] П. Басслер, М. Зиппер, К. Цедзих, М. Генрих, П. Х. Хубер, М. Йоханнинг и М. Клиш, Синтез и компиляция с использованием оптимальных по времени многокубитных вентилей, Quantum 7, 984 (2023), arXiv :2206.06387.
https:/​/​doi.org/​10.22331/​q-2023-04-20-984
Arxiv: 2206.06387

[7] Ф. Барахона и А.Р. Махджуб, О разрезанном многограннике, Mathematical Programming 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

[8] М. Р. Гэри и Д. С. Джонсон, Компьютеры и трудноразрешимые проблемы, Vol. 29 (WH Freeman and Company, Нью-Йорк, 2002 г.).

[9] М. Дж. Бремнер, А. Монтанаро и Д. Д. Шепард, Сложность в среднем случае и приближенное моделирование коммутирующих квантовых вычислений, Phys. Преподобный Летт. 117, 080501 (2016), arXiv:1504.07999.
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501
Arxiv: 1504.07999

[10] Дж. Оллкок, Дж. Бао, Дж. Ф. Доригуэлло, А. Луонго и М. Санта, Схемы постоянной глубины для равномерно управляемых вентилей и логических функций с применением к схемам квантовой памяти, arXiv: 2308.08539 (2023).
Arxiv: 2308.08539

[11] С. Бравый, Д. Маслов и Ю. Нам, Реализации операций Клиффорда с постоянной стоимостью и многократно управляемых вентилей с использованием глобальных взаимодействий, Phys. Преподобный Летт. 129, 230501 (2022), архив: 2207.08691.
https: / / doi.org/ 10.1103 / PhysRevLett.129.230501
Arxiv: 2207.08691

[12] С. Брави и Д. Маслов, Схемы без Адамара раскрывают структуру группы Клиффорда, IEEE Trans. Инф. Theory 67, 4546 (2021), arXiv: 2003.09412.
https: / / doi.org/ 10.1109 / TIT.2021.3081415
Arxiv: 2003.09412

[13] Д. Маслов и Б. Зиндорф, Глубинная оптимизация схем CZ, CNOT и Клиффорда, IEEE Transactions on Quantum Engineering 3, 1 (2022), arxiv:2201.05215.
https: / / doi.org/ 10.1109 / TQE.2022.3180900
Arxiv: 2201.05215

[14] С. Бойд, Л. Ванденберге, Выпуклая оптимизация (Издательство Кембриджского университета, 2009 г.).

[15] Э. Рич, Классы проблем FP и FNP, в книге «Автоматы, вычислимость и сложность: теория и приложения» (Pearson Education, 2007), стр. 510–511.
https://​/​www.cs.utexas.edu/​~ear/​cs341/​automatabook/​AutomataTheoryBook.pdf

[16] М. Йоханнинг, Изопространственные линейные ионные струны, Appl. Физ. Б 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] М. Лоран и С. Поляк, О положительной полуопределенной релаксации разрезанного многогранника, Линейная алгебра и ее приложения 223–224, 439 (1995).
https:/​/​doi.org/​10.1016/​0024-3795(95)00271-R

[18] М. М. Деза и М. Лоран, Геометрия разрезов и метрики, 1-е изд., Алгоритмы и комбинаторика (Springer Berlin Heidelberg, 2009).
https:/​/​doi.org/​10.1007/​978-3-642-04295-9

[19] М.Э.-Надь, М. Лоран и А. Варвициотис, Сложность задачи пополнения положительной полуопределенной матрицы с ограничением ранга, Springer International Publishing, 105 (2013), arXiv:1203.6602.
https:/​/​doi.org/​10.1007/​978-3-319-00200-2_7
Arxiv: 1203.6602

[20] REAC Пейли, Об ортогональных матрицах, Журнал математики и физики 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

[21] А. Хедаят и В. Д. Уоллис, Матрицы Адамара и их приложения, Анналы статистики 6, 1184 (1978).
https: / / doi.org/ 10.1214 / AOS / 1176344370

[22] Х. Харагани и Б. Тайфе-Резаи, Матрица Адамара порядка 428, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] Д. Ж. Чокович, О. Голубицкий и И. С. Коциреас, Некоторые новые порядки матриц Адамара и Скью-Адамара, Журнал комбинаторных расчетов 22, 270 (2014), arXiv:1301.3671.
https://​/​doi.org/​10.1002/​jcd.21358
Arxiv: 1301.3671

[24] Дж. Кон, М. Мотта и Р. М. Пэрриш, Диагонализация квантового фильтра со сжатыми дважды факторизованными гамильтонианами, PRX Quantum 2, 040352 (2021), arXiv: 2104.08957.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040352
Arxiv: 2104.08957

[25] Д.А. Шпильман и С.-Х. Тенг, Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https: / / doi.org/ 10.1145 / 990308.990310
arXiv: cs / 0111050

[26] С. Даймонд и С. Бойд, CVXPY: встроенный в Python язык моделирования для выпуклой оптимизации, J. Mach. Учиться. Рез. 17, 1 (2016), arXiv:1603.00943.
Arxiv: 1603.00943
http: / / jmlr.org/ paper / v17 ​​/ 15-408.html

[27] Агравал А., Вершурен Р., Даймонд С., Бойд С., Система перезаписи для задач выпуклой оптимизации, J. Control Decis. 5, 42 (2018), архив: 1709.04494.
https: / / doi.org/ 10.1080 / 23307706.2017.1397554
Arxiv: 1709.04494

[28] Фонд свободного программного обеспечения, GLPK (комплект линейного программирования GNU) (2012 г.), версия: 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

[29] А. Т. Филлипс и Дж. Б. Розен, Параллельный алгоритм для вогнутой квадратичной глобальной минимизации с ограничениями, Mathematical Programming 42, 421 (1988).
https: / / doi.org/ 10.1007 / BF01589415

[30] М. Дюр, Р. Хорст и М. Локателли, Еще раз о необходимых и достаточных условиях глобальной оптимальности для выпуклой максимизации, Журнал математического анализа и приложений 217, 637 (1998).
https://doi.org/10.1006/jmaa.1997.5745

[31] М. С. Базараа, Х. Д. Шерали и К. М. Шетти, Нелинейное программирование: теория и алгоритмы, 3-е издание (John Wiley & Sons, 2013).
https: / / doi.org/ 10.1002 / 0471787779

[32] М. А. Хэнсон, Invexity и теорема Куна – Такера, Журнал математического анализа и приложений 236, 594 (1999).
https://doi.org/10.1006/jmaa.1999.6484

Цитируется

Не удалось получить Перекрестная ссылка на данные во время последней попытки 2024-03-13 13:00:52: Не удалось получить цитируемые данные для 10.22331 / q-2024-03-13-1279 от Crossref. Это нормально, если DOI был зарегистрирован недавно. На САО / НАСА ADS Данные о цитировании работ не найдены (последняя попытка 2024-03-13 13:00:52).

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

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

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