Algoritmo Quântico para o Número de Deus

O número de Deus é o pior caso do algoritmo de Deus, que é

uma noção originada nas discussões de maneiras de resolver o quebra-cabeça do Cubo de Rubik, mas que também pode ser aplicada a outros quebra-cabeças combinatórios e jogos matemáticos. Refere-se a qualquer algoritmo que produz uma solução com o menor número possível de movimentos, com a idéia de que um ser onisciente conheceria uma etapa ideal de qualquer configuração.

O cálculo do número de Deus para 20 levou "35 anos de CPU do tempo ocioso (clássico) do computador".

Que tipo de aceleração poderia ser alcançada com uma abordagem quântica?

algorithm speedup complexity-theory mathematics quantum-walks meowzz
fonte

O "número de Deus" para quebra-cabeças combinatórios está relacionado ao diâmetro do gráfico semelhante a Cayley, ou seja, o maior caminho menor do gráfico. Eu não acho que o problema generalizado dos quebra-cabeças esteja em . Eu não estudei este artigo - arxiv.org/abs/quant-ph/0303131 - mas acho que ele reivindica uma aceleração de Grover sobre o clássico.

n \times n \times n

$n\times n \times n$

N P

$\mathsf{NP}$

Mark S

@mark s chat.stackexchange.com/rooms/81283/quantum

meowzz (

Você pode fazer uma pergunta como essa para qualquer coisa difícil de calcular. Isso não parece ser muito construtivo. Por que você acha que esse problema específico pode ser interessante para algoritmos quânticos?

Norbert Schuch

@ Norbert Schuch Eu cubo e faço computação quântica. É um problema realmente interessante para mim (e eu pensaria para qualquer pessoa interessada em otimização combinatória quântica).

meowzz

Consulte também mathoverflow.net/questions/77836/… em um site irmão.

Mark S

Podemos pensar no gráfico Cayley do cubo de Rubik com cada aresta (colorida) sendo um dos movimentos do Singmaster e cada vértice sendo uma das configurações diferentes dos cubos . $\Gamma=(V,E)$ $E$ $\langle U,U^{2},U^{3}=U^{-1},D,D^{2},D^{3},\cdots\rangle$ $V$ $43252003274489856000\approx 4.3e{19}$ $3\times 3\times 3$

O diâmetro de um gráfico é o caminho mais curto e mais longo do gráfico. O algoritmo clássico para determinar o diâmetro é polinomial em ; veja, por exemplo, esta resposta em um site irmão. $\vert V \vert$

Como mencionado acima, o número de Deus é (relacionado a) esse diâmetro; para conhecer o caminho mais curto e mais curto entre os vértices de um gráfico de Cayley em um grupo, basta saber quantos passos se afastam do estado resolvido. Sabemos, graças a Rokicki, Kociemba, Davidson e Dethridge, entre outros, que o número de Deus é . Os algoritmos que eles executaram eram polinomiais em , por exemplo, polinomial em . $20$ $\vert V\vert$ $4.3e{19}$

O algoritmo quântico de Heiligman para diâmetro de gráfico, mencionado nos comentários, alcança uma aceleração de Grover sobre os algoritmos de Djikstra, com "um custo quântico total de ". No entanto, acredito que Heiligman codifica o gráfico da mesma maneira que um algoritmo clássico faria; por exemplo, com qubits. Claramente, se , isso não ajudaria. $O(|V|^{9/4})$ $O(|V|)$ $|V|=4.3e{19}$

Em vez disso, outra maneira de codificar o cubo de Rubik, como sugerido nas outras perguntas, é obviamente preparar uma superposição uniforme em todos os . Isso requer apenas qubits. $4.3e{19}$ $\log 4.3e{19}$

Os algoritmos quânticos são bons em falar sobre "autovalores" e "autovetores" e "autovalores". A aplicação de todos os movimentos do Singmaster a uma superposição uniforme de todos os não altera o estado; isto é, a superposição uniforme é um auto-estado da cadeia de Markov no gráfico de Cayley. $4.3e{19}$

Existem relações entre o diâmetro de um gráfico e os autovalores / autovetores da matriz adjacente / Laplaciana correspondente, especialmente a lacuna espectral, a distância entre os dois maiores autovalores ( ). Uma rápida pesquisa no Google de "autovalor de diâmetro" produz isso ; Eu recomendo explorar pesquisas semelhantes no Google. $\lambda_1-\lambda_2$

Lacunas espectrais são exatamente o que limita o algoritmo adiabático . Assim, talvez sabendo o quão rápido um algoritmo adiabático precisa rodar para evoluir do superposto uniforme para o estado resolvido de vários subgrupos / subespaços do grupo de cubos de Rubik, pode-se estimar a lacuna espectral e usá-la para limitar o número de Deus. Mas estou rapidamente fora da minha liga aqui e duvido que qualquer senso de precisão seja possível.

Mark S
fonte

Primeiro de tudo, obrigado pela excelente resposta. Estou muito interessado em descobrir mais sobre lacunas espectrais e processos diabéticos. Você sabe alguma coisa sobre gráficos subcúbicos ? Além disso, você conhece alguma coisa sobre números surreais ( lacunas específicas )? Além disso, você tem alguma opinião sobre o gabinete 2x2? Ou o caso nxn (para )?

3 < n

$3<n$

meowzz

@ meowzz, de nada. Me desculpe, eu não sei nada sobre números surreais ou gráficos subcúbicos. O gráfico de Cayley acima não é cúbico e tem uma valência de eu acho ( faces e um movimento de um quarto, meio ou três quartos por face). Sobre o caso , o mesmo pensamento se aplica ... meça quanto tempo leva um algoritmo adiabático para evoluir para um estado resolvido, use uma relação entre e para limitar o intervalo espectral e o diâmetro com relação entre e ...

18

$18$

6

$6$

n \times n

$n\times n$

τ_{n}

$\tau_n$

τ_{n}

$\tau_n$

λ_{2}

$\lambda_2$

δ

$\delta$

λ_{2}

$\lambda_2$

δ

$\delta$

Mark S

Ao ler a resposta, ainda não está totalmente claro "Que tipo de velocidade poderia ser alcançada com uma abordagem quântica?".

JanVdA

Obrigado por seu comentário. Eu nunca afirmei conhecer todos os detalhes da resposta à pergunta em negrito. Apenas tentei dar algum feedback sobre abordagens que talvez valessem mais a pena explorar e também contrariar levemente outro comentário na pergunta. Além disso, alguém foi muito acolhedor com uma pergunta semelhante minha.

Mark S

Algoritmo Quântico para o Número de Deus

Respostas: