Rumtidseffektiv lav-dybde kvantetilstandsforberedelse med applikationer

Rumtidseffektiv lav-dybde kvantetilstandsforberedelse med applikationer

Tidsstempel: 15. februar 2024 kl. 10:13

Kaiwen Gui1,2,3, Alexander M. Dalzell4, Alessandro Achille5, Martin Suchara1og Frederic T. Chong3

1Amazon Web Services, WA, USA
2Pritzker School of Molecular Engineering, University of Chicago, IL, USA
3Department of Computer Science, University of Chicago, IL, USA
4AWS Center for Quantum Computing, Pasadena, CA, USA
5AWS AI Labs, Pasadena, CA, USA

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

Abstrakt

Vi foreslår en ny deterministisk metode til at forberede vilkårlige kvantetilstande. Når vores protokol er kompileret i CNOT og vilkårlige single-qubit-gates, forbereder den en $N$-dimensional tilstand i dybden $O(log(N))$ og $textit{rumtidsallokering}$ (en metrik, der tager højde for det faktum at nogle ancilla qubits ofte ikke behøver at være aktive for hele kredsløbet) $O(N)$, som begge er optimale. Når det kompileres i ${mathrm{H,S,T,CNOT}}$-portsættet, viser vi, at det kræver asymptotisk færre kvanteressourcer end tidligere metoder. Specifikt forbereder den en vilkårlig tilstand op til fejlen $epsilon$ med optimal dybde på $O(log(N) + log (1/epsilon))$ og rumtidsallokering $O(Nlog(log(N)/epsilon))$ , der forbedres over henholdsvis $O(log(N)log(log (N)/epsilon))$ og $O(Nlog(N/epsilon))$. Vi illustrerer, hvordan den reducerede rumtidsallokering af vores protokol muliggør hurtig forberedelse af mange usammenhængende tilstande med kun konstant-faktor ancilla overhead – $O(N)$ ancilla qubits genbruges effektivt til at forberede en produkttilstand på $w$ $N$-dimensional angiver i dybden $O(w + log(N))$ i stedet for $O(wlog(N))$, hvilket effektivt opnår konstant dybde pr. tilstand. Vi fremhæver flere applikationer, hvor denne evne ville være nyttig, herunder kvantemaskinelæring, Hamilton-simulering og løsning af lineære ligningssystemer. Vi leverer kvantekredsløbsbeskrivelser af vores protokol, detaljerede pseudokode og implementeringseksempler på gateniveau ved hjælp af Braket.

Spacetime-Efficient Low-Depth Quantum State Preparation with Applications PlatoBlockchain Data Intelligence. Vertical Search. Ai.

► BibTeX-data

► Referencer

[1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe og Seth Lloyd. "Kvantemaskinelæring". Nature 549, 195-202 (2017).
https://​/​doi.org/​10.1038/​nature23474

[2] Seth Lloyd, Masoud Mohseni og Patrick Rebentrost. "Quanteprincipal komponentanalyse". Nature Physics 10, 631-633 (2014).
https://doi.org/​10.1038/​nphys3029

[3] Iordanis Kerenidis og Anupam Prakash. "Kvanteanbefalingssystemer". I 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Bind 67 af Leibniz International Proceedings in Informatics (LIPIcs), side 49:1–49:21. (2017).
https://​/​doi.org/​10.4230/​LIPIcs.ITCS.2017.49

[4] Patrick Rebentrost, Adrian Steffens, Iman Marvian og Seth Lloyd. "Quantum singular-value-nedbrydning af ikke-sparsomme lav-rangs matricer". Fysisk anmeldelse A 97, 012327 (2018).
https://​/​doi.org/​10.1103/​PhysRevA.97.012327

[5] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo og Anupam Prakash. "q-betyder: En kvantealgoritme til uovervåget maskinlæring". Fremskridt inden for neurale informationsbehandlingssystemer (2019).
https:/​/​proceedings.neurips.cc/​paper/​2019/​hash/​16026d60ff9b54410b3435b403afd226-Abstract.html

[6] Iordanis Kerenidis og Jonas Landman. "Kvantespektral clustering". Physical Review A 103, 042415 (2021).
https://​/​doi.org/​10.1103/​PhysRevA.103.042415

[7] Patrick Rebentrost, Masoud Mohseni og Seth Lloyd. "Quantum support vektor maskine til big data klassificering". Physical review letters 113, 130503 (2014).
https://​/​doi.org/​10.1103/​PhysRevLett.113.130503

[8] Maria Schuld og Francesco Petruccione. "Maskinlæring med kvantecomputere". Springer. (2021).
https:/​/​doi.org/​10.1007/​978-3-030-83098-4

[9] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari og Rolando D Somma. "Simulering af Hamiltons dynamik med en trunkeret Taylor-serie". Physical review letters 114, 090502 (2015).
https://​/​doi.org/​10.1103/​PhysRevLett.114.090502

[10] Dominic W Berry, Andrew M Childs og Robin Kothari. "Hamiltonsk simulering med næsten optimal afhængighed af alle parametre". I 2015 IEEE 56. årlige symposium om grundlaget for datalogi. Side 792–809. IEEE (2015).
https://​/​doi.org/​10.1109/​FOCS.2015.54

[11] Guang Hao Low og Isaac L Chuang. "Optimal Hamilton-simulering ved kvantesignalbehandling". Physical review letters 118, 010501 (2017).
https://​/​doi.org/​10.1103/​PhysRevLett.118.010501

[12] Guang Hao Low og Isaac L Chuang. "Hamiltonsk simulering ved qubitization". Quantum 3, 163 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[13] Aram W Harrow, Avinatan Hassidim og Seth Lloyd. "Kvantealgoritme for lineære ligningssystemer". Physical review letters 103, 150502 (2009).
https://​/​doi.org/​10.1103/​PhysRevLett.103.150502

[14] Andris Ambainis. "Variabel tidsamplitudeforstærkning og kvantealgoritmer til lineære algebraproblemer". I STACS'12 (29. symposium om teoretiske aspekter af datalogi). Bind 14, side 636–647. LIPIcs (2012).
https://​/​doi.org/​10.4230/​LIPIcs.STACS.2012.636

[15] Leonard Wossnig, Zhikuan Zhao og Anupam Prakash. "Quantelineær systemalgoritme for tætte matricer". Physical review letters 120, 050502 (2018).
https://​/​doi.org/​10.1103/​PhysRevLett.120.050502

[16] Guang Hao Low, Vadym Kliuchnikov og Luke Schaeffer. "Handle T-gates for beskidte qubits i tilstandsforberedelse og enhedssyntese". arXiv.1812.00954 (2018).
https://​/​doi.org/​10.48550/​arXiv.1812.00954

[17] Xiaoming Sun, Guojing Tian, ​​Shuai Yang, Pei Yuan og Shengyu Zhang. "Asymptotisk optimal kredsløbsdybde til forberedelse af kvantetilstand og generel enhedssyntese". IEEE-transaktioner om computerstøttet design af integrerede kredsløb og systemer (2023).
https://​/​doi.org/​10.1109/​TCAD.2023.3244885

[18] Pei Yuan og Shengyu Zhang. "Optimal (kontrolleret) kvantetilstandsforberedelse og forbedret enhedssyntese ved kvantekredsløb med et hvilket som helst antal hjælpequbits". Quantum 7, 956 (2023).
https:/​/​doi.org/​10.22331/​q-2023-03-20-956

[19] Xiao-Ming Zhang, Tongyang Li og Xiao Yuan. "Kvantetilstandsforberedelse med optimal kredsløbsdybde: Implementeringer og applikationer". Physical Review Letters 129, 230504 (2022).
https://​/​doi.org/​10.1103/​PhysRevLett.129.230504

[20] B David Clader, Alexander M Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta og William J Zeng. "Kvanteressourcer, der kræves for at blokere en matrix af klassiske data". IEEE Transactions on Quantum Engineering (2023).
https://​/​doi.org/​10.1109/​TQE.2022.3231194

[21] Gregory Rosenthal. "Forespørgsel og dybde øvre grænser for kvanteenheder via grover-søgning". arXiv.2111.07992 (2021).
https://​/​doi.org/​10.48550/​arXiv.2111.07992

[22] Neil J. Ross og Peter Selinger. "Optimal ancilla-fri Clifford+T tilnærmelse af z-rotationer". Kvante info. Comput. (2016).
https://​/​dl.acm.org/​doi/​10.5555/​3179330.3179331

[23] Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler og Hartmut Neven. "Kodning af elektroniske spektre i kvantekredsløb med lineær T-kompleksitet". Fysisk gennemgang X 8, 041015 (2018).
https://​/​doi.org/​10.1103/​PhysRevX.8.041015

[24] Israel F Araujo, Daniel K Park, Francesco Petruccione og Adenilton J da Silva. "En opdel-og-hersk-algoritme til forberedelse af kvantetilstand". Videnskabelige rapporter 11, 1-12 (2021).
https:/​/​doi.org/​10.1038/​s41598-021-85474-1

[25] Vivek V. Shende og Igor L. Markov. "På CNOT-omkostningerne til TOFFOLI porte". Kvante info. Comput. (2009).
https://​/​dl.acm.org/​doi/​10.5555/​2011791.2011799

[26] John A Smolin og David P DiVincenzo. "Fem to-bit kvanteporte er tilstrækkelige til at implementere kvante-Fredkin-porten". Physical Review A 53, 2855 (1996).
https://​/​doi.org/​10.1103/​PhysRevA.53.2855

[27] Edward Walker. "De reelle omkostninger ved en CPU-time". Computer 42, 35-41 (2009).
https:/​/​doi.org/​10.1109/​MC.2009.135

[28] Yongshan Ding, Xin-Chuan Wu, Adam Holmes, Ash Wiseth, Diana Franklin, Margaret Martonosi og Frederic T Chong. "Square: Strategisk kvanteancilla genbrug til modulære kvanteprogrammer via omkostningseffektiv uncomputation". I 2020 ACM/​IEEE 47th Annual International Symposium on Computer Architecture (ISCA). Side 570–583. IEEE (2020).
https:/​/​doi.org/​10.1109/​ISCA45697.2020.00054

[29] Martin Plesch og Časlav Brukner. "Kvantetilstandsforberedelse med universel portnedbrydning". Phys. Rev. A 83, 032302 (2011).
https://​/​doi.org/​10.1103/​PhysRevA.83.032302

[30] Xiao-Ming Zhang og Xiao Yuan. "Om kredsløbskompleksitet af kvanteadgangsmodeller til kodning af klassiske data". arXiv.2311.11365 (2023).
https://​/​doi.org/​10.48550/​arXiv.2311.11365

[31] Michael A Nielsen og Isaac Chuang. "Kvanteberegning og kvanteinformation". American Association of Physics Teachers. (2002).
https://​/​doi.org/​10.1017/​CBO9780511976667

[32] Sebastian Ruder. "Et overblik over algoritmer til optimering af gradientnedstigning". arXiv.1609.04747 (2016).
https://​/​doi.org/​10.48550/​arXiv.1609.04747

[33] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross og Yuan Su. "Mod den første kvantesimulering med kvantehastighed". Proceedings of the National Academy of Sciences 115, 9456–9461 (2018).
https://​/​doi.org/​10.1073/​pnas.1801723115

[34] Shantanav Chakraborty, András Gilyén og Stacey Jeffery. "Kraften ved blokkodede matrixkræfter: Forbedrede regressionsteknikker via hurtigere Hamilton-simulering". I Proceedings of the 46th International Colloquium on Automata, Languages ​​and Programming (ICALP). Side 33:1–33:14. (2019).
https://​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.33

[35] András Gilyén, Yuan Su, Guang Hao Low og Nathan Wiebe. "Kvante singular værditransformation og videre: Eksponentielle forbedringer for kvantematrixaritmetik". I Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC). Side 193–204. (2019).
https://​/​doi.org/​10.1145/​3313276.3316366

[36] Trygve Helgaker, Poul Jørgensen og Jeppe Olsen. "Molekylær elektronisk strukturteori". John Wiley & sønner. (2013).
https://​/​doi.org/​10.1002/​9781119019572

[37] Mario Motta, Tanvi P Gujarati, Julia E Rice, Ashutosh Kumar, Conner Masteran, Joseph A Latone, Eunseok Lee, Edward F Valeev og Tyler Y Takeshita. "Kvantesimulering af elektronisk struktur med en transkorreleret Hamiltonian: forbedret nøjagtighed med et mindre fodaftryk på kvantecomputeren". Physical Chemistry Chemical Physics 22, 24270–24281 (2020).
https:/​/​doi.org/​10.1039/​D0CP04106H

[38] Sam McArdle og David P Tew. "Forbedring af nøjagtigheden af ​​kvanteberegningskemi ved hjælp af den transkorrelerede metode". arXiv.2006.11181 (2020).
https://​/​doi.org/​10.48550/​arXiv.2006.11181

[39] Sebastien Bubeck, Sitan Chen og Jerry Li. "Entanglement er nødvendigt for optimal kvanteegenskabstestning". I 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Side 692–703. IEEE (2020).
https://​/​doi.org/​10.1109/​FOCS46700.2020.00070

[40] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang og Jerry Li. "Eksponentielle adskillelser mellem læring med og uden kvantehukommelse". I 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Side 574–585. IEEE (2022).
https://​/​doi.org/​10.1109/​FOCS52979.2021.00063

[41] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. "Kvantefordel ved at lære af eksperimenter". Science 376, 1182-1186 (2022).
https://​doi.org/​10.1126/​science.abn7293

[42] Jonathan Richard Shewchuk et al. "En introduktion til konjugatgradientmetoden uden den smertefulde smerte". 1994 Teknisk rapport (1994).
https://​/​dl.acm.org/​doi/​10.5555/​865018

[43] Ashley Montanaro og Sam Pallister. "Kvantealgoritmer og finite element-metoden". Fysisk anmeldelse A 93, 032324 (2016).
https://​/​doi.org/​10.1103/​PhysRevA.93.032324

[44] Ashley Montanaro og Changpeng Shao. "Kvantekommunikationskompleksitet af lineær regression". ACM Trans. Comput. Teori (2023).
https://​/​doi.org/​10.1145/​3625225

[45] Yiğit Subaşi, Rolando D. Somma og Davide Orsucci. "Kvantealgoritmer til systemer af lineære ligninger inspireret af adiabatisk kvanteberegning". Phys. Rev. Lett. 122, 060504 (2019).
https://​/​doi.org/​10.1103/​PhysRevLett.122.060504

[46] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush og Dominic W Berry. "Optimal skalering af kvante-lineære systemløsninger via diskret adiabatisk sætning". PRX Quantum 3, 040303 (2022).
https://​/​doi.org/​10.1103/​PRXQuantum.3.040303

[47] John M. Martyn, Zane M. Rossi, Andrew K. Tan og Isaac L. Chuang. "Store forening af kvantealgoritmer". PRX Quantum 2, 040203 (2021).
https://​/​doi.org/​10.1017/​CBO9780511976667

[48] Craig Gidney. "Quirk: En træk-og-slip kvantekredsløbssimulator". https://​/​algassert.com/​quirk (2016).
https://​/​algassert.com/​quirk

[49] Alexander M Dalzell, B David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A Bader, Nikitas Stamatopoulos, Martin JA Schuetz, Fernando GSL Brandão, Helmut G Katzgraber, et al. "End-to-end ressourceanalyse til kvanteinteriørpunkt-metoder og porteføljeoptimering". PRX Quantum 4, 040325 (2023).
https://​/​doi.org/​10.1103/​PRXQuantum.4.040325

Citeret af

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang og Fernando GSL Brandão, "Quantealgoritmer: En undersøgelse af applikationer og end-to-end kompleksiteter", arXiv: 2310.03011, (2023).

[2] Raghav Jumade og Nicolas PD Sawaya, "Data kan ofte indlæses i kort dybde: Kvantekredsløb fra tensornetværk til finansiering, billeder, væsker og proteiner", arXiv: 2309.13108, (2023).

[3] Gideon Lee, Connor T. Hann, Shruti Puri, SM Girvin og Liang Jiang, "Fejlundertrykkelse for kvanteoperationer i vilkårlig størrelse af Black Box", Physical Review Letters 131 19, 190601 (2023).

[4] Gregory Rosenthal, "Effektiv kvantetilstandssyntese med én forespørgsel", arXiv: 2306.01723, (2023).

[5] Xiao-Ming Zhang og Xiao Yuan, "Om kredsløbskompleksitet af kvanteadgangsmodeller til kodning af klassiske data", arXiv: 2311.11365, (2023).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2024-02-15 15:17:11). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

Kunne ikke hente Crossref citeret af data under sidste forsøg 2024-02-15 15:17:09: Kunne ikke hente citerede data for 10.22331/q-2024-02-15-1257 fra Crossref. Dette er normalt, hvis DOI blev registreret for nylig.

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