A amplificação de amplitude é uma técnica em computação quântica que generaliza a ideia por trás do algoritmo de busca de Grover, e dá origem a uma família de algoritmos quânticos. Foi descoberta por Gilles Brassard e Peter Høyer em 1997, e independentemente redescoberta por Lov Grover em 1998.
Em um computador quântico, a amplificação de amplitude pode ser usada para obter uma aceleração quadrática em relação a diversos algoritmos clássicos.
Algoritmo
A derivação apresentada aqui segue aproximadamente a fornecida por Brassard et al. em 2000. Suponha que temos um Espaço de Hilbert de dimensões representando o espaço de estados de um sistema quântico, gerado pelos estados da base computacional ortonormal .Além disso, suponha que temos um operador de projeção hermitiano . Alternativamente, pode ser dado em termos de uma função oráculo booleana e uma base operacional ortonormal , sendo que, neste caso . pode ser usado para particionar em uma soma direta de dois subespaços mutuamente ortogonais, o subespaço bom e o subespaço ruim :Em outras palavras, estamos definindo um "subespaço bom" por meio do projetor . O objetivo do algoritmo é então evoluir algum estado inicial para um estado pertencente a .
Dado um vetor de estado normalizado com uma sobreposição não nula com ambos os subespaços, podemos decompô-lo de maneira única como
, onde , e e são as projeções normalizadas de nos subespaços e , respectivamente. Esta decomposição define um subespaço bidimensional , gerado pelos vetores e .A probabilidade de encontrar o sistema em um estado bom quando medido é .
Defina um operador unitário , onde
inverte a fase dos estados no subespaço bom, enquanto inverte a fase do estado inicial .
A ação deste operador sobre é dada por e . Portanto, no subespaço , corresponde a uma rotação pelo ângulo : . Aplicar vezes sobre o estado
resulta em , rotacionando o estado entre os subespaços bom e ruim. Após iterações, a probabilidade de encontrar o sistema em um estado bom é .A probabilidade é maximizada se escolhermos . Até este ponto, cada iteração aumenta a amplitude dos estados bons, de onde deriva o nome da técnica.
Aplicações
Suponha que temos um banco de dados não estruturado com elementos, e uma função oráculo que pode reconhecer as entradas boas que estamos procurando, e por simplicidade.
Se houver entradas boas no total no banco de dados, podemos encontrá-las inicializando um registrador quântico com qubits onde em uma superposição uniforme de todos os elementos do banco de dados, tal que
e executando o algoritmo acima. Neste caso, a sobreposição do estado inicial com o subespaço bom é igual à raiz quadrada da frequência das entradas boas no banco de dados, . Se , podemos aproximar o número de iterações necessárias como
Medir o estado agora nos dará uma das entradas boas com alta probabilidade. Como cada aplicação de requer uma única consulta ao oráculo (assumindo que o oráculo é implementado como uma porta lógica quântica), podemos encontrar uma entrada boa com apenas consultas ao oráculo, obtendo assim uma aceleração quadrática em relação ao melhor algoritmo clássico possível. (O método clássico para pesquisar no banco de dados seria realizar a consulta para cada até que uma solução fosse encontrada, custando assim consultas). Além disso, podemos encontrar todas as soluções utilizando consultas.
Se definirmos o tamanho do conjunto como um, o cenário acima se reduz essencialmente à busca de Grover original.
Contagem quântica Suponha que o número de entradas boas seja desconhecido. Nosso objetivo é estimar tal que para um pequeno. Podemos solucionar para aplicando o algoritmo de estimativa de fase quântica sobre o operador unitário .
Como e são os dois únicos autovalores de , podemos fazer com que seus autovetores correspondentes sejam e . Podemos encontrar o autovalor de , o que, neste caso, é equivalente a estimar a fase . Isso pode ser feito aplicando transformadas de Fourier e operações unitárias controladas, conforme descrito no algoritmo de estimativa de fase quântica. Com a estimativa , podemos estimar , que por sua vez estima .
Suponha que queremos estimar com um estado inicial arbitrário , em vez dos autovetores e . Podemos fazer isso decompondo em uma combinação linear de e , e então aplicando o algoritmo de estimativa de fase.
Referências
Categoria:Algoritmos quânticos Categoria:Algoritmos de busca