Quantum lambda calculus
Quantum lambda calculus
复制标题
量子 lambda 演算
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Valiron
中科院分区：
文献类型：
--
作者：
P. Selinger;B. Valiron
The lambda calculus, developed in the 1930’s by Church and Curry, is a formalism for expressing higher-order functions. In a nutshell, a higher-order function is a function that inputs or outputs a “black box”, which is itself a (possibly higher-order) function. Higher-order functions are a computationally powerful tool. Indeed, the pure untyped lambda calculus has the same computational power as Turing machines [Tur36]. At the same time, higher-order functions are a useful abstraction for programmers. They form the basis of functional programming languages such as LISP, ML, Scheme, and Haskell. In this chapter, we discuss how to combine higher-order functions with quantum computation. We believe that this is an interesting question for a number of reasons. First, the combination of higher-order functions with quantum phenomena raises the prospect of entangled functions. Certain well-known quantum phenomena can be naturally described in terms of entangled functions, and we will give some examples of this in Section 1.2. Another interesting aspect of higher-order quantum computation is the interplay between classical objects and quantum objects in a higherorder context. A priori, quantum computation operates on two distinct kinds of data: classical data, which can be read, written, duplicated, and discarded as usual, and quantum data, which has state preparation, unitary maps, and measurements as primitive operations. The higherorder computational paradigm introduces a third kind of data, namely functions, and one may ask whether functions behave like classical data, quantum data, or something intermediate. The answer is that there will actually be two kinds of functions: those
The lambda calculus, developed in the 1930’s by Church and Curry, is a formalism for expressing higher-order functions. In a nutshell, a higher-order function is a function that inputs or outputs a “black box”, which is itself a (possibly higher-order) function. Higher-order functions are a computationally powerful tool. Indeed, the pure untyped lambda calculus has the same computational power as Turing machines [Tur36]. At the same time, higher-order functions are a useful abstraction for programmers. They form the basis of functional programming languages such as LISP, ML, Scheme, and Haskell. In this chapter, we discuss how to combine higher-order functions with quantum computation. We believe that this is an interesting question for a number of reasons. First, the combination of higher-order functions with quantum phenomena raises the prospect of entangled functions. Certain well-known quantum phenomena can be naturally described in terms of entangled functions, and we will give some examples of this in Section 1.2. Another interesting aspect of higher-order quantum computation is the interplay between classical objects and quantum objects in a higherorder context. A priori, quantum computation operates on two distinct kinds of data: classical data, which can be read, written, duplicated, and discarded as usual, and quantum data, which has state preparation, unitary maps, and measurements as primitive operations. The higherorder computational paradigm introduces a third kind of data, namely functions, and one may ask whether functions behave like classical data, quantum data, or something intermediate. The answer is that there will actually be two kinds of functions: those