Se P = BQP, isso implica que PSPACE (= IP) = AM?

Recentemente, Watrous et al provaram que QIP (3) = PSPACE é um resultado notável. Este foi um resultado surpreendente para mim, para dizer o mínimo, e isso me fez pensar ...

Eu me perguntava e se os Computadores Quânticos pudessem ser eficientemente simulados pelos Computadores Clássicos. Isso poderia estar SIMPLESMENTE relacionado à divisão entre IP e AM? O que quero dizer é que IP é caracterizado pelo número polinomial de rodadas de interação clássica, enquanto AM possui 2 rodadas de interação clássica. A simulação de uma computação quântica reduziu a quantidade de interação para IP do polinômio para um valor constante?

Ótima pergunta! Resposta curta: nenhuma implicação como é conhecida; mas isso não significa que não vale a pena tentar provar ...

Eu diria, no entanto, que encontrar tal implicação parece improvável. Penso que a mensagem da teoria da complexidade quântica é que, embora os computadores quânticos não sejam uma panacéia para todos os fins na solução de problemas difíceis, eles podem ser muito mais poderosos que os computadores clássicos em determinadas circunstâncias específicas.

Por exemplo, na complexidade das consultas, os algoritmos quânticos podem resolver com eficiência certos problemas que os clássicos provavelmente não podem, quando é prometido que a entrada obedece a uma boa estrutura global. Por exemplo, o algoritmo de Shor é baseado em um algoritmo para encontrar rapidamente o período desconhecido de uma função que promete ser periódica. Por outro lado, os algoritmos de consulta quântica não são muito mais fortes do que os clássicos para resolver problemas nos quais não há uma estrutura especial assumida na entrada. (Veja Buhrman e de Wolf levantamento da complexidade de consulta para este último ponto.)

Da mesma forma, acho que os resultados nos dizem, não que a interação seja inesperadamente fraca (mesmo que P = B Q P ), mas que a computação quântica seja inesperadamente forte,especificamenteno contexto de interação com provadores computacionalmente ilimitados.$\mathsf{QIP}(3) = \mathsf{QIP} = \mathsf{IP}$$\mathsf{P} = \mathsf{BQP}$

Concordo com o que Andy escreveu e queria que essa "resposta" fosse um comentário para a resposta dele, mas é evidentemente longo demais para um comentário ...

De qualquer forma, pode ser útil dizer algo mais sobre que aspecto da computação quântica (ou talvez informações quânticas) permite provar a contenção do PSPACE no QIP (3). As provas conhecidas dessa contenção não decorrem da capacidade do verificador de calcular funções que são computáveis ​​em tempo polinomial quântico. Uma explicação mais precisa é que as provas fazem uso de maneiras específicas pelas quais um provador pode manipular estados quânticos emaranhados que compartilha com o verificador. Se o provador não fosse capaz de manipular informações quânticas, ou se de alguma forma pudesse manipular magicamente estados emaranhados compartilhados de maneira mais forte do que a teoria da informação quântica permite, as provas não funcionariam.

Então, na minha opinião, a contenção do PSPACE no QIP (3) não diz nada sobre a relação entre AM e PSPACE.

As respostas de John Watrous e Andy Drucker são excelentes para entender alguns dos problemas envolvidos.

Acrescentarei à resposta de Andy que não apenas essa implicação é conhecida, mas mostrar que tal implicação requer técnicas de não relativização (das quais essencialmente apenas uma - aritmetização - é conhecida). Lance Fortnow e John Rogers [1] construíram um oráculo onde mas P H é infinito (e, em particular, isso significa P S P A $P = BQP$$PH$$PSPACE \supseteq PH \supset\neq AM$

Sabemos que $IP = PSPACE$

[1] L. Fortnow e J. Rogers. Limitações de complexidade na computação quântica . Journal of Computer and System Sciences, 59 (2): 240-252, 1999. Edição especial para trabalhos selecionados da 13ª Conferência IEEE sobre Complexidade Computacional. Também disponível aqui .

As outras respostas são excelentes, e isso não pretende substituir ou contradizer nenhuma delas, apenas para oferecer alguma intuição sobre por que P = BQP não implica necessariamente igualdade entre sistemas quânticos e clássicos de prova interativa (para rodadas fixas etc.). No entanto, sabemos agora que QIP = IP, graças ao trabalho de Jain, Ji, Upadhyay e Watrous, por isso certamente não estou tentando afirmar que essas igualdades nunca acontecem.

Se apenas assumirmos que P = BQP, aprenderemos apenas algo sobre quais problemas de decisão podem ser respondidos pelos modelos quântico e clássico. Não é o mesmo que sugerir que os modelos são realmente os mesmos. A principal diferença é que os computadores quânticos podem processar estados em superposição, o que significa que suas entradas e saídas não precisam ser restritas aos estados clássicos. Essa é uma diferença muito importante entre os modelos quântico e clássico, uma vez que a entrada / saída quântica possibilita consultar oráculos com superposições de estados clássicos ou comunicar estados quânticos (que podem ter descrições clássicas exponenciais) entre um verificador e um provador. De fato, existem oráculos que separam BQP de P e a comunicação quântica leva a uma complexidade de comunicação reduzida para vários problemas. Portanto,

Por esse motivo, a questão de se P = BQP não é o fator decisivo para se os modelos quântico e clássico são iguais em situações que fazem uso de consultas de comunicação / oráculo.