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

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 ⁿ 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 ⁿ é 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} ).

$O(n2^{n/2})$

$n/2$$O(2^{n/2})$$n+1$$X$$n+1$

$X$$Y$$O(2^{n/2})$$n/2$$Y$$n/2$$X$$Y$$Y$$O(2^{n/2})$$X_2$$n+2$

$n+3$$X_2$$n/2$$n/2$$X_2$

$n$$O(n2^{n/2})$

$X_t$$X_{t+1}$$t$$n/2$$t+2^{n/2}$$t$$n/2$$t+2^{n/2}$$X_t$.