Časovno optimalna večkubitna vrata: Kompleksnost, učinkovita hevristika in časovne meje vrat

Časovno optimalna večkubitna vrata: Kompleksnost, učinkovita hevristika in časovne meje vrat

Časovni žig: 13. marec 2024 8
Časovno optimalna večkubitna vrata: Kompleksnost, učinkovita hevristika in časovne meje vrat PlatoBlockchain Data Intelligence. Navpično iskanje. Ai.

Pascal Baßler1, Markus Heinrich1in Martin Kliesch2

1Inštitut za teoretično fiziko, Univerza Heinrich Heine Düsseldorf, Nemčija
2Inštitut za kvantno navdihnjeno in kvantno optimizacijo, Tehnološka univerza v Hamburgu, Nemčija

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Večkubitne prepletene interakcije se naravno pojavljajo v več kvantnih računalniških platformah in obljubljajo prednosti pred tradicionalnimi dvokubitnimi vrati. Za sintezo globalnih ZZ-vrat (GZZ-vrat) se lahko uporabi zlasti fiksna večkubitna interakcija Isingovega tipa skupaj z enokbitnimi X-vrati. V tem delu najprej pokažemo, da je sinteza takih kvantnih vrat, ki so časovno optimalna, NP-težka. Drugič, nudimo eksplicitne konstrukcije posebnih časovno optimalnih večkubitnih vrat. Imajo konstantne čase vrat in jih je mogoče implementirati z linearno številnimi plastmi X-gate. Tretjič, razvijamo hevristični algoritem s polinomskim časom izvajanja za sintezo hitrih večkubitnih vrat. Četrtič, izpeljemo spodnjo in zgornjo mejo optimalnega časa prehoda GZZ. Na podlagi eksplicitnih konstrukcij vrat GZZ in numeričnih študij domnevamo, da je mogoče katera koli vrata GZZ izvesti v času O($n$) za $n$ kubitov. Naš hevristični sintezni algoritem vodi do časov vrat GZZ s podobnim skaliranjem, kar je v tem smislu optimalno. Pričakujemo, da naša učinkovita sinteza hitrih multi-kubitnih vrat omogoča hitrejšo in s tem tudi bolj robustno na napake izvedbo kvantnih algoritmov.

► BibTeX podatki

► Reference

[1] X. Wang, A. Sørensen in K. Mølmer, Večbitna vrata za kvantno računalništvo, Phys. Rev. Lett. 86, 3907 (2001), arXiv:quant-ph/​0012055.
https: / / doi.org/ 10.1103 / PhysRevLett.86.3907
arXiv: kvant-ph / 0012055

[2] T. Monz, P. Schindler, JT Barreiro, M. Chwalla, D. Nigg, WA Coish, M. Harlander, W. Hänsel, M. Hennrich in R. Blatt, 14-qubit entanglement: Creation and coherence, Phys. Rev. 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 in WD Oliver, Superprevodni kubiti: trenutno stanje, letni pregled fizike kondenzirane snovi 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 in C. Monroe, Operacije vzporednega zapletanja na univerzalnem kvantnem računalniku z ionsko pastjo, Nature 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 in K. Kim, Razširljiva globalna zapletljiva vrata na poljubnih ionskih kubitih, 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 in M. Kliesch, Sinteza in kompilacija s časovno optimalnimi multi-kubitnimi vrati, Quantum 7, 984 (2023), arXiv :2206.06387.
https:/​/​doi.org/​10.22331/​q-2023-04-20-984
arXiv: 2206.06387

[7] F. Barahona in AR Mahjoub, On the cut politope, Mathematical Programming 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

[8] MR Garey in DS Johnson, Računalniki in nerešljivost, Vol. 29 (WH Freeman and Company, New York, 2002).

[9] MJ Bremner, A. Montanaro in DJ Shepherd, Kompleksnost povprečnega primera v primerjavi s približno simulacijo kvantnih izračunov na delo, Phys. Rev. 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 in M. Santha, vezja s konstantno globino za enotno nadzorovana vrata in logične funkcije z uporabo v kvantnih spominskih vezjih, arXiv:2308.08539 (2023).
arXiv: 2308.08539

[11] S. Bravyi, D. Maslov in Y. Nam, Implementacije Cliffordovih operacij s konstantnimi stroški in večkratno nadzorovana vrata z uporabo globalnih interakcij, Phys. Rev. Lett. 129, 230501 (2022), arXiv:2207.08691.
https: / / doi.org/ 10.1103 / PhysRevLett.129.230501
arXiv: 2207.08691

[12] S. Bravyi in D. Maslov, vezja brez Hadamarda razkrivajo strukturo skupine Clifford, IEEE Trans. Inf. Teorija 67, 4546 (2021), arXiv:2003.09412.
https: / / doi.org/ 10.1109 / TIT.2021.3081415
arXiv: 2003.09412

[13] D. Maslov in B. Zindorf, Globinska optimizacija vezij CZ, CNOT in 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 in L. Vandenberghe, Konveksna optimizacija (Cambridge University Press, 2009).

[15] E. Rich, Problemski razredi FP in FNP, v Avtomati, izračunljivost in kompleksnost: teorija in aplikacije (Pearson Education, 2007) str. 510–511.
https://​/​www.cs.utexas.edu/​~ear/​cs341/​automatabook/​AutomataTheoryBook.pdf

[16] M. Johanning, Isospaced linearni ionski nizi, Appl. Phys. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent in S. Poljak, On a positive poldefinite relaxation of cut politope, Linear Algebra and its Applications 223-224, 439 (1995).
https:/​/​doi.org/​10.1016/​0024-3795(95)00271-R

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

[19] ME-Nagy, M. Laurent in A. Varvitsiotis, Kompleksnost problema dokončanja pozitivne poldoločene matrike z omejitvijo ranga, 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 ortogonalnih matrikah, Journal of Mathematics and Physics 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

[21] A. Hedayat in WD Wallis, Hadamardove matrike in njihove aplikacije, The Annals of Statistics 6, 1184 (1978).
https://​/​doi.org/​10.1214/​aos/​1176344370

[22] H. Kharaghani in B. Tayfeh-Rezaie, Hadamardova matrika reda 428, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] D. Ž. Đoković, O. Golubitsky in IS Kotsireas, Nekateri novi vrstni redi Hadamardovih in Skew-Hadamardovih matrik, 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 in RM Parrish, Diagonalizacija kvantnega filtra s stisnjenimi dvojno faktoriziranimi hamiltonijani, PRX Quantum 2, 040352 (2021), arXiv:2104.08957.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040352
arXiv: 2104.08957

[25] DA Spielman in S.-H. Teng, Smoothed analysis of algorithms: Why the simplex algorithm ponavadi traja polinomski čas, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https: / / doi.org/ 10.1145 / 990308.990310
arXiv: cs / 0111050

[26] S. Diamond in S. Boyd, CVXPY: V Python vdelan jezik za modeliranje za konveksno optimizacijo, J. Mach. Naučite se. Res. 17, 1 (2016), arXiv:1603.00943.
arXiv: 1603.00943
http: / / jmlr.org/ papers / v17 ​​/ 15-408.html

[27] A. Agrawal, R. Verschueren, S. Diamond in S. Boyd, Sistem za prepisovanje problemov konveksne optimizacije, 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), različica: 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

[29] AT Phillips in JB Rosen, Vzporedni algoritem za omejeno konkavno kvadratno globalno minimizacijo, Mathematical Programming 42, 421 (1988).
https: / / doi.org/ 10.1007 / BF01589415

[30] M. Dür, R. Horst in M. Locatelli, Ponovni pregled potrebnih in zadostnih pogojev globalne optimalnosti za konveksno maksimizacijo, Journal of Mathematical Analysis and Applications 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

[31] MS Bazaraa, HD Sherali in CM Shetty, Nelinearno programiranje: teorija in algoritmi, 3. izdaja (John wiley & sinovi, 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

Navedel

Pridobitve ni bilo mogoče Crossref citirani podatki med zadnjim poskusom 2024-03-13 13:00:52: ni bilo mogoče pridobiti navajanih podatkov za 10.22331 / q-2024-03-13-1279 od podjetja Crossref. To je normalno, če je bil DOI registriran pred kratkim. Na SAO / NASA ADS ni bilo najdenih podatkov o navajanju del (zadnji poskus 2024-03-13 13:00:52).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal