Tidsoptimale multi-qubit-porter: kompleksitet, effektiv heuristikk og gate-tidsgrenser

Tidsoptimale multi-qubit-porter: kompleksitet, effektiv heuristikk og gate-tidsgrenser

Tidsstempel: 13. mars 2024 8:59
Tidsoptimale multi-qubit-porter: kompleksitet, effektiv heuristikk og gate-tidsgrenser PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

Pascal Baßler1, Markus Heinrich1, og Martin Kliesch2

1Institutt for teoretisk fysikk, Heinrich Heine University Düsseldorf, Tyskland
2Institute for Quantum Inspired and Quantum Optimization, Hamburg University of Technology, Tyskland

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Multi-qubit-sammenfiltrende interaksjoner oppstår naturlig i flere kvantedatabehandlingsplattformer og lover fordeler fremfor tradisjonelle to-qubit-porter. Spesielt kan en fast multi-qubit Ising-type interaksjon sammen med single-qubit X-porter brukes til å syntetisere globale ZZ-porter (GZZ-porter). I dette arbeidet viser vi først at syntesen av slike kvanteporter som er tidsoptimale er NP-hard. For det andre gir vi eksplisitte konstruksjoner av spesielle tidsoptimale multi-qubit-porter. De har konstante gate-tider og kan implementeres med lineært mange X-gate-lag. For det tredje utvikler vi en heuristisk algoritme med polynomisk kjøretid for å syntetisere raske multi-qubit-porter. For det fjerde utleder vi nedre og øvre grenser for den optimale GZZ-gatetiden. Basert på eksplisitte konstruksjoner av GZZ-porter og numeriske studier, antar vi at enhver GZZ-port kan utføres på en tid O($n$) for $n$ qubits. Vår heuristiske syntesealgoritme fører til GZZ gate-tider med en lignende skalering, som er optimal i denne forstand. Vi forventer at vår effektive syntese av raske multi-qubit-porter tillater raskere og dermed også mer feilrobust utførelse av kvantealgoritmer.

► BibTeX-data

► Referanser

[1] X. Wang, A. Sørensen og K. Mølmer, Multibit-porter for kvanteberegning, 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-porter 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, Syntese av og kompilering med tidsoptimale multi-qubit-porter, 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, Gjennomsnittlig sakskompleksitet versus omtrentlig simulering av pendlende kvanteberegninger, 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, 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 og Y. Nam, Konstantkostnadsimplementeringer av Clifford-operasjoner og multiplisere kontrollerte porter ved bruk av globale interaksjoner, 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 kretser avslører strukturen til 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, Dybdeoptimalisering av CZ-, CNOT- og Clifford-kretser, 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 optimalisering (Cambridge University Press, 2009).

[15] E. Rich, Problemklassene 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 ion strenger, Appl. Phys. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent og 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 og M. Laurent, Geometry of Cuts and Metrics, 1. utg., 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 ortogonal matrices, Journal of Mathematics and Physics 12, 311 (1933).
https://​/​doi.org/​10.1002/​sapm1933121311

[21] A. Hedayat og WD Wallis, Hadamard-matriser 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-matrise av orden 428, Journal of Combinatorial Designs 13, 435 (2005).
https://​/​doi.org/​10.1002/​jcd.20043

[23] D. Ž. Đoković, O. Golubitsky og IS Kotsireas, Noen nye bestillinger av Hadamard- og Skew-Hadamard-matriser, 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 komprimerte dobbeltfaktoriserte 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 vanligvis tar polynomtid, 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-innebygd modelleringsspråk for konveks optimalisering, 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 omskrivingssystem for 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), versjon: 0.4.6.
https://www.gnu.org/​software/​glpk/​

[29] AT Phillips og JB Rosen, En parallell algoritme for begrenset 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 tilstrekkelige globale optimalitetsbetingelser for konveks maksimering revisited, 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. utgave (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

Sitert av

Kunne ikke hente Crossref sitert av data under siste forsøk 2024-03-13 13:00:52: Kunne ikke hente siterte data for 10.22331 / q-2024-03-13-1279 fra Crossref. Dette er normalt hvis DOI nylig ble registrert. På SAO / NASA ADS ingen data om sitering av verk ble funnet (siste forsøk 2024-03-13 13:00:52).

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal