O algoritmo de Grover é usado, entre outras coisas, para pesquisar um item em uma lista não ordenada de itens $\mathbf{y}$ $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ de comprimento . Embora haja muitas perguntas aqui sobre esse tópico, ainda não entendi o ponto. $n$

Pesquisando em uma lista, da maneira clássica

Normalmente, eu projetaria uma função de pesquisa dessa maneira Portanto, dou a lista e o item desejado como entradas e recebo a posição do item na lista como saída. Eu acho que entendi que as informações sobre estão incorporadas no algoritmo através do oracle gate , então nossa função se torna Vamos fazer um exemplo prático. Considere pesquisar o ás de espadas

s e a r c h ([x_{0}, x_{1}, . . ., x_{n - 1}], y) = i \in N such that x_{i} = y

$\mathrm{search}([\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}], \mathbf{y}) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$

y

$\mathbf{y}$

O

$O$

{s e a r c h}_{y} ([x_{1}, x_{2}, . . ., x_{n}]) = i \in N such that x_{i} = y

$\mathrm{search}_\mathbf{y}([\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n] ) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$

1 ♠

$1\spadesuit$ em uma sequência de 8 cartas de um baralho de 52 cartas padrão :

A lista de comprimento é . $8$ $[ \mathbf{x}_0 = J\clubsuit,$ $\mathbf{x}_1 = 10\diamondsuit,$ $\mathbf{x}_2 = 4\heartsuit,$ $\mathbf{x}_3 = Q\clubsuit,$ $\mathbf{x}_4 = 3\spadesuit,$ $\mathbf{x}_5 = 1\spadesuit,$ $\mathbf{x}_6 = 6\spadesuit,$ $\mathbf{x}_7 = 6\clubsuit]$

O elemento desejado é . Eu deveria obter . Cada placa pode ser codificada com bits, a lista possui elementos, portanto precisamos de bits para codificar a lista. Nesse caso, o oráculo $\mathbf{x}_5$ $\mathrm{search}_{\spadesuit}(cards) = 5$ $\lceil{\log_2 52}\rceil = 6$ $8$ $6\times 8 = 48$ $O$ implementará a função:

f (x) = {\begin{cases} 1, & x = 1 ♠ \\ 0, & otherwise \end{cases}

$f(\mathbf{x}) = \begin{cases} 1, & \mathbf{x} = 1\spadesuit \\ 0, & \text{otherwise} \end{cases}$

Entretanto, a entrada do algoritmo de Grover não é um estado de $48$ qubits.

(Nota: a imagem do baralho embaralhado é tirada daqui )

Grover e seu oráculo

Várias fontes (por exemplo, aqui - explicadas graficamente) dizem que a entrada do algoritmo é diferente: a entrada é um estado retirado do espaço de pesquisa onde $S = \{ 0, 1, 2, ..., N \} = \{0, 1, 2, ..., 7 \}$ $N$ é o número de elementos da lista. Cada número corresponde à posição de um elemento na lista.

A entrada de agora é um vetor de qubit , que deve ser uma superposição de todos os itens no espaço de pesquisa $\mathrm{search}_{\spadesuit}(\cdot)$ $\lceil \log_2 8 \rceil = 3$ $|\psi\rangle$ $S$ .

Nós sabemos

$|0_{3\text{qubits}}\rangle = |000\rangle$ corresponde a $J\clubsuit$ ;
$|1_{3\text{qubits}}\rangle = |001\rangle$ corresponde a ; $10\diamondsuit$
$|2_{3\text{qubits}}\rangle = |010\rangle$ corresponde a ; $4\heartsuit$
$|5_{3\text{qubits}}\rangle = |101\rangle$ corresponde a que é o elemento desejado; $1\spadesuit$
e assim por diante...

Nesse caso, temos Mas, neste caso, nosso oráculo teria que implementar a função

{s e a r c h}_{♠} (| ψ ⟩) = | 5_{3 qubits} ⟩

$\mathrm{search}_{\spadesuit}(|\psi\rangle) = |5_{3\text{qubits}}\rangle$

f (| ψ ⟩) = {\begin{cases} 1, & | ψ ⟩ = | 5_{3 qubits} ⟩ \\ 0, & otherwise \end{cases}

$f(|\psi\rangle) = \begin{cases} 1, & |\psi\rangle = |5_{3\text{qubits}}\rangle \\ 0, & \text{otherwise} \end{cases}$

Construir o oráculo exige que saibamos que está na posição 5. Qual é o sentido de executar o algoritmo se já tivermos pesquisado o elemento para construir o oráculo? $\spadesuit$

grovers-algorithm incudir
fonte

Também tenho dificuldade em entender a vantagem do algoritmo de Grover. Suponha que eu tenha N itens na lista. Em cada chamada para o Oracle, ele avaliava todas as N possibilidades? Mesmo que a avaliação seja muito rápida, mas se ainda precisarmos iterar todas as configurações, a complexidade da avaliação do Oracle é O (N). Portanto, o algoritmo de Grover não parece ser mais rápido que a pesquisa idiota. Isso está correto?

Sanparith Marukatat

@SanparithMarukatat Não está correto. Os itens da sua lista são os termos da superposição do estado envolvido na pesquisa. Quando o Oracle opera nesse estado, conta como uma única operação. A capacidade do Oracle para marcar o termo pesquisado de sua superposição é uma parte fundamental da percepção de Grover. Para entender o algoritmo de Grover, eu recomendo que você primeiro entenda como essa marcação do estado desejado acontece. Depois, certifique-se de entender o papel do estado no Oracle.

| - ⟩

$|- \rangle$

R. Chopin

Se você entende isso, deve estudar o operador que é capaz de aumentar a amplitude do termo desejado na superposição e, ao mesmo tempo, diminuir a amplitude dos termos indesejados da superposição. Para mim, a maneira mais fácil de abordar a de Grover é olhar para o operador inverso da média. (Algumas pessoas consideram geométrica, mas eu não encontrá-lo tão claro.)

R. Chopin

10

Se você tiver 8 itens na lista (como no exemplo do seu cartão), a entrada do oracle é de 3 (qu) bits. O número de cartões no baralho (52) é irrelevante, você precisa de 3 bits apenas para codificar 8 cartões.

Você pode pensar que 3 bits codificam a posição na lista do cartão que você está procurando; então você não sabe a posição, mas o oráculo sabe. Portanto, se você estiver pesquisando o ás de espadas, o oráculo saberá que o ás de espadas é a sexta carta (ou a quinta contando a partir de zero) e implementa a função

f (x) = {\begin{cases} 1, & if x = 5, or binary '101' \\ 0, & otherwise \end{cases}

$f(\mathbf{x}) = \begin{cases} 1, & \text{if x = 5, or binary '101'} \\ 0, & \text{otherwise} \end{cases}$

PS: É melhor pensar no algoritmo de Grover de maneira diferente: você tem um oracle implementando uma função booleana que gera para uma única combinação de bits de entrada, caso contrário, gera zero, e sua tarefa é encontrar a combinação. O problema tem a mesma complexidade da pesquisa em uma lista ou banco de dados não classificado, é por isso que o algoritmo de Grover é geralmente descrito como pesquisa em um banco de dados não classificado. Mas aplicar o algoritmo a uma pesquisa no banco de dados do mundo real realmente levanta questões que estão além do próprio algoritmo. O algoritmo de Grover está apenas procurando o que o oráculo sabe. $1$

kludg
fonte

Sim desculpe, esse 6 era de uma edição anterior

incorreto

2

Obrigado pela sua resposta. Corrigi a escrita errada. Qual é o sentido de executar o algoritmo se, para construir o oráculo, preciso saber a posição do elemento pesquisado?

incorreto

1

@incud De fato, não faz sentido. Eu atualizei a resposta.

Kludg

" O algoritmo de Grover está apenas procurando o que o oráculo sabe ": não necessariamente. O oracle pode estar verificando apenas algumas propriedades específicas da entrada, para que o resultado obtido no final contenha mais informações do que as codificadas no próprio oracle. Um exemplo típico é pesquisar em uma lista telefônica. O oráculo "pede" um registro anexado a um nome específico, mas uma vez que o registro correto seja encontrado, também é possível obter informações adicionais do número de telefone anexado a esse registro, que não foi codificado no oracle

glS

4

Embora talvez seja mais fácil pensar na função do oráculo como já tendo calculado todos esses valores, não é isso que está fazendo. No caso descrito, o oracle possui 8 entradas possíveis (ou seja, codificadas em 3 (qu) bits), e o oracle faz todo o cálculo necessário em tempo real . Portanto, no momento em que você tenta avaliar o oráculo por algum valor , o oráculo procura (nesse caso) a carta que o valor de $x$ $x$ corresponde a e, em seguida, verifica se esse cartão é o cartão marcado. A idéia é que cada vez que você chama o oráculo, ele passa por esse processo uma vez. No geral, você avalia a função várias vezes que é igual ao número de vezes que chama o oráculo. O objetivo de qualquer algoritmo de busca é chamar esse oráculo o menor número de vezes possível.

Caso isso pareça um pouco circular (dada uma entrada , encontre qual cartão corresponde), lembre-se de que sua tabela de consulta para qual corresponde a qual cartão pode ser solicitada $x$ $x$ que é uma pergunta de pesquisa diferente, mais simples e muito mais rápida.

As principais diferenças em seu exemplo em comparação com um cenário de uso mais realista são:

O espaço de pesquisa geralmente é enorme. Não existe uma perspectiva realista de pré-computar todos os valores. Na verdade, é exatamente isso que estamos tentando evitar.
Normalmente, na verdade não dizemos 'encontre o ás de espadas'. Em vez disso, há um que não é trivial para avaliar para testar se é o item 'marcado' ou não. O fato de o oráculo levar muito tempo para avaliar, mesmo para uma única entrada, é o que torna o oráculo a parte mais cara a ser implementada (e todos os outros portões são fornecidos gratuitamente) e por que você precisa minimizar o número de chamadas . $f(x)$ $x$

Então, realmente, a maneira como uma pesquisa clássica funcionaria no seu problema é: escolha um aleatoriamente. Avalie . Se , retorne , caso contrário, repita. Enquanto o efeito líquido de é 'é a entrada , a entrada marcada?', Esse não é o cálculo real que ele faz. $x$ $y=f(x)$ $y=1$ $x$ $f(x)$ $x_0$

DaftWullie
fonte

2

A questão é, em última análise: "Qual é o sentido de executar o algoritmo se já pesquisamos o elemento para construir o oráculo?"

Enquanto alguém pré-construiu o oráculo, pode não ter sido a pessoa que o usou.

$\sqrt{\text{size of list}}$ . Naturalmente, não podemos esperar pesquisas de banco de dados respectivas, como proposto anteriormente, contra as quais não posso comentar por falta de reputação, por exemplo, 5 milhões de chaves retornarão o conteúdo que queremos se nosso conteúdo não for abordado por nenhuma dessas 5 milhões de chaves, mas dizendo o Chave milionésima, que por acaso não está em nossa amostra. Como o algoritmo de Grover faz isso então?

Perguntamos ao oráculo: qual é a resposta que ele já tem para a pergunta que já tem? Até Mateus e Omar perguntariam o "oráculo para um símbolo de alfabeto particular" durante o tempo de execução, quais são as posições de seu símbolo na string que ele já compilou? O oráculo dará a resposta para a nossa consulta após apenas uma consulta, mas nesta história, ele não pode, por exemplo, simplesmente escrever a resposta como uma sequência binária e enviá-la para nós através de um canal de comunicação clássico. Esconderá sua resposta em uma superposição para que possamos extraí-la.

Deixei que a fantasia ou a metáfora fuja nesta próxima parte: não ouvimos a resposta da primeira vez e precisamos pedir ao oráculo que repita a mesma resposta repetidamente até ter certeza do que o oráculo disse: exceto que começamos a alucinar da desinformação no processo de difusão, se pedirmos muitas vezes.

Brendan M
fonte

2

Dado o oráculo que você forneceu, a pesquisa é realmente inútil. No entanto, esse oráculo perde o objetivo do algoritmo de Grover, porque procurar uma carta em um baralho de cartas não é uma busca não estruturada, porque, como você afirmou, você já conhece a ordem. Portanto, sua pesquisa está estruturada. A razão pela qual esse oráculo é usado é que ele demonstra como o Grover pode ser aplicado sem ter que discutir um oráculo que tornaria Grover útil, porque esse oráculo seria mais complicado do que valioso. Portanto, um oráculo melhor para demonstrar a utilidade de Grover pode ser algo como:

f (x) = {\begin{cases} 1, & x [0, \dots, 3] + x [4, \dots, 7] = 1010 \\ 0, & otherwise \end{cases}

$f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & \text{otherwise} \end{cases}$

O que esse oráculo implica é que você tem uma pesquisa de 8 qubit, na qual você pega os quatro primeiros qubits e os adiciona aos quatro qubits seguintes e vira M se a adição fizer 10 (1010 em binário). A diferença entre esse oráculo e o que você forneceu é que esse oráculo testa um padrão (os operandos somam 10) enquanto o seu testa a igualdade (esse é o índice 5). Esse oráculo é muito mais difícil de construir, mas aproveita o verdadeiro poder do Grover, que é, em essência, uma busca por força bruta em que seu oráculo define o espaço de busca.

Woody1193
fonte

Algoritmo de Grover: onde está a lista?

Pesquisando em uma lista, da maneira clássica

Grover e seu oráculo

Respostas: