We present a proposal to add measurement operators to the quantum programming language QML, this strategy modifying the semantics on projections of products ( ), by adding some rules to allow measurements.
Programming languages are an important eld in computer science and quantum physics. In the last eld it allows to represent algorithms applying quantum properties. Among the quantum programming languages, quantum lambda calculus q and QML can be mentioned, being functional programming languages and the foundations.
The properties that quantum languages have are that programs operate with quantum data, that is, superpositions of the form t t + u u; Operations are represented with matrix and can be applied to superpositions, also having mixed states and nally to allow quantum measurements.
Quantum measurements on a system determine the probability that an experiment will happen. These occur with some interference (observer) or some phenomenon of nature that happens in these system, these measurements generate irreversibility once they occur.
The measurements in a programming language make it possible to move from
the quantum to the classical environment, emitting the output of a program.
The contribution of measurements to some languages, has been gradual, for
example, the incorporation of measurements in quantum lambda happens after
its de nition [
Lambda calculus is a representative and useful language to theoretically
study the foundations of mathematics and recursion [
q calculus in its initial de nition does not incorporate measurements, similar
to the QML language, which has a semantics with quantum data and control,
but without measurements. In this paper the measurements are added to QML,
taking as a guide the work carried out by D az-Caro, et al. [
Organization: This article is structured as follows: In chapter 2, you will nd the de nition of the QML language and general concepts of quantum measurements. In chapter 3, the description of the quantum lambda calculus language. Chapter 4, presents the contribution of adding measurement operators to QML. This proposal will be found as an example. And nally in part 5, the conclusions and future work are summarized.
Quantum programming language QML
The QML language will be approached from the perspective of Altenkirch,
Grattage, Vizzotto and Sabry, they work on the pure fragment of language and
de ne your semantic model, they also develop a sound and complete equational
theory, omitting recursive types and measurements [
From the syntax you can form conventional programs such as tuples, let, if, among others, and in turn append terms with a probability amplitude , that is, have a probability value that they happen, and also de ne superposition t + u, it means than a term can be in t and u at the same time.
The types are given by the grammar: = Q1jQ2j , where Q1 is the type (), which carry no information and Q2 corresponds to qubits (0 and 1). Semantically J K = J K J K, where is the standard product type and returns a tuple.
Typing contexts ( ; ) are given by: ; x : = j ; x : , where stands for the empty context. The context correspond to functions from a nite set of variables to types. For this case, we assume that every variable appears at most once. To maps pairs of contexts to contexts, the operator is incorporated, with the following operation: ; x : ; x : ; x : ); x : ); x : si x 2= dom = ( = ( =
var ` c : Q2 ` t; u : ` if c then t else u :
if f-intro ` f alse : Q2
` t : ` t : ; x : Q1 ` t : wk-unit ` t :
; x : ` t : let ` let x = t in u : ` t :
` u : ` (t; u) : ` true : Q2 t-intro
intro ` () : Q1
elim unit The quantum measurements are the third postulate of quantum computing, interpreted as:
In a quantum system the measurements disturb a system, collapsing from
a quantum to classic state, implying loss of information from the initial state.
Theoretically, the measurements determine how probable a state can collapse,
for example, take the initial state 0 j0i + 1 j1i, when applying a measurement,
it can collapse to j0i with probability j 0j2 or j1i with probability j 1j2 [
The measurement of state consists of being exposed to an observer, with the following conditions [7{9]. Let quantum state j'i = Pi j ii: { The index mi stands for the measurements outcomes that may occur in the experiment: { Each mi has an associated matrix Mmi , where Mmi are called measurement operators: (1) (2)
; x : ; y : ` u : ` let (x; y) = t in u :
m1; m2; : : : ; mi Mm1 ; Mm2 ; : : : ; Mmi { The operators Mmi must satisfy:
Mm1 Mm1 + Mm2 Mm2 + + Mmn Mmn = I to: called completeness or completeness equation. This equation guarantees that the sum of the probabilities of the state is 1. { Let j'i be the current state of the system, if it is observed then it collapses
Mmi j'i , with probability P (mi), where: P (mi) = h'j Mmi Mmi j'i. jjMmi j'i jj De nition 1 (Operator). An operator of C2 is a square matrix of dimension n with complex coe cients.
De nition 2 (Projection operator). A projection or measurement matrix, are operators of the form P = j i h j.
If P = j i h j is a projection operator and is applied to the j'i state, then: P j'i = (j i h j) j'i = j i h j'i = where j i 2 h j'i
These measurement operators will be considered to incorporate them into the QML language.
Example 1. The base is fj0i ; j1ig, with j0i = are: P0 = j0i h0j = j i = j0i + 01 (1 0) = 01 00 , P1 = j1i h1j = j1i, if we apply P0, then: 1 0 ; j1i =
01 , the operators 01 (0 1) =
00 01 . Suppose = j1i P0 j i = Therefore, the application of a measurement operator is conceived as:j i M!i j 0i. 3
Measurements in Quantum Lambda Calculi Quantum lambda calculus is a functional language that is not typed and without measurements, which allows operations and analysis of properties of this and other languages. After this, a way of adding quantum measurements is incorporated, allowing us to guide the implementation of the same technique to the QML language, this is possible since QML is a quantum programming language, with a functional paradigm, typed and without measurements.
Next we will describe important information and the procedure for adding
measurement operators to the quantum lambda calculi language q [
q calculus carries a history track to preserve the information needed to reverse reductions, ensuring that the computing process satis es quantum properties. A state of this language, after the measurement is irreversibly changed, even retaining the history track.
Lambda calculus was developed with classical data [
Of the most signi cant modi cations, qubits are de ned explicitly, the constants (of the original syntax) are divided into: qubits, measurement operators and gates and the measurement operators MI are added. As a result of the above, the syntax is (Table 3): ( x.t) !t (cU ) MI (q
q) (q) abstraction nonlinear term gate-constant measurement-constant tensorial product scalar product t::= x (t t) ( !x.t) q q::= (j0i; j1i) (q + q) CU ::=
H j j X j cnot j : : : pre-terms: variable application nonlinear abstraction qubit-constant
The rules for well-formed terms are found in Fig. 3 of the following article
[
The measurement rule is de ned as:
H; (MI q) !pw
2m 1 q = X u=0 uq(u)
X { I indicates the indices or positions that are observed in a measurement. For example, if I = f2; 3; 5g, the positions 2, 3 and 5 will be observed. { q(u) =!q1(u) !q2(u) !qm(u), with !qk(u) =! j0i or ! j1i, for k = 1; : : : ; m. Such states (in binary) conform to q with their corresponding probability, these represent all possible values between 0 and 2m 1, for example, the 0 j101i state in terms of this rule is written as: q(5) = ! j1i ! j0i ! j1i). { C(w; m; I),is the set of binary strings of length m, such that they coincide with w over the letters of index I. Assume w = 010 and the set I = f2; 3; 5g, in each qubit you will look for the rst 0 (of w) in index 2, 1 in position 3 and 0 in index 5: q1 0 1 q4 0 . { pw = X j uj2, is the probability of collapsing to the state w.
u2C(w;m;I) { The notation t !pw t0, means that t goes to t0 with probability pw.
To conclude this section, a complete example the application of the rule is shown.
Example 2. Let m = 3; I = f1; 3g and w = 01.
Considering C(w; m; I) = C(01; 3; f1; 3g), of the states in q (0 is in index 1, and 1 in the index 3) you get the following: 1 1 p8 !j0i ! j0i !j1i + p8 !j0i ! j1i !j1i The probability of collapsing with w = 01 in q is given by: pw = j p18 j2 + j p18 j2 = 14 . With this, when measuring we get:
H; (Mf1;3g q) = ! j0i ! j0i ! j1i +
! j0i ! j1i ! j1i When implementing measurements according to q, it is required to access the elements of each state, and considering that the types in QML are given by J rst orKs=ecoJndK eleJmKe,ntthoef ptrhoejepcrtoiojencstiaorne. used which will allow to access to the
{ f st : A { snd : A
B ! A, where f st(a; b) 7! a.
B ! B, where snd(a; b) 7! b. () (A) = 1 A (A1 : : : ; An) = ( (A1 : : : ; An 1))
An For every x 2 A products, the object
B you have x = (f st(x); snd(x)). In a category with
(A1; : : : ; An) is inductively de ned as:
nite
With this, the projection in : (A1 : : : ; An) ! Ai is generalized, establishing:
nn = snd and in = in 1 f st, when i < n [
This de nition applies in QML to the rules of well-formed terms: ` t : ` f irst t : f irst
` t : ` snd t : snd
It is also required to de ne a grouping when you have a applying the following (for associative purposes ): type, inductively = Q1
( 1 14 = (((snd f st) f st) f st) = ((snd f st) f st) f st (Q1 = (snd f st) f st (Q1 = snd (Q1 1) = 1 3
4 1) 2 3 = snd f st (Q1 1) 2 With the above rules, we proceed with the incorporation of quantum measurements. 4.1
The components that will integrate the rule are listed below. { m, is the number of sub-terms that compose the qubit q1. For example, in the following state q1, m = 2: { The quantum states in superposition should be expressed in conventional manner as: Pi2=m0 1 i qi, however, the rule (by de nition) to form superpositions in QML is q = 1 t1 + 2 t2. Where every t0 in q can be formed with true; f alse or tuples (true; f alse); (true; (f alse; f alse)); : : : and superpositions.
What it means is that the sub-terms t0 can be de ned in terms of others and successively; once these t0 have the desired type, then they will have the form Pi2=m0 1 i qi to perform a quantum measurement, for which this should be apply the red rule in the Table 5. { The de nition of I is still conceived as the set of indexes or positions to consider when measuring q. De ned as:
I = f i j i 2 N; 1 i mg In practical terms this means that if I = f2g in a q state, the indexes to be observed are identi ed as: p12 p12 (f alse; f alse) + p12 (f alse; true ) + p12 |I={fz2g} I|={fz2}g p12 (true; true ). The elements of I will determine the
I|={fz2}g (true; f alse) + p12 | {z }
I=f2g projections im (De nition 3) that will be accessed in each state of a qubit. { With respect to w, it is necessary that w = 0; : : : ; 2jIj 1, being the expected value when measuring. The chosen value w, must be coded in binary (1 = true; 0 = f alse), as the following example: w = 5, would be 101 true; f alse; true.
For measurement purposes, the w string is broken down as follows: w = w1; w2; ; wn; where n m The subscripts of w must match I. For example: If I = f1; 3g, w = true; f alse; so, w = w1; w3 where w1 = true and w3 = f alse. { C(w; m; I), it is the function that returns the set of strings of length m, such that they coincide with the expected values w in the indexes I. This function can be de ned as: 8i 2 I; 8 t0 t0 in q; if t0 im(t0) = t0 wi ) t0 t0 2 C(w; m; I) where t0 is an irreducible term. For example, taking the equation 3, with I = f1; 3g; w = f alse; true; m = 3, if it is veri ed that: 8i 2 f1; 3g, 8 t0 t0 | w{z1 } |w{z3} in q, satisfy t0 i3(t0) = t0 wi, then t0 belongs to that function: f alse = p18 true = p18 f alse = p18 true = p18 w1, and w3 w1, and w3 )
1 C(w; m; I) = f p8 (f alse; (f alse; true)) + p18 (f alse; (true; true))g
With the above, the rules for reducing terms described in superpositions and the measurement rule in QML are deduced. Let I = f2g; m = 2; w = true and the state q:
1 (f alse; f alse) + p 2 Performing the measurement with respect to w = f alse:
MI q 1!=2 u2CX(w;m;I) p1u=2 tu
X The addition of a measurement operator in QML, is that given a quantum state (consisting of sub-terms), it is initially determined with respect to which position of each sub-state will be measured and the expected value, collapsing to the state or states that coincide with the above, determining with what probability and normalizing to the nal state.