¿Forma uniforme de cuantificar la "ramificación" en computación no determinista, probabilística y cuántica?

10

Es bien sabido que el cálculo de una máquina de Turing no determinista (NTM) es representable como un árbol de configuraciones, enraizado en la configuración inicial. Cualquier transición en el programa está representada por un enlace padre-hijo en este árbol.

También se pueden construir árboles similares para visualizar los cálculos de las máquinas probabilísticas y cuánticas. (Tenga en cuenta que es mejor para algunos propósitos no ver el gráfico relacionado para los cálculos cuánticos como un árbol, ya que dos nodos que representan configuraciones idénticas en el mismo nivel del árbol pueden "cancelarse" entre sí, debido a la interferencia cuántica, pero esto no tiene nada que ver con la presente pregunta).

Por supuesto, los cálculos deterministas no son así; hay una sola "rama" en el "árbol" correspondiente para cualquier ejecución de una máquina determinista.

En los tres casos mencionados anteriormente, lo que a veces hace que estos cálculos sean "difíciles" para las computadoras deterministas no es realmente que haya una ramificación, sino que se trata de cuánta ramificación está presente en el árbol. Por ejemplo, una máquina de Turing no determinista de tiempo polinomial que garantiza producir árboles de cálculo cuyos "anchos" (es decir, el número de nodos en el nivel más concurrido) también están limitados por una función polinomial del tamaño de entrada que puede ser simulada por un polinomio -tiempo determinista TM. (Tenga en cuenta que esta condición de "ancho polinomial" es equivalente a restringir el NTM para hacer un máximo de conjeturas no deterministas limitadas logarítmicamente). Lo mismo es cierto cuando ponemos límites de ancho similares en cálculos probabilísticos y cuánticos.

Sé que este problema se ha examinado en detalle para los cálculos no deterministas. Véase, por ejemplo, la encuesta " Nondeterminismo limitado " de Goldsmith, Levy y Mundhenk. Mi pregunta es: ¿se ha estudiado este fenómeno de "ramificación limitada" o "ancho limitado" en un marco común que abarca todos los modelos no deterministas, probabilísticos y cuánticos? Si es así, ¿cuál es el nombre estándar? Cualquier enlace a recursos será apreciado.

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

Respuestas:

11

Lx∈Lt(|x|)http://www.wisdom.weizmann.ac.il/~oded/p_laconic.html

P=BPP

O meir
fuente
¡Gracias! Entonces, el fenómeno en cuestión corresponde a "leer un símbolo de prueba" en el primer caso y "lanzar una moneda" en el segundo. Pero, ¿qué pasa con el tercer caso, es decir, cuántico? Realmente agradecería que alguien que comprende estas cosas explicara cuál es la diferencia importante entre una transición cuántica cuya amplitud tiene un módulo 1 (es decir, una transición "no ramificada") y una ramificada. ¿Implementar ramificaciones cuánticas es más difícil, costoso, etc., que implementar no ramificaciones cuánticas, por ejemplo?
Cem Say
No puedo decir nada riguroso en este momento, pero creo que en el caso cuántico es la cantidad de enredos en el estado de las configuraciones en las que se encuentra actualmente su máquina. Si no hay enredos, sería como una máquina probabilística. Entonces, en lugar de contar el grado de ramificación, tal vez contar la cantidad de enredo tiene más sentido en este caso, por ejemplo, calcular el rango del estado (lo que los físicos llaman número de Schmidt), o cualquier otra forma de medir el enredo. Pero, como dije, esto es solo un pensamiento.
Marcos Villagra