QuOne Lab, Phanous Research and Innovation Centre, Teheran, Iran
Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.
Astratto
Ci si aspetta che le evoluzioni delle Hamiltoniane locali in tempi brevi rimangano locali e quindi limitate. In questo articolo, convalidiamo questa intuizione dimostrando alcune limitazioni sulle evoluzioni a breve termine delle Hamiltoniane locali dipendenti dal tempo. Mostriamo che la distribuzione dell'output di misura delle evoluzioni di breve tempo (al massimo logaritmiche) delle Hamiltoniane locali sono $concentrate$ e soddisfano una $textit{disuguaglianza isoperimetrica}$. Per mostrare le applicazioni esplicite dei nostri risultati, studiamo il problema $M$$small{AX}$$C$$small{UT}$ e concludiamo che la ricottura quantistica necessita almeno di un runtime che ridimensioni logaritmicamente nella dimensione del problema per battere gli algoritmi classici su $M$$small{AX}$$C$$small{UT}$. Per stabilire i nostri risultati, dimostriamo anche un limite di Lieb-Robinson che funziona per Hamiltoniane dipendenti dal tempo che potrebbero essere di interesse indipendente.
Immagine in primo piano: questa illustrazione mostra la distribuzione di probabilità del peso di Hamming di tre diversi stati $n$-qubit per $n=100$. La distribuzione centrata nel mezzo (blu) è la distribuzione tipica per lo stato iniziale di un prodotto (ad esempio, $|+rangle^{otimes n}$). La distribuzione che ha il picco appena a destra (arancione) rappresenta la distribuzione dopo una breve evoluzione dello stato iniziale descritto dal Teorema 2 del manoscritto. La distribuzione che ha due picchi su entrambi i lati dello spettro (verde) è un'approssimazione per lo stato GHZ. Ciò mostra che lo stato GHZ non può essere generato nemmeno approssimativamente da una ricottura quantistica di breve durata.
Riepilogo popolare
► dati BibTeX
► Riferimenti
, T. Kadowaki e H. Nishimori. Ricottura quantistica nel modello di Ising trasversale. Revisione fisica E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
, E. Farhi, J. Goldstone, S. Gutmann e M. Sipser. Calcolo quantistico mediante evoluzione adiabatica. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106
, T. Kato. Sul teorema adiabatico della meccanica quantistica. Journal of the Physical Society of Japan 5, 435–439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435
, M. Nato e V. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180 (1928).
https: / / doi.org/ 10.1007 / BF01343193
, T. Albash e DA Lidar. Calcolo quantistico adiabatico. Recensioni di fisica moderna 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002
, I. Gallina e FM Spedalieri. Ricottura quantistica per l'ottimizzazione vincolata. Revisione fisica applicata 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007
, S. Puri, CK Andersen, AL Grimsmo e A. Blais. Ricottura quantistica con oscillatori non lineari collegati all-to-all. Comunicazioni sulla natura 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785
, W. Lechner, P. Hauke e P. Zoller. Un'architettura di ricottura quantistica con connettività totale dalle interazioni locali. La scienza avanza 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838
, S. Jiang, KA Britt, AJ McCaskey, TS Humble e S. Kais. Ricottura quantistica per la fattorizzazione dei primi. Rapporti scientifici 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z
, RY Li, R. Di Felice, R. Rohs e DA Lidar. Ricottura quantistica contro apprendimento automatico classico applicato a un problema di biologia computazionale semplificato. Informazioni quantistiche NPJ 4, 1–10 (2018).
https://doi.org/10.1038/s41534-018-0060-8
, L. Stella, GE Santoro, E. Tosatti. Ottimizzazione mediante ricottura quantistica: lezioni da casi semplici. Revisione fisica B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303
, O. Titiloye e A. Crispin. Ricottura quantistica del problema della colorazione dei grafi. Ottimizzazione discreta 8, 376–384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001
, A. Mott, J. Job, J.-R. Vlimant, D. Lidar e M. Spiropulu. Risoluzione di un problema di ottimizzazione di Higgs con la ricottura quantistica per l'apprendimento automatico. Natura 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047
, KL Pudenz, T. Albash e DA Lidar. Correzione della ricottura quantistica per problemi di Ising casuali. Revisione fisica A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302
, A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose e A. Aspuru-Guzik. Trovare conformazioni a bassa energia di modelli proteici reticolari mediante ricottura quantistica. Rapporti scientifici 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571
, KL Pudenz, T. Albash e DA Lidar. Ricottura quantistica con correzione di errori con centinaia di qubit. Comunicazioni sulla natura 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243
, R. Martoňák, GE Santoro e E. Tosatti. Ricottura quantistica del problema del commesso viaggiatore. Revisione fisica E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
, SH Adachi e MP Henderson. Applicazione della ricottura quantistica all'addestramento di reti neurali profonde. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356
, MW Johnson, et al. Ricottura quantistica con spin fabbricati. Natura 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012
, S. Boixo, T. Albash, FM Spedalieri, N. Cancelliere e DA Lidar. Firma sperimentale di ricottura quantistica programmabile. Comunicazioni sulla natura 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067
, dC King, et al. Ricottura quantistica coerente in una catena Ising programmabile da 2000 qubit. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847
, B. Foxen, et al. Dimostrazione di un insieme continuo di porte a due qubit per algoritmi quantistici a breve termine. Lettere di revisione fisica 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
, K. Wright, et al. Analisi comparativa di un computer quantistico a 11 qubit. Comunicazioni sulla natura 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
, EJ Crosson e DA Lidar. Prospettive per il miglioramento quantistico con la ricottura quantistica diabatica. Revisioni della natura Fisica 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
, E. Farhi, J. Goldstone e S. Gutmann. Un algoritmo di ottimizzazione approssimativo quantistico. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028
, E. Farhi, D. Gamarnik e S. Gutmann. L'algoritmo di ottimizzazione approssimata quantistica ha bisogno di vedere l'intero grafico: esempi di casi peggiori. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747
, E. Farhi, D. Gamarnik e S. Gutmann. L'algoritmo di ottimizzazione approssimata quantistica ha bisogno di vedere l'intero grafico: un caso tipico. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002
, S. Bravyi, A. Kliesch, R. Koenig e E. Tang. Ostacoli all'ottimizzazione quantistica variazionale dalla protezione della simmetria. Lettere di revisione fisica 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
, S. Bravyi, D. Gosset e R. Movassagh. Algoritmi classici per valori medi quantistici. Fisica della natura 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
, S. Bravyi, A. Kliesch, R. Koenig e E. Tang. Algoritmi ibridi quantistici-classici per la colorazione approssimativa di grafi. Quantico 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678
, L. Eldar e AW Harrow. Hamiltoniani locali i cui stati fondamentali sono difficili da approssimare. Nel 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 427–438 (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.46
, LT Brady, CL Baldwin, A. Bapat, Y. Kharkov e AV Gorshkov. Protocolli ottimali nei problemi di Quantum Annealing e Quantum Approssimative Optimization. Lettere di revisione fisica 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505
, LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov e AV Gorshkov. Comportamento degli algoritmi quantistici analogici. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218
, LC Venuti, D. D'Alessandro e DA Lidar. Controllo ottimale per l'ottimizzazione quantistica di sistemi chiusi e aperti. Revisione fisica applicata 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
, AM Childs, Y. Su, MC Tran, N. Wiebe e S. Zhu. Teoria dell'errore Trotter con il Commutator Scaling. Revisione fisica X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
, B. Nachtergaele, Y. Ogata e R. Sims. Propagazione di correlazioni in sistemi a reticolo quantistico. Giornale di fisica statistica 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6
, B. Nachtergaele e R. Sims. Limiti di Lieb-Robinson nella fisica quantistica a molti corpi. Matematica contemporanea 529, 141–176 (2010).
https: / / doi.org/ 10.1090 / conm / 529 / 10429
, S. Bravyi, MB Hastings e F. Verstraete. Limiti di Lieb-robinson e generazione di correlazioni e ordine quantistico topologico. Lettere di revisione fisica 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401
, C.-F. Chen e A. Lucas. Limiti di crescita degli operatori dalla teoria dei grafi. Comunicazioni in fisica matematica 385, pagine 1273–1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6
, EH Lieb e DW Robinson. La velocità a gruppi finiti dei sistemi di spin quantistico. Comunicazioni in Fisica Matematica 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779
, J. Haah, MB Hastings, R. Kothari e GH Low. Algoritmo quantistico per simulare l'evoluzione in tempo reale di Hamiltoniane reticolari. 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 e P. Sarnak. Grafici Ramanujan. Combinatoria 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799
, B. Mohar. Numeri isoperimetrici dei grafici. Journal of Combinatorial Theory, Serie B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4
, AW Marcus, DA Spielman e N. Srivastava. Famiglie interlacciate IV: Grafici Ramanujan bipartiti di tutte le dimensioni. Nel 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 1358–1377 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.87
, AW Marcus, DA Spielman e N. Srivastava. Famiglie interlacciate IV: Grafici Ramanujan bipartiti di tutte le dimensioni. SIAM Journal on Computing 47, 2488–2509 (2018).
https:///doi.org/10.1137/16M106176X
, C. Hall, D. Puder e WF Sawin. Coperture Ramanujan di grafici. Avanzamenti in matematica 323, 367–410 (2018).
https:///doi.org/10.1016/j.aim.2017.10.042
, MX Goemans e DP Williamson. Algoritmi di approssimazione migliorati per il massimo taglio e problemi di soddisfacibilità utilizzando la programmazione semidefinita. Giornale dell'ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684 mila
, RD Somma, D. Nagaj e M. Kieferová. Quantum Speedup di Quantum Annealing. Lettere di revisione fisica 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501
, MB Hastings. Il potere del calcolo quantistico adiabatico senza problemi di segni. Quantico 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597
, A. Gilyén, MB Hastings e U. Vazirani. (Sub)Vantaggio esponenziale del calcolo quantistico adiabatico senza problemi di segno. In Atti del Simposio annuale ACM sulla teoria dell'informatica (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060 mila
, R. Bhatia. Analisi della matrice. Testi di laurea in Matematica. Springer New York (1996).
https://doi.org/10.1007/978-1-4612-0653-8
, R. Bhatia. Matrici definite positive. Princeton University Press, (2007).
https: / / doi.org/ 10.1515 / 9781400827787 mila
, BD McKay, NC Wormald e B. Wysocka. Cicli brevi in grafici regolari casuali. The Electronic Journal of Combinatorics 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819 mila
, F. Kardoš, D. Král e J. Volec. Tagli massimi di spigoli nei grafici cubici con circonferenza ampia e nei grafici cubici casuali. Strutture casuali e algoritmi 41, 506–520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471
, D. Coppersmith, D. Gamarnik, MT Hajiaghayi e GB Sorkin. MAX SAT casuale, MAX CUT casuale e le loro transizioni di fase. Strutture casuali e algoritmi 24, 502–545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015
, A. Dembo, A. Montanari e S. Sen. Tagli estremi di grafi casuali sparsi. Annali di probabilità 45, 1190–1217 (2017).
https:///doi.org/10.1214/15-AOP1084
Citato da
[1] Giacomo De Palma, Milad Marvian, Cambise Rouzé e Daniel Stilck França, “Limitazioni di algoritmi quantistici variazionali: un approccio di trasporto ottimale quantistico”, arXiv: 2204.03455.
Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2022-07-19 03:10:09). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.
On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2022-07-19 03:10:07).
Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.
