QuOne Lab, Phanous Research and Innovation Center, Téhéran, Iran
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
Les évolutions des hamiltoniens locaux en temps courts devraient rester locales et donc limitées. Dans cet article, nous validons cette intuition en prouvant certaines limitations sur les évolutions à court terme des hamiltoniens locaux dépendant du temps. Nous montrons que la distribution de la sortie de mesure des évolutions à court terme (au plus logarithmiques) des hamiltoniens locaux est $concentrée$ et satisfait une $textit{inégalité isopérimétrique}$. Pour présenter des applications explicites de nos résultats, nous étudions le problème $M$$small{AX}$$C$$small{UT}$ et concluons que le recuit quantique nécessite au moins un temps d'exécution qui évolue de manière logarithmique dans la taille du problème pour battre les algorithmes classiques sur $M$$small{AX}$$C$$small{UT}$. Pour établir nos résultats, nous prouvons également une borne de Lieb-Robinson qui fonctionne pour les hamiltoniens dépendant du temps qui pourraient présenter un intérêt indépendant.
Image sélectionnée : cette illustration représente la distribution de probabilité du poids de Hamming de trois états différents de $n$-qubit pour $n=100$. La distribution centrée au milieu (bleu) est la distribution typique pour un état initial de produit (par exemple, $|+rangle^{otimes n}$). La distribution qui culmine juste à droite (orange) représente la distribution après une courte évolution de l'état initial décrit par le théorème 2 du manuscrit. La distribution qui a deux pics de chaque côté du spectre (vert) est une approximation pour l'état GHZ. Cela montre que l'état GHZ ne peut pas être généré même approximativement par un recuit quantique de courte durée.
Résumé populaire
► Données BibTeX
► Références
T. Kadowaki et H. Nishimori. Recuit quantique dans le modèle transverse d'Ising. Examen physique E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
E. Farhi, J. Goldstone, S. Gutmann et M. Sipser. Calcul quantique par évolution adiabatique. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106
T. Kato. Sur le théorème adiabatique de la mécanique quantique. Journal de la Société de physique du Japon 5, 435–439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435
M. Born et V. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180 (1928).
https: / / doi.org/ 10.1007 / BF01343193
T. Albash et DA Lidar. Calcul quantique adiabatique. Avis sur la physique moderne 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002
I. Poule et FM Spedalieri. Recuit quantique pour une optimisation contrainte. Examen physique appliqué 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007
S. Puri, CK Andersen, AL Grimsmo et A. Blais. Recuit quantique avec des oscillateurs non linéaires connectés tout-à-tout. Nature Communications 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785
W. Lechner, P. Hauke et P. Zoller. Une architecture de recuit quantique avec une connectivité tout-à-tout à partir d'interactions locales. Science Advances 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838
S. Jiang, KA Britt, AJ McCaskey, TS Humble et S. Kais. Recuit quantique pour la factorisation première. Rapports scientifiques 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z
RY Li, R. Di Felice, R. Rohs et DA Lidar. Recuit quantique versus apprentissage automatique classique appliqué à un problème simplifié de biologie computationnelle. Informations quantiques NPJ 4, 1–10 (2018).
https://doi.org/10.1038/s41534-018-0060-8
L. Stella, GE Santoro et E. Tosatti. Optimisation par recuit quantique : enseignements tirés de cas simples. Examen physique B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303
O. Titiloye et A. Crispin. Recuit quantique du problème de coloration des graphes. Optimisation discrète 8, 376–384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001
A. Mott, J. Job, J.-R. Vlimant, D. Lidar et M. Spiropulu. Résolution d'un problème d'optimisation de Higgs avec recuit quantique pour l'apprentissage automatique. Nature 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047
KL Pudenz, T. Albash et D. A Lidar. Correction de recuit quantique pour les problèmes d'Ising aléatoires. Examen physique A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302
A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose et A. Aspuru-Guzik. Recherche de conformations à basse énergie de modèles de protéines de réseau par recuit quantique. Rapports scientifiques 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571
KL Pudenz, T. Albash et D. A Lidar. Recuit quantique corrigé des erreurs avec des centaines de qubits. Nature communications 5, 1-10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243
R. Martoňák, GE Santoro et E. Tosatti. Recuit quantique du problème du voyageur de commerce. Examen physique E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
SH Adachi et MP Henderson. Application du recuit quantique à la formation de réseaux de neurones profonds. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356
M.W Johnson, et al. Recuit quantique avec spins manufacturés. Nature 473, 194-198 (2011).
https: / / doi.org/ 10.1038 / nature10012
S. Boixo, T. Albash, FM Spedalieri, N. Chancellor et DA Lidar. Signature expérimentale du recuit quantique programmable. Nature communications 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067
AD King, et al. Recuit quantique cohérent dans une chaîne d'Ising programmable de 2000 qubits. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847
B. Foxen, et al. Démonstration d'un ensemble continu de portes à deux qubits pour les algorithmes quantiques à court terme. Lettres d'examen physique 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
K.Wright, et al. Analyse comparative d'un ordinateur quantique de 11 qubits. Communications naturelles 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
EJ Crosson et DA Lidar. Perspectives d'amélioration quantique avec recuit quantique diabatique. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
E. Farhi, J. Goldstone et S. Gutmann. Un algorithme d'optimisation approximative quantique. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028
E. Farhi, D. Gamarnik et S. Gutmann. L'algorithme d'optimisation approximative quantique doit voir l'ensemble du graphique : exemples des pires cas. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747
E. Farhi, D. Gamarnik et S. Gutmann. L'algorithme d'optimisation approximative quantique doit voir l'ensemble du graphique : un cas typique. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002
S. Bravyi, A. Kliesch, R. Koenig et E. Tang. Obstacles à l'optimisation quantique variationnelle à partir de la protection de la symétrie. Lettres d'examen physique 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
S. Bravyi, D. Gosset et R. Movassagh. Algorithmes classiques pour les valeurs moyennes quantiques. Nature Physics 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
S. Bravyi, A. Kliesch, R. Koenig et E. Tang. Algorithmes hybrides quantiques-classiques pour la coloration approximative des graphes. Quantique 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678
L. Eldar et AW Harrow. Hamiltoniens locaux dont les états fondamentaux sont difficiles à approximer. En 2017, 58e Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS), 427–438 (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.46
LT Brady, CL Baldwin, A. Bapat, Y. Kharkov et AV Gorshkov. Protocoles optimaux dans les problèmes de recuit quantique et d'algorithme d'optimisation approximative quantique. Lettres d'examen physique 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505
LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov et AV Gorshkov. Comportement des algorithmes quantiques analogiques. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218
LC Venuti, D. D'Alessandro et DA Lidar. Contrôle optimal pour l'optimisation quantique des systèmes fermés et ouverts. Examen physique appliqué 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
AM Childs, Y. Su, MC Tran, N. Wiebe et S. Zhu. Théorie de l'erreur de trotteur avec mise à l'échelle du commutateur. Examen physique X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
B. Nachtergaele, Y. Ogata et R. Sims. Propagation des corrélations dans les systèmes de réseaux quantiques. Journal de physique statistique 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6
B. Nachtergaele et R. Sims. Bornes de Lieb-Robinson en physique quantique à plusieurs corps. Mathématiques contemporaines 529, 141–176 (2010).
https: / / doi.org/ 10.1090 / conm / 529/10429
S. Bravyi, MB Hastings et F. Verstraete. Bornes de Lieb-robinson et génération de corrélations et ordre quantique topologique. Lettres d'examen physique 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401
C.-F. Chen et A. Lucas. Limites de croissance des opérateurs de la théorie des graphes. Communications en physique mathématique 385, pages 1273-1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6
EH Lieb et DW Robinson. La vitesse de groupe finie des systèmes de spin quantiques. Communications en physique mathématique 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779
J. Haah, MB Hastings, R. Kothari et GH Low. Algorithme quantique pour simuler l'évolution en temps réel des hamiltoniens de réseau. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 350–360 (2018).
https: / / doi.org/ 10.1109 / FOCS.2018.00041
A. Lubotzky, R. Phillips et P. Sarnak. Graphiques de Ramanujan. Combinatorica 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799
B.Mohar. Numéros isopérimétriques des graphes. Journal of Combinatorial Theory, série B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4
AW Marcus, DA Spielman et N. Srivastava. Familles entrelacées IV : graphes bipartis de Ramanujan de toutes tailles. En 2015, 56e Symposium annuel de l'IEEE sur les fondements de l'informatique (FOCS), 1358–1377 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.87
AW Marcus, DA Spielman et N. Srivastava. Familles entrelacées IV : graphes bipartis de Ramanujan de toutes tailles. SIAM Journal on Computing 47, 2488–2509 (2018).
https:///doi.org/10.1137/16M106176X
C. Hall, D. Puder et WF Sawin. Couvertures Ramanujan de graphes. Avancées en mathématiques 323, 367–410 (2018).
https:///doi.org/10.1016/j.aim.2017.10.042
MX Goemans et DP Williamson. Algorithmes d'approximation améliorés pour les problèmes de coupe maximale et de satisfiabilité à l'aide de la programmation semi-définie. Journal de l'ACM 42, 1115-1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684
RD Somma, D. Nagaj et M. Kieferová. Accélération quantique par recuit quantique. Lettres d'examen physique 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501
MB Hastings. La puissance du calcul quantique adiabatique sans problème de signe. Quantique 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597
A. Gilyén, MB Hastings et U. Vazirani. Avantage (sous)exponentiel du calcul quantique adiabatique sans problème de signe. Dans Actes du Symposium annuel de l'ACM sur la théorie de l'informatique (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060
R. Bhatia. Analyse matricielle. Textes de fin d'études en mathématiques. Springer New York (1996).
https://doi.org/10.1007/978-1-4612-0653-8
R. Bhatia. Matrices définies positives. Presse de l'Université de Princeton, (2007).
https: / / doi.org/ 10.1515 / 9781400827787
BD McKay, NC Wormald et B. Wysocka. Cycles courts dans les graphes réguliers aléatoires. Le Journal électronique de combinatoire 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819
F. Kardoš, D. Král et J. Volec. Coupes de bord maximales dans les graphiques cubiques à grande circonférence et dans les graphiques cubiques aléatoires. Structures et algorithmes aléatoires 41, 506–520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471
D. Coppersmith, D. Gamarnik, MT Hajiaghayi et GB Sorkin. MAX SAT aléatoire, MAX CUT aléatoire et leurs transitions de phase. Structures aléatoires et algorithmes 24, 502–545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015
A. Dembo, A. Montanari et S. Sen. Coupes extrêmes de graphes aléatoires clairsemés. Annals of Probability 45, 1190–1217 (2017).
https:///doi.org/10.1214/15-AOP1084
Cité par
[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck França, « Limitations of variational quantum algorithms: a quantum optimal transport approach », arXiv: 2204.03455.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2022-07-19 03:10:09). 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 2022-07-19 03:10:07).
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.
