A complexidade da consulta aleatória do problema de árvores unidas

23

Um importante artigo de 2003 de Childs et al.introduziu o "problema das árvores conjuntas": um problema que admite uma aceleração quântica exponencial que é diferente de qualquer outro problema desse tipo que conhecemos. Nesse problema, recebemos um gráfico exponencialmente grande como o da figura abaixo, que consiste em duas árvores binárias completas de profundidade n, cujas folhas são conectadas umas às outras por um ciclo aleatório. Nós somos fornecidos com a etiqueta do vértice ENTRANCE. Também somos fornecidos com um oráculo que, dado como entrada o rótulo de qualquer vértice, nos diz os rótulos de seus vizinhos. Nosso objetivo é encontrar o vértice EXIT (que pode ser facilmente reconhecido, como o único vértice de grau 2 no gráfico que não seja o vértice ENTRANCE). Podemos assumir que os rótulos são longas seqüências aleatórias, de modo que, com uma probabilidade esmagadora,outro vértice que não seja o ENTRANCE deve ser dado pelo oráculo.

Childs et al. mostrou que um algoritmo de caminhada quântica é capaz de percorrer este gráfico e encontrar o vértice EXIT após as etapas pol (n). Por outro lado, eles também mostraram que qualquer algoritmo aleatório clássico requer etapas exp (n) para encontrar o vértice EXIT com alta probabilidade. Eles declararam seu limite inferior como Ω (2 n / 6 ), mas acredito que um exame mais detalhado de suas provas produz Ω (2 n / 2 ). Intuitivamente, isso ocorre porque, com uma probabilidade esmagadora, uma caminhada aleatória no gráfico (mesmo uma caminhada que evita a si mesma etc.) fica presa na vasta região central por um período exponencial de tempo: sempre que um caminhante começa a se aproximar da EXIT , o número muito maior de arestas apontando para fora da EXIT funcionará como uma "força repulsiva" que a empurra de volta para o meio.

A maneira como formalizaram o argumento foi mostrar que, até visitar ~ 2 n / 2 vértices, um algoritmo aleatório ainda não encontrou nenhum ciclo no gráfico: o subgrafo induzido que é visto até agora é apenas uma árvore, não fornecendo qualquer informação sobre onde possa estar o vértice EXIT.

Estou interessado em determinar a complexidade da consulta aleatória desse problema com mais precisão. Minha pergunta é esta:

Alguém pode criar um algoritmo clássico que encontre o vértice EXIT em menos de ~ 2 n etapas - digamos, em O (2 n / 2 ) ou O (2 2n / 3 )? Como alternativa, alguém pode dar um limite inferior melhor que Ω (2 n / 2 )?

(Observe que, pelo paradoxo do aniversário, não é difícil encontrar ciclos no gráfico após as etapas O (2 n / 2 ). A questão é se é possível usar os ciclos para obter pistas sobre onde está o vértice EXIT.)

Se alguém puder melhorar o passado do limite inferior Ω (2 n / 2 ), pelo que sei, isso forneceria o primeiro exemplo possível de um problema de caixa preta com uma aceleração quântica exponencial, cuja complexidade de consulta aleatória é maior que √N . (Onde N ~ 2 n é o tamanho do problema.)

Atualização: Aprendi com Andrew Childs que, nesta nota , Fenner e Zhang aprimoram explicitamente o limite inferior aleatório de árvores unidas para Ω (2 n / 3 ). Se eles estavam dispostos a aceitar uma probabilidade de sucesso constante (e não exponencialmente pequena), acredito que poderiam melhorar ainda mais o limite, para Ω (2 n / 2 ).

insira a descrição da imagem aqui

Scott Aaronson
fonte

Respostas:

22

O(n2n/2)

n/2O(2n/2)n+1Xn+1

XYO(2n/2)n/2Yn/2XYYO(2n/2)X2n+2

n+3X2n/2n/2X2

nO(n2n/2)

XtXt+1tn/2t+2n/2tn/2t+2n/2Xt.

Shalev
fonte
Xt+1tXtn/22t2n/2
2n/2
2n/2
1
Xt+1tXtt2tn/22n/2t+2n/2ttt
1
A idéia de iniciar uma pesquisa de ambos os lados e levar a uma melhoria do sqrt () sobre o algoritmo ingênuo é conhecida como pesquisa bidirecional e foi redescoberta de forma independente muitas vezes em vários contextos, por exemplo, planejamento de rotas no Google Maps. A referência original parece ser: GB Dantzig. Programação linear e extensões. Princeton University Press, 1962.
Alex Lopez-Ortiz