Construção Oracle para o algoritmo de Grover

16

No "Quantum Computation and Quantum Information" de Mike e Ike, o algoritmo de Grover é explicado em grande detalhe. No entanto, no livro e em todas as explicações que encontrei on-line para o algoritmo de Grover, parece não haver menção de como o Oracle de Grover é construído, a menos que já saibamos qual o estado que estamos procurando, derrotando o objetivo do algoritmo. Especificamente, minha pergunta é a seguinte: dados alguns f (x) tais que, para algum valor x, f (x) = 1, mas para todos os outros f (x) = 0, como alguém constrói um oráculo que nos tirará nosso estado inicial arbitrário | x> | y> a | x> | y + f (x)>? O máximo de detalhes explícitos possível (talvez um exemplo?) Seria muito apreciado. Se tal construção para qualquer função arbitrária for possível com Hadamard, Pauli ou outros portões quânticos padrão,

Vai
fonte
"aqui parece não haver menção de como o Oracle de Grover é construído, a menos que já saibamos qual é o estado que estamos procurando, derrotando o objetivo do algoritmo." ... "O Oracle de Grover" é o problema a ser resolvido. Você não constrói. Você recebe (acesso da Oracle) e é solicitado a executar o cálculo para descobrir o valor. Se ajudar, finja que eu construo o oráculo e peça para você resolver o problema. (Além disso, nota que a leitura / escrita / preparar um banco de dados de itens leva mais tempo do que correr de Grover -time algoritmo.)NN
Daniel Apon
2
Mas e se, em vez de recebermos o oráculo, recebermos f (x)? Imagine que estamos resolvendo um problema 3-SAT e queremos usar o Grover's para fornecer uma aceleração à solução. Conhecemos o f (x) em questão (as cláusulas de verdade do 3-SAT), mas não sabemos necessariamente qual sequência de bits x produzirá um resultado verdadeiro quando conectado ao 3-SAT. Não deve haver uma maneira de construir um oráculo a partir da função 3-SAT para encontrar a sequência de bits correta? Se não houver, e é como você sugere, algo a ser fornecido por outra pessoa, o algoritmo de Grover parece bastante artificial, apenas um exercício dado a você.
Will

Respostas:

20

O oracle é basicamente apenas uma implementação do predicado para o qual você deseja procurar uma solução satisfatória.

Por exemplo, suponha que você tenha um problema de três sat:

(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)

Ou, na forma de tabela, com cada linha sendo uma cláusula de 3, x significa "essa variável falsa", o significa "essa variável verdadeira" e espaço significa "não na cláusula":

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Agora faça um circuito que calcule se a entrada é uma solução, assim:

verificador de solução

Agora, para transformar seu circuito em um oráculo, acerte o bit de saída com uma porta Z e não calcule o lixo que você fez (por exemplo, execute o circuito de computação na ordem inversa):

circuito oracle

É tudo o que há para isso. Calcule o predicado, acerte o resultado com um Z, não calcule o predicado. Isso é um oráculo.

Itere as etapas de difusão com as etapas do oracle, e você terá uma pesquisa grover :

pesquisa grover

... embora você deva provavelmente escolher um exemplo com menos soluções, o progresso é gradual (em vez de girar ao longo do plano de estado de solução-estado de solução em mais de 90 graus por etapa, como é o meu exemplo).

Craig Gidney
fonte
Obrigado, isso foi imensamente útil. Incrivelmente claro, respondeu tudo o que eu pedi (e até mesmo usei portões quânticos comuns!) Existe alguma razão para você decidir mudar todos os seus qubits iniciais para o estado | 1> antes de colocá-los em superposição com os portões Hadamard em vez de apenas colocar o | 0 > qubits estatais através do Hadamards (isto é, há alguma vantagem nisso)? Além disso, que operação é essa para suas etapas de difusão? Parece um X controlado, mas você está usando | 1> ou | 0> como controle?
18717
@Eu usei um estado inicial diferente. Você pode fazer isso desde que também altere o estado negado pelo operador de difusão (eles precisam corresponder). Todos os estados de partida / difusão que têm distância de ângulo igual a todo estado de base computacional funcionam igualmente bem. O pequeno controle com mais círculos no meu diagrama é um "controle do eixo X", que é equivalente a um controle normal cercado pelos portões Hadamard. Parece um NÃO porque eles são intercambiáveis . Meu estado inicial / difusão é . (12|012|1)n
Craig Gidney
Resposta fantástica e obrigado pelo link para algassert.com/quirk !
Frédéric Grosshans