Zeitoptimale Multi-Qubit-Gates: Komplexität, effiziente Heuristik und Gate-Zeitgrenzen

Zeitoptimale Multi-Qubit-Gates: Komplexität, effiziente Heuristik und Gate-Zeitgrenzen

Zeitstempel: 13. März 2024, 8:59 Uhr
Zeitoptimale Multi-Qubit-Gates: Komplexität, effiziente Heuristik und Gate-Zeitgrenzen PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

Pascal Bassler1, Markus Heinrich1, und Martin Kliesch2

1Institut für Theoretische Physik, Heinrich-Heine-Universität Düsseldorf, Deutschland
2Institut für Quanteninspirierte und Quantenoptimierung, Technische Universität Hamburg, Deutschland

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Multi-Qubit-Verschränkungswechselwirkungen treten auf natürliche Weise in mehreren Quantencomputerplattformen auf und versprechen Vorteile gegenüber herkömmlichen Zwei-Qubit-Gattern. Insbesondere kann eine feste Multi-Qubit-Interaktion vom Ising-Typ zusammen mit Einzel-Qubit-X-Gattern zur Synthese globaler ZZ-Gatter (GZZ-Gatter) verwendet werden. In dieser Arbeit zeigen wir zunächst, dass die Synthese solcher zeitoptimalen Quantengatter NP-schwer ist. Zweitens stellen wir explizite Konstruktionen spezieller zeitoptimaler Multi-Qubit-Gatter bereit. Sie haben konstante Gate-Zeiten und können mit linear vielen X-Gate-Schichten implementiert werden. Drittens entwickeln wir einen heuristischen Algorithmus mit polynomialer Laufzeit zur Synthese schneller Multi-Qubit-Gatter. Viertens leiten wir Unter- und Obergrenzen für die optimale GZZ-Torzeit ab. Basierend auf expliziten Konstruktionen von GZZ-Gattern und numerischen Studien vermuten wir, dass jedes GZZ-Gatter in einer Zeit O($n$) für $n$ Qubits ausgeführt werden kann. Unser heuristischer Synthesealgorithmus führt zu GZZ-Torzeiten mit einer ähnlichen Skalierung, was in diesem Sinne optimal ist. Wir gehen davon aus, dass unsere effiziente Synthese schneller Multi-Qubit-Gatter eine schnellere und damit auch fehlerrobustere Ausführung von Quantenalgorithmen ermöglicht.

► BibTeX-Daten

► Referenzen

[1] X. Wang, A. Sørensen und K. Mølmer, Multibit-Gatter für Quantencomputer, 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 und R. Blatt, 14-Qubit-Verschränkung: Erzeugung und Kohärenz, 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 und 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 und C. Monroe, Parallele Verschränkungsoperationen an einem universellen Ionenfallen-Quantencomputer, 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 und K. Kim, Scalable global entangling gates on Arbitrary Ion Qubits, 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 und M. Kliesch, Synthese von und Kompilierung mit zeitoptimalen 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 und AR Mahjoub, On the Cut Polytope, Mathematical Programming 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

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

[9] MJ Bremner, A. Montanaro und DJ Shepherd, Durchschnittliche Fallkomplexität versus ungefähre Simulation kommutierender Quantenberechnungen, 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 und M. Santha, Constant-Depth Circuits for Uniformly Controlled Gates and Boolean Functions with Application to Quantum Memory Circuits, arXiv:2308.08539 (2023).
arXiv: 2308.08539

[11] S. Bravyi, D. Maslov und Y. Nam, Constant-Cost-Implementierungen von Clifford-Operationen und mehrfach gesteuerten Gates unter Verwendung globaler Interaktionen, Phys. Rev. Lett. 129, 230501 (2022), arXiv:2207.08691.
https://doi.org/ 10.1103/PhysRevLett.129.230501
arXiv: 2207.08691

[12] S. Bravyi und D. Maslov, Hadamard-free circuits exponieren die Struktur der Clifford-Gruppe, IEEE Trans. Inf. Theorie 67, 4546 (2021), arXiv:2003.09412.
https: / / doi.org/ 10.1109 / TIT.2021.3081415
arXiv: 2003.09412

[13] D. Maslov und B. Zindorf, Tiefenoptimierung von CZ-, CNOT- und Clifford-Schaltkreisen, 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 und L. Vandenberghe, Convex Optimization (Cambridge University Press, 2009).

[15] E. Rich, Die Problemklassen FP und FNP, in 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, Isospaced linear ion strings, Appl. Physik. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent und S. Poljak, Über eine positive semidefinite Entspannung des geschnittenen Polytops, Linear Algebra and its Applications 223-224, 439 (1995).
https:/​/​doi.org/​10.1016/​0024-3795(95)00271-R

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

[19] ME-Nagy, M. Laurent und A. Varvitsiotis, Complexity of the Positive 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, Über orthogonale Matrizen, Journal of Mathematics and Physics 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

[21] A. Hedayat und WD Wallis, Hadamard-Matrizen und ihre Anwendungen, The Annals of Statistics 6, 1184 (1978).
https: / / doi.org/ 10.1214 / aos / 1176344370

[22] H. Kharaghani und B. Tayfeh-Rezaie, Eine Hadamard-Matrix der Ordnung 428, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] D. Ž. Đoković, O. Golubitsky und IS Kotsireas, Einige neue Ordnungen von Hadamard- und Skew-Hadamard-Matrizen, 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 und RM Parrish, Quantum Filter Diagonization 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 und S.-H. Teng, Geglättete Analyse von Algorithmen: Warum der Simplex-Algorithmus normalerweise Polynomialzeit benötigt, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https: / / doi.org/ 10.1145 / 990308.990310
arXiv: cs / 0111050

[26] S. Diamond und S. Boyd, CVXPY: Eine in Python eingebettete Modellierungssprache für die konvexe Optimierung, J. Mach. Lernen. 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 und S. Boyd, Ein Umschreibungssystem für konvexe Optimierungsprobleme, 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), Version: 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

[29] AT Phillips und JB Rosen, Ein paralleler Algorithmus zur eingeschränkten konkaven quadratischen globalen Minimierung, Mathematical Programming 42, 421 (1988).
https: / / doi.org/ 10.1007 / BF01589415

[30] M. Dür, R. Horst und M. Locatelli, Notwendige und ausreichende globale Optimalitätsbedingungen für die konvexe Maximierung überarbeitet, Journal of Mathematical Analysis and Applications 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

[31] MS Bazaraa, HD Sherali und CM Shetty, Nichtlineare Programmierung: Theorie und Algorithmen, 3. Auflage (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

Zitiert von

Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2024-03-13 13:00:52: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2024-03-13-1279 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde. Auf SAO / NASA ADS Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2024-03-13 13:00:52).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

Zeitstempel:

Mehr von Quantenjournal