Tenho algumas perguntas sobre a conjectura do Quantum PCP:
Qual é a afirmação da conjectura quântica do PCP?
Que implicações o teorema do PCP quântico teria para simular Hamiltonianos?
Acredita-se que a adoção da prova de Irit Dinur do teorema clássico do PCP provavelmente leve a uma prova da conjectura Quantum PCP?
Que pano de fundo é necessário para ler artigos sobre o problema?
Respostas:
Como Shor disse, ainda não há teorema QPCP. Uma conjectura (vamos chamá-la de conjectura QPCP) é a seguinte: considere um gráfico de N vértices, de grau O (1). Associe um qudit a cada vértice, com a dimensão espacial Hilbert O (1). Seja o hamiltoniano uma soma de termos para cada aresta, cada um desses termos atuando apenas nos qudits dos vértices, com a norma de operador de cada termo delimitada por O (1), de modo que a norma de operador do hamiltoniano seja O (N ) Então, a conjectura é que existe algum epsilon> 0, de modo que é difícil para o QMA aproximar a energia do estado fundamental do problema a uma precisão epsilon N.
Uma conjectura um pouco mais forte é considerar o caso em que cada termo que atua em uma borda é um projetor, para que a energia do estado fundamental não seja negativa e a conjectura é que é difícil para o QMA determinar se a energia do estado fundamental é 0 dada a promessa de que, se não for zero, será pelo menos epsilon N.
Também existem outras versões da conjectura, mas essas são duas interessantes com a relação mais natural com a física. Uma conjectura ainda mais forte (portanto, provavelmente mais fácil de contestar se você acredita que essas conjecturas são falsas) é considerar o caso em que o hamiltoniano é uma soma de projetores pendulares.
fonte
Basicamente, tudo o que se sabe sobre a conjectura do Quantum PCP foi coletado nesta pesquisa por Dorit Aharonov, Itai Arad e Thomas Vidick:
A conjectura Quantum PCP
Veja também a postagem do blog de Thomas sobre o assunto.
fonte