Ruimtetijd-efficiënte kwantumtoestandsvoorbereiding op lage diepte met toepassingen

Ruimtetijd-efficiënte kwantumtoestandsvoorbereiding op lage diepte met toepassingen

Tijdstempel: 15 februari 2024 10:13 uur

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

1Amazon Web Services, WA, VS
2Pritzker School of Molecular Engineering, Universiteit van Chicago, IL, VS
3Afdeling Computerwetenschappen, Universiteit van Chicago, IL, VS
4AWS Centrum voor Quantum Computing, Pasadena, CA, VS
5AWS AI Labs, Pasadena, CA, VS

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

We stellen een nieuwe deterministische methode voor voor het voorbereiden van willekeurige kwantumtoestanden. Wanneer ons protocol wordt gecompileerd in CNOT en willekeurige single-qubit-poorten, bereidt het een $N$-dimensionale staat voor in de diepte $O(log(N))$ en $textit{spacetime allocatie}$ (een metriek die rekening houdt met het feit dat sommige ancilla-qubits vaak niet actief hoeven te zijn voor het hele circuit) $O(N)$, die beide optimaal zijn. Wanneer gecompileerd in de ${mathrm{H,S,T,CNOT}}$ poortset, laten we zien dat er asymptotisch minder kwantumbronnen voor nodig zijn dan eerdere methoden. Concreet bereidt het een willekeurige toestand voor tot fout $epsilon$ met een optimale diepte van $O(log(N) + log (1/epsilon))$ en ruimtetijdtoewijzing $O(Nlog(log(N)/epsilon))$ , een verbetering ten opzichte van respectievelijk $O(log(N)log(log (N)/epsilon))$ en $O(Nlog(N/epsilon))$. We illustreren hoe de verminderde toewijzing van ruimtetijd van ons protocol een snelle voorbereiding van veel disjuncte toestanden mogelijk maakt met alleen ancilla overhead met een constante factor – $O(N)$ ancilla qubits worden efficiënt hergebruikt om een ​​productstatus van $w$ $N$-dimensionaal voor te bereiden staten in de diepte $O(w + log(N))$ in plaats van $O(wlog(N))$, waardoor feitelijk een constante diepte per staat wordt bereikt. We belichten verschillende toepassingen waarbij dit vermogen nuttig zou kunnen zijn, waaronder quantum machine learning, Hamiltoniaanse simulatie en het oplossen van lineaire stelsels van vergelijkingen. We bieden kwantumcircuitbeschrijvingen van ons protocol, gedetailleerde pseudocode en implementatievoorbeelden op poortniveau met behulp van Braket.

Ruimtetijd-efficiënte kwantumstatusvoorbereiding op lage diepte met toepassingen PlatoBlockchain Data Intelligence. Verticaal zoeken. Ai.

► BibTeX-gegevens

► Referenties

[1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe en Seth Lloyd. "Kwantummachine learning". Natuur 549, 195-202 (2017).
https: / / doi.org/ 10.1038 / nature23474

[2] Seth Lloyd, Masoud Mohseni en Patrick Rebentrost. "Quantum hoofdcomponentenanalyse". Natuurfysica 10, 631-633 (2014).
https: / / doi.org/ 10.1038 / nphys3029

[3] Iordanis Kerenidis en Anupam Prakash. "Quantumaanbevelingssystemen". Op de 8e Innovations in Theoretical Computer Science Conference (ITCS 2017). Deel 67 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 49: 1–49:21. (2017).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49

[4] Patrick Rebentrost, Adrian Steffens, Iman Marvian en Seth Lloyd. ‘Kwantum-ontleding van singuliere waarden van niet-schaarse matrices van lage rang’. Fysieke beoordeling A 97, 012327 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.012327

[5] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo en Anupam Prakash. "q-means: een kwantumalgoritme voor machinaal leren zonder toezicht". Vooruitgang in neurale informatieverwerkingssystemen (2019).
https:/​/​proceedings.neurips.cc/​paper/​2019/​hash/​16026d60ff9b54410b3435b403afd226-Abstract.html

[6] Iordanis Kerenidis en Jonas Landman. "Kwantumspectrale clustering". Fysieke beoordeling A 103, 042415 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042415

[7] Patrick Rebentrost, Masoud Mohseni en Seth Lloyd. "Quantum-ondersteuningsvectormachine voor big data-classificatie". Fysieke beoordelingsbrieven 113, 130503 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[8] Maria Schuld en Francesco Petruccione. “Machine learning met kwantumcomputers”. Springer. (2021).
https:/​/​doi.org/​10.1007/​978-3-030-83098-4

[9] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari en Rolando D Somma. "Het simuleren van de Hamiltoniaanse dynamiek met een ingekorte Taylor-reeks". Fysieke beoordelingsbrieven 114, 090502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502

[10] Dominic W Berry, Andrew M Childs en Robin Kothari. "Hamiltoniaanse simulatie met bijna optimale afhankelijkheid van alle parameters". In 2015 IEEE 56e jaarlijkse symposium over de fundamenten van de informatica. Pagina's 792–809. IEEE (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54

[11] Guang Hao Low en Isaac L Chuang. "Optimale Hamiltoniaanse simulatie door kwantumsignaalverwerking". Fysieke beoordelingsbrieven 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[12] Guang Hao Low en Isaac L Chuang. "Hamiltoniaanse simulatie door qubitization". Kwantum 3, 163 (2019).
https:/​/​doi.org/​10.22331/​q-2019-07-12-163

[13] Aram W Harrow, Avinatan Hassidim en Seth Lloyd. "Quantum-algoritme voor lineaire stelsels van vergelijkingen". Fysieke beoordelingsbrieven 103, 150502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[14] Andris Ambainis. "Variabele tijdamplitudeversterking en kwantumalgoritmen voor lineaire algebra-problemen". In STACS'12 (29e symposium over theoretische aspecten van computerwetenschappen). Deel 14, pagina's 636–647. LIPIcs (2012).
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636

[15] Leonard Wossnig, Zhikuan Zhao en Anupam Prakash. ‘Kwantumlineair systeemalgoritme voor dichte matrices’. Fysieke beoordelingsbrieven 120, 050502 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.120.050502

[16] Guang Hao Low, Vadym Kliuchnikov en Luke Schaeffer. "T-poorten ruilen voor vuile qubits bij staatsvoorbereiding en unitaire synthese". arXiv.1812.00954 (2018).
https:/​/​doi.org/​10.48550/​arXiv.1812.00954

[17] Xiaoming Sun, Guojing Tian, ​​Shuai Yang, Pei Yuan en Shengyu Zhang. "Asymptotisch optimale circuitdiepte voor voorbereiding van kwantumtoestanden en algemene unitaire synthese". IEEE-transacties over computerondersteund ontwerp van geïntegreerde schakelingen en systemen (2023).
https: / / doi.org/ 10.1109 / TCAD.2023.3244885

[18] Pei Yuan en Shengyu Zhang. "Optimale (gecontroleerde) voorbereiding van de kwantumtoestand en verbeterde unitaire synthese door kwantumcircuits met een willekeurig aantal ondersteunende qubits". Kwantum 7, 956 (2023).
https:/​/​doi.org/​10.22331/​q-2023-03-20-956

[19] Xiao-Ming Zhang, Tongyang Li en Xiao Yuan. "Kwantumtoestandsvoorbereiding met optimale circuitdiepte: implementaties en toepassingen". Fysieke beoordelingsbrieven 129, 230504 (2022).
https: / / doi.org/ 10.1103 / PhysRevLett.129.230504

[20] B David Clader, Alexander M Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta en William J Zeng. "Kwantumbronnen die nodig zijn om een ​​matrix van klassieke gegevens te blokcoderen". IEEE-transacties over kwantumtechniek (2023).
https: / / doi.org/ 10.1109 / TQE.2022.3231194

[21] Gregorius Rosenthal. "Bovengrenzen voor zoekopdrachten en diepte voor kwantumunits via grover-zoekopdrachten". arXiv.2111.07992 (2021).
https:/​/​doi.org/​10.48550/​arXiv.2111.07992

[22] Neil J. Ross en Peter Selinger. "Optimale ancilla-vrije Clifford + T-benadering van z-rotaties". Kwantuminformatie. Computer. (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 en Hartmut Neven. ‘Elektronische spectra coderen in kwantumcircuits met lineaire T-complexiteit’. Fysieke beoordeling X 8, 041015 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.041015

[24] Israel F Araujo, Daniel K Park, Francesco Petruccione en Adenilton J da Silva. "Een verdeel-en-heers-algoritme voor de voorbereiding van kwantumtoestanden". Wetenschappelijke rapporten 11, 1–12 (2021).
https:/​/​doi.org/​10.1038/​s41598-021-85474-1

[25] Vivek V. Shende en Igor L. Markov. “Op de CNOT-kosten van TOFFOLI-poorten”. Kwantuminformatie. Computer. (2009).
https: / / dl.acm.org/ doi / 10.5555 / 2011791.2011799

[26] John A Smolin en David P DiVincenzo. “Vijf twee-bit kwantumpoorten zijn voldoende om de kwantum Fredkin-poort te implementeren”. Fysieke recensie A 53, 2855 (1996).
https: / / doi.org/ 10.1103 / PhysRevA.53.2855

[27] Edward Walker. "De werkelijke kosten van een CPU-uur". 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 en Frederic T Chong. "Square: Strategisch quantum-ancilla-hergebruik voor modulaire quantumprogramma's via kosteneffectieve uncomputation". In 2020 ACM/​IEEE 47e jaarlijkse internationale symposium over computerarchitectuur (ISCA). Pagina's 570-583. IEEE (2020).
https:/​/​doi.org/10.1109/​ISCA45697.2020.00054

[29] Martin Plesch en Caslav Brukner. "Kwantumtoestandvoorbereiding met universele poortontbindingen". Fysiek. Rev A 83, 032302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.032302

[30] Xiao-Ming Zhang en Xiao Yuan. "Over de circuitcomplexiteit van kwantumtoegangsmodellen voor het coderen van klassieke gegevens". arXiv.2311.11365 (2023).
https:/​/​doi.org/​10.48550/​arXiv.2311.11365

[31] Michael A Nielsen en Isaac Chuang. "Kwantumberekening en kwantuminformatie". American Association of Physics Teachers. (2002).
https: / / doi.org/ 10.1017 / CBO9780511976667

[32] Sebastiaan Ruder. "Een overzicht van algoritmen voor optimalisatie van gradiëntdaling". arXiv.1609.04747 (2016).
https:/​/​doi.org/​10.48550/​arXiv.1609.04747

[33] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross en Yuan Su. "Op weg naar de eerste kwantumsimulatie met kwantumversnelling". Proceedings van de National Academy of Sciences 115, 9456-9461 (2018).
https: / / doi.org/ 10.1073 / pnas.1801723115

[34] Shantanav Chakraborty, András Gilyén en Stacey Jeffery. "De kracht van blokgecodeerde matrixkrachten: verbeterde regressietechnieken via snellere Hamiltoniaanse simulatie". In Proceedings van het 46e Internationale Colloquium over Automaten, Talen en Programmeren (ICALP). Pagina's 33:1–33:14. (2019).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33

[35] András Gilyén, Yuan Su, Guang Hao Low en Nathan Wiebe. "Kwantumtransformatie van singuliere waarden en verder: exponentiële verbeteringen voor kwantummatrixberekeningen". In Proceedings van het 51e ACM-symposium over de theorie van computergebruik (STOC). Pagina's 193–204. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316366

[36] Trygve Helgaker, Poul Jorgensen en Jeppe Olsen. "Moleculaire elektronische structuurtheorie". John Wiley & zonen. (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 en Tyler Y Takeshita. "Kwantumsimulatie van elektronische structuur met een getranscorreleerde Hamiltoniaan: verbeterde nauwkeurigheid met een kleinere voetafdruk op de kwantumcomputer". Fysische chemie Chemische fysica 22, 24270–24281 (2020).
https://​/​doi.org/​10.1039/​D0CP04106H

[38] Sam McArdle en David P. Tew. "Het verbeteren van de nauwkeurigheid van kwantumcomputerchemie met behulp van de transcorrelerende methode". arXiv.2006.11181 (2020).
https:/​/​doi.org/​10.48550/​arXiv.2006.11181

[39] Sebastien Bubeck, Sitan Chen en Jerry Li. “Verstrengeling is noodzakelijk voor het optimaal testen van kwantumeigenschappen”. In 2020 IEEE 61e jaarlijkse symposium over de fundamenten van de computerwetenschappen (FOCS). Pagina's 692–703. IEEE (2020).
https:/​/​doi.org/10.1109/​FOCS46700.2020.00070

[40] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang en Jerry Li. ‘Exponentiële scheidingen tussen leren met en zonder kwantumgeheugen’. In 2021 IEEE 62e jaarlijkse symposium over de grondslagen van computerwetenschappen (FOCS). Pagina's 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. "Kwantumvoordeel bij het leren van experimenten". Wetenschap 376, 1182-1186 (2022).
https://​/​doi.org/​10.1126/​science.abn7293

[42] Jonathan Richard Shewchuk et al. “Een inleiding tot de conjugaatgradiëntmethode zonder de pijnlijke pijn”. Technisch rapport 1994 (1994).
https: / / dl.acm.org/ doi / 10.5555 / 865018

[43] Ashley Montanaro en Sam Pallister. "Kwantumalgoritmen en de eindige elementenmethode". Fysieke beoordeling A 93, 032324 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032324

[44] Ashley Montanaro en Changpeng Shao. ‘Kwantumcommunicatiecomplexiteit van lineaire regressie’. ACM Trans. Computer. Theorie (2023).
https: / / doi.org/ 10.1145 / 3625225

[45] Yiğit Subaşi, Rolando D. Somma en Davide Orsucci. “Kwantumalgoritmen voor systemen van lineaire vergelijkingen geïnspireerd door adiabatische kwantumcomputers”. Fys. Ds. 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 en Dominic W Berry. "Oplosser voor kwantumlineaire systemen op optimale schaal via discrete adiabatische stelling". PRX Quantum 3, 040303 (2022).
https: / / doi.org/ 10.1103 / PRXQuantum.3.040303

[47] John M. Martyn, Zane M. Rossi, Andrew K. Tan en Isaac L. Chuang. "Grote unificatie van kwantumalgoritmen". PRX Quantum 2, 040203 (2021).
https: / / doi.org/ 10.1017 / CBO9780511976667

[48] Craig Gidney. "Quirk: een kwantumcircuitsimulator met slepen en neerzetten". 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 resourceanalyse voor kwantuminterieurpuntmethoden en portfolio-optimalisatie". PRX Quantum 4, 040325 (2023).
https: / / doi.org/ 10.1103 / PRXQuantum.4.040325

Geciteerd door

[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 en Fernando GSL Brandão, “Kwantumalgoritmen: een overzicht van applicaties en end-to-end complexiteiten”, arXiv: 2310.03011, (2023).

[2] Raghav Jumade en Nicolas PD Sawaya, "Gegevens kunnen vaak op korte diepte worden geladen: kwantumcircuits van tensornetwerken voor financiën, afbeeldingen, vloeistoffen en eiwitten", arXiv: 2309.13108, (2023).

[3] Gideon Lee, Connor T. Hann, Shruti Puri, SM Girvin en Liang Jiang, “Foutonderdrukking voor Black Box Quantum Operations van willekeurige omvang”, Fysieke beoordelingsbrieven 131 19, 190601 (2023).

[4] Gregory Rosenthal, “Efficiënte Quantum State Synthese met één zoekopdracht”, arXiv: 2306.01723, (2023).

[5] Xiao-Ming Zhang en Xiao Yuan, "Over de circuitcomplexiteit van kwantumtoegangsmodellen voor het coderen van klassieke gegevens", arXiv: 2311.11365, (2023).

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2024-02-15 15:17:11). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2024-02-15 15:17:09: kon niet geciteerde gegevens voor 10.22331 / q-2024-02-15-1257 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.

Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.

Tijdstempel:

Meer van Quantum Journaal