PCP quântico e dureza de simulação de Hamiltonianos

8

Tenho algumas perguntas sobre a conjectura do Quantum PCP:

  1. Qual é a afirmação da conjectura quântica do PCP?

  2. Que implicações o teorema do PCP quântico teria para simular Hamiltonianos?

  3. 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?

  4. Que pano de fundo é necessário para ler artigos sobre o problema?

A cópia da pergunta no MO

Comunidade
fonte
12
Não há teorema quântico de PCP. As pessoas estão tentando provar isso, mas se esse teorema existe (e talvez exatamente qual a forma que ele tomaria) é uma das grandes questões em aberto na computação quântica.
quer
7
Noah Rahman: Por favor, faça um link para a pergunta original ao fazer uma cruzada. Caso contrário, nem todos estariam cientes de que você já recebeu uma resposta muito boa de Peter Shor. mathoverflow.net/questions/45106/quantum-pcp-theorem
Tsuyoshi Ito
3
Eu gostaria de saber qual é a melhor abordagem para provar ou refutar um teorema quântico do PCP. O problema é que, se eu soubesse, já o teria provado ou refutado.
Tsuyoshi Ito
2
Desculpe, eu vou fechar a pergunta. Alguém me disse para postar aqui. mas, para responder à pergunta de Robin, minha pesquisa tem a ver com a aplicabilidade desses chamados algoritmos DMRG, e foi assim que me deparei com a conjectura QPCP (depois de ter apresentado uma aula para um seminário sobre os vários problemas completos de QMA de Kitaev)

Respostas:

8

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.

hastings mate
fonte
6
O teorema clássico do PCP diz que todas essas perguntas são pelo menos difíceis de NP.
Peter Shor
6

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.

Alessandro Cosentino
fonte