37
$\begingroup$

Classically, there are 3 popular ways to think about computation: Turing machine, circuits, and lambda-calculus (I use this as a catch all for most functional views). All 3 have been fruitful ways to think about different types of problems, and different fields use different formulation for this reason.

When I work with quantum computing, however, I only ever think about the circuit model. Originally, QC was defined in terms of quantum Turing machines but as far as I understand, this definition (although equivalent to quantum circuits if both are formulated carefully) has not been nearly as fruitful. The 3rd formulation (in terms of lambda-calculus or similar functional settings) I am completely unfamiliar with. Hence my questions:

  • What are useful definitions of quantum lambda-calculus (or other functional paradigms)?

  • What subfields of QIP gain deeper insight from using this formulation instead of the circuit model?

Notes

I am aware that I am ignoring many other popular formalisms like cellular automata, RAM-models, etc. I exclude these mostly because I don't have experience with thinking in terms of these models classically, let alone quantumly.

I am also aware that there are popular alternatives in the quantum setting, such as measurement-based, topological, and adiabatic. I do not discuss them because I am not familiar with the classical counterparts.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ I think this would be fine on Theoretical Computer Science also. :) $\endgroup$
    – Kaveh
    Commented Apr 2, 2012 at 3:52
  • 1
    $\begingroup$ @Kaveh I am highly confused as to where to ask between cstheory and CS.SE :(. I decided not to ask on cstheory because I had come across a recent thesis that talks about quantum functional programming (in section 2.2) but haven't had the time to carefully think about it. So I thought: hey, I'll ask a half-baked question. $\endgroup$
    – Artem Kaznatcheev
    Commented Apr 2, 2012 at 4:02
  • 1
    $\begingroup$ Hopefully it will lead to a baked question for cstheory. :) $\endgroup$
    – Kaveh
    Commented Apr 2, 2012 at 4:45
  • 1
    $\begingroup$ You might want to take a look at LPQL, a linear functional quantum programming language developed at Calgary. $\endgroup$
    – Joey Eremondi
    Commented Mar 8, 2015 at 12:00

2 Answers 2

Reset to default
17
+25
$\begingroup$

here is a half-baked answer: I know that Ugo Dal Lago at University of Bologna has been studying quantum lambda calculus. You may want to check his publications and perhaps this one in particular:

Quantum implicit computational complexity by U. Dal Lago, A. Masini, M. Zorzi.

I am saying it's a half-baked answer, because I haven't had chance to read any of his works.

Improve this answer
$\endgroup$
13
$\begingroup$

Apologies in advance for the shameless plug, but there is a paper of mine on a quantum lambda calculus that you may find interesting. It is called The Dagger Lambda Calculus and provides a higher-order representation for the diagrammatic circuits that the categorical school of quantum computation have introduced:

http://arxiv.org/abs/1406.1633

You can also check my talk on YouTube for more info:

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

Other works in the area include the Selinger-Valiron quantum lambda calculi, and the lambda calculus by Andre van Tonder: [Sel04a], [Sel04b], [vTD03], [vT04], [SV04], [SV08], [SV10].

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.