Otimização do algoritmo de Grover com alta probabilidade de sucesso

9

É sabido que a complexidade da consulta quântica de erro limitado da função é . Agora, a questão é: se queremos que nosso algoritmo quântico seja bem-sucedido para cada entrada com probabilidade em vez dos usuais . Agora, em termos de quais seriam os limites superior e inferior apropriados?Θ ( OR(x1,x2,,xn)1-ε2/3εΘ(n)1ϵ2/3ϵ

É imediato que as consultas suficientes para esta tarefa, repetindo o algoritmo Grover. Mas pelo que me lembro, isso não é de todo ideal, já que o algoritmo Grover simples, se executado com cuidado, ou seja, para um número apropriado de iterações, pode obter algo como com apenas iterações. E, portanto, usá-lo pode obter uma melhoria para todos os 's. Por outro lado, não espero que seja a resposta certa para 's muito pequenos .ϵ=O(1/n)O(O(nlog(1/ϵ))ϵ=O(1/n)ϵΩ(O(n)ϵϵΩ(n)ϵ

Mas estou interessado em ver o que se pode mostrar em termos dos limites superior e inferior dependentes de para diferentes intervalos de especialmente quando é muito pequeno, digamos ou para 's grandes .ϵ ϵ ϵ = exp ( - Ω ( n ) ) ϵ = 1 / n k kϵϵϵϵ=exp(Ω(n))ϵ=1/nkk

(Para dar algum contexto, o fenômeno geral que estou abordando é a amplificação no contexto da complexidade quântica de consultas.)

Mohammad Bavarian
fonte
3
Este trabalho deve fornecer respostas às suas perguntas: arxiv.org/abs/cs/9904019v2
John Watrous
11
Hmmm, agora estou um pouco confuso no caso de . Parece que este artigo arxiv.org/pdf/quant-ph/9605034v1.pdf afirma que com cerca de iterações é possível obter um resultado de alta probabilidade, como . (página 2 parte inferior da primeira coluna) Por outro lado, o artigo que você mencionou diz, na página 4 final da seção 3, que probabilidade de falha é impossível para consultas . πϵ=1N ϵ= 1π4N o(1)O(ϵ=1No(1)O(N)
Mohammad Bavarian
11
@ MohammadBavarian: Eu acho que é apenas no caso em que o número de soluções é conhecido (ou existe uma solução única).
22412 Robin Kothari

Respostas:

3

Por uma questão de integridade, aqui está uma resposta.

Seja a complexidade quântica de consultas error de calcular uma função e seja a função OR em bits, definida como . (Observe que isso é diferente do problema em que você promete que a entrada possui exatamente um 1 e o objetivo é descobrir que 1. Esse problema pode ser resolvido sem nenhum erro nas consultas .)ϵ f O R n n O R n ( x 1 , , x n ) = n i = 1 x i Θ ( Qϵ(f)ϵfORnnORn(x1,,xn)=i=1nxiΘ(n)

Então temos para todos ,ϵ[2n,1/3]

Qϵ(ORn)=Θ(nlog(1/ϵ)) .

Segue Limites para algoritmos quânticos de erro pequeno e erro zero .

De fato, sabemos algo mais geral. Para todas as funções simétricas , que são funções que dependem apenas do peso de Hamming da entrada, temos isso para todos ,£ [ 2 - N , 1 / 3 ]fϵ[2n,1/3]

Qϵ(f)=Θ(Q1/3(f)+nlog(1/ϵ)) .

Isso foi mostrado em uma nota sobre algoritmos quânticos e o grau mínimo de polinômios de erro épsilon para funções simétricas .

Robin Kothari
fonte