Um computador quântico pode determinar facilmente o tempo de mistura do grupo de cubos de Rubik?

Os oficiais dos torneios de cubo de Rubik usaram duas maneiras diferentes de embaralhar um cubo. Atualmente, eles partem um cubo e remontam os cubos em uma ordem aleatória $\pi\in G$ do grupo do cubo de Rubik $G$. Anteriormente, iriam aplicar uma sequência aleatória $g$ de Singmaster movimentos $\langle U,D, F, B, L, R\rangle$ .

$t$$g$$\Vert G\Vert=43,252,003,274,489,856,000$ $20$$t$$\langle U,D, F, B, L, R\rangle$

Um computador quântico teria vantagens em determinar o tempo de mistura $t$ do grupo de cubos de Rubik?

Acho que podemos ter uma sequência inteligente de movimentos do Hadamard para criar um registro $\vert A \rangle$ como uma superposição uniforme em todas as configurações de $\Vert G\Vert$ ; assim, aplicar qualquer sequência de movimentos do Singmaster para $\vert A \rangle$ não muda $\vert A \rangle$ .

Se temos um palpite'como o que o tempo de mistura é, nós também pode criar outro registro como uma superposição uniforme de todas as palavras Singmaster de comprimento , e condicionalmente aplicar cada tal palavra a um estado resolvido , para obter um estado tal forma que, se medirmos , cada uma das configurações de terá a mesma probabilidade de ser medida. Se , então não teremos andado ao longo do gráfico de Cayley de por tempo suficiente e se medirmos t | B ⟩ t ' | A ' ⟩ | B ⟩ | A ⟩ | A ⟩ ‖ G ‖ t ' < t G | A ⟩ | B ⟩ | A $t'$$t$$\vert B \rangle$$t'$$\vert A'\rangle$$\vert B\rangle \vert A\rangle$$\vert A \rangle$$\Vert G \Vert$$t'\lt t$$G$$\vert A \rangle$, as configurações "mais próximas" do estado resolvido seriam mais prováveis. Alguma inteligente transformação de Fourier no estilo pode ser capaz de medir a distribuição uniforme de .$\vert B \rangle$$\vert A \rangle$

Para mim, isso parece algo em que um computador quântico pode ser bom. Por exemplo, se não foi uniformemente misturado por todas as palavras em , então algumas configurações são mais prováveis ​​que outras, por exemplo, é mais "constante"; ao passo que se tem sido completamente misturado por todos os passeios, então é mais "equilibrada". Mas minha sugestão sobre algoritmos quânticos e cadeias de Markov não é forte o suficiente para ir muito longe.| B ⟩ | A ⟩ | A ⟩ | A $\vert A \rangle$$\vert B\rangle$$\vert A \rangle$$\vert A \rangle$ $\vert A \rangle$

EDITAR

Compare esta questão com o problema de verificação do nó quântico.

Na verificação quântica do nó, o comerciante recebe uma moeda quântica como um estado de todos os nós que possuem uma invariante específica. Para verificar a moeda quântica, ela aplica uma cadeia de Markov na transição para si mesma (se for uma moeda válida.) Ela deve aplicar essa cadeia de Markov e medir o resultado pelo menos vezes, mas, caso contrário, ela não há como construir por conta própria (para que ela não possa forjar a moeda.) Portanto, se ela recebe uma moeda válida, ela recebe um estado que ela não pode produzir sozinha , juntamente com uma cadeia de Markov como uma moeda. matriz , e ela presumivelmente conhece o tempo de misturaM | K ⟩ t | K ⟩ M t | K $\vert K \rangle$$M$$\vert K \rangle$$t$$\vert K \rangle$$M$$t$; ela é obrigada a testar se é válido.$\vert K \rangle$

Na presente pergunta, provavelmente é muito fácil gerar de todas as permutações do cubo de Rubik. O circuito quântico correspondente à cadeia de Markov, chamado , dos movimentos Singmaster, também é provavelmente muito fácil de construir. No entanto, o tempo de mistura é desconhecido e é a única coisa a ser determinada.S $\vert RC \rangle$$S$$t$

É uma pergunta interessante que é melhor que a maioria "existe um algoritmo quântico para x?" questões. Não conheço um algoritmo quântico existente. Deixe-me descrever o que acho que seria uma primeira tentativa típica e por que isso falha. No final, descreverei algumas coisas que podem levar a algumas melhorias.

Primeira tentativa de um algoritmo

Digamos que eu queira testar um tempo de mistura específico . Vou criar um registro, para conter espaço de trabalho suficiente para conter qualquer uma das configurações possíveis do cubo de Rubik. O estado inicial disso é um estado do produto que corresponde ao estado inicial do cubo.R $t$$RC$

Então eu vou fazer registros , de a . Cada um deles tem o mesmo tamanho do número possível de movimentos do Singmaster e é preparado como uma superposição uniforme em todos os elementos possíveis da base. Então, para cada , aplicamos uma controlada de para onde o registro especifica qual movimento do Singmaster é aplicado no .A 1 A t i = 1 , … t A i R C A i R $t$$A_1$$A_t$$i=1,\ldots t$$A_i$$RC$$A_i$$RC$

Depois de tudo isso, se apenas olharmos para o , ele deve estar no estado misto máximo se a mistura aconteceu como desejado. O problema é como testar se essa saída é ou não o estado misto máximo. Existem técnicas úteis como esta , mas que precisão precisamos (ou seja, quantas repetições?). Precisamos ter cerca de para ter certeza, eu acho.| Um | $RC$$|A|^t$

De fato, essa maneira de fazer as coisas é tão ruim quanto clássica: você pode substituir o estado inicial de cada por e isso não altera o resultado . Mas isso realmente é como fazer uma escolha aleatória de cada vez e rodar várias vezes, verificando a distribuição de saída correta.I / 2 | A i $A_i$$\mathbb{I}/2^{|A_i|}$

Possíveis melhorias

• Executando como eu descrevi, a matriz de densidade de saída (no ) deve ser diagonal. Isso significa que a superposição uniforme sobre todos os estados da base é um eigenstate se e somente se o sistema é maximamente misturado. Eu faria se alguém pudesse combinar essa observação com algum tipo de amplificação de amplitude para obter uma leve aceleração. Observe que cria uma diferença muito rapidamente a partir de se o estado não for um vetor próprio.$\rho$| u ⟩ p k | u ⟩ | u $RC$$|u\rangle$$\rho^k|u\rangle$$|u\rangle$

• Além disso, você provavelmente precisará fazer algo mais inteligente com os registros ancilla. Há alguma esperança de que isso seja possível porque há bastante estrutura de grupo incorporada ao cubo de Rubik. Uma coisa que você pode tentar é ver se você pode substituir todos os registros ancilla com um único registo, aplicar portões Hadmard em cada qubit do registo entre cada rodada de-unitaries controladas. Pode ser que tudo isso faça com uma economia de eficiência em termos de número de qubits em comparação à minha sugestão original. Pode nem fazer isso.$t$

Se algum deles funciona diretamente, eu não sei. Ainda assim, acho que os princípios fundamentais são encontrar alguma estrutura de grupo útil e encontrar uma maneira de aplicar a amplificação de amplitude.

Você pode achar útil ler sobre projetos unitários . Este é certamente um problema distinto do que estamos falando aqui, mas algumas das ferramentas técnicas podem ser úteis. Grosso modo, a idéia é que um conjunto de unitaristas seja um design se a aplicação aleatória desses unitaristas permitir simular uma unidade verdadeiramente aleatória (extraída da medida de Haar) nas funções de saída quais, quando expandidas usando uma série de Taylor, são precisas até o grau . A conexão aproximada aqui é que, se você considerar os unitários que representam uma sequência de movimentos do Singmaster como , seria suficiente se esse conjunto fosse de design 2 (se você conseguirt f t t { U } Tr ( ρ 2$\{U\}$$t$$f$$t$$t$$\{U\}$$\text{Tr}(\rho^2)$ correto, você terminou).

(CW para evitar que os representantes respondam automaticamente)

Não pode ser uma maneira interativa para duas partes para reduzir em no valor de , acompanhando @ resposta de DaftWullie e comentários de @ Steven Sagona. Meu formalismo é ruim, mas espero que a idéia seja aprovada ...$t$

Por exemplo, ligue para as duas partes, Alice e Bob. As partes devem cooperar e se comportar honestamente de acordo com o protocolo.

Alice sabe como preparar dois estados, e . Aqui, é a superposição uniforme de todas as combinações de cubos de Rubik e é outro estado de macaco com o mesmo número de qubits (como o estado correspondente a um cubo de Rubik resolvido ou uma superposição uniforme sobre um grande subgrupo de ). Bob sabe como aplicar uma matriz a um estado quântico, em que corresponde ao único passo de todos os movimentos do Singmaster (com ancillas, quando apropriado).| A 1 ⟩ | Um 0 ⟩ | Um 1 ⟩ L M $\vert A_0 \rangle$$\vert A_1 \rangle$$\vert A_0\rangle$$\vert A_1\rangle$$G$$M$$M$

Alice e Bob querem mostrar que o tempo de mistura do grupo de cubos de Rubik sob os movimentos Singmaster é no máximo . Alice e Bob repetem os seguintes tempos.$t$$r$$s$

1. Alice joga uma moeda e fornece a Bob$i\in\{0,1\}$$\vert A_i \rangle$
2. Bob repete vezes para aplicar em e mede o projetor a cada vez.$r$$M$$\vert A_i \rangle$
3. Se o projector é para cada um dos iterações, então Bob diz que . Se o projetor não é por pelo menos um dos iterações, então Bob diz que Alice é .$1$$r$$i=0$$1$$r$$i=1$

Se , em seguida, cada um de Bob iterações no passo 2 não muda - porque, por definição é um eigenstate da matriz de Bob, e matriz de Bob apenas permuta os estados entre si. Se , o estado do macaco não é um eigenstate do projetor de Bob, e a chance de um não ser medido cresce rapidamente com . $i=0$$r$$\vert A_0\rangle$$\vert A_0 \rangle$$i=1$$\vert A_1 \rangle$$1$$r$

Assim, se Bob previu com precisão para iterações, a probabilidade de sucesso aumenta exponencialmente com , e o de Bob é grande o suficiente para distinguir um estado do cubo de Rubik válido de um estado de macaco.$i$$s$$s$$r$

Não sei a que distância o deve estar do . Também não sei se a interação pode ser removida.$\vert A_1\rangle$$\vert A_0\rangle$

Inicialmente, vamos considerar alguns registros e operadores.

1. O registrador , que codifica superposições de estados do cubo (por exemplo, uma permutação do cubo );$\vert A\rangle$$G$
2. O operador , que atua no para mapear o ket de all-0 para a superposição uniforme em todos os estados ;$U$$\vert A\rangle$$\vert 00\cdots 0\rangle$$\Vert G\Vert$
3. O registro , que codifica superposições de um conjunto de movimentos do Singmaster a serem aplicados a uma determinada posição (por exemplo, superposições de palavras do Singmaster movimentos de comprimento );$\vert B\rangle=\vert b_1\rangle\vert b_2\rangle\cdots\vert b_k\rangle$$k$
4. Os operadores e , que agem em para mapear o ket de todos os para a superposição uniforme de todas as palavras dos movimentos Singmaster de comprimento (e vice versa); e$V$$V^{-1}$$\vert B\rangle$$\vert 00\cdots 0\rangle$$18^k$$k$
5. O operador (controlado) , que aplica o Singmaster, move para uma determinada posição do cubo.$W$$b$

Se está na superposição uniforme de todos os elementos de , então está em um eigenstate de , e aplicações repetidas de não serão retrocedidas para afetar .$\vert A\rangle$$G$$\vert A\rangle$$W$$W$$\vert B\rangle$

Ou seja, deve retornar no circuito acima para o valor zero de todos os zeros ket .$V^{-1}$$\vert B\rangle$$\vert 00\cdots 0\rangle$

No entanto , como observado por @DaftWullie, se não estiver em igualdade de condições, então a diferença entre e aumenta muito rapidamente - acredito que uma velocidade na qual essa diferença acumulada depende precisamente das propriedades de mistura do operador de interesse.$\vert u\rangle$$\vert u \rangle$$\rho^k \vert u\rangle$

Assim, se são capazes de preparar um estado que está perturbada a partir da distribuição uniforme, de tal modo que não é uma autoestado, aplicações em seguida repetidos de será rapidamente construir uma diferença, e pode não ser o ponto zero.$\vert A\rangle$$\vert A\rangle$$W$ $V^{-1}\vert B\rangle$

Se tivéssemos uma função agindo em e uma resposta qubit que determina, digamos, se algum hash da posição do cubo de Rubik é menor que algum limiar , e usamos esse para controlar uma rotação de , então acredito que no O circuito acima não lerá o cetê com todos os zeros e, em vez disso, provavelmente desviará do cetê com todos os zeros de uma maneira que depende apenas de e do tempo de mistura do grupo de cubos de Rubik com o grupo gerador Singmaster.$F$$\vert A\rangle$$\vert C\rangle$$\{0,1\}^{\log_2 \Vert G\Vert}\mapsto (0,1)$$\delta$$F$$\vert A\rangle$V - 1 | B ⟩ ô$V^{-1}\vert B\rangle$$\delta$

Ou seja, espero que a medição de no circuito acima seja ou algo semelhante, em que o índice do primeiro dependa apenas do tempo de mistura e do limiar .$\vert B\rangle$$\vert 00000\cdots000101101\rangle$1 δ$1$$\delta$