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$ 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$ Commented Apr 2, 2012 at 4:02
  • 1
    $\begingroup$ Hopefully it will lead to a baked question for cstheory. :) $\endgroup$ 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$ 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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.