Limiti di concentrazione per stati quantistici e limitazioni sul QAOA da approssimazioni polinomiali

Ripubblicato da Platone

Seguaci: 0

Limiti di concentrazione per stati quantistici e limitazioni sulla QAOA da approssimazioni polinomiali PlatoBlockchain Data Intelligence. Ricerca verticale. Ai.

Anurag Anshu¹ e Tony Metger²

¹Facoltà di Ingegneria e Scienze Applicate, Università di Harvard
²Istituto di fisica teorica, ETH Zurigo

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Dimostriamo i limiti di concentrazione per le seguenti classi di stati quantistici: (i) stati di uscita di circuiti quantistici poco profondi, rispondendo a una domanda aperta da [16]; (ii) stati del prodotto di matrici iniettive; (iii) stati output di evoluzione hamiltoniana densa, cioè stati della forma $e^{iota H^{(p)}} cdots e^{iota H^{(1)}} |psi_0rangle$ per ogni $n$- stato del prodotto qubit $|psi_0rangle$, dove ogni $H^{(i)}$ può essere qualsiasi hamiltoniano di pendolarismo locale che soddisfi un vincolo di norma, inclusi gli hamiltoniani densi con interazioni tra qualsiasi qubit. Le nostre dimostrazioni usano approssimazioni polinomiali per mostrare che questi stati sono vicini agli operatori locali. Ciò implica che la distribuzione del peso di Hamming di una misura di base computazionale (e di altre osservabili correlate) si concentri.
Un esempio di (iii) sono gli stati prodotti dall'algoritmo di ottimizzazione approssimata quantistica (QAOA). Usando i nostri risultati di concentrazione per questi stati, mostriamo che per un modello di spin casuale, il QAOA può avere successo solo con probabilità trascurabile anche a livello super-costante $p = o(log log n)$, assumendo una versione rafforzata del so- chiamata proprietà gap di sovrapposizione. Questo fornisce le prime limitazioni sulla QAOA su istanze dense a livello super-costante, migliorando il recente risultato [BGMZ22].

[Contenuto incorporato]

► dati BibTeX

@article{Anshu2023limiti di concentrazione, doi = {10.22331/q-2023-05-11-999}, url = {https://doi.org/10.22331/q-2023-05-11-999}, title = {limiti di concentrazione per stati quantistici e limitazioni su {QAOA} da approssimazioni polinomiali}, autore = {Anshu, Anurag and Metger, Tony}, rivista = {{Quantum}}, issn = {2521-327X}, editore = {{Verein zur F {“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pagine = {999}, mese = maggio, anno = {2023} }

► Riferimenti

, Anurag Anshu, Itai Arad e David Gosset. Una legge di area per i sistemi di rotazione senza frustrazione 2d. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 12–18, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519935.3519962.
https: / / doi.org/ 10.1145 / 3519935.3519962 mila

, Anurag Anshu e Nikolas P. Breuckmann. Una costruzione di NLTS combinatorio. Journal of Mathematical Physics, 63(12), 12 2022. doi:10.1063/5.0113731.
https: / / doi.org/ 10.1063 / 5.0113731 mila

, Anurag Anshu, Nikolas Breuckmann e Chinmay Nirkhe. Hamiltoniani NLTS da buoni codici quantistici. arXiv preprint arXiv:2206.13228, 2022. URL: https://arxiv.org/abs/2206.13228.
arXiv: 2206.13228

, Nilin Abrahamsen. Breve prova di uno spettrale Chernoff diretto agli hamiltoniani locali. arXiv preprint arXiv:2009.04993, 2020. URL: https://arxiv.org/abs/2009.04993.
arXiv: 2009.04993

, Álvaro M Alhambra. Sistemi quantistici a molti corpi in equilibrio termico. arXiv preprint arXiv:2204.08349, 2022. URL: https://arxiv.org/abs/2204.08349.
arXiv: 2204.08349

, Anurag Anshu e Chinmay Nirkhe. Limiti inferiori del circuito per stati a bassa energia di hamiltoniani di codice quantistico. In Mark Braverman, editore, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 6:1–6:22, Dagstuhl, Germania, 2022. Schloss Dagstuhl – Leibniz- Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.6.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.6

, Anurag Anshu. Limiti di concentrazione per stati quantistici con lunghezza di correlazione finita su sistemi reticolari di spin quantistici. New Journal of Physics, 18(8):083011, ago 2016. doi:10.1088/1367-2630/18/8/083011.
https://doi.org/10.1088/1367-2630/18/8/083011

, Fernando GSL Brandao e Marcus Cramer. Equivalenza di insiemi meccanici statistici per sistemi quantistici non critici. arXiv preprint arXiv:1502.03263, 2015. URL: https://arxiv.org/abs/1502.03263.
arXiv: 1502.03263

, H. Buhrman, R. Cleve, R. De Wolf e C. Zalka. Limiti per algoritmi quantistici a errore piccolo e zero. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pagine 358–368, 1999. doi:10.1109/SFFCS.1999.814607.
https: / / doi.org/ 10.1109 / SFFCS.1999.814607

, FGSL Brandao, Marcus Cramer e Madalin Guta. Un teorema berry-esseen per i sistemi a reticolo quantistico e l'equivalenza di insiemi meccanici statistici. QIP2015 Talk, 2015. URL: http:///www.quantum-lab.org/qip2015/talks/125-Brandao.pdf.
http:///www.quantum-lab.org/qip2015/talks/125-Brandao.pdf

, Joao Basso, David Gamarnik, Song Mei e Leo Zhou. Prestazioni e limitazioni del qaoa a livelli costanti su grandi ipergrafi sparsi e modelli di spin glass. Nel 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022. doi:10.1109/FOCS54457.2022.00039.
https:///doi.org/10.1109/FOCS54457.2022.00039

, Sergey Bravyi, Alexander Kliesch, Robert Koenig e Eugene Tang. Ostacoli all'ottimizzazione quantistica variazionale dalla protezione della simmetria. Fis. Rev. Lett., 125:260505, Dec. doi:10.1103/PhysRevLett.125.260505.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

, Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko e Mustazee Rahman. Subottimalità di algoritmi locali per una classe di problemi di max-cut. The Annals of Probability, 47(3):1587 – 1618, 2019. doi:10.1214/18-AOP1291.
https:///doi.org/10.1214/18-AOP1291

, Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu e Jonathan Shi. Limitazioni degli algoritmi quantistici locali su MAX-k-XOR casuale e oltre. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 41:1–41:20, Dagstuhl, Germania, 2022. Schloss Dagstuhl – Leibniz-Zentrum fur Informatica. doi:10.4230/LIPIcs.ICALP.2022.41.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2022.41

, J Ignacio Cirac, David Perez-Garcia, Norbert Schuch e Frank Verstraete. Stati prodotto di matrici e stati di coppie entangled proiettate: Concetti, simmetrie, teoremi. Recensioni di Fisica Moderna, 93(4):045003, 2021. doi:10.1103/RevModPhys.93.045003.
https: / / doi.org/ 10.1103 / RevModPhys.93.045003

, Giacomo De Palma, Milad Marvian, Cambyse Rouzé, Daniel Stilck Franca. Limitazioni degli algoritmi quantistici variazionali: un approccio di trasporto ottimale quantistico. PRX Quantum, 4:010309, Jan 2023. doi:10.1103/PRXQuantum.4.010309.
https: / / doi.org/ 10.1103 / PRXQuantum.4.010309

, Giacomo De Palma e Cambyse Rouzé. Disuguaglianze quantistiche di concentrazione. Annales Henri Poincaré, aprile 2022. doi:10.1007/s00023-022-01181-1.
https://doi.org/10.1007/s00023-022-01181-1

, 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), pagine 427–438, 2017. doi:10.1109/FOCS.2017.46.
https: / / doi.org/ 10.1109 / FOCS.2017.46

, Edward Farhi, Jeffrey Goldstone e Sam Gutmann. Un algoritmo di ottimizzazione approssimata quantistica. arXiv preprint arXiv:1411.4028, 2014. URL: https://arxiv.org/abs/1411.4028.
arXiv: 1411.4028

, Edward Farhi, David Gamarnik e Sam Gutmann. L'algoritmo di ottimizzazione approssimata quantistica deve vedere l'intero grafico: un caso tipico. arXiv preprint arXiv:2004.09002, 2020. URL: https://arxiv.org/abs/2004.09002.
arXiv: 2004.09002

, Davide Gamarnik. La proprietà del gap di sovrapposizione: una barriera topologica all'ottimizzazione su strutture casuali. Atti dell'Accademia Nazionale delle Scienze, 118(41):e2108492118, 2021. doi:10.1073/pnas.2108492118.
https: / / doi.org/ 10.1073 / pnas.2108492118

, Ronald L Graham, Martin Grötschel e László Lovász. Manuale di combinatoria, volume 1. Elsevier, 1995.

, David Gamarnik e Aukosh Jagannath. La proprietà del gap di sovrapposizione e gli algoritmi approssimativi di passaggio dei messaggi per i modelli $p$-spin. The Annals of Probability, 49(1):180–205, 2021. URL: https://hdl.handle.net/1721.1/145311.
https:///hdl.handle.net/1721.1/145311

, David Gamarnik, Aukosh Jagannath e Alexander S Wein. Durezza di basso grado di problemi di ottimizzazione casuale. Nel 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pagine 131–140. IEEE, 2020. doi:10.1109/FOCS46700.2020.00021.
https:///doi.org/10.1109/FOCS46700.2020.00021

, David Gamarnik e Quan Li. Trovare una grande sottomatrice di una matrice casuale gaussiana. The Annals of Statistics, 46(6A):2511–2561, 2018. URL: http://hdl.handle.net/1721.1/120593.
http: / / hdl.handle.net/ 1721.1/120593

, Francesco Guerra e Fabio Lucio Toninelli. Il limite termodinamico nei modelli di spin glass a campo medio. Communications in Mathematical Physics, 230(1):71–79, 2002. doi:10.1007/s00220-002-0699-y.
https: / / doi.org/ 10.1007 / s00220-002-0699-y

, D. Goderis e P. Vets. Teorema del limite centrale per la miscelazione di sistemi quantistici e l'algebra CCR delle fluttuazioni. Communications in Mathematical Physics, 122:249–265, 1989. doi:10.1007/BF01257415.
https: / / doi.org/ 10.1007 / BF01257415

, MB Hastings. Lieb-schultz-mattis in dimensioni superiori. Fis. Rev. B, 69:104431, marzo 2004. doi:10.1103/PhysRevB.69.104431.
https: / / doi.org/ 10.1103 / PhysRevB.69.104431

, Michael Hartmann, Günter Mahler e Ortwin Hess. Esistenza della temperatura su scala nanometrica. Fis. Rev. Lett., 93:080402, ago 2004. doi:10.1103/PhysRevLett.93.080402.
https: / / doi.org/ 10.1103 / PhysRevLett.93.080402

, Tomotaka Kuwahara, Itai Arad, Luigi Amico e Vlatko Vedral. Reversibilità locale e struttura di entanglement di stati fondamentali a molti corpi. Quantum Science and Technology, 2(1):015005, 2017. doi:10.1088/2058-9565/aa523d.
https: / / doi.org/ 10.1088 / 2058-9565 / aa523d

, Jeff Kahn, Nathan Linial e Alex Samorodnitsky. Inclusione-esclusione: Esatto e approssimativo. Combinatorica, 16(4):465–477, dic 1996. doi:10.1007/BF01271266.
https: / / doi.org/ 10.1007 / BF01271266

, Tomotaka Kuwahara e Keiji Saito. Thermalizzazione dell'autostato dalla proprietà di clustering della correlazione. Fis. Rev. Lett., 124:200604, maggio 2020. doi:10.1103/PhysRevLett.124.200604.
https: / / doi.org/ 10.1103 / PhysRevLett.124.200604

, Tomotaka Kuwahara e Keiji Saito. Concentrazione gaussiana legata ed equivalenza d'insieme in sistemi quantistici generici a molti corpi comprese le interazioni a lungo raggio. Annals of Physics, 421:168278, 2020. doi:10.1016/j.aop.2020.168278.
https: / / doi.org/ 10.1016 / j.aop.2020.168278

, Tomotaka Kuwahara. Collegamento delle distribuzioni di probabilità di diversi operatori e generalizzazione della disuguaglianza di Chernoff-Hoeffding. Journal of Statistical Mechanics: Theory and Experiment, 2016(11):113103, nov 2016. doi:10.1088/1742-5468/2016/11/113103.
https://doi.org/10.1088/1742-5468/2016/11/113103

, Elliott Lieb, Theodore Schultz e Daniel Mattis. Due modelli solubili di una catena antiferromagnetica. Annals of Physics, 16(3):407–466, 1961. doi:10.1016/0003-4916(61)90115-4.
https://doi.org/10.1016/0003-4916(61)90115-4

, Anthony Leverrier e Gilles Zemor. Codici tanner quantistici. Nel 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022. doi:10.1109/FOCS54457.2022.00117.
https:///doi.org/10.1109/FOCS54457.2022.00117

, D. Perez-Garcia, F. Verstraete, MM Wolf e JI Cirac. Rappresentazioni dello stato del prodotto matriciale. Informazioni quantistiche. Comput., 7(5):401–430, lug 2007. URL: https://dl.acm.org/doi/10.5555/2011832.2011833.
https: / / dl.acm.org/ doi / 10.5555 / 2011832.2011833 mila

, Pavel Panteleev e Gleb Kalachev. Codici ldpc classici quantistici asintoticamente buoni e verificabili localmente. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pagine 375–388, 2022. doi:10.1145/3519935.3520017.
https: / / doi.org/ 10.1145 / 3519935.3520017 mila

, Sushant Sachdeva e Nisheeth K. Vishnoi. Algoritmi più veloci tramite la teoria dell'approssimazione. Foundations and Trends® in Theoretical Computer Science, 9(2):125–210, 2014. doi:10.1561/0400000065.
https: / / doi.org/ 10.1561 / 0400000065 mila

, Hal Tasaki. Sull'equivalenza locale tra insiemi canonico e microcanonico per sistemi di spin quantistici. Journal of Statistical Physics, 172(4):905–926, agosto 2018. doi:10.1007/s10955-018-2077-y.
https: / / doi.org/ 10.1007 / s10955-018-2077-y

Citato da

[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé e Daniel Stilck França, “Limitazioni degli algoritmi quantistici variazionali: un approccio di trasporto ottimale quantistico”, PRX Quantico 4 1, 010309 (2023).

[2] Ojas Parekh, "Sinergie tra ricerca operativa e scienza dell'informazione quantistica", arXiv: 2301.05554, (2023).

[3] Dominik S. Wild e Álvaro M. Alhambra, “Classical simulation of short-time quantum dynamics”, arXiv: 2210.11490, (2022).

[4] Lennart Bittel, Sevag Gharibian e Martin Kliesch, "L'ottimizzazione della profondità degli algoritmi quantistici variazionali è fortemente QCMA-difficile da approssimare", arXiv: 2211.12519, (2022).

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2023-05-11 10:33:33). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

Impossibile recuperare Crossref citato da dati durante l'ultimo tentativo 2023-05-11 10:33:31: Impossibile recuperare i dati citati per 10.22331 / q-2023-05-11-999 da Crossref. Questo è normale se il DOI è stato registrato di recente.

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.

Distribuzione di contenuti basati su SEO e PR. Ricevi amplificazione oggi.
PlatoAiStream. Intelligenza dei dati Web3. Conoscenza amplificata. Accedi qui.
Coniare il futuro con Adryenn Ashley. Accedi qui.
Acquista e vendi azioni in società PRE-IPO con PREIPO®. Accedi qui.
Fonte: https://quantum-journal.org/papers/q-2023-05-11-999/

Timestamp: 11 Maggio 2023

Ripubblicato da Platone

Astratto

► dati BibTeX

► Riferimenti

Citato da

Trasformazioni in reti quantistiche tramite operazioni locali assistite da un numero finito di cicli di comunicazione classica

Modelli di collegamento topologici di entanglement multipartito

Crittografia composibilmente sicura indipendente dal dispositivo con eliminazione certificata

LIMDD: un diagramma decisionale per la simulazione del calcolo quantistico compresi gli stati stabilizzatori

Algoritmi quantistici generali per la simulazione hamiltoniana con applicazioni ad una teoria di Gauge reticolare non abeliana

Il ruolo della teoria della coerenza nelle reti neurali quantistiche di attrattori

Misurazioni della sindrome adattiva per la correzione degli errori in stile Shor

Un codice di superficie di misurazione della coppia sui pentagoni

Algoritmi efficienti per il collo di bottiglia dell'informazione quantistica

Disuguaglianze di concentrazione di matrici ed efficienza di insiemi casuali universali di porte quantistiche

Mappe di conservazione dell'ordine su misure quantistiche

Chi siamo

Ricerca verticale e Ai

Piattaforma

Rimani in contatto

Il mio account