cálculo, álgebra, lógica

Question

Por tanto, una forma muy sencilla de describir un ordenador digital es decir que es un dispositivo para realizar operaciones booleanas. Le alimentas con un montón de cadenas de bits, que es una descripción del problema y sus parámetros en binario, el ordenador realiza un montón de operaciones booleanas como $\wedge$ , $\vee$ , $\neg$ y te devuelve otra cadena de bits que, con suerte, es la versión codificada de la respuesta que estabas buscando. A partir de esta descripción, no es difícil ver la conexión de la computación clásica con los sistemas dinámicos discretos y la lógica clásica: las operaciones proporcionan la dinámica cambiando los bits de forma controlada y, dado que restringimos las operaciones a un subconjunto determinado, obtenemos la lógica clásica. Mi pregunta se refiere a la computación analógica y cuántica. ¿Existe una descripción sencilla de un ordenador cuántico o de un ordenador analógico que haga un poco más evidente la conexión de esa noción de computación con las otras ramas de las matemáticas? ¿Cuál es el tipo más básico de codificación de un problema que puede introducirse en un ordenador cuántico o analógico y cuáles son las operaciones más básicas que se realizan con esta codificación?

Edit: Los downvotes deberían venir con comentarios para saber qué cambiar para que mi pregunta sea más clara. Siendo un novato sólo estoy tratando de reconstruir algunos temas acerca de la computación, la lógica y el álgebra.

Edición: alpheccar ha proporcionado un enlace a un artículo de John Baez y Mike Stay que responde bastante bien a mi pregunta e incluso la sitúa en un contexto mucho más amplio. Aquí está el enlace proporcionado por alpheccar.

Answer 1

A partir de esta descripción, no es difícil ver la conexión de la computación clásica con los sistemas dinámicos discretos y la lógica clásica: las operaciones proporcionan la dinámica mediante la rotación controlada de bits y, dado que restringimos las operaciones a un subconjunto determinado, obtenemos la lógica clásica.

Cuidado: esta observación sólo es válida para sistemas de estado finito. Si su modelo idealizado de ordenador digital puede manejar cantidades de entrada potencialmente ilimitadas, se pierde la conexión con la lógica clásica. Afortunadamente, falla de un modo que revela conexiones con la topología y explica por qué existen modelos topológicos de lógica intuicionista.

La idea básica es que consideramos que un ordenador realiza una función $f$ . Entonces, para cualquier valor de entrada (del conjunto de entrada $A$ ), si devuelve una respuesta en un tiempo finito, puede haber observado como máximo una cantidad finita de información sobre la entrada. Esto significa que podemos dotar a nuestro conjunto de entrada de una topología de la siguiente manera: supongamos que nuestras observaciones básicas son una colección de predicados sobre $A$ . Entonces obtenemos la estructura topológica del siguiente hecho: sólo podemos tomar intersecciones finitas porque sólo podemos hacer un número finito de observaciones y, por tanto, sólo podemos concluir la conjunción de un número finito de predicados. Podemos tomar uniones infinitas (es decir, existenciales) porque podemos "tener suerte" y adivinar la rama correcta de la unión (es decir, el testigo del existencial).

Entonces, sorprendentemente, podemos utilizar continuidad como sustituto de computabilidad ¡! Esta es más o menos la idea que tuvo Dana Scott cuando inventó la teoría de dominios (que recibe un nombre diferente porque las topologías que obtenemos de esta manera son "raras" -por ejemplo, normalmente no son Hausdorff- y por tanto los teoremas que quieres se desarrollan de forma un poco diferente).

Answer 2

El paso básico de un cálculo cuántico es la aplicación de una matriz unitaria a los qubits. Así, una computación cuántica consiste en iterar esta matriz unitaria.

Se puede ver la computación cuántica como construida a partir de puertas, no puertas lógicas clásicas, sino más bien, puertas cuánticas cada una representada por una matriz unitaria. Una diferencia interesante con las puertas de cálculo clásicas es que estas puertas cuánticas son necesariamente reversibles, por lo que los cálculos cuánticos son, en principio, reversibles. (También existen puertas reversibles clásicas, como la puerta Puerta Toffoli que bastan para el cálculo clásico).

Solovay y Kitaev proporcionaron un conjunto de puertas cuánticas universales.