Patrick Rall
Centre d'information quantique, Université du Texas à Austin
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
Nous envisageons d'effectuer une estimation de phase dans les conditions suivantes : on ne nous donne qu'une seule copie de l'état d'entrée, l'état d'entrée n'a pas besoin d'être un état propre de l'unitaire, et l'état ne doit pas être mesuré. La plupart des algorithmes d'estimation quantique font des hypothèses qui les rendent inadaptés à ce cadre « cohérent », ne laissant que l'approche du manuel. Nous présentons de nouveaux algorithmes pour l'estimation de phase, d'énergie et d'amplitude qui sont à la fois conceptuellement et informatiquement plus simples que la méthode des manuels, présentant à la fois une complexité de requête et une empreinte ancillaires plus petites. Ils ne nécessitent pas de transformée de Fourier quantique, et ils ne nécessitent pas de réseau de tri quantique pour calculer la médiane de plusieurs estimations. Au lieu de cela, ils utilisent des techniques de codage par blocs pour calculer l'estimation un bit à la fois, effectuant toute l'amplification via une transformation de valeur singulière. Ces sous-programmes améliorés accélèrent les performances de l'échantillonnage quantique Metropolis et de l'inférence bayésienne quantique.
Image vedette : Nous présentons un nouvel algorithme pour l'estimation de l'énergie qui calcule l'estimation un bit à la fois. Chaque bit est extrait via un polynôme qui est appliqué à l'hamiltonien via une transformation en valeur singulière. L'image montre des approximations polynomiales de cosinus qui sont post-traitées pour approximer les ondes carrées qui indiquent les bits.
Présentation au TQC 2021
Résumé populaire
► Données BibTeX
► Références
[1] Pawel Wocjan, Kristan Temme, Unités de marche Szegedy pour cartes quantiques arXiv :2107.07365 (2021).
arXiv: 2107.07365
[2] John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang, Une grande unification des algorithmes quantiques arXiv:2105.02859 (2021).
arXiv: 2105.02859
[3] Lin Lin, Yu Tong, Estimation de l'énergie de l'état fondamental limitée par Heisenberg pour les premiers ordinateurs quantiques tolérants aux pannes arXiv: 2102.11340 (2021).
arXiv: 2102.11340
[4] Earl T. Campbell, Premières simulations tolérantes aux pannes du modèle Hubbard arXiv:2012.09238 (2020).
arXiv: 2012.09238
[5] Yuan Su, Hsin-Yuan Huang, Earl T. Campbell, Trotterisation presque serrée des électrons en interaction arXiv:2012.09194 Quantum 5, 495 (2020).
https://doi.org/10.22331/q-2021-07-05-495
arXiv: 2012.09194
[6] Alexander Engel, Graeme Smith, Scott E. Parker, Un cadre pour appliquer le calcul quantique aux systèmes dynamiques non linéaires arXiv:2012.06681 Physics of Plasmas 28, 062305 (2020).
https: / / doi.org/ 10.1063 / 5.0040313
arXiv: 2012.06681
[7] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, Jiasu Wang, Méthodes de Monte Carlo multiniveaux accélérées quantiques pour les équations différentielles stochastiques en finance mathématique arXiv:2012.06283 Quantum 5, 481 (2020).
https://doi.org/10.22331/q-2021-06-24-481
arXiv: 2012.06283
[8] Isaac Chuang, Grande unification des algorithmes quantiques. Présentation du séminaire à IQC Waterloo. (2020).
https:///uwaterloo.ca/institute-for-quantum-computing/events/grand-unification-quantum-algorithms
[9] Lewis Wright, Fergus Barratt, James Dborin, George H. Booth, Andrew G. Green, Post-sélection automatique par Ancillae Thermalisation arXiv:2010.04173 Phys. Rev.Recherche 3, 033151 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033151
arXiv: 2010.04173
[10] Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, Pawel Wocjan, Algorithmes plus simples (classiques) et plus rapides (quantiques) pour les fonctions de partition de Gibbs arXiv:2009.11270 (2020).
arXiv: 2009.11270
[11] András Gilyén, Zhao Song, Ewin Tang, Un algorithme amélioré d'inspiration quantique pour la régression linéaire arXiv:2009.07268 (2020).
arXiv: 2009.07268
[12] Phillip WK Jensen, Lasse Bjørn Kristensen, Jakob S. Kottmann, Alán Aspuru-Guzik, Calcul quantique des valeurs propres dans les intervalles cibles Quantum Science and Technology 6, 015004 arXiv:2005.13434 (2020).
https:///doi.org/10.1088/2058-9565/abc096
arXiv: 2005.13434
[13] Patrick Rall, Quantum Algorithms for Estimating Physical Quantities using Block-Encodings Phys. Rév. A 102, 022408 arXiv:2004.06832 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022408
arXiv: 2004.06832
[14] Alessandro Roggero, Estimation de la densité spectrale avec la transformée intégrale gaussienne Phys. Rév. A 102, 022409 arXiv:2004.04889 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022409
arXiv: 2004.04889
[15] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, Mario Szegedy, Trouver des angles pour le traitement du signal quantique avec précision machine arXiv:2003.02831 (2020).
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 2003.02831
[16] Lin Lin, Yu Tong, Préparation quasi optimale de l'état fondamental arXiv:2002.12508 Quantum 4, 372 (2020).
https://doi.org/10.22331/q-2020-12-14-372
arXiv: 2002.12508
[17] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, Shuchen Zhu, A Theory of Trotter Error Phys. Rev.X 11, 011020 arXiv:1912.08854 (2019).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
arXiv: 1912.08854
[18] Dmitry Grinko, Julien Gacon, Christa Zoufal, Stefan Woerner, Estimation itérative de l'amplitude quantique npj Quantum Inf 7, 52 arXiv:1912.05559 (2019).
https://doi.org/10.1038/s41534-021-00379-1
arXiv: 1912.05559
[19] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, Matthias Troyer, Circuits de marche quantiques efficaces pour l'algorithme Metropolis-Hastings Quantum 4, 287 arXiv : 1910.01659 (2019).
https://doi.org/10.22331/q-2020-06-29-287
arXiv: 1910.01659
[20] Scott Aaronson, Patrick Rall, Comptage approximatif quantique, Symposium simplifié sur la simplicité dans les algorithmes. 2020, 24-32 arXiv :1908.10846(2019).
https: / / doi.org/ 10.1137 / 1.9781611976014.5
arXiv: 1908.10846
[21] Aram W. Harrow, Annie Y. Wei, Recuit simulé quantique adaptatif pour l'inférence bayésienne et l'estimation des fonctions de partition Proc. de SODA 2020 arXiv:1907.09965 (2019).
https: / / doi.org/ 10.1137 / 1.9781611975994.12
arXiv: 1907.09965
[22] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo et Anupam Prakash, q-means: A quantum algorithm for unsupervised machine learning arXiv:1812.03584 NIPS 32 (2018).
arXiv: 1812.03584
[23] Yassine Hamoudi, Frédéric Magniez, Quantum Chebyshev's Inequality and Applications ICALP, LIPics Vol 132, pages 69:1-99:16 arXiv:1807.06456 (2018).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.69
arXiv: 1807.06456
[24] Jeongwan Haah, Décomposition du produit des fonctions périodiques dans le traitement quantique du signal Quantum 3, 190. arXiv:1806.10236 (2018).
https://doi.org/10.22331/q-2019-10-07-190
arXiv: 1806.10236
[25] András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe, Transformation de valeur singulière quantique et au-delà : améliorations exponentielles pour l'arithmétique matricielle quantique arXiv:1806.01838 Actes du 51e Symposium annuel ACM SIGACT sur la théorie de l'informatique (STOC 2019) Pages 193 –204 (2018).
arXiv: 1806.01838
[26] David Poulin, Alexei Kitaev, Damian S. Steiger, Matthew B. Hastings, Matthias Troyer, Quantum Algorithm for Spectral Measurement with Lower Gate Count arXiv:1711.11025 Phys. Rév. Lett. 121, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.121.010501
arXiv: 1711.11025
[27] Guang Hao Low, Isaac L. Chuang, Simulation hamiltonienne par amplification spectrale uniforme arXiv:1707.05391 (2017).
arXiv: 1707.05391
[28] Iordanis Kerenidis, Anupam Prakash, Descente de gradient quantique pour les systèmes linéaires et les moindres carrés arXiv:1704.04992 Phys. Rév. A 101, 022316 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.101.022316
arXiv: 1704.04992
[29] Yosi Atia, Dorit Aharonov, Avance rapide des hamiltoniens et mesures d'une précision exponentielle Nature Communications volume 8, 1572 arXiv:1610.09619 (2016).
https://doi.org/10.1038/s41467-017-01637-7
arXiv: 1610.09619
[30] Guang Hao Low, Isaac L. Chuang, Simulation hamiltonienne par Qubitisation Quantum 3, 163 arXiv:1610.06546 (2016).
https://doi.org/10.22331/q-2019-07-12-163
arXiv: 1610.06546
[31] Guang Hao Low, Isaac L. Chuang, Simulation hamiltonienne optimale par traitement quantique du signal Phys. Rév. Lett. 118, 010501 arXiv : 1606.02685 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685
[32] Iordanis Kerenidis, Anupam Prakash, Systèmes de recommandation quantique arXiv : 1603.08675 ITCS 2017, p. 49 :1–49 :21 (2016).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49
arXiv: 1603.08675
[33] Andrew M. Childs, Robin Kothari, Rolando D. Somma, Algorithme quantique pour les systèmes d'équations linéaires avec une dépendance exponentiellement améliorée à la précision SIAM Journal on Computing 46, 1920-1950 arXiv:1511.02306 (2015).
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: 1511.02306
[34] Ashley Montanaro, Accélération quantique des méthodes de Monte Carlo Proc. Roy. Soc. Ser. A, vol. 471 non. 2181, 20150301 arXiv :1504.06987 (2015).
https: / / doi.org/ 10.1098 / rspa.2015.0301
arXiv: 1504.06987
[35] Shelby Kimmel, Guang Hao Low, Theodore J. Yoder, Étalonnage robuste d'un ensemble de portes universel à un seul qubit via une estimation de phase robuste Phys. Rev. A 92, 062315 arXiv:1502.02677 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.92.062315
arXiv: 1502.02677
[36] Dominic W. Berry, Andrew M. Childs, Robin Kothari, simulation hamiltonienne avec une dépendance presque optimale sur tous les paramètres arXiv:1501.01715 Proc. FOCS, pages 792-809 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715
[37] Amnon Ta-Shma, Inversion de matrices bien conditionnées dans l'espace logarithmique quantique STOC '13, Pages 881–890 (2013).
https: / / doi.org/ 10.1145 / 2488608.2488720
[38] Robert Beals, Stephen Brierley, Oliver Gray, Aram Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather, Efficient Distributed Quantum Computing Proc. R. Soc. A 2013 469, 20120686 arXiv : 1207.2307 (2012).
https: / / doi.org/ 10.1098 / rspa.2012.0686
arXiv: 1207.2307
[39] Maris Ozols, Martin Roetteler, Jérémie Roland, Quantum Rejection Sampling arXiv:1103.2774 IRCS'12 pages 290-308 (2011).
https: / / doi.org/ 10.1145 / 2493252.2493256
arXiv: 1103.2774
[40] Man-Hong Yung, Alán Aspuru-Guzik, Un algorithme de métropole quantique-quantique arXiv : 1011.1468 PNAS 109, 754-759 (2011).
https: / / doi.org/ 10.1073 / pnas.1111758109
arXiv: 1011.1468
[41] Andris Ambainis, Amplification d'amplitude à temps variable et algorithme quantique plus rapide pour résoudre des systèmes d'équations linéaires arXiv:1010.4458 STACS'12, 636-647 (2010).
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636
arXiv: 1010.4458
[42] K. Temme, TJ Osborne, KG Vollbrecht, D. Poulin, F. Verstraete, Quantum Metropolis Sampling arXiv:0911.3635 Nature volume 471, pages 87–90 (2009).
https: / / doi.org/ 10.1038 / nature09770
arXiv: 0911.3635
[43] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola, Bounded Independence Fools Halfspaces arXiv:0902.3757 FOCS '09, Pages 171–180 (2009).
arXiv: 0902.3757
[44] Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, Algorithme quantique pour la résolution de systèmes linéaires d'équations Phys. Rév. Lett. 103, 150502 arXiv:0811.3171 (2008).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171
[45] BL Higgins, DW Berry, SD Bartlett, HM Wiseman, GJ Pryde, Entanglement-free Heisenberg-limited phase estimation Nature.450:393-396 arXiv:0709.2996 (2007).
https: / / doi.org/ 10.1038 / nature06257
arXiv: 0709.2996
[46] Chris Marriott, John Watrous, Quantum Arthur-Merlin Games CC, 14(2) : 122 – 152 arXiv:cs/0506068 (2005).
https: / / doi.org/ 10.1007 / s00037-005-0194-x
arXiv: cs / 0506068
[47] Mario Szegedy, Accélération quantique des algorithmes basés sur la chaîne de Markov FOCS '04, Pages 32-41 (2004).
https: / / doi.org/ 10.1109 / FOCS.2004.53
[48] Hartmut Klauck, Quantum Time-Space Tradeoffs for Sorting STOC 03, Pages 69–76 arXiv:quant-ph/0211174 (2002).
https: / / doi.org/ 10.1145 / 780542.780553
arXiv: quant-ph / 0211174
[49] Peter Hoyer, Jan Neerbek, Yaoyun Shi, Complexités quantiques de la recherche ordonnée, du tri et de la distinction des éléments 28e ICALP, LNCS 2076, pp. 346-357 arXiv:quant-ph/0102078 (2001).
https://doi.org/10.1007/3-540-48224-5_29
arXiv: quant-ph / 0102078
[50] Isaac Chuang et Michael Nielsen, Quantum Computation and Quantum Information Cambridge University Press. ISBN-13 : 978-1107002173 (2000).
[51] Gilles Brassard, Peter Hoyer, Michèle Mosca, Alain Tapp, Quantum Amplitude Amplification and Estimation Quantum Computation and Quantum Information, 305:53-74 arXiv:quant-ph/0005055 (2000).
https: / / doi.org/ 10.1090 / conm / 305/05215
arXiv: quant-ph / 0005055
[52] Dorit Aharonov, Alexei Kitaev, Noam Nisan, Quantum Circuits with Mixed States STOC '97, pages 20-30 arXiv:quant-ph/9806029 (1998).
https: / / doi.org/ 10.1145 / 276698.276708
arXiv: quant-ph / 9806029
[53] Ashwin Nayak, Felix Wu, La complexité de la requête quantique de l'approximation de la médiane et des statistiques connexes arXiv:quant-ph/9804066 STOC '99 pp 384-393 (1998).
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066
[54] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani, Forces et faiblesses de l'informatique quantique arXiv:quant-ph/9701001 SIAM Journal on Computing 26(5):1510-1523 (1997).
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: quant-ph / 9701001
[55] A.Yu. Kitaev, Mesures quantiques et problème du stabilisateur abélien arXiv:quant-ph/9511026 (1995).
arXiv: quant-ph / 9511026
[56] Peter W. Shor, Algorithmes de temps polynomial pour la factorisation première et les logarithmes discrets sur un ordinateur quantique SIAM J.Sci.Statist.Comput. 26, 1484 arXiv:quant-ph/9508027 (1995).
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: quant-ph / 9508027
[57] Theodore J. Rivlin, Une introduction à l'approximation des fonctions Dover Publications, Inc. New York. ISBN-13:978-0486640693 (1969).
Cité par
[1] Yuan Su, Hsin-Yuan Huang et Earl T. Campbell, «Trottérisation presque serrée d'électrons en interaction», arXiv: 2012.09194.
[2] John M. Martyn, Zane M. Rossi, Andrew K. Tan et Isaac L. Chuang, « Une grande unification des algorithmes quantiques », arXiv: 2105.02859.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2021-10-23 15:14:11). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.
On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2021-10-23 15:14:09).
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.
PlatonAi. Web3 réinventé. L'intelligence des données amplifiée.
Cliquez ici pour y accéder.
Source : https://quantum-journal.org/papers/q-2021-10-19-566/
