Idő-optimális többkbites kapuk: Bonyolultság, hatékony heurisztika és kapuidő korlátok

Idő-optimális többkbites kapuk: Bonyolultság, hatékony heurisztika és kapuidő korlátok

Időbélyeg: 13. március 2024. 8:59
Idő-optimális többkbites kapuk: Bonyolultság, hatékony heurisztika és kapuidő-határok PlatoBlockchain adatintelligencia. Függőleges keresés. Ai.

Pascal Baßler1, Markus Heinrich1és Martin Kliesch2

1Elméleti Fizikai Intézet, Heinrich Heine Egyetem, Düsseldorf, Németország
2Institute for Quantum Inspired and Quantum Optimization, Hamburgi Műszaki Egyetem, Németország

Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.

Absztrakt

A több qubit összefonódó interakciók természetesen számos kvantumszámítási platformon jönnek létre, és előnyökkel kecsegtetnek a hagyományos kétkubites kapukkal szemben. Különösen egy rögzített több qubit Ising-típusú interakció és egy qubit X-kapu használható globális ZZ-kapuk (GZZ-kapuk) szintetizálására. Ebben a munkában először azt mutatjuk be, hogy az ilyen időben optimális kvantumkapuk szintézise NP-nehéz. Másodszor, explicit konstrukciókat biztosítunk speciális idő-optimális több qubites kapukból. Állandó kapuidővel rendelkeznek, és lineárisan sok X-gate réteggel megvalósíthatók. Harmadszor, polinomiális futásidejű heurisztikus algoritmust dolgozunk ki gyors, több kvbites kapuk szintetizálására. Negyedszer, levezetjük az optimális GZZ kapuidő alsó és felső határait. A GZZ kapuk explicit konstrukciói és numerikus tanulmányok alapján azt feltételezzük, hogy bármely GZZ kapu végrehajtható O($n$) idő alatt $n$ qubitre. Heurisztikus szintézis algoritmusunk hasonló skálázással vezet GZZ-kapuidőhöz, ami ilyen értelemben optimális. Arra számítunk, hogy a gyors, több kvbites kapuk hatékony szintézise lehetővé teszi a kvantum algoritmusok gyorsabb és ennélfogva hibarobusztusabb végrehajtását.

► BibTeX adatok

► Referenciák

[1] X. Wang, A. Sørensen és K. Mølmer, Multibit gates for quantum computing, Phys. Rev. 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 és R. Blatt, 14 qubit összefonódás: Teremtés és koherencia, 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 és WD Oliver, Szupravezető qubitek: 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 és C. Monroe, Parallel Enangling operations on univerzális ioncsapda kvantumszámítógépen, 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 és K. Kim, Scalable global Enangling gates on tetszőleges ion qubit, 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 és M. Kliesch, Synthesis of and Compilation of Time-optimal multi-qubit gates, Quantum 7, 984 (2023), arXiv :2206.06387.
https:/​/​doi.org/​10.22331/​q-2023-04-20-984
arXiv: 2206.06387

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

[8] MR Garey és DS Johnson, Computers and intractability, Vol. 29 (WH Freeman and Company, New York, 2002).

[9] MJ Bremner, A. Montanaro és DJ Shepherd, Átlagos eset komplexitás versus ingázási kvantumszámítások közelítő szimulációja, 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 és M. Santha, Állandó mélységű áramkörök egyenletesen vezérelt kapukhoz és logikai függvényekhez kvantum memóriaáramkörökre történő alkalmazással, arXiv:2308.08539 (2023).
arXiv: 2308.08539

[11] S. Bravyi, D. Maslov és Y. Nam: Clifford-műveletek állandó költségű megvalósításai és többszörösen ellenőrzött kapuk globális interakciók segítségével, Phys. Rev. Lett. 129, 230501 (2022), arXiv:2207.08691.
https://​/​doi.org/​10.1103/​PhysRevLett.129.230501
arXiv: 2207.08691

[12] S. Bravyi és D. Maslov, Hadamard-mentes áramkörök feltárják a Clifford csoport, az IEEE Trans szerkezetét. Inf. Theory 67, 4546 (2021), arXiv:2003.09412.
https://​/​doi.org/​10.1109/​TIT.2021.3081415
arXiv: 2003.09412

[13] D. Maslov és B. Zindorf, CZ, CNOT és Clifford áramkörök mélységi optimalizálása, 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 és L. Vandenberghe, Convex Optimization (Cambridge University Press, 2009).

[15] E. Rich, Az FP és FNP problémaosztályai, Automata, Computability and Complexity: Theory and Applications (Pearson Education, 2007) 510–511. o.
https://​/​www.cs.utexas.edu/​~ear/​cs341/​automatabook/​AutomataTheoryBook.pdf

[16] M. Johanning, Isospaced lineáris ion strings, Appl. Phys. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent és S. Poljak: A vágott politóp pozitív félig meghatározott relaxációjáról, Linear Algebra and its Applications 223-224, 439 (1995).
https:/​/​doi.org/​10.1016/​0024-3795(95)00271-R

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

[19] ME-Nagy, M. Laurent és A. Varvitsiotis, Complexity of the pozitív semidefinite matrix completion 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, Az ortogonális mátrixokról, Journal of Mathematics and Physics 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

[21] A. Hedayat és WD Wallis, Hadamard-mátrixok és alkalmazásaik, The Annals of Statistics 6, 1184 (1978).
https://​/​doi.org/​10.1214/​aos/​1176344370

[22] H. Kharaghani és B. Tayfeh-Rezaie, A Hadamard mátrix 428. sorrendben, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] D. Ž. Đoković, O. Golubitsky és IS Kotsireas, Hadamard és Skew-Hadamard mátrixok néhány új sorrendje, 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 és RM Parrish, Quantum filter diagonalization with compressed double-factorized Hamiltonians, PRX Quantum 2, 040352 (2021), arXiv:2104.08957.
https://​/​doi.org/​10.1103/​PRXQuantum.2.040352
arXiv: 2104.08957

[25] DA Spielman és S.-H. Teng: Algoritmusok simított elemzése: Miért vesz igénybe a szimplex algoritmus általában polinomiális időt, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https://​/​doi.org/​10.1145/​990308.990310
arXiv:cs/0111050

[26] S. Diamond és S. Boyd, CVXPY: Pythonba ágyazott modellező nyelv konvex optimalizáláshoz, J. Mach. Tanul. 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 és S. Boyd, A rewriting system for convex optimization problems, 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), verzió: 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

[29] AT Phillips és JB Rosen, Párhuzamos algoritmus kényszerített konkáv kvadratikus globális minimalizáláshoz, Mathematical Programming 42, 421 (1988).
https://​/​doi.org/​10.1007/​BF01589415

[30] M. Dür, R. Horst és M. Locatelli: A konvex maximalizálás szükséges és elégséges globális optimalitási feltételei, Journal of Mathematical Analysis and Applications 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

[31] MS Bazaraa, HD Sherali és CM Shetty, Nemlineáris programozás: elmélet és algoritmusok, 3. kiadás (John wiley és fiai, 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

Idézi

Nem sikerült lekérni Az adatok által hivatkozott kereszthivatkozás utolsó próbálkozáskor 2024-03-13 13:00:52: Nem sikerült lekérni a 10.22331/q-2024-03-13-1279 hivatkozás által hivatkozott adatokat a Crossref-től. Ez normális, ha a DOI-t nemrég regisztrálták. Tovább SAO/NASA HIRDETÉSEK művekre hivatkozó adat nem található (utolsó próbálkozás 2024-03-13 13:00:52).

Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.

Időbélyeg:

Még több Quantum Journal