Que tipos de problemas estatísticos provavelmente se beneficiarão da computação quântica?

14

Estamos no advento da computação quântica , com linguagens quânticas antecipando computadores quânticos de hardware agora disponíveis em níveis alto e baixo para computadores quânticos simulados. A computação quântica traz novas funções elementares, como emaranhamento e teletransporte de qubits, medição de qubits e imposição de superposição a qubits.

Que tipos de problemas estatísticos provavelmente se beneficiarão da computação quântica?

Por exemplo, os computadores quânticos fornecerão geração de números aleatórios verdadeiros mais onipresente? E quanto à geração de números pseudo-aleatórios computacionalmente baratos? A computação quântica ajudará a acelerar a convergência do MCMC ou garantirá limites superiores no tempo de convergência? Haverá algoritmos quânticos para outros estimadores baseados em amostragem?

Essa é uma pergunta ampla, e respostas aceitáveis ​​também serão amplas, mas parabéns se diferenciarem a computação quântica e a clássica. (Se essa é uma pergunta muito ampla , ajude-me a torná-la melhor.)

Alexis
fonte
6
+1 Acho que é uma pergunta boa e interessante. Como ele convida muitas respostas (e potencialmente especulativas), está na fronteira de que tipo de pergunta funciona aqui. Ele compartilha essa fronteira com alguns de nossos threads mais populares e duradouros e, como esses, merece o status CW.
whuber
7
Como o aprendizado de máquina é uma espécie de subdisciplina da estatística, você pode achar interessantes os algoritmos Quantum para aprendizado de máquina supervisionado e não supervisionado .
Jakub Bartczuk 31/12/19
2
A computação mais rápida é sempre valiosa, mas atualmente a computação quântica está em um estágio inicial e eles ainda não conseguiram superar a computação clássica. Agradeço esta pergunta porque me levou a aprender algo sobre ela. Até agora, acho difícil entender.
Michael R. Chernick 01/01/19
1
Importa que a computação quântica ainda esteja na infância? Funciona e supera a computação clássica quando era bebê. Também não é tão sem importância, a velocidade pode ser exponencial para problemas como resolver equações matriciais ou encontrar o inverso de funções e caixas pretas. Agora só precisamos fazê-lo crescer. Os algoritmos que podem ser executados em tais computadores futuros já foram criados há décadas. É simples (embora muito amplo, pense nas equações da matriz) criar aplicativos para estatísticas.
Sextus Empiricus 01/01
1
Penso que o primeiro e mais importante ponto é que a computação quântica pode teoricamente acelerar a aritmética em um grau significativo. Isso está correto? Nesse caso, todas as rotinas de álgebra linear já têm um benefício.
Adamo

Respostas:

1

É provável que os métodos de força bruta se beneficiem por causa do que é a computação quântica. Por quê? Uma possível explicação física do caminho de uma bola de beisebol é que todos os caminhos quânticos possíveis são automaticamente explorados e o caminho de menor gasto de energia, ou seja, o caminho de menor resistência disponível, é escolhido e tudo o que é feito sem a necessidade de construir uma calculadora ; os cálculos são inefáveis. Generalização; a natureza pode ser vista como uma calculadora quântica. Assim, os problemas semelhantes, os que otimizam, como a minimização da regressão de algum critério, são que a qualidade do ajuste ou outro (qualidade do ajuste é, em alguns casos, mal colocada) são os que se beneficiarão.

BTW, as etapas intermediárias; as iterações, na otimização, não seriam calculadas, apenas o resultado final, exatamente como quando ocorre um campo de beisebol. Ou seja, apenas o caminho real do beisebol ocorre, os caminhos alternativos são automaticamente excluídos. Uma diferença entre uma implementação estatística e um evento físico é, no entanto, que o erro do cálculo estatístico pode ser tão pequeno quanto desejado, aumentando arbitrariamente a precisão (por exemplo, até 65 casas decimais), e isso normalmente não é possível fisicamente. . Por exemplo, mesmo uma máquina de arremessar não lançará uma bola de beisebol em um caminho exatamente duplicado.

Carl
fonte
+1 Obrigado. Você diria que os métodos de Monte Carlo, os métodos de inicialização e outras abordagens quantitativas das soluções se encaixam no rótulo "força bruta"?
Alexis
1
Potencialmente, eles podem, mas não da mesma maneira que a programação linear. Por exemplo, o método de Metropolis e Ulam (simulação de Monte Carlo) foi originalmente aplicado por Ulam para calcular a massa crítica da bomba atômica. Com a computação quântica verdadeira, uma bomba simulada sofrerá uma explosão simulada, ou não, na mesma velocidade da explosão real. Aliás, eu conheci o Ulam em 1964, eu era jovem na época.
1525 Carl
1
Obrigado, esse ponto sobre "explosão simulada" realmente ajuda e acho que está construindo minha intuição sobre esse tópico. Também:: D Uau!
Alexis
1

Gostei da resposta acima no beisebol. Mas eu seria cauteloso sobre o que a computação quântica poderia fazer bem.

Parece que pode se sair muito bem em coisas como quebrar esquemas criptográficos e coisas do tipo: ser capaz de sobrepor todas as soluções e depois colapsar na solução real pode ser bastante rápido.

Mas na década de 1980 - que foi há muito tempo - havia uma empresa de alto nível chamada Thinking Machines. Veja este artigo: https://en.wikipedia.org/wiki/Thinking_Machines_Corporation

A ideia toda tinha um cheiro de computação quântica. Utilizou um arranjo de hipercubo n-dimensional. Imagine, se quiser, quatro microprocessadores (muito simples) conectados em um quadrado. Cada um poderia fazer um cálculo e compartilhar o resultado com o processador antes (no sentido anti-horário), depois (no sentido horário) ou no lado oposto (no sentido contrário). Em seguida, imagine 8 processadores em um cubo que podem expandir esse conceito para três dimensões (agora cada processador pode compartilhar sua saída com uma ou mais de 7 outras: 3 ao longo de um vértice do cubo; três na face de um quadrado que o processador fazia parte de e uma diagonal em 3 espaços).

Agora leve isso para talvez 64 processadores em um hipercubo 6-dimensional.

Essa foi uma das idéias mais quentes da época (junto com a dedicada máquina Lisp de 34 bits que a Symbolics lançou e o sistema de memória levemente bizarro lançado pela Kendall Square Research - ambos têm páginas da Wikipédia que merecem ser lidas).

O problema era que havia precisamente um, e apenas um algoritmo que realmente funcionou bem na arquitetura da TM: uma Transformada Rápida de Fourier usando o que foi chamado de "Algoritmo de Aleatório Perfeito". Foi uma visão genial de como usar uma técnica de máscara binária, o algoritmo sob medida e a arquitetura para processar paralelamente uma FFT de uma maneira brilhante e inteligente e rápida. Mas acho que eles nunca encontraram outro uso único para isso. (consulte esta pergunta relacionada: /cs/10572/perfect-shuffle-in-parallel-processing )

Estou aqui há tempo suficiente para perceber que tecnologias que parecem brilhantes e poderosas geralmente acabam não resolvendo um problema (ou problemas suficientes) para torná-las úteis.

Havia muitas idéias brilhantes na época: TM, Symbolics, KSR, assim como Tandem (ido) e Stratus (surpreendentemente, ainda vivo). Todos pensavam que essas empresas - pelo menos algumas delas - dominariam o mundo e revolucionariam a computação.

Mas, em vez disso, temos o FaceBook.

eSurfsnake
fonte
Você está certo em chamar a atenção, e eu gosto da sua perspectiva histórica, o eSurfsnake. Eu cresci no Condado de Santa Clara quando se tornou o Vale do Silício ... Há muito que aprecio profundamente a computação universal. Uma das razões pelas quais a estatística me comove é porque a probabilidade - verdadeira aleatoriedade - está fora do domínio da computação. Podemos simulá-lo ... muito bem para muitos propósitos, mas há aspectos da natureza, aparentemente, que não são computação. A computação quântica parece oferecer operações elementares que também não são a computação de Turing ... então, eu quero entender o que essas ferramentas podem significar.
Alexis
@ Alexis Na verdade, os computadores quânticos não têm nenhuma habilidade de super-Turing. Qualquer problema que possa ser calculado usando um computador quântico também pode ser calculado usando um computador clássico, que decorre do fato de que computadores clássicos podem simular computadores quânticos. Porém, existem alguns problemas conhecidos que podem ser resolvidos com mais eficiência usando computadores quânticos.
usar o seguinte comando
@ user20160 A verdadeira aleatoriedade é uma habilidade super-Turing. Superposição é uma habilidade super-Turing. Simulação não é a coisa em si.
Alexis
@ Alexis Não tenho certeza se estamos falando da mesma coisa, mas o que quero dizer com super-Turing é a capacidade de calcular uma função que uma máquina de Turing não pode. Curiosamente, a verdadeira aleatoriedade não permite calcular qualquer função que não possa ser calculada deterministicamente. Concordo plenamente que a simulação não é a coisa em si, mas está no cerne da equivalência computacional (onde abstraímos a coisa em si). Se a máquina A pode simular a máquina B, A pode calcular qualquer função que B possa. Mais em Nielsen e Chuang. Computação quântica e informação quântica
user20160
0

Que tipos de problemas estatísticos provavelmente se beneficiarão da computação quântica?

Na página 645 de " Química Física: Conceitos e Teoria " Kenneth S. Schmitz explica:

Os efeitos quânticos se tornam importantes quando o comprimento de onda de De Broglie se torna comparável ou é maior que as dimensões da partícula. Quando isso ocorre, as funções de onda podem se sobrepor, fornecendo diferentes propriedades do sistema.

Os sistemas macroscópicos podem ser analisados ​​por métodos clássicos, como explica a página da Wikipedia:

Considerações mais refinadas distinguem a mecânica clássica e a quântica com base no fato de que a mecânica clássica falha em reconhecer que matéria e energia não podem ser divididas em parcelas infinitesimalmente pequenas, de modo que, em última análise, a divisão fina revela características irredutivelmente granulares. O critério da finura é se as interações são ou não descritas em termos da constante de Planck. Grosso modo, a mecânica clássica considera as partículas em termos matematicamente idealizados, tão finos quanto os pontos geométricos sem magnitude, ainda tendo suas massas finitas. A mecânica clássica também considera materiais estendidos matematicamente idealizados como substanciais geometricamente continuamente. Tais idealizações são úteis para a maioria dos cálculos do dia a dia, mas podem falhar inteiramente em moléculas, átomos, fótons e outras partículas elementares. De várias maneiras, a mecânica clássica pode ser considerada uma teoria principalmente macroscópica. Em uma escala muito menor de átomos e moléculas, a mecânica clássica pode falhar e as interações das partículas são descritas pela mecânica quântica.

   

Por exemplo, os computadores quânticos fornecerão geração de números aleatórios verdadeiros mais onipresente ?

Não. Você não precisa de um computador para gerar um número aleatório verdadeiro , e usar um computador quântico para fazer isso seria um enorme desperdício de recursos, sem melhoria na aleatoriedade.

A ID Quantique tem disponíveis SoCs, placas independentes e PCIe à venda por US $ 1200 a US $ 3500 . É um pouco mais do que fótons viajando através de um espelho semi-transparente, mas possui propriedades aleatórias quânticas suficientes para passar no AIS 31 ("Classes de funcionalidade e metodologia de avaliação para um gerador de números aleatórios verdadeiro (físico) - Versão 3.1, 29 de setembro de 2001" .PDF ). É assim que eles descrevem seu método:

Quantis é um gerador físico de números aleatórios que explora um processo de óptica quântica elementar. Os fótons - partículas de luz - são enviados um a um para um espelho semi-transparente e detectados. Esses eventos exclusivos (reflexão - transmissão) estão associados aos valores de bits “0” - “1”. Isso nos permite garantir um sistema verdadeiramente imparcial e imprevisível.

Um sistema mais rápido (1 Gbit / s) é oferecido pelo QuintessenceLabs . O gerador de números aleatórios quânticos “qStream” é compatível com o NIST SP 800-90A e atende aos requisitos do NIST SP 800 90B e C. Ele usa diodos de túnel da Esaki . Seus produtos são novos e os preços ainda não estão disponíveis ao público.

Também estão disponíveis sistemas da Comscire por várias centenas a alguns milhares de dólares. Seus métodos e patentes PCQNG e RNG pós-quantum são explicados em seu site.

A Quantum Numbers Corp. desenvolveu um dispositivo do tamanho de um chip para produzir rapidamente (1 Gbit / s) números aleatórios quânticos que, segundo eles, estarão disponíveis em breve.

E quanto à geração de números pseudo-aleatórios computacionalmente baratos?

Se você quer dizer "computacionalmente barato", como em poucas instruções e execução rápida = sim.

Se você quer dizer que qualquer computador é um meio barato para gerar números aleatórios verdadeiros = não.

Qualquer propriedade implementada no QRNG não produzirá números pseudo- aleatórios.

A computação quântica ajudará a acelerar a convergência de Markov Chain Monte Carlo (MCMC) ou garantirá limites superiores no tempo de convergência?

Por enquanto, deixarei que outra pessoa dê uma olhada nisso.

Haverá algoritmos quânticos para outros estimadores baseados em amostragem?

Provavelmente.

Por favor edite e melhore esta resposta da Wiki.

Rob
fonte
Não sei se concordo com o "verdadeiro desperdício de recursos" para um RNG verdadeiro e confiável. Por um lado, o pseudo-RNG leva tempo, o que aumenta rapidamente em trabalhos de simulação em larga escala. Por outro lado, a RNG consome memória e também para trabalhos de simulação em larga escala. Ter uma fonte garantida rápida de aleatoriedade verdadeira a partir de uma distribuição conhecida não parece tão inútil. Além disso, outras soluções para o verdadeiro RNG não impedem que computadores quânticos também forneçam essa solução.
Alexis