Quantum lambda calcul

35

Classiquement, il y a 3 façons populaires de penser au calcul: la machine de Turing, les circuits et le lambda-calcul (je l'utilise comme un tout pour la plupart des vues fonctionnelles). Tous les trois ont été des moyens fructueux de réfléchir à différents types de problèmes, et différents domaines utilisent une formulation différente pour cette raison.

Cependant, lorsque je travaille avec l'informatique quantique, je ne pense jamais qu'au modèle de circuit. A l'origine, le CQ était défini en termes de machines de Turing quantiques mais, autant que je sache, cette définition (bien qu'équivalent aux circuits quantiques si les deux sont formulés avec soin) n'a pas été aussi fructueuse. La 3ème formulation (en termes de lambda-calcul ou de paramètres fonctionnels similaires) ne me connaît pas du tout. D'où mes questions:

  • Quelles sont les définitions utiles du quantum lambda-calcul (ou d'autres paradigmes fonctionnels)?

  • Quels sous-champs de QIP gagnent en connaissances grâce à l’utilisation de cette formulation au lieu du modèle de circuit?

Remarques

Je suis conscient du fait que j'ignore beaucoup d'autres formalismes populaires tels que les automates cellulaires, les modèles de RAM, etc. Je les exclure surtout parce que je n'ai pas l'expérience de la pensée classique en termes de modèles, et encore moins quantique .

Je suis également conscient qu'il existe des alternatives populaires dans le cadre quantique, telles que la mesure, la topologie et l'adiabatique. Je n'en discute pas car je ne connais pas les homologues classiques.

lambda-calculus quantum-computing reference-request computation-models Artem Kaznatcheev
la source
4
Je pense que cela conviendrait également pour l' informatique théorique . :)
Kaveh le
1
@Kaveh Je suis très confus quant à l' endroit où poser entre cstheory et CS.SE :(. J'ai décidé de ne pas poser sur cstheory parce que je l' avais rencontré une thèse récente qui parle de la programmation fonctionnelle quantique (dans la section 2.2) , mais pas J'ai eu le temps d'y réfléchir attentivement. Alors j'ai pensé: hé, je vais poser une question à moitié cuite.
Artem Kaznatcheev
1
Espérons que cela conduira à une question de fond pour la théorie. :)
Kaveh
1
Vous voudrez peut-être jeter un coup d'œil à LPQL , un langage de programmation quantique fonctionnel linéaire développé à Calgary.
jmite

Réponses:

17

Voici une réponse à moitié cuite: je sais qu'Ugo Dal Lago de l'université de Bologne étudie le calcul lambda quantique. Vous voudrez peut-être consulter ses publications et peut-être celle-ci en particulier:

Complexité informatique implicite quantique par U. Dal Lago, A. Masini, M. Zorzi.

Je dis que c'est une réponse à moitié cuite, parce que je n'ai pas eu l'occasion de lire aucune de ses œuvres.

Alessandro Cosentino
la source
12

Toutes mes excuses par avance pour la fiche éhontée, mais il y a un de mes papiers sur un calcul quantique lambda que vous pouvez trouver intéressant. Il s'appelle The Dagger Lambda Calculus et fournit une représentation d'ordre supérieur des circuits schématiques que l'école catégorique du calcul quantique a introduit:

http://arxiv.org/abs/1406.1633

Vous pouvez également consulter ma présentation sur YouTube pour plus d'informations:

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

Les autres travaux dans la région incluent les calculs de Selinger-Valiron quantum lambda et le calcul de lambda par Andre van Tonder: [ Sel04a ], [ Sel04b ], [ vTD03 ], [ vT04 ], [ SV04 ], [ SV08 ], [ SV08 ] .

Philip Atz
la source