O que se sabe sobre a eficácia da computação confiável?

Quão bem o seguinte problema foi investigado no TCS? (Peço desculpas se a declaração do problema parece vaga!)

Dado um modelo de computação MC (máquina de Turing, autômato celular, máquina Kolmogorov-Uspenskii ... etc.) e um modelo de ruído que poderia afetar o cálculo da MC, existe uma maneira de se recuperar dos erros causados ​​por esse ruído em uma maneira eficaz ? Por exemplo, digamos que algum tipo de ruído afeta uma máquina de Turing M, alguém poderia conceber uma máquina de Turing M 'que simula M sem um custo maior e é confiável (o que significa que M' é tolerante a esse ruído)?

Parece que alguns modelos de computação são melhores que outros ao fazer isso: autômatos celulares, por exemplo. Algum resultado se o ruído for substituído por um modelo adversário?

Desculpe pela tag! Não tenho reputação suficiente para colocar uma etiqueta adequada (computação confiável, computação tolerante a falhas ... etc.)

Embora existam algumas técnicas que podem ser aplicadas à tolerância a falhas para todos os modelos, a resistência de um modelo computacional à tolerância a falhas depende do modelo. Por exemplo, Peter Gacs pesquisou bastante a tolerância a falhas em autômatos celulares e mostra que (com muito trabalho) é possível criar autômatos celulares tolerantes a falhas.

Von Neumann provou que, usando a redundância, era possível construir um computador confiável a partir de componentes não confiáveis, usando apenas sobrecarga logarítmica.

Para computação quântica, os circuitos quânticos podem ser tolerantes a falhas com sobrecarga polilogarítmica ( sobrecarga, onde encontrar o valor correto de c ainda está aberto). Outra questão em aberto para o cálculo quântico é se o cálculo quântico adiabático pode ser tolerado a falhas de uma maneira fisicamente razoável (fisicamente razoável significa que é possível que o método leve a um computador quântico adiabático escalável; por exemplo, você não pode usar o temperatura a 0 à medida que o tamanho da computação aumenta).$\log^c n$$c$

Eu acho que o trabalho relacionado à autoestabilização está próximo do espírito da sua pergunta.

Um sistema auto-estabilizador se recupera de qualquer corrupção da RAM.

A pergunta é: "Existe uma maneira de se recuperar dos erros causados ​​pelo ruído [quântico] de maneira eficaz?" e a resposta de Peter Shor admiravelmente cobre uma maneira eficaz de responder a essa pergunta, a saber, projetando computadores quânticos tolerantes a falhas.

Uma maneira alternativa eficaz é muito comum na prática de engenharia. Argumentamos: "Se o ruído é suficientemente grande para que nenhuma computação quântica seja viável, talvez a dinâmica do sistema possa ser simulada com recursos clássicos em P."

Em outras palavras, muitas vezes podemos "recuperar-nos de maneira eficaz" do ruído, reconhecendo que o ruído está fornecendo um serviço importante para nós, reduzindo exponencialmente a complexidade computacional da simulação de sistemas clássicos e quânticos.

A literatura sobre abordagens centradas no ruído para simulação dinâmica é grande e crescente; uma referência recente cujos teoremas são motivados fisicamente e agradavelmente rigorosos, e que inclui muitas referências à literatura mais ampla, são os limites superiores de Plenio e Virmani sobre os limites de tolerância a falhas de computadores quânticos barulhentos baseados em Clifford (arXiv: 0810.4340v1).

Os dinamistas clássicos usam uma linguagem muito diferente na qual os mecanismos de ruído recebem o nome técnico de termostato ; Entendendo a Simulação Molecular de Frenkel e Smit : de Algoritmos a Aplicações (1996) fornece uma introdução matemática básica.

Quando transcrevemos termostatos clássicos e quânticos na linguagem da dinâmica geométrica, descobrimos (sem surpresa) que os métodos clássicos e quânticos para explorar o ruído para aumentar a eficiência da simulação são essencialmente idênticos; que suas respectivas literaturas tão raramente se referem é em grande parte um acidente da história que foi sustentado por obstruções notacionais.

Menos rigorosamente, mas de maneira mais geral, os resultados acima iluminam as origens da teoria da informação quântica de uma regra heurística amplamente adotada por químicos, físicos e biólogos, de que qualquer sistema clássico ou quântico que esteja em contato dinâmico com um banho térmico provavelmente provar ser simulável com recursos computacionais em P para todos os fins práticos (FAPP).

As exceções a essa heurística, clássica e quântica, representam importantes problemas em aberto. Seu número diminui notavelmente ano a ano; a avaliação crítica bienal da previsão de estrutura (CASP) fornece uma medida objetiva dessa melhoria.

Os limites fundamentais para esse progresso "More than Moore", impulsionado por ruído e de muitas décadas, no momento, são imperfeitamente conhecidos. Desnecessário dizer que, a longo prazo, nosso entendimento cada vez melhor desses limites nos aproximará da construção de computadores quânticos, enquanto, a curto prazo, esse conhecimento nos ajudará bastante a simular com eficiência sistemas que não são computadores quânticos. De qualquer forma, são boas notícias.

Parece que Gacs está a caminho de construir uma máquina de Turing tolerante a falhas. Dê uma olhada no seguinte: http://arxiv.org/abs/1203.1335

Os modelos de computação quântica lidam explicitamente com ruídos e maneiras de tornar os cálculos resilientes aos erros introduzidos nesse vetor. A computação quântica, curiosamente, pode ser feita para frente e para trás (por natureza das transformações de QM Hadamard e da independência do tempo do Hamiltoniano) - "não computar" é uma técnica usada para conter a maré de tais erros.

Em computadores 'reais' - servidores corporativos - há uma chance pequena, mas viável, de que um pouco de RAM seja lido incorretamente. A teoria dos códigos de detecção e correção de erros pode ser aplicada no nível da palavra da máquina para detectar e corrigir esses erros de 1 bit (sem muita sobrecarga). E, de fato, muitos servidores Enterprise que possuem operações críticas convidam um pequeno pedaço de paridade em cada palavra de RAM.

Embora esteja longe de ser uma prova, parece-me que os esquemas de codificação de correção de erros padrão podem ser feitos para funcionar com quase todos os autômatos teóricos (os autômatos celulares são suspeitos) com apenas desaceleração polinomial (de fato linear?).

Há algum trabalho sobre as chamadas estruturas e algoritmos de dados "resilientes" (árvores de pesquisa, contadores, dicionário). O modelo é o de uma RAM com a suposição de que até$k$os bits podem ser modificados por um adversário a qualquer momento. Constantemente muitos registros não podem ser modificados pelo adversário. Dependendo do parâmetro$k$, você pode obter algoritmos que ainda funcionam corretamente e cujo tempo de execução depende de $k$ é melhor do que correr $k$cópias independentes de um algoritmo. Uma recente palestra convidada de G. Italiano deve fornecer uma visão geral: Algoritmos resilientes e estruturas de dados (acabei de encontrar este artigo e ainda não o li, mas estou certo de que é um bom indicador).