Quantum programming: Difference between revisions

Revision as of 01:41, 19 August 2025

Revision as of 09:50, 20 August 2025

Line 176:

His lambda-q calculus is powerful enough to express any quantum computation. However, this language can efficiently solve [[NP-complete]] problems, and therefore appears to be strictly stronger than the standard quantum computational models (such as the [[quantum Turing machine]] or the [[quantum circuit]] model). Therefore, Maymin's lambda-q calculus is probably not implementable on a physical device {{Citation needed|date=February 2019}}.

In 2003, André van Tonder defined an extension of the [[lambda calculus]] suitable for proving correctness of quantum programs. He also provided an implementation in the [[Scheme (programming language)|Scheme]] programming language.<ref>{{cite web |author=André van Tonder |title=A lambda calculus for quantum computation (website) |url=httphttps://www.het.brown.edu/people/andre/qlambda |access-date=October 2, 2007 |archive-date=March 5, 2016 |archive-url=https://web.archive.org/web/20160305100936/http://www.het.brown.edu/people/andre/qlambda/ |url-status=dead }}</ref>

In 2004, Selinger and Valiron defined a [[strongly typed]] lambda calculus for quantum computation with a type system based on [[linear logic]].<ref>Peter Selinger, Benoˆıt Valiron, [https://www.mscs.dal.ca/~selinger/papers/qlambdabook.pdf "Quantum Lambda Calculus"]</ref>