Оптимальні за часом багатокубітні ворота: складність, ефективна евристика та межі часу воріт

Оптимальні за часом багатокубітні ворота: складність, ефективна евристика та межі часу воріт

Мітка часу: 13 березня 2024 р., 8:59
Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds PlatoBlockchain Data Intelligence. Vertical Search. Ai.

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

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

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

абстрактний

Взаємодії багатокубітного заплутування виникають природним чином на кількох платформах квантових обчислень і обіцяють переваги перед традиційними двокубітовими воротами. Зокрема, фіксовану багатокубітну взаємодію типу Ізінга разом з однокубітовими X-ворітами можна використовувати для синтезу глобальних ZZ-воріт (воріт GZZ). У цій роботі ми спочатку показуємо, що синтез таких квантових вентилів, які є оптимальними за часом, є NP-складним. По-друге, ми надаємо явні конструкції спеціальних мультикубітових вентилів з оптимальним часом. Вони мають постійний час затвора і можуть бути реалізовані з лінійно багатьма шарами X-gate. По-третє, ми розробляємо евристичний алгоритм із поліноміальним часом виконання для синтезу швидких мультикубітових вентилів. По-четверте, ми виводимо нижню та верхню межі оптимального часу стробування GZZ. Базуючись на явних конструкціях вентилів GZZ і чисельних дослідженнях, ми припускаємо, що будь-який вентиль GZZ може бути виконаний за час O($n$) для $n$ кубітів. Наш алгоритм евристичного синтезу призводить до GZZ воріт-часів із подібним масштабуванням, що є оптимальним у цьому сенсі. Ми очікуємо, що наш ефективний синтез швидких багатокубітових вентилів дозволить швидше і, отже, більш стійке до помилок виконання квантових алгоритмів.

► Дані BibTeX

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

[1] X. Wang, A. Sørensen і K. Mølmer, Multibit gates for quantum computing, Phys. Преподобний Летт. 86, 3907 (2001), arXiv:quant-ph/​0012055.
https: / / doi.org/ 10.1103 / PhysRevLett.86.3907
arXiv: quant-ph / 0012055

[2] T. Monz, P. Schindler, JT Barreiro, M. Chwalla, D. Nigg, WA Coish, M. Harlander, W. Hänsel, M. Hennrich, and R. Blatt, 14-qubit entanglement: Creation and coherence, Phys. Преподобний Летт. 106, 130506 (2011), arXiv:1009.6126.
https: / / doi.org/ 10.1103 / PhysRevLett.106.130506
arXiv: 1009.6126

[3] M. Kjaergaard, ME Schwartz, J. Braumüller, P. Krantz, JI-J. Ван, С. Густавссон і В. Д. Олівер, Надпровідні кубіти: поточний стан гри, 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] C. Figgatt, A. Ostrander, NM Linke, KA Landsman, D. Zhu, D. Maslov і C. Monroe, Паралельні операції заплутування на універсальному квантовому комп’ютері з іонною пасткою, 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] P. Baßler, M. Zipper, C. Cedzich, M. Heinrich, PH Huber, M. Johanning, and M. Kliesch, Synthesis of and compilation with time-optimal multi-cubit gate, Quantum 7, 984 (2023), arXiv :2206.06387.
https:/​/​doi.org/​10.22331/​q-2023-04-20-984
arXiv: 2206.06387

[7] Ф. Барахона та А. Р. Маджуб, Про розрізаний багатогранник, Математичне програмування 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

[8] MR Garey і DS Johnson, Комп'ютери та нерозв'язність, Vol. 29 (WH Freeman and Company, Нью-Йорк, 2002).

[9] MJ Bremner, A. Montanaro та DJ Shepherd, Average-case complexity versus aproximate simulation of commuting quantum computations, 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] S. Bravyi, D. Maslov та Y. Nam, Реалізації операцій Кліффорда з постійною вартістю та множинно керованих вентилів із використанням глобальних взаємодій, Phys. Преподобний Летт. 129, 230501 (2022), arXiv: 2207.08691.
https: / / doi.org/ 10.1103 / PhysRevLett.129.230501
arXiv: 2207.08691

[12] С. Бравий і Д. Маслов, Без Адамара схеми розкривають структуру групи Кліффорда, IEEE Trans. Інф. Теорія 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] С. Бойд і Л. Ванденберге, опукла оптимізація (Cambridge University Press, 2009).

[15] E. Rich, The problem classes FP and FNP, in Automata, Computability and Complexity: Theory and Applications (Pearson Education, 2007) стор. 510–511.
https://​/​www.cs.utexas.edu/​~ear/​cs341/​automatabook/​AutomataTheoryBook.pdf

[16] М. Йоганнінг, Лінійні іонні струни з рівним простором, Appl. фіз. B 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, Гейдельберг, 2009).
https:/​/​doi.org/​10.1007/​978-3-642-04295-9

[19] ME-Nagy, M. Laurent і A. Varvitsiotis, Complexity of the positive halfdefinite matrix complement problem with a rank constraint, Springer International Publishing, 105 (2013), arXiv:1203.6602.
https:/​/​doi.org/​10.1007/​978-3-319-00200-2_7
arXiv: 1203.6602

[20] REAC Paley, On orthogonal matrices, Journal of Mathematics and Physics 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

[21] A. Hedayat і WD Wallis, Матриці Адамара та їх застосування, The Annals of Statistics 6, 1184 (1978).
https://​/​doi.org/​10.1214/​aos/​1176344370

[22] H. Kharaghani і B. Tayfeh-Rezaie, Матриця Адамара порядку 428, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] Д. Ж. Джокович, О. Голубіцький та І. С. Коціреас, Деякі нові порядки матриць Адамара та косо-Адамара, Journal of Combinatorial Designs 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 мова моделювання для опуклої оптимізації, Дж. Мах. вчитися. рез. 17, 1 (2016), arXiv:1603.00943.
arXiv: 1603.00943
http://​/​jmlr.org/​papers/​v17/​15-408.html

[27] A. Agrawal, R. Verschueren, S. Diamond і S. Boyd, Система переписування задач опуклої оптимізації, J. Control Decis. 5, 42 (2018), arXiv:1709.04494.
https: / / doi.org/ 10.1080 / 23307706.2017.1397554
arXiv: 1709.04494

[28] Free Software Foundation, GLPK (GNU Linear Programming Kit) (2012), версія: 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

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

[30] M. Dür, R. Horst, and M. Locatelli, Необхідні та достатні умови глобальної оптимальності для опуклої максимізації знову, Journal of Mathematical Analysis and Applications 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

[31] MS Bazaraa, HD Sherali та CM Shetty, Nonlinear programming: theory and algorithms, 3rd edition (John Wiley & sons, 2013).
https: / / doi.org/ 10.1002 / 0471787779

[32] MA Hanson, Invexity and the Kuhn–Tucker Theorem, Journal of Mathematical Analysis and Applications 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 був зареєстрований нещодавно. Увімкнено SAO / NASA ADS даних про цитування робіт не знайдено (остання спроба 2024-03-13 13:00:52).

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

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

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