4 ms·

A lambda calculus for quantum computation

114 points by jessup 9y ago

darkkindness 9y ago
Very cool! The examples on this page are Scheme implementations of the Examples section of his 2003 paper[0] linked on the page. He goes over the derivation of the programs for these examples in more detail in the paper. [0]: https://arxiv.org/pdf/quant-ph/0307150.pdf https://arxiv.org/pdf/quant-ph/0307150.pdf
ssivark 9y ago
Interesting resource. Given that "no-cloning" [1] seems to be a fundamental property of quantum mechanics, I would expect any relevant programming language to enforce linear types i.e. "use exactly once" constraint. [1]: https://quantiki.org/wiki/no-cloning-theorem https://quantiki.org/wiki/no-cloning-theorem
- fovc 9y ago
  The linked paper says in the abstract: The calculus turns out to be closely related to the linear lambda calculi used in the study of Linear Logic. We set up a computational model and an equational proof system for this calculus, and we argue that it is equivalent to the quantum Turing machine.
  - ssivark 9y ago
    Yes, I was placing that statement in context.
naasking 9y ago
A brief survey of quantum programming languages, http://lambda-the-ultimate.org/node/1618 http://lambda-the-ultimate.org/node/1618 A functional quantum programming language, http://lambda-the-ultimate.org/node/251 http://lambda-the-ultimate.org/node/251 A Quantum Lambda Calculus, http://lambda-the-ultimate.org/node/3769 http://lambda-the-ultimate.org/node/3769
- vtomole 9y ago
  That survey was written over 10 years ago. The field of quantum computation has grown by leaps and bounds since then. Modern quantum programming languages like pyQuil [0], Qiskit [1], and Q# [2] are designed to address the progress of quantum computing; like the fact that we now have small devices with 10s of qubits. [0]: http://pyquil.readthedocs.io/en/latest/ http://pyquil.readthedocs.io/en/latest/ [1]: https://www.qiskit.org/ https://www.qiskit.org/ [2]: https://docs.microsoft.com/en-us/quantum/quantum-qr-intro?view=qsharp-preview https://docs.microsoft.com/en-us/quantum/quantum-qr-intro?vi...
  - adamisntdead 9y ago
    There is an abundance of tools for reasearchers now, each with specific purposes. Libraries such as libquantum have different uses to libraries such as qiskit.
    - vtomole 9y ago
      Could you give me an example of different use cases for libquantum vs qiskit? Thanks.
kuwze 9y ago
That's awesome! Also D-Wave uses Common Lisp[0]. [0]: https://cjelupton.wordpress.com/2014/08/14/quantum-computing-and-lisp/ https://cjelupton.wordpress.com/2014/08/14/quantum-computing...
- vtomole 9y ago
  D-Wave doesn't have a quantum computer. They have a quantum annealer.

114 points by jessup 9y ago

Very cool! The examples on this page are Scheme implementations of the Examples section of his 2003 paper[0] linked on the page. He goes over the derivation of the programs for these examples in more detail in the paper. [0]: https://arxiv.org/pdf/quant-ph/0307150.pdf https://arxiv.org/pdf/quant-ph/0307150.pdf

ssivark 9y ago

Interesting resource. Given that "no-cloning" [1] seems to be a fundamental property of quantum mechanics, I would expect any relevant programming language to enforce linear types i.e. "use exactly once" constraint. [1]: https://quantiki.org/wiki/no-cloning-theorem https://quantiki.org/wiki/no-cloning-theorem

fovc 9y ago
The linked paper says in the abstract: The calculus turns out to be closely related to the linear lambda calculi used in the study of Linear Logic. We set up a computational model and an equational proof system for this calculus, and we argue that it is equivalent to the quantum Turing machine.
- ssivark 9y ago
  Yes, I was placing that statement in context.

naasking 9y ago

A brief survey of quantum programming languages, http://lambda-the-ultimate.org/node/1618 http://lambda-the-ultimate.org/node/1618 A functional quantum programming language, http://lambda-the-ultimate.org/node/251 http://lambda-the-ultimate.org/node/251 A Quantum Lambda Calculus, http://lambda-the-ultimate.org/node/3769 http://lambda-the-ultimate.org/node/3769

vtomole 9y ago
That survey was written over 10 years ago. The field of quantum computation has grown by leaps and bounds since then. Modern quantum programming languages like pyQuil [0], Qiskit [1], and Q# [2] are designed to address the progress of quantum computing; like the fact that we now have small devices with 10s of qubits. [0]: http://pyquil.readthedocs.io/en/latest/ http://pyquil.readthedocs.io/en/latest/ [1]: https://www.qiskit.org/ https://www.qiskit.org/ [2]: https://docs.microsoft.com/en-us/quantum/quantum-qr-intro?view=qsharp-preview https://docs.microsoft.com/en-us/quantum/quantum-qr-intro?vi...
- adamisntdead 9y ago
  There is an abundance of tools for reasearchers now, each with specific purposes. Libraries such as libquantum have different uses to libraries such as qiskit.
  - vtomole 9y ago
    Could you give me an example of different use cases for libquantum vs qiskit? Thanks.

kuwze 9y ago

That's awesome! Also D-Wave uses Common Lisp[0]. [0]: https://cjelupton.wordpress.com/2014/08/14/quantum-computing-and-lisp/ https://cjelupton.wordpress.com/2014/08/14/quantum-computing...

vtomole 9y ago
D-Wave doesn't have a quantum computer. They have a quantum annealer.