Lendo sobre

O que devo ler para entender esse problema?

O poder dos circuitos quânticos de pequena profundidade. Is ? Em outras palavras, a parte "quântica" de qualquer algoritmo quântico pode ser compactada até a profundidade do polilog (n), desde que desejemos realizar um pós-processamento clássico em tempo polinomial? (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 e , mas a questão é se existe alguma função concreta "instanciando" esse oráculo. - Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html$BQP = BPP^{BQNC}$$BQP$$BPP^{BQNC}$

Isso foi conjecturado por R. Jozsa na Seção 8 do arXiv: quant-ph / 0508124 . Se você já está familiarizado com a computação quântica e a teoria da complexidade quântica, pode começar lendo essa seção.

Uma leitura importante é arXiv: quant-ph / 0006004 , onde Cleve e Watrous mostram que o algoritmo de Shor está nessa classe.