Tidsoptimale multi-qubit-gates: kompleksitet, effektiv heuristik og gate-tidsgrænser

Tidsoptimale multi-qubit-gates: kompleksitet, effektiv heuristik og gate-tidsgrænser

Tidsstempel: 13. marts 2024 kl. 8:59
Tidsoptimale multi-qubit-gates: kompleksitet, effektiv heuristik og gate-tidsgrænser PlatoBlockchain Data Intelligence. Lodret søgning. Ai.

Pascal Baßler1, Markus Heinrich1, og Martin Kliesch2

1Institut for Teoretisk Fysik, Heinrich Heine Universitet Düsseldorf, Tyskland
2Institut for Quantum Inspired and Quantum Optimization, Hamburg University of Technology, Tyskland

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Multi-qubit entangling-interaktioner opstår naturligt i flere kvantecomputerplatforme og lover fordele i forhold til traditionelle to-qubit-gates. Især kan en fast multi-qubit Ising-type interaktion sammen med single-qubit X-gates bruges til at syntetisere globale ZZ-gates (GZZ gates). I dette arbejde viser vi først, at syntesen af ​​sådanne kvanteporte, der er tidsoptimale, er NP-hård. For det andet leverer vi eksplicitte konstruktioner af specielle tidsoptimale multi-qubit-gates. De har konstante gate-tider og kan implementeres med lineært mange X-gate-lag. For det tredje udvikler vi en heuristisk algoritme med polynomial runtime til syntetisering af hurtige multi-qubit-gates. For det fjerde udleder vi nedre og øvre grænser for den optimale GZZ gate-tid. Baseret på eksplicitte konstruktioner af GZZ-porte og numeriske undersøgelser antager vi, at enhver GZZ-gate kan udføres i en tid O($n$) for $n$ qubits. Vores heuristiske syntesealgoritme fører til GZZ gate-tider med en lignende skalering, hvilket er optimalt i denne forstand. Vi forventer, at vores effektive syntese af hurtige multi-qubit-gates muliggør hurtigere og dermed også mere fejl-robust udførelse af kvantealgoritmer.

► BibTeX-data

► Referencer

[1] X. Wang, A. Sørensen og 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 og 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 og WD Oliver, Superconducting qubits: Current status 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 og C. Monroe, Parallelle 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 og K. Kim, Skalerbare globale entangling-gates på vilkårlige 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 og 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 og AR Mahjoub, On the cut polytope, Mathematical Programming 36, 157 (1986).
https://​/​doi.org/​10.1007/​BF02592023

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

[9] MJ Bremner, A. Montanaro og DJ Shepherd, Gennemsnitlig sagskompleksitet versus omtrentlig simulering af pendlingskvanteberegninger, 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 og M. Santha, kredsløb med konstant dybde til ensartet kontrollerede porte og booleske funktioner med anvendelse på kvantehukommelseskredsløb, arXiv:2308.08539 (2023).
arXiv: 2308.08539

[11] S. Bravyi, D. Maslov og Y. Nam, Konstant-omkostningsimplementeringer af Clifford-operationer og multiplicere kontrollerede porte ved hjælp af globale interaktioner, Phys. Rev. Lett. 129, 230501 (2022), arXiv:2207.08691.
https://​/​doi.org/​10.1103/​PhysRevLett.129.230501
arXiv: 2207.08691

[12] S. Bravyi og D. Maslov, Hadamard-frie kredsløb afslører strukturen af ​​Clifford-gruppen, IEEE Trans. Inf. Theory 67, 4546 (2021), arXiv:2003.09412.
https://​/​doi.org/​10.1109/​TIT.2021.3081415
arXiv: 2003.09412

[13] D. Maslov og B. Zindorf, Dybdeoptimering af CZ-, CNOT- og Clifford-kredsløb, 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 og L. Vandenberghe, Konveks optimering (Cambridge University Press, 2009).

[15] E. Rich, Problemklasserne FP og FNP, i 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 lineære ionstrenge, Appl. Phys. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent og S. Poljak, Om en positiv semibestemt afslapning af den afskårne polytop, Linear Algebra and its Applications 223-224, 439 (1995).
https:/​/​doi.org/​10.1016/​0024-3795(95)00271-R

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

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

[21] A. Hedayat og WD Wallis, Hadamard-matricer og deres anvendelser, The Annals of Statistics 6, 1184 (1978).
https://​/​doi.org/​10.1214/​aos/​1176344370

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

[23] D. Ž. Đoković, O. Golubitsky og IS Kotsireas, Nogle nye ordrer af Hadamard- og Skew-Hadamard-matricer, 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 og RM Parrish, Kvantefilterdiagonalisering med komprimerede dobbeltfaktoriserede Hamiltonians, PRX Quantum 2, 040352 (2021), arXiv:2104.08957.
https://​/​doi.org/​10.1103/​PRXQuantum.2.040352
arXiv: 2104.08957

[25] DA Spielman og S.-H. Teng, Smoothed analysis of algorithms: Why simplex-algoritmen normalt tager polynomiel tid, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https://​/​doi.org/​10.1145/​990308.990310
arXiv:cs/0111050

[26] S. Diamond og S. Boyd, CVXPY: Et Python-indlejret modelleringssprog til konveks optimering, J. Mach. Lære. 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 og S. Boyd, Et omskrivningssystem til konvekse optimeringsproblemer, 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 og JB Rosen, En parallel algoritme for begrænset konkav kvadratisk global minimering, Mathematical Programming 42, 421 (1988).
https://​/​doi.org/​10.1007/​BF01589415

[30] M. Dür, R. Horst og M. Locatelli, Nødvendige og tilstrækkelige globale optimalitetsbetingelser for konveks maksimering gentaget, Journal of Mathematical Analysis and Applications 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

[31] MS Bazaraa, HD Sherali og CM Shetty, Ikke-lineær programmering: teori og algoritmer, 3. udgave (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

Citeret af

Kunne ikke hente Crossref citeret af data under sidste forsøg 2024-03-13 13:00:52: Kunne ikke hente citerede data for 10.22331/q-2024-03-13-1279 fra Crossref. Dette er normalt, hvis DOI blev registreret for nylig. På SAO/NASA ADS ingen data om at citere værker blev fundet (sidste forsøg 2024-03-13 13:00:52).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

Tidsstempel:

Mere fra Quantum Journal