Optymalne czasowo bramki wielokubitowe: złożoność, wydajna heurystyka i ograniczenia czasowe bramki

Optymalne czasowo bramki wielokubitowe: złożoność, wydajna heurystyka i ograniczenia czasowe bramki

Znacznik czasu: 13 marca 2024 8:59
Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Pascala Basslera1, Markusa Heinricha1i Martina Kliescha2

1Instytut Fizyki Teoretycznej, Uniwersytet Heinricha Heinego w Düsseldorfie, Niemcy
2Instytut Inspirowanych Kwantami i Optymalizacji Kwantowej, Politechnika w Hamburgu, Niemcy

Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.

Abstrakcyjny

Interakcje splątania wielu kubitów powstają naturalnie na kilku platformach obliczeń kwantowych i zapewniają przewagę nad tradycyjnymi bramkami dwukubitowymi. W szczególności ustalona wielokubitowa interakcja typu Isinga wraz z jednokubitowymi bramkami X może zostać wykorzystana do syntezy globalnych bramek ZZ (bramki GZZ). W tej pracy najpierw pokazujemy, że synteza takich bramek kwantowych, które są optymalne czasowo, jest NP-trudna. Po drugie, zapewniamy jawne konstrukcje specjalnych optymalnych czasowo bramek wielokubitowych. Mają stałe czasy bramek i mogą być realizowane z liniowo wieloma warstwami bramki X. Po trzecie, opracowujemy algorytm heurystyczny z wielomianowym czasem wykonania do syntezy szybkich bramek wielokubitowych. Po czwarte, wyznaczamy dolną i górną granicę optymalnego czasu bramki GZZ. Na podstawie jawnych konstrukcji bramek GZZ i badań numerycznych przypuszczamy, że dowolną bramkę GZZ można wykonać w czasie O($n$) dla $n$ kubitów. Nasz algorytm syntezy heurystycznej prowadzi do czasów bramek GZZ o podobnym skalowaniu, co jest optymalne w tym sensie. Oczekujemy, że nasza wydajna synteza szybkich bramek wielokubitowych umożliwi szybsze, a co za tym idzie, również bardziej odporne na błędy wykonywanie algorytmów kwantowych.

► Dane BibTeX

► Referencje

[1] X. Wang, A. Sørensen i K. Mølmer, Multibitowe bramki do obliczeń kwantowych, Phys. Wielebny Lett. 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 i R. Blatt, splątanie 14-kubitowe: tworzenie i koherencja, Phys. Wielebny Lett. 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. Wang, S. Gustavsson i WD Oliver, Superconducting qubits: Current state of play, 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 i C. Monroe, Równoległe operacje splątania na uniwersalnym komputerze kwantowym z pułapką jonową, Natura 572, 368 (2019), arXiv: 1810.11948 .
https:/​/​doi.org/​10.1038/​s41586-019-1427-5
arXiv: 1810.11948

[5] Y. Lu, S. Zhang, K. Zhang, W. Chen, Y. Shen, J. Zhang, J.-N. Zhang i K. Kim, Skalowalne globalne bramki splątujące na arbitralnych kubitach jonowych, 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 i M. Kliesch, Synteza i kompilacja z optymalnymi czasowo bramkami wielokubitowymi, Quantum 7, 984 (2023), arXiv :2206.06387.
https:/​/​doi.org/​10.22331/​q-2023-04-20-984
arXiv: 2206.06387

[7] F. Barahona i AR Mahjoub, O ciętym wielotopie, Programowanie matematyczne 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

[8] MR Garey i DS Johnson, Komputery i niewykonalność, tom. 29 (WH Freeman and Company, Nowy Jork, 2002).

[9] MJ Bremner, A. Montanaro i DJ Shepherd, Złożoność średniego przypadku a przybliżona symulacja obliczeń kwantowych dojeżdżających do pracy, Phys. Wielebny Lett. 117, 080501 (2016), arXiv:1504.07999.
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501
arXiv: 1504.07999

[10] J. Allcock, J. Bao, JF Doriguello, A. Luongo i M. Santha, Obwody o stałej głębokości dla bramek jednolicie kontrolowanych i funkcji boolowskich z zastosowaniem do obwodów pamięci kwantowej, arXiv:2308.08539 (2023).
arXiv: 2308.08539

[11] S. Bravyi, D. Maslov i Y. Nam, Implementacje operacji Clifforda o stałym koszcie i wielokrotnie kontrolowane bramki przy użyciu globalnych interakcji, Phys. Wielebny Lett. 129, 230501 (2022), arXiv:2207.08691.
https: / / doi.org/ 10.1103 / PhysRevLett.129.230501
arXiv: 2207.08691

[12] S. Bravyi i D. Maslov, Obwody wolne od Hadamarda ujawniają strukturę grupy Clifforda, IEEE Trans. Inf. Teoria 67, 4546 (2021), arXiv: 2003.09412.
https: / / doi.org/ 10.1109 / TIT.2021.3081415
arXiv: 2003.09412

[13] D. Maslov i B. Zindorf, Optymalizacja głębokości obwodów CZ, CNOT i Clifford, IEEE Transactions on Quantum Engineering 3, 1 (2022), arxiv:2201.05215.
https: // doi.org/ 10.1109 / TQE.2022.3180900
arXiv: 2201.05215

[14] S. Boyd i L. Vandenberghe, Convex Optimization (Cambridge University Press, 2009).

[15] E. Rich, Klasy problemów FP i FNP, w: Automata, Computability and Complexity: Theory and Applications (Pearson Education, 2007), s. 510–511.
https://​/​www.cs.utexas.edu/​~ear/​cs341/​automatabook/​AutomataTheoryBook.pdf

[16] M. Johanning, Liniowe struny jonowe w izoodległych odstępach, Appl. Fiz. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent i S. Poljak, O dodatniej, półokreślonej relaksacji ciętego wielotopu, Linear Algebra and his Applications 223-224, 439 (1995).
https:/​/​doi.org/​10.1016/​0024-3795(95)00271-R

[18] MM Deza i M. Laurent, Geometry of Cuts and Metrics, wydanie 1, Algorithms and Combinatorics (Springer Berlin Heidelberg, 2009).
https:/​/​doi.org/​10.1007/​978-3-642-04295-9

[19] ME-Nagy, M. Laurent i A. Varvitsiotis, Złożoność problemu uzupełniania macierzy dodatniej półokreślonej z ograniczeniem rangowym, 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, O macierzach ortogonalnych, Journal of Mathematics and Physics 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

[21] A. Hedayat i WD Wallis, Macierze Hadamarda i ich zastosowania, The Annals of Statistics 6, 1184 (1978).
https://​/​doi.org/​10.1214/​aos/​1176344370

[22] H. Kharaghani i B. Tayfeh-Rezaie, Macierz Hadamarda rzędu 428, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] D. Ż. Đoković, O. Golubitsky i IS Kotsireas, Niektóre nowe porządki macierzy Hadamarda i Skew-Hadamarda, Journal of Combinatorial Designs 22, 270 (2014), arXiv: 1301.3671.
https://​/​doi.org/​10.1002/​jcd.21358
arXiv: 1301.3671

[24] J. Cohn, M. Motta i RM Parrish, Diagonalizacja filtrów kwantowych ze skompresowanymi hamiltonianami z podwójnymi czynnikami, PRX Quantum 2, 040352 (2021), arXiv: 2104.08957.
https: // doi.org/ 10.1103 / PRXQuantum.2.040352
arXiv: 2104.08957

[25] DA Spielman i S.-H. Teng, Wygładzona analiza algorytmów: dlaczego algorytm simpleks zwykle zajmuje czas wielomianowy, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https: / / doi.org/ 10.1145 / 990308.990310
arXiv: cs / 0111050

[26] S. Diamond i S. Boyd, CVXPY: Język modelowania osadzony w Pythonie do optymalizacji wypukłej, J. Mach. Uczyć się. Rozdzielczość 17, 1 (2016), arXiv:1603.00943.
arXiv: 1603.00943
http: // jmlr.org/ papers / v17 ​​/ 15-408.html

[27] A. Agrawal, R. Verschueren, S. Diamond i S. Boyd, system przepisywania wypukłych problemów optymalizacyjnych, 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), wersja: 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

[29] AT Phillips i JB Rosen, Algorytm równoległy dla ograniczonej globalnej minimalizacji wklęsłej kwadratowej, Mathematical Programming 42, 421 (1988).
https: / / doi.org/ 10.1007 / BF01589415

[30] M. Dür, R. Horst i M. Locatelli, Ponowne spojrzenie na konieczne i wystarczające globalne warunki optymalności dla maksymalizacji wypukłej, Journal of Mathematical Analysis and Applications 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

[31] MS Bazaraa, HD Sherali i CM Shetty, Programowanie nieliniowe: teoria i algorytmy, wydanie 3 (John Wiley & Sons, 2013).
https: / / doi.org/ 10.1002 / 0471787779

[32] MA Hanson, Invexity i twierdzenie Kuhna – Tuckera, Journal of Mathematical Analysis and Applications 236, 594 (1999).
https://​/​doi.org/​10.1006/​jmaa.1999.6484

Cytowany przez

Nie można pobrać Przywołane przez Crossref dane podczas ostatniej próby 2024-03-13 13:00:52: Nie można pobrać cytowanych danych dla 10.22331 / q-2024-03-13-1279 z Crossref. Jest to normalne, jeśli DOI zostało niedawno zarejestrowane. Na Reklamy SAO / NASA nie znaleziono danych na temat cytowania prac (ostatnia próba 2024-03-13 13:00:52).

Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.

Znak czasu:

Więcej z Dziennik kwantowy