Separando NP do BQP em relação a um oráculo

Eu estava olhando para esta nota de aula em que o autor faz uma separação entre oracle e . Ele sugere como "técnicas padrão de diagonalização podem ser usadas para tornar isso rigoroso".$\mathsf{BQP}$$\mathsf{NP}$

Alguém pode detalhar uma técnica de diagonalização que deve ser usada? Intuitivamente, deve haver diferenças importantes entre as usadas para colocar algo fora das classes de complexidade clássica e as usadas para colocar algo fora de . Especificamente, dado que o algoritmo de Grover é ideal, estou procurando uma técnica de diagonalização para que possamos construir um oráculo para o qual .$\mathsf{BQP}$$A$$\mathsf{NP}^{A} \not\subseteq \mathsf{BQP}^{A}$

Parece-me que os argumentos de diagonalização que podem ser usados ​​são apenas ligeiramente diferentes dos argumentos padrão, por exemplo  , os que podem ser encontrados nessas notas de aula sobre o Teorema de Baker – Gill – Solovay ( ou seja , que existem oráculos para os quais e também oráculos para os quais ). Basicamente, você deve descrever como 'projetar' uma entrada do adversário de maneira um pouco diferente.$A$$\mathsf P^A = \mathsf{NP}^A$$A$$\mathsf P^A \ne \mathsf{NP}^A$

Veja como podemos usar essa abordagem para provar a existência de um oráculo para o qual . Para qualquer oráculo , defina um idioma Está claro que pela simples razão de que uma máquina de Turing não determinística pode examinar se a entrada tem o formato para alguns e, em seguida, adivinhar uma string para o qual se esse existir. O objetivo é mostrar que$A$$\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$$A$

$$L_A = \Bigl\{ 1^n \;\Big\vert\; \exists z \in \{0,1\}^n : A(z,0) = (z,1)\Bigr\} .$$ $L_A \in \mathsf{NP}^A$$1^n$$n$$z \in \{0,1\}^n$$A(z,0) = (z,1)$$z$$L_A$não pode ser decidido em tempo polinomial, com erro limitado, por uma família de circuitos unitários uniforme, usando o limite inferior no problema de pesquisa.$O(2^{n/2})$

1. Seja tal que o problema de pesquisa em oráculos com entradas de bits exija pelo menos consultas oracle para decidir corretamente (com probabilidade de pelo menos 2/3), para todos os .$c,N > 0$$n$$c 2^{n/2}$$n > N$
   
   

2. Vamos,, ser uma enumeração de todas as famílias unitárias de circuitos oracle , de modo que a sequência da porta do circuitoatuar em entradas de bits pode ser produzido em tempo estritamente menor que . (Esse tempo limite refere-se à condição de 'uniformidade', na qual estaremos interessados ​​em circuitos podem ser calculados por uma máquina de Turing determinística em tempo polinomial - uma condição mais forte do que a que impomos aqui. A enumeração dessas famílias de circuitos poderia ser feita, por Por exemplo, representando-os indiretamente pelas máquinas determinísticas de Turing$\mathbf C^{(1)}\!$$\mathbf C^{(2)}\!$$\ldots$$\mathbf C^{(k)} \!= \{ C^{(k)}_n \}_{n \geqslant 0 }$$C^{(k)}_n\!$$n$$c 2^{n/2}$$\mathbf T^{(k)}$ , que produzem as suas sequências de porta, e enumerando aqueles .) Nós enumerar as famílias de circuito de modo a que cada família circuito ocorre infinitamente muitas vezes na enumeração.

   • A partir dos limites de tempo de execução na descrição da sequência do gate, segue-se, em particular, que possui menos de portas para todos os e, em particular, produz menos que consultas ao oráculo.$C^{(k)}_n$$c 2^{n/2}$$k$$c 2^{n/2}$

   • Para qualquer , considere o circuito. Pelo limite inferior do problema de pesquisa, sabemos que para existem valores possíveis da função oracle avaliada pelo oracle, como que com probabilidade 2/3, a saída produzida porna entrada não é a resposta correta para se .$n$$C^{(n)}_n\!$$n > N$$f: \{0,1\}^n \to \{0,1\}$$C^{(n)}_n\!$$1^n$$\exists z \!\in\! \{0,1\}^n\!:\! f(z) \!=\! 1$

   • Para cada , selecione a função para a qual "falha" dessa maneira.$n > N$$f_n$$C^{(n)}_n$
     
     

3. Seja um oráculo que, nas entradas de tamanho , avalia .$A$$n > N$$f_{\!\!\:n\!\:}$

Tendo construído dessa maneira, cada família de circuitos falha em decidir corretamente com probabilidade de pelo menos 2/3, para alguns (e infinitamente muitos desses de fato). Então, nenhuma das famílias de circuitos decide corretamente com probabilidade de sucesso limitada abaixo de 2/3 em todas as entradas, de modo que não possa ser resolvido com tais limites por nenhuma família uniforme de circuitos unitários construtível no tempo .$A$$\mathbf C^{(n)}$$L_A$$n > N$$n$$\mathbf C^{(k)}$$L_A$$L_A$$p(n)$

Assim, , a partir do qual se segue que .$L_A \notin \mathsf{BQP}^A$$\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$