Accélérer les algorithmes quantiques avec le précalcul

Republié par Platon

Suiveurs: 0

Accélérer les algorithmes quantiques avec le précalcul PlatoBlockchain Data Intelligence. Recherche verticale. Aï.

William J. Huggins et Jarrod R. McClean

Google Quantum AI, Venise, Californie, États-Unis

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Les applications informatiques du monde réel peuvent être extrêmement sensibles au facteur temps. Il serait utile que nous puissions accélérer ces tâches en effectuant une partie du travail à l'avance. Motivés par cela, nous proposons un modèle de coût pour les algorithmes quantiques qui permet le précalcul quantique ; c'est-à-dire pour une quantité polynomiale de calcul « libre » avant que l'entrée d'un algorithme ne soit entièrement spécifiée, et les méthodes pour en tirer parti. Nous analysons deux familles d’unitaires asymptotiquement plus efficaces à mettre en œuvre dans ce modèle de coûts que dans le modèle standard. Le premier exemple de précalcul quantique, basé sur l’exponentiation d’une matrice de densité, pourrait offrir un avantage exponentiel sous certaines conditions. Le deuxième exemple utilise une variante de téléportation de porte pour obtenir un avantage quadratique par rapport à la mise en œuvre directe des unitaires. Ces exemples suggèrent que le précalcul quantique pourrait offrir un nouveau domaine dans lequel rechercher un avantage quantique.

► Données BibTeX

@article{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, title = {Accélération { Q}uantum {A}lgorithmes avec {P}recalcul}, auteur = {Huggins, William J. et McClean, Jarrod R.}, journal = {{Quantum}}, issn = {2521-327X}, éditeur = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1264}, mois = février, année = {2024} }

► Références

S Aaronson. Limites des conseils quantiques et de la communication à sens unique. Dans les actes. 19e Conférence annuelle de l'IEEE sur la complexité informatique, 2004, pages 320-332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

Scott Aaronson et Andris Ambainis. Par rapport. Dans Actes du quarante-septième symposium annuel de l'ACM sur la théorie de l'informatique, STOC '15, pages 307-316, New York, NY, États-Unis, 14 juin 2015. ACM. ISBN 9781450335362. 10.1145/2746539.2746547.
https: / / doi.org/ 10.1145 / 2746539.2746547

Scott Aaronson et Guy N Rothblum. Mesure douce des états quantiques et de la confidentialité différentielle. 18 avril 2019. URL http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo et Hartmut Neven. Concentrez-vous au-delà des accélérations quadratiques pour un avantage quantique corrigé des erreurs. Quantique PRX, 2 (1) : 010103, 29 mars 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

Daniel J. Bernstein et Tanja Lange. Fissures non uniformes dans le béton : le pouvoir du précalcul gratuit. Dans Advances in Cryptology – ASIACRYPT 2013, Notes de cours en informatique, pages 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

Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean et Ryan Babbush. Qubitisation de la chimie quantique sur des bases arbitraires en tirant parti de la parcimonie et de la factorisation de bas rang. 6 février 2019. URL https:///doi.org/10.22331/q-2019-12-02-208.
https://doi.org/10.22331/q-2019-12-02-208

Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe et Seth Lloyd. Apprentissage automatique quantique. Nature, 549 (7671) : 195-202, septembre 2017. ISSN 0028-0836,1476, 4687-10.1038. 23474/natureXNUMX.
https: / / doi.org/ 10.1038 / nature23474

Sergueï Bravyi et Alexei Kitaev. Calcul quantique universel avec portes clifford idéales et ancillas bruyantes. Phys. A, 71 (2) : 022316, 22 février 2005. ISSN 1050-2947,1094, 1622-10.1103. 71.022316/physreva.XNUMX.
https: / / doi.org/ 10.1103 / physreva.71.022316

Sergueï Bravyi et Dmitri Maslov. Les circuits sans Hadamard exposent la structure du groupe Clifford. IEEETrans. Inf. Théorie, 67 (7) : 4546-4563, juillet 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

Earl T Campbell et Joe O'Gorman. Une approche efficace de l’état magique pour les rotations à petits angles. 14 mars 2016. URL https:///doi.org/10.1088/2058-9565/1/1/015007.
https://doi.org/10.1088/2058-9565/1/1/015007

Sitan Chen, Jordan Cotler, Hsin-Yuan Huang et Jerry Li. Séparations exponentielles entre l'apprentissage avec et sans mémoire quantique. En 2021, le 62e symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS). IEEE, février 2022. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

Andrew M Childs, Robin Kothari et Rolando D Somma. Algorithme quantique pour systèmes d'équations linéaires avec une dépendance exponentiellement améliorée à la précision. SIAM J. Comput., 46 (6) : 1920-1950, 1er janvier 2017. ISSN 0097-5397. 10.1137/16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik et Yoshihisa Yamamoto. Simulation de chimie quantique plus rapide sur des ordinateurs quantiques tolérants aux pannes. New J. Phys., 14 (11) : 115023, 27 novembre 2012. ISSN 1367-2630. 10.1088/1367-2630/14/11/115023.
https://doi.org/10.1088/1367-2630/14/11/115023

Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush et Dominic W Berry. Solveur de systèmes linéaires quantiques à mise à l'échelle optimale via le théorème adiabatique discret. Quantique PRX, 3 (4) : 040303, 7 octobre 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

Jordan Cotler, Hsin-Yuan Huang et Jarrod R McClean. Revisiter la déquantification et l'avantage quantique dans les tâches d'apprentissage. 1er décembre 2021. URL http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

Shawn X Cui, Daniel Gottesman et Anirudh Krishna. Portes diagonales dans la hiérarchie clifford. Phys. Rév. A, 95 (1), 26 janvier 2017. ISSN 2469-9926,2469, 9934-10.1103. 95.012329/physreva.XNUMX.
https: / / doi.org/ 10.1103 / physreva.95.012329

Edward Farhi, Jeffrey Goldstone et Sam Gutmann. Un algorithme d'optimisation approximative quantique. 14 novembre 2014. URL http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

Austin G Fowler. Calcul quantique optimal en termes de temps. 17 octobre 2012. URL http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

Sevag Gharibian et François Le Gall. Déquantification de la transformation quantique des valeurs singulières : dureté et applications à la chimie quantique et à la conjecture quantique du PCP. Dans Actes du 54e Symposium annuel ACM SIGACT sur la théorie de l'informatique, STOC 2022, pages 19-32, New York, NY, États-Unis, 9 juin 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https: / / doi.org/ 10.1145 / 3519935.3519991

Craig Gidney et Martin Ekerå. Comment factoriser des entiers RSA de 2048 bits en 8 heures en utilisant 20 millions de qubits bruyants. Quantum, 5 (433) : 433, 15 avril 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

Craig Gidney et Austin G Fowler. Disposition flexible des calculs de code de surface à l'aide des états AutoCCZ. 21 mai 2019. URL http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

András Gilyén et Alexander Poremba. Algorithmes quantiques améliorés pour l’estimation de la fidélité. 29 mars 2022. URL http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

Daniel Gottesman et Isaac L Chuang. La téléportation quantique est une primitive informatique universelle. 2 août 1999. URL https://doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / 46503

Léo Grady et Ali Kemal Sinop. Segmentation aléatoire approximative et rapide des marcheurs à l'aide du précalcul de vecteurs propres. Dans la conférence IEEE 2008 sur la vision par ordinateur et la reconnaissance de formes, pages 1 à 8. IEEE, juin 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

Amour K Grover. Un algorithme de mécanique quantique rapide pour la recherche dans des bases de données. Dans Actes du vingt-huitième symposium annuel de l'ACM sur la théorie de l'informatique – STOC '96, STOC '96, pages 212-219, New York, New York, États-Unis, 1996. ACM Press. ISBN9780897917858. 10.1145/237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866

Aram W Harrow, Avinatan Hassidim et Seth Lloyd. Algorithme quantique pour systèmes d'équations linéaires. Phys. Rev. Lett., 103 (15) : 150502, 9 octobre 2009. ISSN 0031-9007,1079, 7114-10.1103. 103.150502/PhysRevLett.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill et Jarrod R McClean. Avantage quantique dans l’apprentissage des expériences. Science, 376 (6598) : 1182-1186, 10 juin 2022. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https:///doi.org/10.1126/science.abn7293

Cody Jones. Protocoles de distillation pour les états de Fourier en informatique quantique. 12 mars 2013. URL http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

John Kallaugher. Un avantage quantique pour un problème de streaming naturel. En 2021, 62e Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS), pages 897-908. IEEE, février 2022. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

Richard M Karp et Richard J Lipton. Quelques connexions entre les classes de complexité non uniformes et uniformes. Dans Actes du douzième symposium annuel de l'ACM sur la théorie de l'informatique – STOC '80, STOC '80, pages 302-309, New York, New York, États-Unis, 28 avril 1980. ACM Press. ISBN9780897910170/10.1145.
https: / / doi.org/ 10.1145 / 800141.804678

Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols et Theodore J Yoder. Simulation hamiltonienne avec une complexité d'échantillon optimale. Npj Quantum Inf., 3 (1) : 1-7, 30 mars 2017. ISSN 2056-6387,2056, 6387-10.1038. 41534/s017-0013-7-XNUMX.
https://doi.org/10.1038/s41534-017-0013-7

François Le Gall. Séparation exponentielle de la complexité quantique et classique de l'espace en ligne. Dans Actes du dix-huitième symposium annuel de l'ACM sur le parallélisme dans les algorithmes et les architectures, SPAA '06, pages 67-73, New York, NY, États-Unis, 30 juillet 2006. ACM. ISBN9781595934529/10.1145.
https: / / doi.org/ 10.1145 / 1148109.1148119

Lin Lin et Yu Tong. Filtrage d'états propres quantiques optimaux basés sur des polynômes avec application à la résolution de systèmes linéaires quantiques. Quantum, 4 (361) : 361, 11 novembre 2020. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

Daniel Litinski. Distillation de l’état magique : pas aussi coûteuse que vous le pensez. Quantum, 3 (205) : 205, 2 décembre 2019a. ISSN2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

Daniel Litinski. Un jeu de codes de surface : informatique quantique à grande échelle avec chirurgie du réseau. Quantum, 3 (128) : 128, 5 mars 2019b. ISSN2521-327X. 10.22331/q-2019-03-05-128.
https://doi.org/10.22331/q-2019-03-05-128

Seth Lloyd, Masoud Mohseni et Patrick Rebentrost. Analyse des composantes principales quantiques. Nat. Phys., 10 (9) : 631-633, 27 septembre 2014. ISSN 1745-2473,1745, 2481-10.1038. 3029/nphysXNUMX.
https: / / doi.org/ 10.1038 / nphys3029

John M Martyn, Zane M Rossi, Andrew K Tan et Isaac L Chuang. Grande unification des algorithmes quantiques. Quantique PRX, 2 (4) : 040203, 3 décembre 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

Iman Marvian et Seth Lloyd. Émulateur quantique universel. 8 juin 2016. URL http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

F Motzoi, député Kaicher et FK Wilhelm. Compositions temporelles linéaires et logarithmiques d'opérateurs quantiques à N corps. Phys. Rev. Lett., 119 (16) : 160503, 20 octobre 2017. ISSN 0031-9007,1079, 7114-10.1103. 119.160503/PhysRevLett.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

Michael A. Nielsen. Calcul quantique optique utilisant les états de cluster. Phys. Rev. Lett., 93 (4) : 040503, 23 juillet 2004. ISSN 0031-9007,1079, 7114-10.1103. 93.040503/PhysRevLett.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.93.040503

Bryan O'Gorman, William J Huggins, Eleanor G Rieffel et K Birgitta Whaley. Réseaux d'échange généralisés pour l'informatique quantique à court terme. 13 mai 2019. URL http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

Paul Pham et Krysta M Svore. Une architecture quantique 2D du plus proche voisin pour prendre en compte la profondeur polylogarithmique. 27 juillet 2012. URL http:///arxiv.org/abs/1207.6655.
arXiv: 1207.6655

R Raussendorf et HJ Briegel. Un ordinateur quantique à sens unique. Phys. Rev. Lett., 86 (22) : 5188-5191, 28 mai 2001. ISSN 0031-9007,1079, 7114-10.1103. 86.5188/PhysRevLett.XNUMX.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

Yuval R Sanders, Dominic W Berry, Pedro CS Costa, Louis W Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven et Ryan Babbush. Compilation d'heuristiques quantiques tolérantes aux pannes pour l'optimisation combinatoire. Quantique PRX, 1 (2) : 020312, 9 novembre 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

Dan Shepherd et Michael J Bremner. Calcul quantique temporellement non structuré. Proc. Mathématiques. Phys. Ing. Sci., 465 (2105) : 1413-1439, 8 mai 2009. ISSN 1364-5021,1471, 2946-10.1098. 2008.0443/rspa.XNUMX.
https: / / doi.org/ 10.1098 / rspa.2008.0443

Peter-Pike Sloan, Jan Kautz et John Snyder. Transfert de rayonnement précalculé pour un rendu en temps réel dans des environnements d'éclairage dynamiques à basse fréquence. Dans Actes de la 29e conférence annuelle sur l'infographie et les techniques interactives, SIGGRAPH '02, pages 527-536, New York, NY, États-Unis, 1er juillet 2002. ACM. ISBN9781581135213/10.1145.
https: / / doi.org/ 10.1145 / 566570.566612

James E Smith. Une étude des stratégies de prédiction de branche. Dans 25 ans de colloques internationaux sur l'architecture informatique (articles sélectionnés), ISCA '98, pages 202-215, New York, NY, États-Unis, 1er août 1998. ACM. ISBN9781581130584/10.1145.
https: / / doi.org/ 10.1145 / 285930.285980

Rolando D. Somma et Yiğit Subaşı. Complexité de la vérification de l'état quantique dans le problème des systèmes linéaires quantiques. Quantique PRX, 2 (1) : 010315, 27 janvier 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

Barbara M. Terhal. Correction d'erreurs quantiques pour les mémoires quantiques. Rév. Mod. Phys., 87 (2) : 307-346, 7 avril 2015. ISSN 0034-6861,1539, 0756-10.1103. 87.307/revmodphys.XNUMX.
https: / / doi.org/ 10.1103 / revmodphys.87.307

Xinlan Zhou, Debbie W Leung et Isaac L Chuang. Méthodologie de construction de portes logiques quantiques. Phys. Rév. A, 62 (5), 18 octobre 2000. ISSN 1050-2947,1094, 1622-10.1103. 62.052316/physreva.XNUMX.
https: / / doi.org/ 10.1103 / physreva.62.052316

Cité par

[1] Dar Gilboa et Jarrod R. McClean, « Avantage de la communication quantique exponentielle dans l'apprentissage distribué », arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost et Mikel Sanz, « Exponentiation matricielle de densité assistée par clonage approximatif quantique », arXiv: 2311.11751, (2023).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2024-02-22 13:13:08). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

Impossible de récupérer Données de référence croisée lors de la dernière tentative 2024-02-22 13:13:06: Impossible de récupérer les données citées par 10.22331 / q-2024-02-22-1264 de Crossref. C'est normal si le DOI a été enregistré récemment.

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
PlatoData.Network Ai générative verticale. Autonomisez-vous. Accéder ici.
PlatoAiStream. Intelligence Web3. Connaissance Amplifiée. Accéder ici.
PlatonESG. Carbone, Technologie propre, Énergie, Environnement, Solaire, La gestion des déchets. Accéder ici.
PlatoHealth. Veille biotechnologique et essais cliniques. Accéder ici.
La source: https://quantum-journal.org/papers/q-2024-02-22-1264/

Horodatage: 22 février 2024

Horodatage: Le 1 juin 2023

Accélérer les algorithmes quantiques avec le précalcul

Republié par Platon

Abstract

► Données BibTeX

► Références

Cité par

Plus de Journal quantique

Perceval : une plate-forme logicielle pour le calcul quantique photonique à variables discrètes

Circuits quantiques universels pour la chimie quantique

Théorie efficace versus Floquet pour l'oscillateur paramétrique Kerr

Circuits de canaux quantiques spatiaux et temporels

La conservation de l'énergie et le théorème de fluctuation sont incompatibles avec le travail quantique

Encodage optimal des oscillateurs dans plus d'oscillateurs

Discrimination et certification des mesures quantiques inconnues

Échantillonnage d'importance pour les simulations quantiques stochastiques

Algorithme de passage de message quantique pour un décodage optimal et efficace

Tomographie d'ombre classique évolutive et flexible avec réseaux de tenseurs

À propos de nous

Recherche verticale et Ai

Plateforme

Restez à l'affût

Compte