Construção Oracle para o algoritmo de Grover

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,

quantum-computing quantum-information oracles search-problem black-box 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.)

N

$N$

\sqrt{N}

$\sqrt{N}$

Daniel Apon

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:

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:

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):

É 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 :

... 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 é .

(\frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩)^{\otimes n}

$(\frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} |1\rangle)^{\otimes n}$

Craig Gidney

Resposta fantástica e obrigado pelo link para algassert.com/quirk !

Frédéric Grosshans