O estado da conjectura PCP quântica (versão de jogos)

Na teoria clássica da complexidade, as duas definições de provas verificáveis probabilisticamente -- a satisfação de restrições e a versão de jogos não locais -- são computacionalmente iguais em poder. No contexto quântico, a situação é muito menos clara. O resultado MIP* = RE de Ji et al. (arXiv:2001.04383) e os refinamentos de Natarajan e Zhang (arXiv:2302.04322) mostram que sistemas de prova interativos com múltiplos provadores e mensagens de comprimento polilogarítmico podem resolver qualquer problema de decisão em RE, incluindo problemas indecidíveis como o problema da parada. Esses resultados mostram que qualquer conexão entre a conjectura PCP quântica "satisfação de restrições" ou "Hamiltoniana" e jogos não locais deve envolver a restrição dos jogadores no jogo para serem computacionalmente eficientes. Esta nota contém dois resultados principais: (1) apresentamos um "PCP de jogos quânticos para AM" na forma de uma nova construção de um protocolo MIP* sucinto com provadores eficientes para o problema canônico completo de AM, e (2) explicamos um erro no procedimento de amplificação de energia de Natarajan e Vidick (arXiv:1710.03062) que invalida a alegação deles de terem construído um PCP de jogos quânticos para um problema completo de QMA. Ao investigar os obstáculos restantes para um PCP de jogos quânticos para QMA, destacamos a importância e o desafio de compreender a amplificação de gaps para Hamiltonianas, mesmo quando a localidade é substituída por restrições muito mais fracas, como limites no "espectro de Pauli" da Hamiltoniana. Esperamos que essas questões motivem progressos rumo a novas "versões iniciais" da conjectura PCP quântica Hamiltoniana.