Cálculo lambda cuántico

35

Clásicamente, hay 3 formas populares de pensar en la computación: la máquina de Turing, los circuitos y el cálculo lambda (lo uso como una trampa para la mayoría de las vistas funcionales). Los 3 han sido formas fructíferas de pensar sobre diferentes tipos de problemas, y diferentes campos utilizan diferentes formulaciones por este motivo.

Sin embargo, cuando trabajo con computación cuántica, solo pienso en el modelo de circuito. Originalmente, el control de calidad se definió en términos de máquinas cuánticas de Turing, pero que yo entienda, esta definición (aunque es equivalente a los circuitos cuánticos si ambos se formulan cuidadosamente) no ha sido tan fructífera. La tercera formulación (en términos de cálculo lambda o configuraciones funcionales similares) no estoy completamente familiarizado. De ahí mis preguntas:

  • ¿Cuáles son las definiciones útiles del cálculo lambda cuántico (u otros paradigmas funcionales)?

  • ¿Qué subcampos de QIP obtienen una visión más profunda al usar esta formulación en lugar del modelo de circuito?

Notas

Soy consciente de que estoy ignorando muchos otros formalismos populares como autómatas celulares, modelos RAM, etc. Los excluyo principalmente porque no tengo experiencia en pensar en términos de estos modelos de manera clásica, y mucho menos cuánticamente .

También soy consciente de que existen alternativas populares en el entorno cuántico, como las basadas en mediciones, topológicas y adiabáticas. No los discuto porque no estoy familiarizado con las contrapartes clásicas.

lambda-calculus quantum-computing reference-request computation-models Artem Kaznatcheev
fuente
44
Creo que esto también estaría bien en Ciencias de la Computación Teórica también. :)
Kaveh
1
@Kaveh Estoy muy confundido sobre dónde preguntar entre cstheory y CS.SE :(. Decidí no preguntar sobre cstheory porque me encontré con una tesis reciente que habla sobre programación funcional cuántica (en la sección 2.2) pero no tuve tiempo de pensarlo cuidadosamente. Entonces pensé: hey, haré una pregunta a medias.
Artem Kaznatcheev
1
Con suerte, dará lugar a una pregunta al azar para la teoría. :)
Kaveh
1
Es posible que desee echar un vistazo a LPQL , un lenguaje de programación cuántica funcional lineal desarrollado en Calgary.
jmite

Respuestas:

17

Aquí hay una respuesta a medias: sé que Ugo Dal Lago, de la Universidad de Bolonia, ha estado estudiando cálculo cuántico de lambda. Es posible que desee consultar sus publicaciones y tal vez esta en particular:

Complejidad computacional implícita cuántica por U. Dal Lago, A. Masini, M. Zorzi.

Estoy diciendo que es una respuesta a medias, porque no he tenido la oportunidad de leer ninguno de sus trabajos.

Alessandro Cosentino
fuente
12

Disculpas de antemano por el enchufe descarado, pero hay un documento mío sobre un cálculo lambda cuántico que puede encontrar interesante. Se llama The Dagger Lambda Calculus y proporciona una representación de orden superior para los circuitos esquemáticos que la escuela categórica de computación cuántica ha introducido:

http://arxiv.org/abs/1406.1633

También puedes consultar mi charla en YouTube para obtener más información:

https://www.youtube.com/watch?v=2pDPVd1BukI

Otros trabajos en el área incluyen los cálculos lambda cuánticos de Selinger-Valiron y el cálculo lambda de Andre van Tonder: [ Sel04a ], [ Sel04b ], [ vTD03 ], [ vT04 ], [ SV04 ], [ SV08 ], [ SV10 ] .

Philip Atz
fuente