QuOne Lab, Phanous Research and Innovation Centre, Teerã, Irã
Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.
Sumário
Espera-se que as evoluções de hamiltonianos locais em tempos curtos permaneçam locais e, portanto, limitadas. Neste artigo, validamos essa intuição provando algumas limitações em evoluções de curto prazo de hamiltonianos dependentes do tempo local. Mostramos que a distribuição da saída de medição de evoluções de curto prazo (no máximo logarítmica) de hamiltonianos locais são $concentrados$ e satisfazem uma $textit{desigualdade isoperimétrica}$. Para mostrar aplicações explícitas de nossos resultados, estudamos o problema $M$$small{AX}$$C$$small{UT}$ e concluímos que o recozimento quântico precisa de pelo menos um tempo de execução que escale logaritmicamente no tamanho do problema para vença algoritmos clássicos em $M$$small{AX}$$C$$small{UT}$. Para estabelecer nossos resultados, também provamos um limite de Lieb-Robinson que funciona para hamiltonianos dependentes do tempo que podem ser de interesse independente.
Imagem em destaque: Esta ilustração mostra a distribuição de probabilidade do peso de Hamming de três estados $n$-qubit diferentes para $n=100$. A distribuição centralizada no meio (azul) é a distribuição típica para um estado inicial do produto (por exemplo, $|+rangle^{otimes n}$). A distribuição com pico à direita (laranja) representa a distribuição após um curto período de evolução do estado inicial descrito pelo Teorema 2 do manuscrito. A distribuição que tem dois picos em cada lado do espectro (verde) é uma aproximação para o estado GHZ. Isso mostra que o estado GHZ não pode ser gerado nem mesmo aproximadamente por um recozimento quântico de curta duração.
Resumo popular
► dados BibTeX
► Referências
[1] T. Kadowaki e H. Nishimori. Recozimento quântico no modelo transversal de Ising. Physical Review E 58, 5355-5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
[2] E. Farhi, J. Goldstone, S. Gutmann e M. Sipser. Computação Quântica por Evolução Adiabática. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106
[3] T. Kato. Sobre o teorema adiabático da mecânica quântica. Jornal da Sociedade Física do Japão 5, 435-439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435
[4] M. Born e V. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165-180 (1928).
https: / / doi.org/ 10.1007 / BF01343193
[5] T. Albash e DA Lidar. Computação quântica adiabática. Revisões de Física Moderna 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002
[6] I. Galinha e FM Spedalieri. Recozimento quântico para otimização restrita. Revisão Física Aplicada 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007
[7] S. Puri, CK Andersen, AL Grimsmo e A. Blais. Recozimento quântico com osciladores não lineares conectados de tudo para todos. Nature Communications 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785
[8] W. Lechner, P. Hauke e P. Zoller. Uma arquitetura de recozimento quântico com conectividade total a partir de interações locais. Science Advances 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838
[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble e S. Kais. Recozimento quântico para fatoração de primos. Relatórios Científicos 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z
[10] RY Li, R. Di Felice, R. Rohs e DA Lidar. Recozimento quântico versus aprendizado de máquina clássico aplicado a um problema simplificado de biologia computacional. Informações quânticas do NPJ 4, 1-10 (2018).
https://doi.org/10.1038/s41534-018-0060-8
[11] L. Stella, GE Santoro, and E. Tosatti. Otimização por recozimento quântico: Lições de casos simples. Revisão Física B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303
[12] O. Titiloye e A. Crispin. Recozimento quântico do problema de coloração de grafos. Otimização Discreta 8, 376–384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001
[13] A. Mott, J. Job, J.-R. Vlimant, D. Lidar e M. Spiropulu. Resolvendo um problema de otimização de Higgs com recozimento quântico para aprendizado de máquina. Natureza 550, 375-379 (2017).
https: / / doi.org/ 10.1038 / nature24047
[14] KL Pudenz, T. Albash e D. A Lidar. Correção de recozimento quântico para problemas de Ising aleatórios. Revisão Física A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302
[15] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose e A. Aspuru-Guzik. Encontrando conformações de baixa energia de modelos de proteínas de rede por recozimento quântico. Relatórios científicos 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571
[16] KL Pudenz, T. Albash e D. A Lidar. Recozimento quântico com correção de erros com centenas de qubits. Comunicações da natureza 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243
[17] R. Martoňák, GE Santoro e E. Tosatti. Recozimento quântico do problema do caixeiro viajante. Revisão Física E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
[18] SH Adachi e MP Henderson. Aplicação do recozimento quântico ao treinamento de redes neurais profundas. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356
[19] M.W Johnson, et ai. Recozimento quântico com spins fabricados. Natureza 473, 194-198 (2011).
https: / / doi.org/ 10.1038 / nature10012
[20] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor e DA Lidar. Assinatura experimental de recozimento quântico programável. Comunicações da natureza 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067
[21] AD King, et ai. Recozimento quântico coerente em uma cadeia Ising de 2000 qubits programável. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847
[22] B. Foxen, et ai. Demonstrando um conjunto contínuo de portas de dois qubits para algoritmos quânticos de curto prazo. Cartas de Revisão Física 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
[23] K. Wright, et ai. Benchmarking de um computador quântico de 11 qubits. Comunicações da natureza 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
[24] EJ Crosson e DA Lidar. Perspectivas para aprimoramento quântico com recozimento quântico diabático. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
[25] E. Farhi, J. Goldstone e S. Gutmann. Um Algoritmo de Otimização Aproximada Quântica. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028
[26] E. Farhi, D. Gamarnik e S. Gutmann. O algoritmo de otimização aproximada quântica precisa ver o gráfico inteiro: exemplos de pior caso. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747
[27] E. Farhi, D. Gamarnik e S. Gutmann. O algoritmo de otimização aproximada quântica precisa ver o gráfico inteiro: um caso típico. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002
[28] S. Bravyi, A. Kliesch, R. Koenig e E. Tang. Obstáculos à otimização quântica variacional da proteção de simetria. Cartas de Revisão Física 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[29] S. Bravyi, D. Gosset e R. Movassagh. Algoritmos clássicos para valores médios quânticos. Nature Physics 17, 337-341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
[30] S. Bravyi, A. Kliesch, R. Koenig e E. Tang. Algoritmos quântico-clássicos híbridos para coloração aproximada de grafos. Quantum 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678
[31] L. Eldar e AW Harrow. Hamiltonianos Locais Cujos Estados Fundamentais são Difíceis de Aproximar. Em 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 427–438 (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.46
[32] LT Brady, CL Baldwin, A. Bapat, Y. Kharkov e AV Gorshkov. Protocolos Ótimos em Problemas de Algoritmo de Aproximação Quântica e Recozimento Quântico. Cartas de Revisão Física 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505
[33] LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov e AV Gorshkov. Comportamento de Algoritmos Quânticos Analógicos. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218
[34] LC Venuti, D. D'Alessandro e DA Lidar. Controle Ótimo para Otimização Quântica de Sistemas Fechados e Abertos. Revisão Física Aplicada 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
[35] AM Childs, Y. Su, MC Tran, N. Wiebe e S. Zhu. Teoria do erro do trotador com escala do comutador. Revisão Física X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
[36] B. Nachtergaele, Y. Ogata e R. Sims. Propagação de correlações em sistemas reticulados quânticos. Journal of Statistical Physics 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6
[37] B. Nachtergaele e R. Sims. Limites de Lieb-Robinson na física quântica de muitos corpos. Matemática Contemporânea 529, 141-176 (2010).
https: / / doi.org/ 10.1090 / conm / 529/10429
[38] S. Bravyi, MB Hastings e F. Verstraete. Limites de Lieb-robinson e geração de correlações e ordem quântica topológica. Cartas de Revisão Física 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401
[39] C.-F. Chen e A. Lucas. Limites de crescimento do operador da teoria dos grafos. Comunicações em Física Matemática 385, páginas 1273-1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6
[40] EH Lieb e DW Robinson. A velocidade de grupo finita de sistemas de spin quânticos. Communications in Mathematical Physics 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779
[41] J. Haah, MB Hastings, R. Kothari e GH Low. Algoritmo quântico para simular a evolução em tempo real de Hamiltonianos de rede. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 350–360 (2018).
https: / / doi.org/ 10.1109 / FOCS.2018.00041
[42] A. Lubotzky, R. Phillips e P. Sarnak. Gráficos Ramanujan. Combinatória 8, 261-277 (1988).
https: / / doi.org/ 10.1007 / BF02126799
[43] B. Mohar. Números isoperimétricos de gráficos. Journal of Combinatorial Theory, Série B 47, 274-291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4
[44] AW Marcus, DA Spielman e N. Srivastava. Famílias entrelaçadas IV: Gráficos bipartidos de Ramanujan de todos os tamanhos. Em 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 1358–1377 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.87
[45] AW Marcus, DA Spielman e N. Srivastava. Famílias entrelaçadas IV: Gráficos bipartidos de Ramanujan de todos os tamanhos. SIAM Journal on Computing 47, 2488–2509 (2018).
https:///doi.org/10.1137/16M106176X
[46] C. Hall, D. Puder e WF Sawin. Coberturas Ramanujan de gráficos. Avanços em Matemática 323, 367-410 (2018).
https:///doi.org/10.1016/j.aim.2017.10.042
[47] MX Goemans e DP Williamson. Algoritmos de aproximação aprimorados para problemas de corte máximo e satisfatibilidade usando programação semidefinida. Jornal do ACM 42, 1115-1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684
[48] RD Somma, D. Nagaj e M. Kieferová. Aceleração quântica por recozimento quântico. Cartas de Revisão Física 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501
[49] MB Hastings. O poder da computação quântica adiabática sem problema de sinal. Quantum 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597
[50] A. Gilyén, MB Hastings e U. Vazirani. (Sub)Vantagem exponencial da computação quântica adiabática sem problema de sinal. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060
[51] R. Bhatia. Análise matricial. Textos de Graduação em Matemática. Springer Nova York (1996).
https://doi.org/10.1007/978-1-4612-0653-8
[52] R. Bhatia. Matrizes definidas positivas. Princeton University Press, (2007).
https: / / doi.org/ 10.1515 / 9781400827787
[53] BD McKay, NC Wormald e B. Wysocka. Ciclos Curtos em Gráficos Regulares Aleatórios. The Electronic Journal of Combinatorics 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819
[54] F. Kardoš, D. Král e J. Volec. Cortes máximos de arestas em grafos cúbicos com grande circunferência e em grafos cúbicos aleatórios. Random Structures & Algorithms 41, 506–520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471
[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi e GB Sorkin. Random MAX SAT, random MAX CUT e suas transições de fase. Random Structures and Algorithms 24, 502–545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015
[56] A. Dembo, A. Montanari e S. Sen. Cortes extremos de gráficos aleatórios esparsos. Annals of Probability 45, 1190–1217 (2017).
https:///doi.org/10.1214/15-AOP1084
Citado por
[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé e Daniel Stilck França, “Limitações de algoritmos quânticos variacionais: uma abordagem de transporte ótimo quântico”, arXiv: 2204.03455.
As citações acima são de SAO / NASA ADS (última atualização com êxito 2022-07-19 03:10:09). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.
On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2022-07-19 03:10:07).
Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.
