O oráculo no algoritmo de Grover precisa conter informações sobre a totalidade do banco de dados?

8

O algoritmo de Grover é frequentemente descrito como uma maneira de pesquisar um banco de dados em O(N)tempo. Para usá-lo, precisamos de um oracle gate que represente alguma funçãofmodo quef1(1)seja a resposta. Mas como você realmente faz um "oráculo de banco de dados"?

Suponha que eu tenho uma matriz de números a que contém w exatamente uma vez e preciso encontrar o índice de w . Em um computador clássico, eu carregava a matriz na memória e percorria-a até encontrar w .

Por exemplo, se a=[3,2,0,1,2,3] e w=0 , I esperar obter 2 como a resposta (ou 3 em 1-indexação).

Como eu represento essa matriz em um computador quântico e faço um gate que retorna ax para algum x ?

Em particular, você precisa ter a totalidade do "banco de dados" na memória quântica (assumindo que existem algumas maneiras de acessar registros clássicos a partir de portas quânticas)?

Norrius
fonte

Respostas:

5

Não, não tem.

O " oráculo " no algoritmo de Grover é uma função que, dado qualquer elemento , verifica se é o elemento que estamos procurando, digamos . Para fazer isso, o oracle não precisa de nenhum conhecimento de todos os outros elementos que estão no banco de dados .x k x alvo x jxkxkxtargetxj

Pode ajudar a considerar um exemplo mais concreto. Digamos que você tenha um banco de dados com números de telefone de quatro dígitos, com indicando o elemento nesse banco de dados. Você está interessado em saber qual posição no banco de dados corresponde ao elemento . Vamos supor que o elemento 10000 do banco de dados seja o único elemento, ou seja, e para todos os .x k k 1234 x 10000 = 1234 x k1234 k 1000020000xkk1234x10000=1234xk1234k10000

No caso clássico, sendo o banco de dados não classificado, não há maneira melhor do que passar por todos os elementos do banco de dados, comparando cada um com o alvo . Para fazer isso, você só precisa ter um algoritmo que, dado , retorne se e caso contrário. Uma maneira equivalente de afirmar esse problema é dizer que queremos um algoritmo que, dada uma lista de pares , retorne o par de modo que é o que queremos. Assim, no nosso caso, queremos um algoritmo que, retornex k sim x k = 1234 não { ( k , x k ) } 20000 k = 1 x k { ( k , x k ) } 20000 k = 1 ( 10000 , x 10000 = 1234 ) x k1234xkyesxk=1234no{(k,xk)}k=120000xk{(k,xk)}k=120000(10000,x10000=1234). Observe que isso significa que a função que verifica cada par verifica apenas os recursos de uma parte do estado , ou seja, a parte . De fato, se esse não fosse o caso, tudo seria inútil, porque não estaríamos recuperando nenhuma informação.xk

Esse último enquadramento do problema é aquele que se deve ter em mente ao pensar no algoritmo de Grover.

No caso quântico, os pares se tornam os estados quânticos (ou apenas como geralmente são indicados), e a função oracular verifica apenas essa parte da informação armazenada em corresponde ao destino . A saída do procedimento é o estado . Agora, parte desse estado já sabemos , porque foi codificada no oráculo: sabemos que a segunda parte da informação codificada em é(k,xk)|ψk|k|ψk|ψ10000|ψ100001234, porque é isso que estávamos procurando em primeiro lugar e são as informações que foram codificadas no próprio oráculo. No entanto , o estado também carrega informações adicionais , ou seja, a posição no banco de dados: . Esta informação não foi usada para construir o oráculo e é a informação que obtemos ao executar o algoritmo.|ψ10000 10000

Por fim, observe que o oracle não sabe nada sobre o conteúdo do banco de dados completo. Ele apenas implementa coerentemente uma função que verifica um único estado relação ao seu destino. No entanto, o fato de esse portão funcionar de forma coerente significa que é possível inserir nesse verificador uma superposição de muitos (possivelmente todos) os elementos do banco de dados e obter uma saída que contenha algumas informações globais sobre todos os elementos no banco de dados.|ψk

glS
fonte
1

ff(x)xw

pirâmides
fonte
Existe uma maneira de representá-lo em circuitos ou matrizes de operador ou em alguma outra forma mais concreta? Estou um pouco confuso sobre como você faz para acessar uma entrada específica.
Norrius 28/03
Como a entrada é uma informação clássica (bits em vez de qubits, apenas codificados como qubits), pode-se simplesmente "copiá-los" com CNOTs. Essa não é uma cópia verdadeira, mas uma emaranhada, mas que é boa o suficiente para isso. É importante não calcular a cópia (novamente com CNOTs), caso contrário, o algoritmo de Grover não funcionará.
pyramids