Tidsoptimala multi-qubit-grindar: komplexitet, effektiv heuristik och gate-tidsgränser

Tidsoptimala multi-qubit-grindar: komplexitet, effektiv heuristik och gate-tidsgränser

Tidsstämpel: 13 mars 2024 8:59
Tidsoptimala multi-qubit-grindar: Komplexitet, effektiv heuristik och gate-tidsgränser PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Pascal Baßler1, Markus Heinrich1, och Martin Kliesch2

1Institutet för teoretisk fysik, Heinrich Heine University Düsseldorf, Tyskland
2Institute for Quantum Inspired and Quantum Optimization, Hamburgs tekniska universitet, Tyskland

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Multi-qubit intrasslande interaktioner uppstår naturligt i flera quantum computing-plattformar och lovar fördelar jämfört med traditionella två-qubit-grindar. Speciellt kan en fast multi-qubit-interaktion av Ising-typ tillsammans med en-qubit X-grindar användas för att syntetisera globala ZZ-grindar (GZZ-grindar). I detta arbete visar vi först att syntesen av sådana kvantportar som är tidsoptimala är NP-hård. För det andra tillhandahåller vi explicita konstruktioner av speciella tidsoptimala multi-qubit-grindar. De har konstanta gate-tider och kan implementeras med linjärt många X-gate-lager. För det tredje utvecklar vi en heuristisk algoritm med polynom körtid för att syntetisera snabba multi-qubit-grindar. För det fjärde härleder vi nedre och övre gränser för den optimala GZZ gate-tiden. Baserat på explicita konstruktioner av GZZ-grindar och numeriska studier, antar vi att vilken GZZ-grind som helst kan exekveras på en tid O($n$) för $n$ qubits. Vår heuristiska syntesalgoritm leder till GZZ-gate-tider med en liknande skalning, vilket är optimalt i denna mening. Vi förväntar oss att vår effektiva syntes av snabba multi-qubit-grindar möjliggör snabbare och därmed också mer felrobust exekvering av kvantalgoritmer.

► BibTeX-data

► Referenser

[1] X. Wang, A. Sørensen och K. Mølmer, Multibit-grindar för kvantberäkning, Phys. Rev. Lett. 86, 3907 (2001), arXiv:quant-ph/​0012055.
https: / / doi.org/ 10.1103 / PhysRevLett.86.3907
arXiv: kvant-ph / 0012055

[2] T. Monz, P. Schindler, JT Barreiro, M. Chwalla, D. Nigg, WA Coish, M. Harlander, W. Hänsel, M. Hennrich och 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 och 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 och C. Monroe, Parallell 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 och 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 och 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 och AR Mahjoub, On the cut polytope, Mathematical Programming 36, 157 (1986).
https: / / doi.org/ 10.1007 / BF02592023

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

[9] MJ Bremner, A. Montanaro och DJ Shepherd, Genomsnittlig fallkomplexitet kontra ungefärlig simulering av pendlingskvantberäkningar, 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 och 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 och Y. Nam, Konstantkostnadsimplementeringar av Clifford-operationer och multiplicera styrda grindar med hjälp av globala interaktioner, Phys. Rev. Lett. 129, 230501 (2022), arXiv:2207.08691.
https: / / doi.org/ 10.1103 / PhysRevLett.129.230501
arXiv: 2207.08691

[12] S. Bravyi och D. Maslov, Hadamard-fria kretsar avslöjar strukturen hos 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 och B. Zindorf, Djupoptimering av CZ-, CNOT- och Clifford-kretsar, 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 och L. Vandenberghe, konvex optimering (Cambridge University Press, 2009).

[15] E. Rich, Problemklasserna FP och 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 linjär jonsträngar, Appl. Phys. B 122, 71 (2016).
https:/​/​doi.org/​10.1007/​s00340-016-6340-0

[17] M. Laurent och S. Poljak, On a positiv 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 och M. Laurent, Geometry of Cuts and Metrics, 1:a upplagan, Algorithms and Combinatorics (Springer Berlin Heidelberg, 2009).
https:/​/​doi.org/​10.1007/​978-3-642-04295-9

[19] ME-Nagy, M. Laurent och 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 och WD Wallis, Hadamard-matriser och deras tillämpningar, The Annals of Statistics 6, 1184 (1978).
https: / / doi.org/ 10.1214 / AOS / 1176344370

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

[23] D. Ž. Đoković, O. Golubitsky och IS Kotsireas, Några nya beställningar av Hadamard- och 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 och 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 och S.-H. Teng, Smoothed analysis of algorithms: Why simplex-algoritmen tar vanligtvis polynomtid, Journal of the ACM 51, 385 (2004), arXiv:cs/​0111050.
https: / / doi.org/ 10.1145 / 990308.990310
arXiv: cs / 0111050

[26] S. Diamond och S. Boyd, CVXPY: Ett Python-inbäddat modelleringsspråk för konvex optimering, J. Mach. Lära sig. 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 och S. Boyd, Ett omskrivningssystem för konvexa optimeringsproblem, 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 och JB Rosen, En parallell algoritm för begränsad konkav kvadratisk global minimering, Mathematical Programming 42, 421 (1988).
https: / / doi.org/ 10.1007 / BF01589415

[30] M. Dür, R. Horst och M. Locatelli, Nödvändiga och tillräckliga globala optimalitetsvillkor för konvex maximering återbesöks, Journal of Mathematical Analysis and Applications 217, 637 (1998).
https://​/​doi.org/​10.1006/​jmaa.1997.5745

[31] MS Bazaraa, HD Sherali och CM Shetty, Icke-linjär programmering: teori och algoritmer, 3:e upplagan (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

Citerad av

Det gick inte att hämta Crossref citerade data under sista försök 2024-03-13 13:00:52: Det gick inte att hämta citerade data för 10.22331 / q-2024-03-13-1279 från Crossref. Detta är normalt om DOI registrerades nyligen. På SAO / NASA ADS Inga uppgifter om citerande verk hittades (sista försök 2024-03-13 13:00:52).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal