Algoritmo de Grover: o que inserir no Oracle?

Estou confuso sobre o que inserir no Oracle no algoritmo de Grover.

Não precisamos inserir o que estamos procurando e onde encontrar o que estamos procurando para a Oracle, além dos estados quânticos sobrepostos?

Por exemplo, suponha que tenhamos uma lista de nomes de pessoas {"Alice", "Bob", "Corey", "Dio"} e queremos descobrir se "Dio" está na lista. Em seguida, a Oracle deve tomar como uma entrada e saída de . Eu meio que entendo isso. $1/2(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$

Mas também não precisamos inserir a palavra "Dio" e a lista {"Alice", "Bob", "Corey", "Dio"} no Oracle? Caso contrário, como o Oracle pode retornar a saída? Não é mencionado explicitamente, pois o Oracle é uma caixa preta e não precisamos pensar em como implementá-lo?

Meu entendimento sobre Oracle é,

A Oracle tem a capacidade de reconhecer se a palavra "Dio" está na lista.
Para fazer isso, o Oracle usa os estados quânticos sobrepostos como uma entrada, onde cada estado quântico representa o índice da lista.
Então, insira aos meios da Oracle, verifique se a palavra "Dio" está no índice 0 da lista e retorno se sim e retorno contrário. $|00\rangle$ $-|00\rangle$ $|00\rangle$
No nosso caso, a Oracle retorna . $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$
Mas e a lista e a palavra?

algorithm grovers-algorithm oracles Bick
fonte

Embora não seja formulada da mesma maneira, acredito que sua pergunta é mais ou menos a mesma: Esta: o algoritmo de Grover: onde está a lista?

DaftWullie

Respostas:

$O(\sqrt{N} \cdot F)$ $N$ $F$

$N$ $F$ $O(N)$ $O(\sqrt{N} \cdot F) = O(\sqrt{N} \cdot N) = O(N^{1.5})$ $N^{1.5} > N$

Craig Gidney
fonte

O (\sqrt{N} \log (N))

$O(\sqrt{N}\log(N))$

@DaftWullie O problema é que Grover deve fazer uma pesquisa sob superposição, e isso requer um circuito multiplexador com portas N AND (ou outras operações que não sejam de Clifford). Um portão quântico AND (ou seja, um Toffoli) tem um custo não desprezível ao executar a correção de erros. Tecnicamente, esse custo também está presente na máquina clássica (ou seja, a RAM possui portas O (N) AND)), mas é desprezível e até evitável nesse contexto.

Craig Gidney

Eu não entendo o que você está dizendo. Você seria capaz de expressar uma pergunta e respondê-la para mostrar os detalhes? (Eu não acho que posso formular uma pergunta boa o suficiente neste momento)

DaftWullie

@DaftWullie Acho que a pergunta seria algo como "como faço para dar a um computador quântico acesso de leitura a um banco de dados clássico e quão caro é".

Craig Gidney