Beschleunigung von Quantenalgorithmen durch Vorberechnung

Neuauflage von Plato

Verfolger: 0

Beschleunigung von Quantenalgorithmen mit Precomputation PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

William J. Huggins und Jarrod R. McClean

Google Quantum AI, Venice, CA, USA

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Reale Computeranwendungen können äußerst zeitkritisch sein. Es wäre wertvoll, wenn wir solche Aufgaben beschleunigen könnten, indem wir einen Teil der Arbeit im Voraus erledigen. Aus diesem Grund schlagen wir ein Kostenmodell für Quantenalgorithmen vor, das eine Quantenvorberechnung ermöglicht; dh für eine polynomiale Menge „freier“ Berechnungen, bevor die Eingabe in einen Algorithmus vollständig spezifiziert ist, und Methoden, um diese zu nutzen. Wir analysieren zwei Familien von Unitären, die in diesem Kostenmodell asymptotisch effizienter zu implementieren sind als im Standardmodell. Das erste Beispiel einer Quantenvorberechnung, die auf der Potenzierung der Dichtematrix basiert, könnte unter bestimmten Bedingungen einen exponentiellen Vorteil bieten. Das zweite Beispiel nutzt eine Variante der Gate-Teleportation, um einen quadratischen Vorteil im Vergleich zur direkten Implementierung der Unitaries zu erzielen. Diese Beispiele deuten darauf hin, dass die Quantenvorberechnung einen neuen Bereich für die Suche nach Quantenvorteilen bieten könnte.

► BibTeX-Daten

@article{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, Titel = {Accelerating { Q}uantum {A}algorithms with {P}recomputation}, Autor = {Huggins, William J. und McClean, Jarrod R.}, Zeitschrift = {{Quantum}}, issn = {2521-327X}, Herausgeber = {{ Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften}}, Band = {8}, Seiten = {1264}, Monat = Februar, Jahr = {2024} }

► Referenzen

[1] S Aaronson. Einschränkungen der Quantenberatung und der einseitigen Kommunikation. Im Verfahren. 19. IEEE-Jahreskonferenz zu Computational Complexity, 2004, Seiten 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scott Aaronson und Andris Ambainis. Forrelation. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC '307, Seiten 316–14, New York, NY, USA, 2015. Juni 9781450335362. ACM. ISBN 10.1145. 2746539.2746547/XNUMX.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Scott Aaronson und Guy N. Rothblum. Sanfte Messung von Quantenzuständen und differenzieller Privatsphäre. 18. April 2019. URL http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo und Hartmut Neven. Konzentrieren Sie sich über quadratische Beschleunigungen hinaus auf fehlerkorrigierte Quantenvorteile. PRX Quantum, 2 (1): 010103, 29. März 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniel J. Bernstein und Tanja Lange. Ungleichmäßige Risse im Beton: Die Kraft der freien Vorberechnung. In Advances in Cryptology – ASIACRYPT 2013, Vorlesungsskript in Informatik, Seiten 321–340. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. ISBN 9783642420443,9783642420450. 10.1007/978-3-642-42045-0_17.
https://doi.org/10.1007/978-3-642-42045-0_17

[6] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean und Ryan Babbush. Qubitisierung der Quantenchemie auf willkürlicher Basis unter Nutzung von Sparsity und Low-Rank-Faktorisierung. 6. Februar 2019. URL https:///doi.org/10.22331/q-2019-12-02-208.
https://doi.org/10.22331/q-2019-12-02-208

[7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe und Seth Lloyd. Quantenmaschinelles Lernen. Nature, 549 (7671): 195–202, September 2017. ISSN 0028-0836,1476-4687. 10.1038/natur23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Sergey Bravyi und Alexei Kitaev. Universelle Quantenberechnung mit idealen Clifford-Gattern und verrauschten Ancillas. Physik. Rev. A, 71 (2): 022316, 22. Februar 2005. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Sergey Bravyi und Dmitri Maslov. Hadamard-freie Schaltkreise legen die Struktur der Clifford-Gruppe offen. IEEE Trans. Inf. Theory, 67 (7): 4546–4563, Juli 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Earl T. Campbell und Joe O'Gorman. Ein effizienter magischer Zustandsansatz für Drehungen um kleine Winkel. 14. März 2016. URL https:///doi.org/10.1088/2058-9565/1/1/015007.
https://doi.org/10.1088/2058-9565/1/1/015007

[11] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang und Jerry Li. Exponentielle Unterschiede zwischen Lernen mit und ohne Quantengedächtnis. Im Jahr 2021 findet das 62. IEEE-Jahressymposium zu Grundlagen der Informatik (FOCS) statt. IEEE, Februar 2022. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Andrew M. Childs, Robin Kothari und Rolando D. Somma. Quantenalgorithmus für lineare Gleichungssysteme mit exponentiell verbesserter Genauigkeitsabhängigkeit. SIAM J. Comput., 46 (6): 1920–1950, 1. Januar 2017. ISSN 0097-5397. 10.1137/16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[13] N. Cody Jones, James D. Whitfield, Peter L. McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik und Yoshihisa Yamamoto. Schnellere Simulation der Quantenchemie auf fehlertoleranten Quantencomputern. New J. Phys., 14 (11): 115023, 27. November 2012. ISSN 1367-2630. 10.1088/1367-2630/14/11/115023.
https://doi.org/10.1088/1367-2630/14/11/115023

[14] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush und Dominic W Berry. Optimaler Skalierungslöser für quantenlineare Systeme mittels diskretem adiabatischem Theorem. PRX Quantum, 3 (4): 040303, 7. Oktober 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang und Jarrod R. McClean. Überprüfung der Dequantisierung und des Quantenvorteils bei Lernaufgaben. 1. Dezember 2021. URL http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman und Anirudh Krishna. Diagonale Tore in der Clifford-Hierarchie. Physik. Rev. A, 95 (1), 26. Januar 2017. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone und Sam Gutmann. Ein Quantennäherungsoptimierungsalgorithmus. 14. November 2014. URL http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[18] Austin G. Fowler. Zeitoptimale Quantenberechnung. 17. Oktober 2012. URL http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian und François Le Gall. Dequantisierung der Quanten-Singulärwerttransformation: Härte und Anwendungen in der Quantenchemie und der Quanten-PCP-Vermutung. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, Seiten 19–32, New York, NY, USA, 9. Juni 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Craig Gidney und Martin Ekerå. So faktorisieren Sie 2048-Bit-RSA-Ganzzahlen in 8 Stunden unter Verwendung von 20 Millionen verrauschten Qubits. Quantum, 5 (433): 433, 15. April 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Craig Gidney und Austin G Fowler. Flexibles Layout von Oberflächencodeberechnungen mithilfe von AutoCCZ-Zuständen. 21. Mai 2019. URL http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

[22] András Gilyén und Alexander Poremba. Verbesserte Quantenalgorithmen zur Genauigkeitsschätzung. 29. März 2022. URL http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman und Isaac L. Chuang. Quantenteleportation ist ein universelles Rechenprinzip. 2. August 1999. URL https:///doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady und Ali Kemal Sinop. Schnelle ungefähre Random-Walker-Segmentierung mithilfe der Eigenvektor-Vorberechnung. In der IEEE-Konferenz 2008 über Computer Vision und Mustererkennung, Seiten 1–8. IEEE, Juni 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

[25] Liebe K Grover. Ein schneller quantenmechanischer Algorithmus für die Datenbanksuche. In Proceedings of the 96th Annual ACM Symposium on Theory of Computing – STOC '96, STOC '212, Seiten 219–1996, New York, New York, USA, 9780897917858. ACM Press. ISBN 10.1145. 237814.237866/XNUMX.
https: / / doi.org/ 10.1145 / 237814.237866

[26] Aram W. Harrow, Avinatan Hassidim und Seth Lloyd. Quantenalgorithmus für lineare Gleichungssysteme. Physik. Rev. Lett., 103 (15): 150502, 9. Oktober 2009. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.103.150502.
https://doi.org/ 10.1103/PhysRevLett.103.150502

[27] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill und Jarrod R McClean. Quantenvorteil beim Lernen aus Experimenten. Science, 376 (6598): 1182–1186, 10. Juni 2022. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https:///doi.org/10.1126/science.abn7293

[28] Cody Jones. Destillationsprotokolle für Fourier-Zustände im Quantencomputing. 12. März 2013. URL http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Ein Quantenvorteil für ein natürliches Streaming-Problem. Im Jahr 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), Seiten 897–908. IEEE, Februar 2022. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Richard M. Karp und Richard J. Lipton. Einige Zusammenhänge zwischen uneinheitlichen und einheitlichen Komplexitätsklassen. In Proceedings of the 80th Annual ACM Symposium on Theory of Computing – STOC '80, STOC '302, Seiten 309–28, New York, New York, USA, 1980. April 9780897910170. ACM Press. ISBN 10.1145. 800141.804678/XNUMX.
https: / / doi.org/ 10.1145 / 800141.804678

[31] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols und Theodore J Yoder. Hamilton-Simulation mit optimaler Probenkomplexität. Npj Quantum Inf., 3 (1): 1–7, 30. März 2017. ISSN 2056-6387,2056-6387. 10.1038/s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7

[32] François Le Gall. Exponentielle Trennung von Quantenkomplexität und klassischer Online-Weltraumkomplexität. In Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '06, Seiten 67–73, New York, NY, USA, 30. Juli 2006. ACM. ISBN 9781595934529. 10.1145/1148109.1148119.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Lin Lin und Yu Tong. Optimale polynombasierte Quanteneigenzustandsfilterung mit Anwendung zur Lösung quantenlinearer Systeme. Quantum, 4 (361): 361, 11. November 2020. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

[34] Daniel Litinski. Destillation im magischen Zustand: Nicht so teuer, wie Sie denken. Quantum, 3 (205): 205, 2. Dezember 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinski. Ein Spiel mit Oberflächencodes: Quantencomputing im großen Maßstab mit Gitterchirurgie. Quantum, 3 (128): 128, 5. März 2019b. ISSN 2521-327X. 10.22331/q-2019-03-05-128.
https://doi.org/10.22331/q-2019-03-05-128

[36] Seth Lloyd, Masoud Mohseni und Patrick Rebentrost. Quantenhauptkomponentenanalyse. Nat. Phys., 10 (9): 631–633, 27. September 2014. ISSN 1745-2473,1745-2481. 10.1038/nphys3029.
https: / / doi.org/ 10.1038 / nphys3029

[37] John M. Martyn, Zane M. Rossi, Andrew K. Tan und Isaac L. Chuang. Große Vereinheitlichung der Quantenalgorithmen. PRX Quantum, 2 (4): 040203, 3. Dezember 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian und Seth Lloyd. Universeller Quantenemulator. 8. Juni 2016. URL http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

[39] F Motzoi, MP Kaicher und FK Wilhelm. Lineare und logarithmische Zeitzusammensetzungen von Quanten-Vielteilchenoperatoren. Physik. Rev. Lett., 119 (16): 160503, 20. Oktober 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https://doi.org/ 10.1103/PhysRevLett.119.160503

[40] Michael A. Nielsen. Optische Quantenberechnung unter Verwendung von Clusterzuständen. Physik. Rev. Lett., 93 (4): 040503, 23. Juli 2004. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.93.040503.
https://doi.org/ 10.1103/PhysRevLett.93.040503

[41] Bryan O'Gorman, William J. Huggins, Eleanor G. Rieffel und K. Birgitta Whaley. Generalisierte Swap-Netzwerke für kurzfristiges Quantencomputing. 13. Mai 2019. URL http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

[42] Paul Pham und Krysta M Svore. Eine 2D-Nearest-Neighbor-Quantenarchitektur zur Berücksichtigung der polylogarithmischen Tiefe. 27. Juli 2012. URL http:///arxiv.org/abs/1207.6655.
arXiv: 1207.6655

[43] R Raussendorf und HJ Briegel. Ein Einweg-Quantencomputer. Physik. Rev. Lett., 86 (22): 5188–5191, 28. Mai 2001. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.86.5188.
https://doi.org/ 10.1103/PhysRevLett.86.5188

[44] Yuval R. Sanders, Dominic W. Berry, Pedro CS Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven und Ryan Babbush. Zusammenstellung fehlertoleranter Quantenheuristiken für die kombinatorische Optimierung. PRX Quantum, 1 (2): 020312, 9. November 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Dan Shepherd und Michael J. Bremner. Zeitlich unstrukturierte Quantenberechnung. Proz. Mathematik. Physik. Ing. Sci., 465 (2105): 1413–1439, 8. Mai 2009. ISSN 1364-5021,1471-2946. 10.1098/rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

[46] Peter-Pike Sloan, Jan Kautz und John Snyder. Vorberechnete Strahlungsübertragung für Echtzeit-Rendering in dynamischen, niederfrequenten Beleuchtungsumgebungen. In Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '02, Seiten 527–536, New York, NY, USA, 1. Juli 2002. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https: / / doi.org/ 10.1145 / 566570.566612

[47] James E. Smith. Eine Studie über Verzweigungsvorhersagestrategien. In 25 Jahren internationaler Symposien zur Computerarchitektur (ausgewählte Beiträge), ISCA '98, Seiten 202–215, New York, NY, USA, 1. August 1998. ACM. ISBN 9781581130584. 10.1145/285930.285980.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Rolando D Somma und Yiğit Subaşı. Komplexität der Quantenzustandsüberprüfung im Problem linearer Quantensysteme. PRX Quantum, 2 (1): 010315, 27. Januar 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M. Terhal. Quantenfehlerkorrektur für Quantenspeicher. Rev. Mod. Phys., 87 (2): 307–346, 7. April 2015. ISSN 0034-6861,1539-0756. 10.1103/revmodphys.87.307.
https://doi.org/ 10.1103/revmodphys.87.307

[50] Xinlan Zhou, Debbie W. Leung und Isaac L. Chuang. Methodik für den Bau von Quantenlogikgattern. Physik. Rev. A, 62 (5), 18. Oktober 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Zitiert von

[1] Dar Gilboa und Jarrod R. McClean, „Exponentieller Quantenkommunikationsvorteil beim verteilten Lernen“, arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost und Mikel Sanz, „Quantum Approximated Cloning-Assisted Density Matrix Exponentiation“, arXiv: 2311.11751, (2023).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2024, 02:22:13 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2024-02-22 13:13:06: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2024-02-22-1264 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde.

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

SEO-gestützte Content- und PR-Distribution. Holen Sie sich noch heute Verstärkung.
PlatoData.Network Vertikale generative KI. Motiviere dich selbst. Hier zugreifen.
PlatoAiStream. Web3-Intelligenz. Wissen verstärkt. Hier zugreifen.
PlatoESG. Kohlenstoff, CleanTech, Energie, Umwelt, Solar, Abfallwirtschaft. Hier zugreifen.
PlatoHealth. Informationen zu Biotechnologie und klinischen Studien. Hier zugreifen.
Quelle: https://quantum-journal.org/papers/q-2024-02-22-1264/

Zeitstempel: 22. Februar 2024

Zeitstempel: 1. Juni 2023

Beschleunigung von Quantenalgorithmen durch Vorberechnung

Neuauflage von Plato

Abstrakt

► BibTeX-Daten

► Referenzen

Zitiert von

Mehr von Quantenjournal

Perceval: Eine Softwareplattform für diskrete variable photonische Quantencomputer

Universelle Quantenschaltkreise für die Quantenchemie

Effektive versus Floquet-Theorie für den parametrischen Kerr-Oszillator

Schaltkreise von Raum- und Zeitquantenkanälen

Energieerhaltungs- und Fluktuationssatz sind für Quantenarbeit nicht kompatibel

Optimale Kodierung von Oszillatoren in mehrere Oszillatoren

Diskriminierung und Zertifizierung unbekannter Quantenmessungen

Importance Sampling für stochastische Quantensimulationen

Quantum Message-Passing-Algorithmus für optimale und effiziente Dekodierung

Skalierbare und flexible klassische Schattentomographie mit Tensornetzwerken

Über uns

Vertikale Suche & Ai

Plattform

Bleiben Sie in Verbindung

Konto