Koncentrationsgrænser for kvantetilstande og begrænsninger på QAOA fra polynomielle approksimationer

Genudgivet af Platon

Abonnenter: 0

Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Anurag Anshu¹ og Tony Metger²

¹School of Engineering and Applied Sciences, Harvard University
²Institut for Teoretisk Fysik, ETH Zürich

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Vi beviser koncentrationsgrænser for følgende klasser af kvantetilstande: (i) outputtilstande af lavvandede kvantekredsløb, besvarer et åbent spørgsmål fra [16]; (ii) injektiv matrix produkttilstande; (iii) outputtilstande for tæt Hamiltonsk evolution, dvs. tilstande af formen $e^{iota H^{(p)}} cdots e^{iota H^{(1)}} |psi_0rangle$ for enhver $n$- qubit-produkttilstand $|psi_0rangle$, hvor hver $H^{(i)}$ kan være en hvilken som helst lokal pendling Hamiltonian, der opfylder en normbegrænsning, inklusive tætte Hamiltonians med interaktioner mellem eventuelle qubits. Vores beviser bruger polynomielle tilnærmelser til at vise, at disse stater er tæt på lokale operatører. Dette indebærer, at fordelingen af Hamming-vægten af en beregningsbaseret måling (og af andre relaterede observerbare) koncentreres.
Et eksempel på (iii) er de tilstande, der frembringes af den kvantetilnærmede optimeringsalgoritme (QAOA). Ved at bruge vores koncentrationsresultater for disse tilstande viser vi, at for en tilfældig spin-model kan QAOA kun lykkes med ubetydelig sandsynlighed selv på superkonstant niveau $p = o(log log n)$, forudsat en styrket version af den så- kaldet overlap gap-egenskab. Dette giver de første begrænsninger for QAOA på tætte instanser på superkonstant niveau, hvilket forbedrer det seneste resultat [BGMZ22].

[Indlejret indhold]

► BibTeX-data

@article{Anshu2023concentrationbounds, doi = {10.22331/q-2023-05-11-999}, url = {https://doi.org/10.22331/q-2023-05-11-999}, title = {Concentration bounds for kvantetilstande og begrænsninger på {QAOA} fra polynomielle approksimationer}, forfatter = {Anshu, Anurag og Metger, Tony}, tidsskrift = {{Quantum}}, issn = {2521-327X}, udgiver = {{Verein zur F {“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, bind = {7}, sider = {999}, måned = maj, år = {2023} }

► Referencer

[1] Anurag Anshu, Itai Arad og David Gosset. En områdelov for 2d frustration-fri spin-systemer. I Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, side 12-18, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519935.3519962.
https:///doi.org/10.1145/3519935.3519962

[2] Anurag Anshu og Nikolas P. Breuckmann. En konstruktion af kombinatorisk NLTS. Journal of Mathematical Physics, 63(12), 12 2022. doi:10.1063/5.0113731.
https:///doi.org/10.1063/5.0113731

[3] Anurag Anshu, Nikolas Breuckmann og Chinmay Nirkhe. NLTS hamiltonians fra gode kvantekoder. arXiv preprint arXiv:2206.13228, 2022. URL: https:///arxiv.org/abs/2206.13228.
arXiv: 2206.13228

[4] Nilin Abrahamsen. Kort bevis på en spektral chernoff på vej til lokale hamiltonianere. arXiv preprint arXiv:2009.04993, 2020. URL: https:///arxiv.org/abs/2009.04993.
arXiv: 2009.04993

[5] Álvaro M Alhambra. Kvante mange-legeme-systemer i termisk ligevægt. arXiv preprint arXiv:2204.08349, 2022. URL: https:///arxiv.org/abs/2204.08349.
arXiv: 2204.08349

[6] Anurag Anshu og Chinmay Nirkhe. Kredsløbs nedre grænser for lavenergitilstande af kvantekode Hamiltonians. I Mark Braverman, redaktør, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), bind 215 af Leibniz International Proceedings in Informatics (LIPIcs), side 6:1–6:22, Dagstuhl, Tyskland, 2022. Schloss Dagstuhl – Leibniz- Zentrum for Informatik. doi:10.4230/LIPIcs.ITCS.2022.6.
https:///doi.org/10.4230/LIPIcs.ITCS.2022.6

[7] Anurag Anshu. Koncentrationsgrænser for kvantetilstande med begrænset korrelationslængde på kvantespingittersystemer. New Journal of Physics, 18(8):083011, aug 2016. doi:10.1088/1367-2630/18/8/083011.
https://doi.org/10.1088/1367-2630/18/8/083011

[8] Fernando GSL Brandao og Marcus Cramer. Ækvivalens af statistiske mekaniske ensembler for ikke-kritiske kvantesystemer. arXiv preprint arXiv:1502.03263, 2015. URL: https:///arxiv.org/abs/1502.03263.
arXiv: 1502.03263

[9] H. Buhrman, R. Cleve, R. De Wolf og C. Zalka. Grænser for små-fejl og nul-fejl kvantealgoritmer. I Proceedings of the 40th Annual Symposium on Foundations of Computer Science, side 358-368, 1999. doi:10.1109/SFFCS.1999.814607.
https:///doi.org/10.1109/SFFCS.1999.814607

[10] FGSL Brandao, Marcus Cramer og Madalin Guta. En berry-esseen-sætning for kvantegittersystemer og ækvivalensen af statistiske mekaniske ensembler. QIP2015 Talk, 2015. URL: http:///www.quantum-lab.org/qip2015/talks/125-Brandao.pdf.
http:///www.quantum-lab.org/qip2015/talks/125-Brandao.pdf

[11] Joao Basso, David Gamarnik, Song Mei og Leo Zhou. Ydeevne og begrænsninger af qaoa ved konstante niveauer på store sparsomme hypergrafer og spinglasmodeller. I 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

[12] Sergey Bravyi, Alexander Kliesch, Robert Koenig og Eugene Tang. Forhindringer for variationsmæssig kvanteoptimering fra symmetribeskyttelse. Phys. Rev. Lett., 125:260505, dec. doi:10.1103/PhysRevLett.125.260505.
https:///doi.org/10.1103/PhysRevLett.125.260505

[13] Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko og Mustazee Rahman. Suboptimalitet af lokale algoritmer til en klasse af max-cut-problemer. The Annals of Probability, 47(3):1587 – 1618, 2019. doi:10.1214/18-AOP1291.
https:///doi.org/10.1214/18-AOP1291

[14] Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu og Jonathan Shi. Begrænsninger af lokale kvantealgoritmer på tilfældig MAX-k-XOR og videre. I 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), bind 229 af Leibniz International Proceedings in Informatics (LIPIcs), side 41:1–41:20, Dagstuhl, Tyskland, 2022. Schloss Dagstuhl – Leibniz-Zentrum fur Informatik. doi:10.4230/LIPIcs.ICALP.2022.41.
https:///doi.org/10.4230/LIPIcs.ICALP.2022.41

[15] J Ignacio Cirac, David Perez-Garcia, Norbert Schuch og Frank Verstraete. Matrixprodukttilstande og projekterede sammenfiltrede partilstande: Begreber, symmetrier, teoremer. Reviews of Modern Physics, 93(4):045003, 2021. doi:10.1103/RevModPhys.93.045003.
https:///doi.org/10.1103/RevModPhys.93.045003

[16] Giacomo De Palma, Milad Marvian, Cambyse Rouzé og Daniel Stilck Franca. Begrænsninger af variationskvantealgoritmer: En kvanteoptimal transporttilgang. PRX Quantum, 4:010309, januar 2023. doi:10.1103/PRXQuantum.4.010309.
https:///doi.org/10.1103/PRXQuantum.4.010309

[17] Giacomo De Palma og Cambyse Rouzé. Kvantekoncentrationsuligheder. Annales Henri Poincaré, apr 2022. doi:10.1007/s00023-022-01181-1.
https://doi.org/10.1007/s00023-022-01181-1

[18] L. Eldar og AW Harrow. Lokale hamiltonianere, hvis grundtilstande er svære at tilnærme sig. I 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), side 427-438, 2017. doi:10.1109/FOCS.2017.46.
https:///doi.org/10.1109/FOCS.2017.46

[19] Edward Farhi, Jeffrey Goldstone og Sam Gutmann. En omtrentlig kvanteoptimeringsalgoritme. arXiv preprint arXiv:1411.4028, 2014. URL: https:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[20] Edward Farhi, David Gamarnik og Sam Gutmann. Den omtrentlige kvanteoptimeringsalgoritme skal se hele grafen: Et typisk tilfælde. arXiv preprint arXiv:2004.09002, 2020. URL: https:///arxiv.org/abs/2004.09002.
arXiv: 2004.09002

[21] David Gamarnik. Overlap gap-egenskaben: En topologisk barriere for optimering over tilfældige strukturer. Proceedings of the National Academy of Sciences, 118(41):e2108492118, 2021. doi:10.1073/pnas.2108492118.
https:///doi.org/10.1073/pnas.2108492118

[22] Ronald L Graham, Martin Grötschel og László Lovász. Håndbog i kombinatorik, bind 1. Elsevier, 1995.

[23] David Gamarnik og Aukosh Jagannath. Overlap gap-egenskaben og omtrentlige meddelelsesoverførselsalgoritmer for $p$-spin-modeller. The Annals of Probability, 49(1):180–205, 2021. URL: https:///hdl.handle.net/1721.1/145311.
https://hdl.handle.net/1721.1/145311

[24] David Gamarnik, Aukosh Jagannath og Alexander S Wein. Lav grad af hårdhed af tilfældige optimeringsproblemer. I 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), side 131-140. IEEE, 2020. doi:10.1109/FOCS46700.2020.00021.
https:///doi.org/10.1109/FOCS46700.2020.00021

[25] David Gamarnik og Quan Li. At finde en stor submatrix af en gaussisk tilfældig matrix. The Annals of Statistics, 46(6A):2511–2561, 2018. URL: http:///hdl.handle.net/1721.1/120593.
http://hdl.handle.net/1721.1/120593

[26] Francesco Guerra og Fabio Lucio Toninelli. Den termodynamiske grænse i middelfelts spinglasmodeller. 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

[27] D. Goderis og P. Vets. Central grænsesætning for blanding af kvantesystemer og CCR-algebraen af fluktuationer. Communications in Mathematical Physics, 122:249–265, 1989. doi:10.1007/BF01257415.
https:///doi.org/10.1007/BF01257415

[28] MB Hastings. Lieb-schultz-mattis i højere dimensioner. Phys. Rev. B, 69:104431, Mar 2004. doi:10.1103/PhysRevB.69.104431.
https:///doi.org/10.1103/PhysRevB.69.104431

[29] Michael Hartmann, Günter Mahler og Ortwin Hess. Eksistens af temperatur på nanoskalaen. Phys. Rev. Lett., 93:080402, aug 2004. doi:10.1103/PhysRevLett.93.080402.
https:///doi.org/10.1103/PhysRevLett.93.080402

[30] Tomotaka Kuwahara, Itai Arad, Luigi Amico og Vlatko Vedral. Lokal reversibilitet og sammenfiltringsstruktur af jordtilstande med mange krop. Quantum Science and Technology, 2(1):015005, 2017. doi:10.1088/2058-9565/aa523d.
https://doi.org/10.1088/2058-9565/aa523d

[31] Jeff Kahn, Nathan Linial og Alex Samorodnitsky. Inklusion-eksklusion: Præcis og omtrentlig. Combinatorica, 16(4):465–477, dec. 1996. doi:10.1007/BF01271266.
https:///doi.org/10.1007/BF01271266

[32] Tomotaka Kuwahara og Keiji Saito. Egentilstand termalisering fra clustering egenskaben af korrelation. Phys. Rev. Lett., 124:200604, maj 2020. doi:10.1103/PhysRevLett.124.200604.
https:///doi.org/10.1103/PhysRevLett.124.200604

[33] Tomotaka Kuwahara og Keiji Saito. Gaussisk koncentrationsbundet og ensemble-ækvivalens i generiske kvante-mange-kropssystemer inklusive lang rækkevidde interaktioner. Annals of Physics, 421:168278, 2020. doi:10.1016/j.aop.2020.168278.
https:///doi.org/10.1016/j.aop.2020.168278

[34] Tomotaka Kuwahara. Forbindelse af sandsynlighedsfordelinger af forskellige operatorer og generalisering af chernoff-hoeffding ulighed. 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

[35] Elliott Lieb, Theodore Schultz og Daniel Mattis. To opløselige modeller af en antiferromagnetisk kæde. 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

[36] Anthony Leverrier og Gilles Zémor. Quantum tanner koder. I 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

[37] D. Perez-Garcia, F. Verstraete, MM Wolf og JI Cirac. Matrix produkt tilstand repræsentationer. Kvante info. Comput., 7(5):401–430, jul 2007. URL: https:///dl.acm.org/doi/10.5555/2011832.2011833.
https:///dl.acm.org/doi/10.5555/2011832.2011833

[38] Pavel Panteleev og Gleb Kalachev. Asymptotisk gode kvante- og lokalt testbare klassiske ldpc-koder. I Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, side 375-388, 2022. doi:10.1145/3519935.3520017.
https:///doi.org/10.1145/3519935.3520017

[39] Sushant Sachdeva og Nisheeth K. Vishnoi. Hurtigere algoritmer via tilnærmelsesteori. Foundations and Trends® in Theoretical Computer Science, 9(2):125–210, 2014. doi:10.1561/0400000065.
https:///doi.org/10.1561/0400000065

[40] Hal Tasaki. Om den lokale ækvivalens mellem det kanoniske og det mikrokanoniske ensembler for kvantespinsystemer. Journal of Statistical Physics, 172(4):905–926, aug 2018. doi:10.1007/s10955-018-2077-y.
https:///doi.org/10.1007/s10955-018-2077-y

Citeret af

[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé og Daniel Stilck França, "Limitations of Variational Quantum Algorithms: A Quantum Optimal Transport Approach", PRX Quantum 4 1, 010309 (2023).

[2] Ojas Parekh, "Synergier mellem operationsforskning og kvanteinformationsvidenskab", arXiv: 2301.05554, (2023).

[3] Dominik S. Wild og Álvaro M. Alhambra, "Klassisk simulering af korttids kvantedynamik", arXiv: 2210.11490, (2022).

[4] Lennart Bittel, Sevag Gharibian og Martin Kliesch, "Optimering af dybden af variationskvantealgoritmer er stærkt QCMA-svært at tilnærme", arXiv: 2211.12519, (2022).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2023-05-11 10:33:33). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

Kunne ikke hente Crossref citeret af data under sidste forsøg 2023-05-11 10:33:31: Kunne ikke hente citerede data for 10.22331/q-2023-05-11-999 fra Crossref. Dette er normalt, hvis DOI blev registreret for nylig.

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

SEO Powered Content & PR Distribution. Bliv forstærket i dag.
PlatoAiStream. Web3 Data Intelligence. Viden forstærket. Adgang her.
Udmøntning af fremtiden med Adryenn Ashley. Adgang her.
Køb og sælg aktier i PRE-IPO-virksomheder med PREIPO®. Adgang her.
Kilde: https://quantum-journal.org/papers/q-2023-05-11-999/

Tidsstempel: Maj 11, 2023

Genudgivet af Platon

Abstrakt

► BibTeX-data

► Referencer

Citeret af

Transformationer i kvantenetværk via lokale operationer assisteret af endeligt mange runder af klassisk kommunikation

Topologiske forbindelsesmodeller af flerpartssammenfiltring

Sammensat sikker enhedsuafhængig kryptering med certificeret sletning

LIMDD: Et beslutningsdiagram til simulering af kvanteberegning inklusive stabilisatortilstande

Generelle kvantealgoritmer til Hamilton-simulering med applikationer til en ikke-abelsk gittermåler-teori

Kohærensteoriens rolle i attraktor kvanteneurale netværk

Adaptive syndrommålinger til Shor-stil fejlkorrektion

Et par måleoverfladekode på femkanter

Effektive algoritmer til flaskehals med kvanteinformation

Matrixkoncentrationsuligheder og effektivitet af tilfældige universelle sæt af kvanteporte

Bestil bevarende kort på kvantemålinger

Om os

Vertikal søgning & Ai

perron

Stay Connected

Konto