Porți multi-qubit optime pentru timp: complexitate, euristică eficientă și limite de timp de poartă

Porți multi-qubit optime pentru timp: complexitate, euristică eficientă și limite de timp de poartă

Marca temporală: 13 martie 2024 8:59 AM
Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Pascal Baßler1, Markus Heinrich1și Martin Kliesch2

1Institutul de Fizică Teoretică, Universitatea Heinrich Heine Düsseldorf, Germania
2Institutul pentru Inspirat Cuantic și Optimizare Cuantică, Universitatea de Tehnologie din Hamburg, Germania

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Interacțiunile încurcate cu mai mulți qubiți apar în mod natural în mai multe platforme de calcul cuantic și promit avantaje față de porțile tradiționale de doi qubiți. În special, o interacțiune fixă ​​de tip Ising cu mai mulți qubit împreună cu porți X cu un singur qubit poate fi utilizată pentru a sintetiza porți ZZ globale (porți GZZ). În această lucrare, arătăm mai întâi că sinteza unor astfel de porți cuantice care sunt optime în timp este NP-hard. În al doilea rând, oferim construcții explicite ale porților multi-qubit optime pentru timp. Au timpi de poartă constanti și pot fi implementate liniar cu multe straturi X-gate. În al treilea rând, dezvoltăm un algoritm euristic cu timp de rulare polinomial pentru sintetizarea porților rapide multi-qubit. În al patrulea rând, derivăm limitele inferioare și superioare ale timpului optim de poartă GZZ. Pe baza construcțiilor explicite ale porților GZZ și a studiilor numerice, presupunem că orice poartă GZZ poate fi executată într-un timp O($n$) pentru $n$ qubiți. Algoritmul nostru de sinteză euristică conduce la timpi-portă GZZ cu o scalare similară, ceea ce este optim în acest sens. Ne așteptăm ca sinteza noastră eficientă de porți rapide multi-qubit să permită o execuție mai rapidă și, prin urmare, de asemenea, mai robustă la erori a algoritmilor cuantici.

► Date BibTeX

► Referințe

[1] X. Wang, A. Sørensen și K. Mølmer, Porți multibiți pentru calculul cuantic, 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 și 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 ș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, Parallel entangling operations on a universal ion-trap quantum computer, 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 și 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 și M. Kliesch, Synthesis of and compilation with 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 și AR Mahjoub, On the cut polytope, Mathematical Programming 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

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

[9] MJ Bremner, A. Montanaro și DJ Shepherd, Complexitatea medie a cazului versus simularea aproximativă a calculelor cuantice de navetă, 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 și 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 și Y. Nam, Implementări cu costuri constante ale operațiunilor Clifford și porți controlate multipli folosind interacțiuni globale, Phys. Rev. Lett. 129, 230501 (2022), arXiv:2207.08691.
https: / / doi.org/ 10.1103 / PhysRevLett.129.230501
arXiv: 2207.08691

[12] S. Bravyi și D. Maslov, circuitele fără Hadamard expun structura grupului Clifford, IEEE Trans. Inf. Theory 67, 4546 (2021), arXiv:2003.09412.
https: / / doi.org/ 10.1109 / TIT.2021.3081415
arXiv: 2003.09412

[13] D. Maslov și B. Zindorf, Optimizarea adâncimii circuitelor 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, Clasele de probleme FP și FNP, în Automate, Computability and Complexity: Theory and Applications (Pearson Education, 2007) pp. 510–511.
https:/​/​www.cs.utexas.edu/​~ear/​cs341/​automatabook/​AutomataTheoryBook.pdf

[16] M. Johanning, Corzi de ioni lineari izospațiați, Appl. Fiz. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent și S. Poljak, On a positive semidefinite relaxation of the cut polytope, Linear Algebra and its 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, prima ed., Algorithms and Combinatorics (Springer Berlin Heidelberg, 1).
https:/​/​doi.org/​10.1007/​978-3-642-04295-9

[19] ME-Nagy, M. Laurent și 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, On orthogonal matrices, Journal of Mathematics and Physics 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

[21] A. Hedayat și WD Wallis, Matricele Hadamard și aplicațiile lor, The Annals of Statistics 6, 1184 (1978).
https: / / doi.org/ 10.1214 / AOS / 1176344370

[22] H. Kharaghani și B. Tayfeh-Rezaie, A Hadamard matrix of order 428, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] D. Ž. Đoković, O. Golubitsky și IS Kotsireas, Some new orders of Hadamard and Skew-Hadamard matrices, 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, 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 și S.-H. Teng, Smoothed analysis of algorithms: Why the simplex algorithm often takes polynomial time, 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: Un limbaj de modelare încorporat în Python pentru optimizarea convexă, J. Mach. Învăța. 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 și 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), versiunea: 0.4.6.
https://​/​www.gnu.org/​software/​glpk/​

[29] AT Phillips și JB Rosen, A parallel algorithm for concave quadratic global minimization, Mathematical Programming 42, 421 (1988).
https: / / doi.org/ 10.1007 / BF01589415

[30] M. Dür, R. Horst și M. Locatelli, Necessary and sufficient global optimality conditions for convex maximization revisited, 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, Programare neliniară: teorie și algoritmi, ediția a 3-a (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

Citat de

Nu a putut să aducă Date citate încrucișate în ultima încercare 2024-03-13 13:00:52: Nu s-au putut prelua date citate pentru 10.22331 / q-2024-03-13-1279 de la Crossref. Acest lucru este normal dacă DOI a fost înregistrat recent. Pe ADS SAO / NASA nu s-au găsit date despre citarea lucrărilor (ultima încercare 2024-03-13 13:00:52).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic