Maneira uniforme de quantificar “ramificação” em computação não-determinística, probabilística e quântica?

Sabe-se que o cálculo de uma máquina de Turing não determinística (NTM) é representável como uma árvore de configurações, enraizada na configuração inicial. Qualquer transição no programa é representada por um link pai-filho nesta árvore.

Árvores semelhantes também podem ser construídas para visualizar os cálculos de máquinas quânticas e probabilísticas. (Observe que, para alguns propósitos, é melhor não exibir o gráfico relacionado para cálculos quânticos como uma árvore, pois dois nós que representam configurações idênticas no mesmo nível da árvore podem "cancelar" um ao outro devido à interferência quântica, mas isso não tem nada a ver com a presente pergunta.)

Certamente, os cálculos determinísticos não são assim; existe um único "ramo" na "árvore" correspondente para qualquer execução de uma máquina determinística.

Nos três casos mencionados acima, o que às vezes torna esses cálculos "difíceis" para computadores determinísticos não é realmente o fato de haver ramificações acontecendo, é uma questão de quanta ramificação está presente na árvore. Por exemplo, uma máquina de Turing não determinística de tempo polinomial que é garantida para produzir árvores de computação cujas "larguras" (isto é, número de nós no nível mais cheio) também são limitadas acima por uma função polinomial do tamanho da entrada que pode ser simulada por um polinômio TM determinística de tempos em tempos. (Observe que essa condição de "largura polinomial" é equivalente a restringir o NTM para criar no máximo um número logaritmicamente limitado de suposições não determinísticas.) O mesmo ocorre quando colocamos limites de largura semelhantes em cálculos probabilísticos e quânticos.

Eu sei que esse problema foi examinado em detalhes para cálculos não determinísticos. Veja, por exemplo, a pesquisa "Não determinismo limitado ", de Goldsmith, Levy e Mundhenk. Minha pergunta é: esse fenômeno de "ramificação limitada" ou "largura limitada" foi estudado em uma estrutura comum que abrange todos os modelos não determinísticos, probabilísticos e quânticos? Em caso afirmativo, qual é o nome padrão para ele? Quaisquer links para recursos serão apreciados.

cc.complexity-theory quantum-computing randomness derandomization nondeterminism Cem Say
fonte

Respostas:

Cálculos não determinísticos também podem ser vistos como verificação de reivindicações usando provas curtas. Ou seja, a classe NTIME (t) também pode ser vista como a classe das linguagens modo que uma reivindicação do formato possa ser verificada no tempo lendo uma breve prova. Nesse modelo, "quantificar a braquete" é análogo ao estudo de quão curtas as provas podem ser. Embora eu não conheça os trabalhos que estudaram essa questão, isso pode lhe dar uma direção de onde procurá-los. Um artigo que estudou uma questão relacionada no contexto de provas interativas é "Sobre Provas Interativas com Provador Laconic", de Goldreich, Vadhan e Wigderson: http://www.wisdom.weizmann.ac.il/~oded/p_laconic. html $L$ $x \in L$ $t(|x|)$

Em relação à computação probabilística: A quantidade de "ramificação" usada na computação é exatamente o número de bits aleatórios / moedas que o algoritmo usa. Quantificando esse número e minimizando-o, ele é estudado extensivamente na área de "Derandomização". Você pode ler sobre isso nos capítulos 20 e 21 do livro de Arora-Barak ( http://www.cs.princeton.edu/theory/index.php/Compbook/Draft ) ou no capítulo 8 do livro de Goldreich ( http: / /www.wisdom.weizmann.ac.il/~oded/cc-book.html ). Também deve ser mencionado que a crença comum nessa área é que . Se isso for verdade, o número de bits aleatórios que uma computação usa não afeta sua potência, desde que esse número seja polinomial. $P=BPP$

Ou Meir
fonte

Obrigado! Portanto, o fenômeno em questão corresponde a "ler um símbolo de prova" no primeiro caso e "jogar uma moeda" no segundo. Mas e o terceiro caso, ou seja, quântico? Eu realmente apreciaria se alguém que entendesse essas coisas explicasse qual é a diferença importante entre uma transição quântica cuja amplitude possui o módulo 1 (isto é, uma transição "não ramificada") e uma ramificação. A implementação de ramificações quânticas é mais difícil, onerosa etc. do que a implementação de não ramificações quânticas, por exemplo?

Cem Say

Não posso dizer nada rigoroso agora, mas acho que, no caso quântico, é a quantidade de emaranhamento no estado das configurações em que sua máquina está atualmente. Se não houver emaranhamento, seria como uma máquina probabilística. Então, em vez de contar o grau de ramificação, talvez contar a quantidade de emaranhamento faça mais sentido nesse caso, por exemplo, calcular a classificação do estado (o que os físicos chamam de número de Schmidt) ou qualquer outra maneira de medir o emaranhamento. Mas, como eu disse, isso é apenas um pensamento.

Marcos Villagra