Separações oraculares entre circuitos quânticos de profundidade poli e logarítmica

16

O problema a seguir aparece na lista de Aaronson, Dez semi-grandes desafios para a teoria da computação quântica .

É BQP=BPPBQNC Em outras palavras, pode a parte "quantum" de qualquer algoritmo quântico ser comprimido para polylog(n) de profundidade, desde que está disposto para fazer polynomial- pós-processamento clássico? (Sabe-se que isso é verdade no algoritmo de Shor.) Nesse caso, construir um computador quântico de uso geral seria muito mais fácil do que se pensa! Aliás, não é difícil fazer uma separação do oráculo entre BQP e BPPBQNC , mas a questão é se existe alguma função concreta "instanciando" tal oráculo.

Foi conjecturado por Jozsa que a resposta para a pergunta é sim no '' modelo de computação quântica baseado em medição ": onde são permitidas medições locais, portões locais adaptáveis ​​e pós-processamento clássico eficiente. Veja também este post relacionado .

Pergunta . Gostaria de saber sobre as separações oraculares atualmente conhecidas entre essas classes (ou, pelo menos, a separação de oráculos a que Aaronson está se referindo).

Juan Bermejo Vega
fonte
5
Eu acho que o problema das árvores coladas é um bom candidato à separação. A intuição é que um computador clássico é essencialmente inútil para esta tarefa, e um circuito quântico de profundidade de polilógeno só pode alcançá-lo profundamente nas árvores coladas, mas você precisa alcançar o vértice de saída que é polinomialmente distante do vértice de entrada.
Robin Kothari

Respostas:

12

Peço desculpas; Eu era muito simplória quando escrevi isso. Embora eu acredite que seja possível provar uma separação do oráculo entre e B P P B Q N C usando as técnicas atuais, isso ainda não foi feito (12 anos depois de eu ter pensado sobre o problema pela primeira vez, em seguida, adiado!), e certamente valeria um trabalho para quem fez isso. Talvez sua postagem ajude a me motivar a finalmente resolver esse problema!BQPBPPBQNC

Scott Aaronson
fonte
1
Entendo, obrigado Scott. Bem, eu pessoalmente gosto disso BQP = BPP ^ BQNC? questão, devido à sua importância na construção de computadores quânticos. Eu acho que vale a pena pensar um ou dois.
Juan Bermejo Vega
1
Esta questão parece ter sido resolvida: consulte arXiv: 1909.10303 e arXiv: 1909.10503 .
Sanketh Menda 8/12/19