O problema de Simon - Simon's problem

Na teoria da complexidade computacional e na computação quântica , o problema de Simon é um problema computacional comprovado para ser resolvido exponencialmente mais rápido em um computador quântico do que em um computador clássico (isto é, tradicional). O algoritmo quântico que resolve o problema de Simon, geralmente chamado de algoritmo de Simon , serviu de inspiração para o algoritmo de Shor . Ambos os problemas são casos especiais do problema do subgrupo oculto abeliano , que agora é conhecido por ter algoritmos quânticos eficientes.

O problema é definido no modelo de complexidade de árvore de decisão ou complexidade de consulta e foi concebido por Daniel Simon em 1994. Simon exibiu um algoritmo quântico que resolve o problema de Simon exponencialmente mais rápido e com exponencialmente menos consultas do que o melhor algoritmo clássico probabilístico (ou determinístico). Em particular, o algoritmo de Simon usa um número linear de pesquisas e qualquer algoritmo probabilístico clássico deve usar um número exponencial de pesquisas.

Este problema produz uma separação oráculo entre as classes de complexidade BPP (complexidade de consulta clássica de erro limitado) e BQP (complexidade de consulta quântica de erro limitado). Esta é a mesma separação que o algoritmo de Bernstein-Vazirani consegue, e diferente da separação fornecida pelo algoritmo de Deutsch-Jozsa , que separa P e EQP . Ao contrário do algoritmo de Bernstein-Vazirani , a separação do algoritmo de Simon é exponencial .

Como esse problema pressupõe a existência de um oráculo de "caixa preta" altamente estruturado para obter sua aceleração, esse problema tem pouco valor prático. No entanto, sem tal oráculo, acelerações exponenciais não podem ser facilmente provadas, pois isso provaria que P é diferente de PSPACE .

Descrição do Problema

Dada uma função (implementada por uma caixa preta ou oráculo) com a promessa de que, para algum desconhecido , para todos , ${\ displaystyle f: \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \} ^ {n}}$${\ displaystyle s \ in \ {0,1 \} ^ {n}}$${\ displaystyle x, y \ in \ {0,1 \} ^ {n}}$

${\ displaystyle f (x) = f (y)}$se e somente se ,${\ displaystyle x \ oplus y \ in \ {0 ^ {n}, s \}}$

O objetivo é identificar s fazendo o mínimo de consultas possível a f (x) .

Outra afirmação comum desse problema é distinguir o caso, em que a função é um-para-um, do caso em que a função é dois-para-um e satisfaz . ${\ displaystyle s = 0 ^ {n}}$${\ displaystyle s \ neq 0 ^ {n}}$${\ displaystyle f (x) = f (x \ oplus s)}$

Exemplo

Por exemplo, se , então a função a seguir é um exemplo de uma função que satisfaz a propriedade necessária e mencionada: ${\ displaystyle n = 3}$

${\ displaystyle x}$	${\ displaystyle f (x)}$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

Neste caso, (ou seja, a solução). Pode ser facilmente verificado que cada saída de ocorre duas vezes, e as duas strings de entrada correspondentes a qualquer saída dada têm XOR bit a bit igual a . ${\ displaystyle s = 110}$${\ displaystyle f}$${\ displaystyle s = 110}$

Por exemplo, as strings de entrada e são mapeadas (por ) para a mesma string de saída . e . Se aplicarmos XOR a 010 e 100, obteremos 110, ou seja${\ displaystyle 010}$${\ displaystyle 100}$${\ displaystyle f}$${\ displaystyle 000}$${\ displaystyle {\ displaystyle f (010) = 000}}$${\ displaystyle {\ displaystyle f (100) = 000}}$${\ displaystyle {\ displaystyle 010 \ oplus 100 = 110 = s}.}$

${\ displaystyle s = 110}$também pode ser verificado usando as strings de entrada 001 e 111 que são mapeadas (por f) para a mesma string de saída 010. Se aplicarmos XOR a 001 e 111, obteremos 110, isto é . Isso nos dá a mesma solução que resolvemos antes. ${\ displaystyle 001 \ oplus 111 = 110 = s}$${\ displaystyle s = 110}$

Neste exemplo, a função f é de fato uma função dois para um onde . ${\ displaystyle {\ displaystyle s \ neq 0 ^ {n}}}$

Para uma função um-para-um, de modo que${\ displaystyle f (x) = f (y)}$${\ displaystyle f (1) = 1, f (2) = 2, f (3) = 3, {\ text {e assim por diante}}.}$

Dureza do problema

Intuitivamente, este é um problema muito difícil de resolver de uma forma "clássica", mesmo que se use a aleatoriedade e aceite uma pequena probabilidade de erro. A intuição por trás da dureza é razoavelmente simples: se você deseja resolver o problema classicamente, precisa encontrar duas entradas diferentes e para quais . Não há necessariamente qualquer estrutura na função que nos ajude a encontrar duas dessas entradas: mais especificamente, podemos descobrir algo sobre (ou o que ela faz) somente quando, para duas entradas diferentes, obtemos a mesma saída. Em qualquer caso, precisaríamos adivinhar entradas diferentes antes de podermos encontrar um par com a mesma saída, de acordo com o problema do aniversário . Visto que, classicamente, para encontrar s com 100% de certeza, seria necessário verificar as entradas, o problema de Simon busca encontrar s usando menos consultas do que este método clássico. ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle f (x) = f (y)}$${\ displaystyle f}$${\ displaystyle f}$${\ displaystyle {\ displaystyle \ Omega ({\ sqrt {2 ^ {n}}})}}$${\ displaystyle f}$${\ displaystyle 2 ^ {n-1} +1}$

Visão geral do algoritmo de Simon

Ideia

A ideia de alto nível por trás do algoritmo de Simon é "sondar" (ou "amostrar") um circuito quântico (veja a imagem abaixo) "vezes suficientes" para encontrar ( linearmente independentes ) strings de n bits, ou seja ${\ displaystyle n-1}$

${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n},}$

de modo que as seguintes equações sejam satisfeitas

${\ displaystyle \ left \ {{\ begin {alinhados} y_ {1} \ cdot s & = 0 \\ y_ {2} \ cdot s & = 0 \\ & \, \, \, \ vdots \\ y_ {n- 1} \ cdot s & = 0 \ end {alinhado}} \ direito.}$

onde está o produto escalar módulo-2 ; isto é,, e , para e para . ${\ displaystyle y_ {i} \ cdot s}$ ${\ displaystyle y_ {i} \ cdot s = y_ {i1} s_ {1} \ oplus y_ {i2} s_ {2} \ oplus \ dots \ oplus y_ {em} s_ {n}}$${\ displaystyle y_ {ij}, s_ {j} \ in \ {0,1 \}}$${\ displaystyle i = 1, \ dots, n-1}$${\ displaystyle j = 1, \ dots, n}$

Portanto, este sistema linear contém equações lineares em incógnitas (ou seja, os bits de ), e o objetivo é resolvê-lo para obter , e é fixo para uma determinada função . Nem sempre existe uma solução (única). ${\ displaystyle n-1}$${\ displaystyle n}$${\ displaystyle s \ in \ {0,1 \} ^ {n}}$${\ displaystyle s}$${\ displaystyle s}$${\ displaystyle f}$

Circuito quântico de Simon

O circuito quântico (veja a imagem) é a implementação (e visualização) da parte quântica do algoritmo de Simon.

Um estado quântico de todos os zeros é primeiro preparado (isso pode ser feito facilmente). O estado representa onde está o número de qubits. Metade desse estado é então transformada usando uma transformação de Hadamard. O resultado é então alimentado em um oráculo (ou "caixa preta"), que sabe como computar . Onde atua nos dois registros como . Depois disso, parte da saída produzida pelo oráculo é transformada usando outra transformada de Hadamard. Finalmente, uma medição no estado quântico geral resultante é realizada. É durante essa medição que recuperamos as sequências de n bits,, mencionadas na subseção anterior. ${\ displaystyle | 0 \ rangle}$${\ displaystyle | 0 ^ {n} \ rangle}$${\ displaystyle n}$${\ displaystyle f}$${\ displaystyle U_ {f}}$${\ displaystyle | x \ rangle | 0 ^ {n} \ rangle \ rightarrow | x \ rangle | f (x) \ rangle}$${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n}}$

O algoritmo de Simon pode ser pensado como um algoritmo iterativo (que faz uso de um circuito quântico) seguido por um (possivelmente) algoritmo clássico para encontrar a solução para um sistema linear de equações.

Algoritmo de Simon

Nesta seção, cada parte do algoritmo de Simon é explicada (em detalhes). Pode ser útil olhar para a imagem do circuito quântico de Simon acima enquanto lê cada uma das subseções a seguir.

Entrada

O algoritmo de Simon começa com a entrada , onde está o estado quântico com zeros. ${\ displaystyle | 0 ^ {n} \ rangle \ otimes | 0 ^ {n} \ rangle = | 0 ^ {n} \ rangle | 0 ^ {n} \ rangle}$${\ displaystyle | 0 ^ {n} \ rangle}$${\ displaystyle n}$

(O símbolo é o símbolo típico usado para representar o produto tensorial . Para não confundir a notação, o símbolo é às vezes omitido: por exemplo, na frase anterior, é equivalente a . Neste artigo, é (frequentemente) usado para remover ambiguidade ou para evitar confusão.) ${\ displaystyle \ otimes}$${\ displaystyle \ otimes}$${\ displaystyle | 0 ^ {n} \ rangle \ otimes | 0 ^ {n} \ rangle}$${\ displaystyle | 0 ^ {n} \ rangle | 0 ^ {n} \ rangle}$

Exemplo

Então, por exemplo, se , então a entrada inicial é ${\ displaystyle n = 2}$

${\ displaystyle | 0 ^ {2} \ rangle \ otimes | 0 ^ {2} \ rangle = | 00 \ rangle \ otimes | 00 \ rangle = (| 0 \ rangle \ otimes | 0 \ rangle) \ otimes (| 0 \ rangle \ otimes | 0 \ rangle) = | 0 \ rangle \ otimes | 0 \ rangle \ otimes | 0 \ rangle \ otimes | 0 \ rangle = | 0000 \ rangle = | 0 ^ {4} \ rangle = | 0 ^ {2n} \ rangle}$.

Primeira transformação Hadamard

Depois disso, a entrada (conforme descrito na subseção anterior) é transformada usando uma transformada de Hadamard . Especificamente, a transformada de Hadamard (o produto tensorial também pode ser aplicado a matrizes) é aplicada aos primeiros qubits, ou seja, ao estado "parcial" , de modo que o estado composto após esta operação seja ${\ displaystyle H ^ {\ otimes n}}$${\ displaystyle n}$${\ displaystyle | 0 ^ {n} \ rangle}$

${\ displaystyle | \ Psi \ rangle = \ left (H ^ {\ otimes n} | 0 ^ {n} \ rangle \ right) \ otimes | 0 ^ {n} \ rangle = \ left (\ sum _ {x \ em \ {0,1 \} ^ {n}} {\ frac {1} {\ sqrt {2 ^ {n}}}} \ left | x \ right \ rangle \ right) \ otimes \ left | 0 ^ { n} \ right \ rangle = \ left ({\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left | x \ right \ rangle \ right) \ otimes \ left | 0 ^ {n} \ right \ rangle = {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ sum _ {x \ em \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | 0 ^ {n} \ right \ rangle \ right)}$

onde denota qualquer string de n bits (ou seja, a soma é sobre qualquer string de n bits). O termo pode ser fatorado fora da soma porque não depende de (ou seja, é uma constante em relação a ) e . ${\ displaystyle x \ in \ {0,1 \} ^ {n}}$${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}}}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} = {\ frac {1} {2 ^ {\ frac {n} {2}}}}}$

Exemplo

Suponha (novamente) , então a entrada é e a transformação de Hadamard é ${\ displaystyle n = 2}$${\ displaystyle | 0000 \ rangle}$${\ displaystyle H ^ {\ otimes 2}}$

${\ displaystyle H ^ {\ otimes 2} = {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} \ otimes {\ frac {1 } {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} = {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} & {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix } 1 & 1 \\ 1 & -1 \ end {bmatrix}} \\ {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} & - \ esquerda ({\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} \ right) \ end {bmatrix}} = {\ frac {1} {2}} {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \ end {bmatrix}}}$

Se agora nos aplicarmos ao primeiro , ou seja, ao estado ${\ displaystyle H ^ {\ otimes 2}}$${\ displaystyle | 00 \ rangle}$

${\ displaystyle | 00 \ rangle = {\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}}}$

nós obtemos

${\ displaystyle {\ begin {align} H ^ {\ otimes 2} | 00 \ rangle & = {\ frac {1} {2}} {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & - 1 & -1 \\ 1 & -1 & -1 & 1 \ end {bmatrix}} {\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}} = {\ frac {1} {2}} { \ begin {bmatrix} 1 \\ 1 \\ 1 \\ 1 \ end {bmatrix}} \\ [6pt] & = {\ frac {1} {2}} \ left ({\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 1 \\ 0 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 0 \\ 1 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 0 \\ 0 \\ 1 \ end {bmatrix}} \ right) = {\ frac {1} {2}} \ left (| 00 \ rangle + | 01 \ rangle + | 10 \ rangle + | 11 \ rangle \ right) = {\ frac {1} {2 ^ {2/2}}} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left | x \ right \ rangle \ end {alinhado}}}$

Para obter o estado quântico composto final, podemos agora tensor o produto com , isto é ${\ displaystyle H ^ {\ otimes 2} | 00 \ rangle}$${\ displaystyle | 00 \ rangle}$

${\ displaystyle {\ begin {alinhados} \ left (H ^ {\ otimes 2} | 00 \ rangle \ right) \ otimes | 00 \ rangle & = \ left ({\ frac {1} {2}} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left | x \ right \ rangle \ right) \ otimes | 00 \ rangle = {\ frac {1} {2}} \ left (| 00 \ rangle + | 01 \ rangle + | 10 \ rangle + | 11 \ rangle \ right) \ otimes | 00 \ rangle \\ [6pt] & = {\ frac {1} {2}} \ left (| 00 \ rangle \ otimes | 00 \ rangle + | 01 \ rangle \ otimes | 00 \ rangle + | 10 \ rangle \ otimes | 00 \ rangle + | 11 \ rangle \ otimes | 00 \ rangle \ right) = {\ frac {1} {2 }} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left (\ left | x \ right \ rangle \ otimes | 00 \ rangle \ right). \ end {alinhado}}}$

Oráculo

Em seguida, chamamos o oráculo ou caixa preta ( na imagem acima) para calcular a função na entrada transformada , para obter o estado ${\ displaystyle U_ {f}}$${\ displaystyle f}$${\ displaystyle | \ Psi \ rangle = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | 0 ^ {n} \ right \ rangle \ right)}$

${\ displaystyle | \ Psi \ rangle '= {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | f (x) \ right \ rangle \ right)}$

Segunda transformação Hadamard

Em seguida, aplicamos a transformada de Hadamard aos estados dos primeiros qubits do estado , para obter ${\ displaystyle H ^ {\ otimes n}}$${\ displaystyle n}$${\ displaystyle | \ Psi \ rangle '}$

${\ displaystyle {\ begin {alinhados} | \ Psi \ rangle '' & = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ { n}} \ left (\ left (H ^ {\ otimes n} \ left | x \ right \ rangle \ right) \ otimes \ left | f (x) \ right \ rangle \ right) \\ [4pt] & = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left ({\ frac {1} {2 ^ {n / 2}}} \ sum _ {y \ in \ {0,1 \} ^ {n}} (- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ right) \ otimes \ left | f (x) \ right \ rangle \ right) = {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ sum _ {y \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ otimes \ left | f (x ) \ right \ rangle \ right) \ right) \ end {alinhado}}}$

onde pode ser ou , dependendo de , onde , para . Então, por exemplo, se e , então , que é um número par. Portanto, neste caso, e é sempre um número não negativo. ${\ displaystyle (-1) ^ {x \ cdot y}}$${\ displaystyle -1}$${\ displaystyle 1}$${\ displaystyle x \ cdot y = x_ {1} y_ {1} + \ dots + x_ {n} y_ {n}}$${\ displaystyle x_ {i}, y_ {i} \ in \ {0,1 \}}$${\ displaystyle i = 1, \ dots, n}$${\ displaystyle x = 101}$${\ displaystyle y = 111}$${\ displaystyle x \ cdot y = 1 * 1 + 0 * 1 + 1 * 1 = 2}$${\ displaystyle (-1) ^ {x \ cdot y} = (- 1) ^ {1 * 1 + 0 * 1 + 1 * 1} = (- 1) ^ {2} = 1}$${\ displaystyle {x \ cdot y}}$

A intuição por trás dessa transformação inversa de Hadamard que é aplicada aqui pode ser encontrada nas notas de aula do CMUs

Agora vamos reescrever

${\ displaystyle | \ Psi \ rangle '' = {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ sum _ {y \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ otimes \ left | f (x) \ right \ rangle \ right) \ right)}$

do seguinte modo

${\ displaystyle | \ Psi \ rangle '' = \ sum _ {y \ in \ {0,1 \} ^ {n}} \ left (\ left | y \ right \ rangle \ otimes \ left ({\ frac { 1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) \ right) \ right)}$

Essa manipulação será conveniente para entender as explicações nas próximas seções. A ordem das somas foi invertida.

Medição

Após ter realizado todas as operações descritas anteriormente, no final do circuito, é realizada uma medição .

Existem agora dois casos possíveis que precisamos considerar separadamente

• ${\ displaystyle x \ oplus y = 0 ^ {n}}$ ou
• ${\ displaystyle x \ oplus y = s}$, onde .${\ displaystyle s \ neq 0 ^ {n}}$

Primeiro caso

Vamos primeiro analisar o caso (especial) , o que significa que é (por requisito) uma função um-para-um (conforme explicado acima na "descrição do problema"). ${\ displaystyle x \ oplus y = 0 ^ {n}}$${\ displaystyle f}$

Vamos ter em mente que o estado quântico antes da medição é

${\ displaystyle \ sum _ {y \ in \ {0,1 \} ^ {n}} \ left | y \ right \ rangle \ otimes \ left ({\ frac {1} {2 ^ {n}}} \ soma _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) \ right)}$

Agora, a probabilidade de que os resultados da medição em cada string é ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$

${\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {\ frac {1} {2 ^ {n} }}}$

Isso segue de

${\ displaystyle {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {{\ Bigg \ |} {\ frac {1} {2 ^ { n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | x \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}$

porque os dois vetores diferem apenas na ordem de suas entradas, visto que é um-para-um . ${\ displaystyle f}$

O valor do lado direito, isto é

${\ displaystyle {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | x \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}$

é mais facilmente visto ser . ${\ displaystyle {\ frac {1} {2 ^ {n}}}}$

Assim, quando , o resultado é simplesmente uma string de bits uniformemente distribuída . ${\ displaystyle x \ oplus y = 0 ^ {n}}$ ${\ displaystyle n}$

Segundo caso

Vamos agora analisar o caso , onde . Nesse caso, é uma função dois para um, ou seja, há duas entradas que mapeiam para a mesma saída de . ${\ displaystyle x \ oplus y = s}$${\ displaystyle s \ neq 0 ^ {n}}$${\ displaystyle f}$${\ displaystyle f}$

A análise realizada no primeiro caso ainda é válida para este segundo caso, ou seja, a probabilidade de medir qualquer string dada ainda pode ser representada como ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$

${\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}$

No entanto, neste segundo caso, ainda precisamos descobrir qual é esse valor . Vamos ver o porquê nas seguintes explicações. ${\ displaystyle p_ {y}}$

Vamos , a imagem de . Let (ie é alguma saída da função ), então para cada , há um (e apenas um) , tal que ; além disso, também temos , que é equivalente a (consulte a seção "descrição do problema" acima para uma revisão deste conceito). ${\ displaystyle A = f (\ {0,1 \} ^ {n})}$${\ displaystyle f}$${\ displaystyle z \ in A}$${\ displaystyle z}$${\ displaystyle f}$${\ displaystyle x_ {1} \ in \ {0,1 \} ^ {n}}$${\ displaystyle x_ {2} \ in \ {0,1 \} ^ {n}}$${\ displaystyle f (x_ {1}) = f (x_ {2}) = z}$${\ displaystyle x_ {1} \ oplus x_ {2} = s}$${\ displaystyle x_ {2} = s \ oplus x_ {1}}$

Portanto, temos

${\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {{\ Bigg \ |} {\ frac {1 } {2 ^ {n}}} \ sum _ {z \ in A} \ left (((- 1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y }) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}$

Dado isso , então podemos reescrever o coeficiente da seguinte forma ${\ displaystyle x_ {2} = s \ oplus x_ {1}}$${\ displaystyle (-1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y}}$

${\ displaystyle (-1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y} = (- 1) ^ {x_ {1} \ cdot y} + (- 1) ^ {(x_ {1} \ oplus s) \ cdot y}}$

Dado isso , então podemos escrever a expressão acima como ${\ displaystyle (x_ {1} \ oplus s) \ cdot y = (x_ {1} \ cdot y) \ oplus (s \ cdot y)}$

${\ displaystyle (-1) ^ {x_ {1} \ cdot y} (1 + (- 1) ^ {y \ cdot s})}$

Portanto, pode ainda ser escrito como ${\ displaystyle p_ {y}}$

${\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {z \ in A} \ left ((- 1) ^ {x_ {1 } \ cdot y} (1 + (- 1) ^ {y \ cdot s}) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}$

Número ímpar

Agora, se é um número ímpar, então . Nesse caso, ${\ displaystyle y \ cdot s = y_ {1} s_ {1} + \ dots + y_ {n} s_ {n}}$${\ displaystyle (-1) ^ {y \ cdot s} = - 1}$

${\ displaystyle (-1) ^ {x_ {1} \ cdot y} (1 + (- 1) ^ {y \ cdot s}) = (- 1) ^ {x_ {1} \ cdot y} (1- 1) = 0}$

Consequentemente, temos

${\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {z \ in A} \ left ((- 1) ^ {x_ {1 } \ cdot y} (1 + (- 1) ^ {y \ cdot s}) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = 0}$

Dado isso , então nunca teremos este caso, ou seja, nenhuma string é vista (após a medição) neste caso. ${\ displaystyle p_ {y} = 0}$${\ displaystyle y \ in \ {0,1 \} ^ {n}}$

(Este é o caso em que temos interferência destrutiva .)

Numero par

Se, em vez disso, for um número par (por exemplo, zero), então . Nesse caso, ${\ displaystyle y \ cdot s}$${\ displaystyle (-1) ^ {y \ cdot s} = 1}$

${\ displaystyle (-1) ^ {x_ {1} \ cdot y} (1 + (- 1) ^ {y \ cdot s}) = (- 1) ^ {x_ {1} \ cdot y} 2}$

Então nós temos

${\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {z \ in A} \ left ((- 1) ^ {x_ {1 } \ cdot y} (2) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {{\ Bigg \ |} {\ frac {2} {2 ^ {n} }} \ sum _ {z \ in A} \ left ((- 1) ^ {x_ {1} \ cdot y} \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n-1}}} \ sum _ {z \ in A} \ left ((- 1) ^ {x_ {1} \ cdot y} \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}$

É o caso da interferência construtiva ,

${\ displaystyle {\ frac {2} {2 ^ {n}}} = 2 * 2 ^ {- n} = 2 ^ {1} * 2 ^ {- n} = 2 ^ {- n + 1} = 2 ^ {- (n-1)} = {\ frac {1} {2 ^ {n-1}}}}$. Então, em resumo, para este segundo caso, temos as seguintes probabilidades

${\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {\ begin {cases} {\ frac {1} {2 ^ {n-1}}} & \ quad {\ text {if}} y \ cdot s {\ text {é par}} \\ 0 & \ quad {\ text {if}} y \ cdot s {\ texto {é estranho}} \\\ fim {casos}}}$

Pós-processamento clássico

Quando executamos o circuito (operações) acima, existem dois casos:

• no caso (especial) onde (ou seja ), os resultados da medição em cada string com probabilidade${\ displaystyle x \ oplus y = 0 ^ {n}}$${\ displaystyle s = 0 ^ {n}}$${\ displaystyle y \ in \ {0,1 \} ^ {n}}$${\ displaystyle p_ {y} = {\ frac {1} {2 ^ {n}}}}$

• no caso (onde ), a probabilidade de obter cada string é dada por${\ displaystyle x \ oplus y = s}$${\ displaystyle s \ neq 0 ^ {n}}$${\ displaystyle y \ in \ {0,1 \} ^ {n}}$

${\ displaystyle p_ {y} = {\ begin {cases} {\ frac {1} {2 ^ {n-1}}} & \ quad {\ text {if}} y \ cdot s {\ text {é par }} \\ 0 & \ quad {\ text {if}} y \ cdot s {\ text {is odd}} \\\ end {cases}}}$

Assim, em ambos os casos, o resultado da medição é alguma string que satisfaz e a distribuição é uniforme em todas as strings que satisfazem essa restrição. ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$${\ displaystyle s \ cdot y = 0}$

Esta informação é suficiente para determinar ? A resposta é "sim", desde que o processo (acima) seja repetido várias vezes (e uma pequena probabilidade de falha seja aceita). Especificamente, se o processo acima for executado em tempos de execução , obteremos strings , de modo que ${\ displaystyle s}$${\ displaystyle n-1}$${\ displaystyle n-1}$${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n}}$

${\ displaystyle {\ begin {cases} y_ {1} \ cdot s & = 0 \\ y_ {2} \ cdot s & = 0 \\ & \ vdots \\ y_ {n-1} \ cdot s & = 0 \ end { casos}}}$

Este é um sistema de equações lineares em incógnitas (ou seja, os bits de ), e o objetivo é resolvê-lo para obter . Observe que cada um dos que obtemos após cada medição (para cada "rodada" do processo) é, naturalmente, o resultado de uma medição, por isso é conhecido (ao final de cada "rodada"). ${\ displaystyle n-1}$${\ displaystyle n}$${\ displaystyle s}$${\ displaystyle s}$${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n}}$

Só obtemos uma solução única diferente de zero se tivermos "sorte" e formos linearmente independentes. A probabilidade de que sejam linearmente independentes é pelo menos ${\ displaystyle s}$${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n}}$${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1}}$

${\ displaystyle \ prod _ {k = 1} ^ {\ infty} \ left (1 - {\ frac {1} {2 ^ {k}}} \ right) = 0,288788 \ dots> {\ frac {1} { 4}}}$

Se tivermos independência linear, podemos resolver o sistema para obter uma solução candidata e testá-la . Sim , sabemos disso , e o problema foi resolvido. Se , deve ser isso (porque, se não fosse assim, a única solução diferente de zero para as equações lineares teria sido ). De qualquer forma, uma vez que tenhamos independência linear, podemos resolver o problema. ${\ displaystyle s '\ neq 0 ^ {n}}$${\ displaystyle f (0 ^ {n}) = f (s ')}$${\ displaystyle f (0 ^ {n}) = f (s ')}$${\ displaystyle s = s '}$${\ displaystyle f (0 ^ {n}) \ neq f (s ')}$${\ displaystyle s = 0 ^ {n}}$${\ displaystyle s}$

Complexidade

O algoritmo de Simon requer consultas à caixa preta, enquanto um algoritmo clássico precisaria de pelo menos consultas. Também se sabe que o algoritmo de Simon é ótimo no sentido de que qualquer algoritmo quântico para resolver esse problema requer consultas. ${\ displaystyle O (n)}$${\ displaystyle \ Omega (2 ^ {n / 2})}$${\ displaystyle \ Omega (n)}$

Veja também

• Algoritmo Deutsch-Jozsa

Referências