Spacetime-Efficient Low-Depth Quantum State Preparation With Applications

Republicat de Platon

Urmaritori: 0

Kaiwen Gui^1,2,3, Alexander M. Dalzell⁴, Alessandro Achille⁵, Martin Suchara¹și Frederic T. Chong³

¹Amazon Web Services, WA, SUA
²Pritzker School of Molecular Engineering, Universitatea din Chicago, IL, SUA
³Departamentul de Informatică, Universitatea din Chicago, IL, SUA
⁴AWS Center for Quantum Computing, Pasadena, CA, SUA
⁵AWS AI Labs, Pasadena, CA, SUA

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Propunem o nouă metodă deterministă pentru pregătirea stărilor cuantice arbitrare. Când protocolul nostru este compilat în CNOT și porți arbitrare cu un singur qubit, acesta pregătește o stare $N$-dimensională în profunzime $O(log(N))$ și $textit{alocarea spațiu-timp}$ (o metrică care ține cont de faptul că de multe ori unii qubiți ancilla nu trebuie să fie activi pentru întregul circuit) $O(N)$, care sunt ambele optime. Când este compilat în setul de porți ${mathrm{H,S,T,CNOT}}$, arătăm că necesită mai puține resurse cuantice asimptotic decât metodele anterioare. Mai exact, pregătește o stare arbitrară până la eroarea $epsilon$ cu adâncimea optimă de $O(log(N) + log (1/epsilon))$ și alocarea spațiu-timp $O(Nlog(log(N)/epsilon))$ , îmbunătățind peste $O(log(N)log(log (N)/epsilon))$ și, respectiv, $O(Nlog(N/epsilon))$. Ilustram modul în care alocarea redusă de spațiu-timp a protocolului nostru permite pregătirea rapidă a multor stări disjunctive cu doar supraîncărcare ancilla cu factor constant - $O(N)$ qubiții ancilla sunt reutilizați eficient pentru a pregăti o stare de produs de $w$ $N$-dimensional stări în profunzime $O(w + log(N))$ mai degrabă decât $O(wlog(N))$, realizând în mod efectiv o adâncime constantă per stare. Subliniem mai multe aplicații în care această abilitate ar fi utilă, inclusiv învățarea cuantică a mașinilor, simularea hamiltoniană și rezolvarea sistemelor liniare de ecuații. Oferim descrieri ale circuitelor cuantice ale protocolului nostru, pseudocod detaliat și exemple de implementare la nivel de poartă folosind Braket.

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

► Date BibTeX

@article{Gui2024spacetimeefficient, doi = {10.22331/q-2024-02-15-1257}, url = {https://doi.org/10.22331/q-2024-02-15-1257}, title = {Spacetime-{E}fficient {L}ow-{D}epth {Q}uantum {S}tate {P}reparation with {A}pplications}, author = {Gui, Kaiwen and Dalzell, Alexander M. and Achille, Alessandro and Suchara, Martin and Chong, Frederic T.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1257}, month = feb, year = {2024}<br /> }

► Referințe

[1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe și Seth Lloyd. „Învățare automată cuantică”. Natura 549, 195–202 (2017).
https: / / doi.org/ 10.1038 / nature23474

[2] Seth Lloyd, Masoud Mohseni și Patrick Rebentrost. „Analiză cuantică a componentelor principale”. Fizica naturii 10, 631–633 (2014).
https: / / doi.org/ 10.1038 / nphys3029

[3] Iordanis Kerenidis și Anupam Prakash. „Sisteme de recomandare cuantică”. La a 8-a Conferință Inovații în Informatică Teoretică (ITCS 2017). Volumul 67 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 49:1–49:21. (2017).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49

[4] Patrick Rebentrost, Adrian Steffens, Iman Marvian și Seth Lloyd. „Descompunerea cuantică cu valoare singulară a matricelor de rang scăzut non-sparse”. Revizuire fizică A 97, 012327 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.012327

[5] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo și Anupam Prakash. „q-means: un algoritm cuantic pentru învățarea automată nesupravegheată”. Progrese în sistemele de procesare a informațiilor neuronale (2019).
https://proceedings.neurips.cc/paper/2019/hash/16026d60ff9b54410b3435b403afd226-Abstract.html

[6] Iordanis Kerenidis și Jonas Landman. „Agrupare spectrală cuantică”. Physical Review A 103, 042415 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042415

[7] Patrick Rebentrost, Masoud Mohseni și Seth Lloyd. „Mașină vectorială de suport cuantic pentru clasificarea datelor mari”. Scrisorile de revizuire fizică 113, 130503 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[8] Maria Schuld și Francesco Petruccione. „Învățare automată cu calculatoare cuantice”. Springer. (2021).
https://doi.org/10.1007/978-3-030-83098-4

[9] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari și Rolando D Somma. „Simularea dinamicii hamiltoniene cu o serie Taylor trunchiată”. Scrisorile de revizuire fizică 114, 090502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502

[10] Dominic W Berry, Andrew M Childs și Robin Kothari. „Simulare hamiltoniană cu dependență aproape optimă de toți parametrii”. În 2015, cel de-al 56-lea simpozion anual IEEE despre fundamentele informaticii. Paginile 792–809. IEEE (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54

[11] Guang Hao Low și Isaac L Chuang. „Simulare Hamiltoniană optimă prin procesarea semnalului cuantic”. Scrisorile de revizuire fizică 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[12] Guang Hao Low și Isaac L Chuang. „Simularea hamiltoniană prin qubitizare”. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163

[13] Aram W Harrow, Avinatan Hassidim și Seth Lloyd. „Algoritm cuantic pentru sisteme liniare de ecuații”. Scrisorile de revizuire fizică 103, 150502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[14] Andris Ambainis. „Amplificare cu amplitudine de timp variabilă și algoritmi cuantici pentru probleme de algebră liniară”. În STACS'12 (al 29-lea simpozion privind aspectele teoretice ale informaticii). Volumul 14, paginile 636–647. LIPIcs (2012).
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636

[15] Leonard Wossnig, Zhikuan Zhao și Anupam Prakash. „Algoritm de sistem liniar cuantic pentru matrici dense”. Scrisorile de revizuire fizică 120, 050502 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.120.050502

[16] Guang Hao Low, Vadym Kliuchnikov și Luke Schaeffer. „Tranzacționarea porților T pentru qubiți murdari în pregătirea stării și sinteza unitară”. arXiv.1812.00954 (2018).
https:///doi.org/10.48550/arXiv.1812.00954

[17] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan și Shengyu Zhang. „Adâncimea circuitului optimă asimptotic pentru pregătirea stării cuantice și sinteza unitară generală”. Tranzacții IEEE privind proiectarea asistată de computer a circuitelor și sistemelor integrate (2023).
https: / / doi.org/ 10.1109 / TCAD.2023.3244885

[18] Pei Yuan și Shengyu Zhang. „Pregătirea optimă (controlată) a stării cuantice și sinteza unitară îmbunătățită prin circuite cuantice cu orice număr de qubiți auxiliari”. Quantum 7, 956 (2023).
https://doi.org/10.22331/q-2023-03-20-956

[19] Xiao-Ming Zhang, Tongyang Li și Xiao Yuan. „Pregătirea stării cuantice cu adâncime optimă a circuitului: implementări și aplicații”. 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 și William J Zeng. „Resurse cuantice necesare pentru a codifica în bloc o matrice de date clasice”. Tranzacții IEEE privind inginerie cuantică (2023).
https: / / doi.org/ 10.1109 / TQE.2022.3231194

[21] Gregory Rosenthal. „Interogare și limite superioare de profunzime pentru unitare cuantice prin căutare Grover”. arXiv.2111.07992 (2021).
https:///doi.org/10.48550/arXiv.2111.07992

[22] Neil J. Ross și Peter Selinger. „Aproximația optimă Clifford+T fără ancillare a rotațiilor z”. Informații cuantice. Calculator. (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 și Hartmut Neven. „Codificarea spectrelor electronice în circuite cuantice cu complexitate T liniară”. Physical Review X 8, 041015 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.041015

[24] Israel F Araujo, Daniel K Park, Francesco Petruccione și Adenilton J da Silva. „Un algoritm de împărțire și cucerire pentru pregătirea stării cuantice”. Rapoarte științifice 11, 1–12 (2021).
https://doi.org/10.1038/s41598-021-85474-1

[25] Vivek V. Shende și Igor L. Markov. „Pe CNOT-costul porților TOFFOLI”. Informații cuantice. Calculator. (2009).
https: / / dl.acm.org/ doi / 10.5555 / 2011791.2011799

[26] John A Smolin și David P DiVincenzo. „Cinci porți cuantice de doi biți sunt suficiente pentru a implementa poarta cuantică Fredkin”. Physical Review A 53, 2855 (1996).
https: / / doi.org/ 10.1103 / PhysRevA.53.2855

[27] Edward Walker. „Costul real al unei ore de procesor”. 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 și Frederic T Chong. „Pătrat: reutilizare strategică a ancillarii cuantice pentru programe cuantice modulare prin necalcularea rentabilă”. În 2020, cel de-al 47-lea simpozion internațional anual ACM/IEEE privind arhitectura calculatoarelor (ISCA). Paginile 570–583. IEEE (2020).
https:///doi.org/10.1109/ISCA45697.2020.00054

[29] Martin Plesch și Časlav Brukner. „Pregătire în stare cuantică cu descompunere universală”. Fiz. Rev. A 83, 032302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.032302

[30] Xiao-Ming Zhang și Xiao Yuan. „Despre complexitatea circuitelor modelelor de acces cuantic pentru codificarea datelor clasice”. arXiv.2311.11365 (2023).
https:///doi.org/10.48550/arXiv.2311.11365

[31] Michael A Nielsen și Isaac Chuang. „Calcul cuantic și informații cuantice”. Asociația Americană a Profesorilor de Fizică. (2002).
https: / / doi.org/ 10.1017 / CBO9780511976667

[32] Sebastian Ruder. „O prezentare generală a algoritmilor de optimizare a coborârii gradientului”. arXiv.1609.04747 (2016).
https:///doi.org/10.48550/arXiv.1609.04747

[33] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross și Yuan Su. „Spre prima simulare cuantică cu accelerare cuantică”. 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 și Stacey Jeffery. „Puterea puterilor matricei codificate în bloc: tehnici de regresie îmbunătățite prin simulare hamiltoniană mai rapidă”. În Proceedings of the 46th International Colocvium on Automata, Languages, and Programming (ICALP). Paginile 33:1–33:14. (2019).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33

[35] András Gilyén, Yuan Su, Guang Hao Low și Nathan Wiebe. „Transformarea valorii cuantice singulare și nu numai: îmbunătățiri exponențiale pentru aritmetica matricei cuantice”. În Proceedings of the 51st ACM Symposium on theory of Computing (STOC). Paginile 193–204. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316366

[36] Trygve Helgaker, Poul Jorgensen și Jeppe Olsen. „Teoria structurii electronice moleculare”. John Wiley & Sons. (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 și Tyler Y Takeshita. „Simularea cuantică a structurii electronice cu un hamiltonian transcorelat: precizie îmbunătățită cu o amprentă mai mică pe computerul cuantic”. Physical Chemistry Chemical Physics 22, 24270–24281 (2020).
https:///doi.org/10.1039/D0CP04106H

[38] Sam McArdle și David P Tew. „Îmbunătățirea acurateței chimiei computaționale cuantice folosind metoda transcorelate”. arXiv.2006.11181 (2020).
https:///doi.org/10.48550/arXiv.2006.11181

[39] Sebastien Bubeck, Sitan Chen și Jerry Li. „Entanglementul este necesar pentru testarea optimă a proprietăților cuantice”. În 2020, cel de-al 61-lea simpozion anual IEEE privind fundamentele informaticii (FOCS). Paginile 692–703. IEEE (2020).
https: / / doi.org/ 10.1109 / FOCS46700.2020.00070

[40] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang și Jerry Li. „Separații exponențiale între învățarea cu și fără memorie cuantică”. În 2021, cel de-al 62-lea simpozion anual IEEE privind fundamentele informaticii (FOCS). Paginile 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 și colab. „Avantaj cuantic în învățarea din experimente”. Science 376, 1182–1186 (2022).
https:///doi.org/10.1126/science.abn7293

[42] Jonathan Richard Shewchuk și colab. „O introducere în metoda gradientului conjugat fără durerea agonizantă”. 1994 Raport tehnic (1994).
https: / / dl.acm.org/ doi / 10.5555 / 865018

[43] Ashley Montanaro și Sam Pallister. „Algoritmi cuantici și metoda elementelor finite”. Physical Review A 93, 032324 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032324

[44] Ashley Montanaro și Changpeng Shao. „Complexitatea comunicării cuantice a regresiei liniare”. ACM Trans. Calculator. Teorie (2023).
https: / / doi.org/ 10.1145 / 3625225

[45] Yiğit Subaşi, Rolando D. Somma, and Davide Orsucci. „Algoritmi cuantici pentru sisteme de ecuații liniare inspirate de calculul cuantic adiabatic”. Fiz. 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 și Dominic W Berry. „Rezolvator de sisteme liniare cuantice cu scalare optimă prin teorema adiabatică discretă”. PRX Quantum 3, 040303 (2022).
https: / / doi.org/ 10.1103 / PRXQuantum.3.040303

[47] John M. Martyn, Zane M. Rossi, Andrew K. Tan și Isaac L. Chuang. „Marea unificare a algoritmilor cuantici”. PRX Quantum 2, 040203 (2021).
https: / / doi.org/ 10.1017 / CBO9780511976667

[48] Craig Gidney. „Quirk: Un simulator de circuit cuantic drag-and-drop”. 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 și colab. „Analiză end-to-end a resurselor pentru metode cuantice de punct interior și optimizare a portofoliului”. PRX Quantum 4, 040325 (2023).
https: / / doi.org/ 10.1103 / PRXQuantum.4.040325

Citat de

[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 și Fernando GSL Brandão, „Algoritmi cuantici: un studiu asupra aplicațiilor și complexităților de la capăt la capăt”, arXiv: 2310.03011, (2023).

[2] Raghav Jumade și Nicolas PD Sawaya, „Datele sunt adesea încărcate în profunzime scurtă: circuite cuantice din rețele tensoare pentru finanțe, imagini, fluide și proteine”, arXiv: 2309.13108, (2023).

[3] Gideon Lee, Connor T. Hann, Shruti Puri, SM Girvin și Liang Jiang, „Error Suppression for Arbitrary-Size Black Box Quantum Operations”, Scrisori de revizuire fizică 131 19, 190601 (2023).

[4] Gregory Rosenthal, „Sinteză eficientă a stării cuantice cu o singură interogare”, arXiv: 2306.01723, (2023).

[5] Xiao-Ming Zhang și Xiao Yuan, „Despre complexitatea circuitului modelelor de acces cuantic pentru codificarea datelor clasice”, arXiv: 2311.11365, (2023).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2024-02-15 15:17:11). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

Nu a putut să aducă Date citate încrucișate în ultima încercare 2024-02-15 15:17:09: Nu s-au putut prelua date citate pentru 10.22331 / q-2024-02-15-1257 de la Crossref. Acest lucru este normal dacă DOI a fost înregistrat recent.

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.