Como a computação quântica mudará a programação? [fechadas]

Como a programação de um algoritmo quântico é diferente? Como seria a linguagem C se fosse projetada para qubits? Os tipos mudariam?

Quando examinei isso há algum tempo, ficou claro que os algoritmos quânticos, embora não particularmente rápidos, permitem um paralelismo exponencialmente maciço. Portanto, eles brilharão nos casos que envolvem pesquisa em espaços que não são práticos com hardware seqüencial, mesmo hardware sequencial massivamente paralelo.

Uma propriedade dos algoritmos quânticos é que eles precisam ser reversíveis . Qualquer algoritmo pode ser convertido em um que seja reversível, adicionando-lhe bastante manutenção de registros para permitir que ele seja executado para trás.

Outra propriedade é que obter uma resposta de um algoritmo quântico é uma questão de acerto e fracasso, porque o que você obtém no final de uma computação são várias respostas, cada uma com sua própria probabilidade. Ele precisa ser executado de tal maneira que a resposta que você deseja tenha alta probabilidade. Isso pode envolver a execução do algoritmo para frente e para trás várias vezes.

Confira o algoritmo de pesquisa de Grover .

INSERIDO para mostrar a operação fundamental do algoritmo de Grover. Suponha que haja um problema de pesquisa. As respostas possíveis são 0, 1, 2 e 3, mas a resposta certa é 2. Portanto, o computador quântico é colocado em uma superposição de todos os quatro estados e passa por uma sequência de etapas para ver qual está correto e inverte sua amplitude, como os pontos e setas pretos abaixo:

Você pode ver que a seta 2 foi invertida dentro da máquina, mas não há como dizer isso lá fora, porque apenas probabilidades são visíveis fora, que são amplitudes ao quadrado , e quando ao quadrado são todas iguais.

No entanto, as amplitudes têm uma média, indicada pela linha vermelha, e o computador pode passar por uma sequência de etapas que inverte cada amplitude sobre a média . Quando isso é feito, as amplitudes e as probabilidades são transferidas para o estado 2, a resposta certa ! Portanto, se a máquina for observada, o estado 2 brilha.

Não é tão simples assim. Geralmente são necessários vários ciclos da máquina, para frente e para trás, invertendo no final de cada ciclo, para maximizar a probabilidade da resposta correta. Além disso, deve-se tomar cuidado para não fazê-lo mais do que esse número de vezes, porque pode facilmente se reverter.

Então, por que eles dizem que computadores quânticos são tão rápidos ? Porque toda vez que você duplica o número de qubits, você soma o paralelismo, mas não o tempo, então acaba vencendo.

Isso não é divertido?

Eu estava pessoalmente interessado em como isso poderia ser aplicado à verificação da correção do software. Agora testamos o software lançando várias entradas de teste e (para ser simples demais) verificando se ele atinge um Assert. Em um computador quântico, pode ser possível executá-lo em paralelo contra um conjunto de entradas muito mais denso e ver se algum desses casos atinge um Assert.

Como se a entrada para o algoritmo fosse de 128 bytes ou 1024 bits, existem 2 ^ 1024 ou 10 ^ 308 possíveis entradas diferentes. Não há como testar muitas entradas em um computador convencional, mas um computador quântico pode testá-las todas em paralelo.

Como seria a linguagem C se fosse projetada para qubits? Os tipos mudariam?

Seria tão drasticamente diferente a ponto de ser incompreensível como C.

A questão principal (como eu a entendo) é que a computação quântica não funciona de uma maneira imperativa agradável 'faça isso, depois aquilo, depois essa outra coisa'. Tentar forçar a capacidade de C de fazer isso no 'processador' do computador quântico será, se não impossível, descontroladamente ineficiente.

Os algoritmos de programação para computadores quânticos (novamente, como eu os entendo) tendem a estar mais próximos do mapa / redução do estilo de programação funcional, uma vez que a computação quântica permite que todos os candidatos da parte 'reduzir' existam simultaneamente e "caiam" do computador quando observado.

Observe que existem alguns algoritmos para computadores quânticos, mesmo que os dispositivos não existam para executá-los. Algoritmo de Simon, por exemplo.

Para fazer o uso mais eficaz possível de um computador quântico, é preciso ser capaz de lidar com entradas e saídas que são estados de um registro quântico, para o qual não há realmente nenhum análogo clássico. Falando de alguns anos de experiência no campo da informação quântica, devo adverti-lo de que ninguém realmente tem uma boa intuição para isso além da matemática abstrata das álgebras C *, e me disseram que mesmo essa intuição se mostra inadequada se você começar a pensar sobre a teoria da relatividade.

A classe de problemas que são eficientemente solucionáveis ​​em um computador quântico é conhecida como BQP, para polinômio quântico encadernado. Esta é a versão quântica do BPP, e você pode encontrar mais informações neste documento: http://www.scottaaronson.com/papers/bqpph.pdf

Foi ontem à noite que um pesquisador de algoritmos quânticos me disse que há um problema muito importante que é completo no BQP: resolver um sistema linear de N equações. Classicamente, isso é solucionável em etapas O (N) com eliminação gaussiana. O algoritmo de Harrow-Hassidim-Lloyd ( http://arxiv.org/abs/0811.3171 ) o resolve no polilog (N), desde que você esteja disposto a aceitar uma resposta que tenha a solução codificada como um estado quântico. Se você deseja fazer pleno uso de um computador quântico, parece necessário ter um tipo correspondente ao estado de um registro quântico.

Embora eu esteja um pouco fora da minha experiência específica, arriscaria adivinhar que você seria capaz de programar um computador quântico enquanto tivesse acesso a um tipo correspondente a estados mágicos. Esse é um conceito difícil, porém, que requer bastante estudo do assunto.

Esteja avisado de que estamos há muito tempo com uma linguagem de programação quântica, porque estamos em um estágio muito primitivo da pesquisa em computação quântica. Pedir um C quântico agora seria como ir a Alan Turing e pedir para ele projetar Python. Ainda não temos a versão quântica do tubo de vácuo!