Quanten-Lambda-Kalkül

35

Klassischerweise gibt es drei gängige Methoden, um über Berechnungen nachzudenken: Turing-Maschine, Schaltkreise und Lambda-Kalkül (ich verwende dies als Fang für die meisten funktionalen Ansichten). Alle drei haben sich als fruchtbar erwiesen, um über verschiedene Arten von Problemen nachzudenken, und verschiedene Bereiche verwenden aus diesem Grund unterschiedliche Formulierungen.

Wenn ich mit Quantencomputern arbeite, denke ich jedoch immer nur an das Schaltungsmodell. Ursprünglich wurde QC in Bezug auf Quantenturing-Maschinen definiert, aber soweit ich weiß, war diese Definition (obwohl sie Quantenschaltungen entspricht, wenn beide sorgfältig formuliert werden) bei weitem nicht so fruchtbar. Die 3. Formulierung (in Bezug auf Lambda-Kalkül oder ähnliche funktionale Einstellungen) ist mir völlig unbekannt. Daher meine Fragen:

  • Was sind nützliche Definitionen von Quanten-Lambda-Kalkül (oder anderen Funktionsparadigmen)?

  • Welche Teilbereiche von QIP erhalten einen tieferen Einblick in die Verwendung dieser Formulierung anstelle des Schaltungsmodells?

Anmerkungen

Mir ist bewusst, dass ich viele andere gängige Formalismen wie zelluläre Automaten, RAM-Modelle usw. ignoriere. Ich schließe diese aus, weil ich keine Erfahrung mit dem klassischen oder gar quantitativen Denken in diesen Modellen habe .

Mir ist auch bewusst, dass es in der Quanteneinstellung beliebte Alternativen gibt, wie messbasiert, topologisch und adiabatisch. Ich diskutiere sie nicht, weil ich mit den klassischen Gegenstücken nicht vertraut bin.

lambda-calculus quantum-computing reference-request computation-models Artem Kaznatcheev
quelle
4
Ich denke, das wäre auch in der theoretischen Informatik in Ordnung . :)
Kaveh
1
@Kaveh Ich bin sehr verwirrt, wo ich zwischen cstheory und CS.SE fragen soll :(. Ich habe mich entschieden, nicht nach cstheory zu fragen, weil ich kürzlich auf eine These gestoßen bin , die sich mit quantenfunktionaler Programmierung befasst (in Abschnitt 2.2), aber nicht Ich hatte die Zeit darüber nachzudenken und dachte: Hey, ich stelle eine halbherzige Frage.
Artem Kaznatcheev
1
Hoffentlich wird es zu einer gebackenen Frage für die Theorie führen. :)
Kaveh
1
Vielleicht möchten Sie sich mit LPQL befassen , einer linearen funktionalen Quantenprogrammiersprache, die in Calgary entwickelt wurde.
jmite

Antworten:

17

Hier ist eine halbherzige Antwort: Ich weiß, dass Ugo Dal Lago von der Universität Bologna die Quanten-Lambda-Rechnung studiert hat. Vielleicht möchten Sie seine Veröffentlichungen überprüfen und vielleicht diese im Besonderen:

Quantenimplizite Rechenkomplexität von U. Dal Lago, A. Masini, M. Zorzi.

Ich sage, es ist eine halbherzige Antwort, weil ich keine Gelegenheit hatte, eines seiner Werke zu lesen.

Alessandro Cosentino
quelle
12

Ich entschuldige mich im Voraus für den schamlosen Stecker, aber es gibt ein Papier von mir über eine Quanten-Lambda-Rechnung, die Sie vielleicht interessant finden. Es heißt The Dagger Lambda Calculus und bietet eine Darstellung höherer Ordnung für die Diagrammschaltungen, die die kategoriale Schule der Quantenberechnung eingeführt hat:

http://arxiv.org/abs/1406.1633

Sie können meinen Vortrag auch auf YouTube lesen, um weitere Informationen zu erhalten:

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

Weitere Arbeiten in diesem Bereich sind die Selinger-Valiron-Quanten-Lambda-Kalküle und die Lambda-Kalküle von Andre van Tonder: [ Sel04a ], [ Sel04b ], [ vTD03 ], [ vT04 ], [ SV04 ], [ SV08 ], [ SV10 ]. .

Philip Atz
quelle