Measurements in quantum programming language QML Nely Plata-Cesar1 , J. Raymundo Marcial-Romero1 , and J. Antonio Hernández-Servı́n1 Facultad de Ingenierı́a Universidad Autónoma del Estado de México nplatac@uaemex.mx, jrmarcialr@uaemex.mx, xoseahernandez@uaemex.mx Abstract. 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. Keywords: Functional quantum programming · QML · Measurement 1 Introduction Programming languages are an important field in computer science and quan- tum physics. In the last field it allows to represent algorithms applying quantum properties. Among the quantum programming languages, quantum lambda cal- culus λ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 finally to allow quantum measurements. Quantum measurements on a system determine the probability that an ex- periment will happen. These occur with some interference (observer) or some phenomenon of nature that happens in these system, these measurements gen- erate 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 definition [10]. Lambda calculus is a representative and useful language to theoretically study the foundations of mathematics and recursion [3, 4]. Van Tonder pro- poses quantum lambda calculus λq , with the mentioned above properties [10]. Subsequently, Dı́az-Caro, Arrighi, et al. incorporate a family of measurement operators to λq calculus [5]. λq calculus in its initial definition does not incorporate measurements, similar to the QML language, which has a semantics with quantum data and control, Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) 159 2 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. [5]. Organization: This article is structured as follows: In chapter 2, you will find the definition of the QML language and general concepts of quantum measure- ments. 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 finally in part 5, the conclusions and future work are summarized. 2 Preliminaries 2.1 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 define your semantic model, they also develop a sound and complete equational theory, omitting recursive types and measurements [1]. This latest research will be retaken, the syntax of terms is: (Variables) x, y, . . . ∈ V ars (Prob. amplitudes) κ, ι, . . . ∈ C (Patterns) p, q ::= x | (x, y) (Terms) t, u ::= x | () | (t, u) | let p = t in u | 0 | f alse| true| κ ∗ t | t + u | if◦ t then u else u0 Table 1: Syntax for QML. 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 define 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: σ = Q1 |Q2 |σ ⊗ τ , 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 : σ = •|Γ, x : σ, where • stands for the empty context. The context correspond to functions from a finite 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 ∈ / dom∆ •⊗∆ =∆ 160 Measurements in quantum programming language QML 3 Interpret a judgement Γ ` t : σ as a function is JΓ ` t : σ K ∈ JΓ K → Jσ K, where, given a typing contexts, it returns a type of the collection of qubits. To define well-formed programs Γ ` t : σ, the rules can be observed in Table 2. For example: Γ ⊗ ∆ ` if◦ c then t else u : σ, requires that Γ ` c : Q2 and ∆ ` t, u : σ, that is, c has a value of qubit, and t and u are the same type. Γ `t:σ ∆, x : σ ` t : τ var let x:σ`x:σ Γ ⊗ ∆ ` let x = t in u : τ Γ ` c : Q2 ∆ ` t, u : σ Γ `t:σ ∆`u:τ if◦ ⊗ intro Γ ⊗ ∆ ` if◦ c then t else u : σ Γ ⊗ ∆ ` (t, u) : σ ⊗ τ f-intro t-intro • ` f alse : Q2 • ` true : Q2 Γ `t:σ⊗τ ∆, x : σ, y : τ ` u : ρ ⊗ −elim Γ ⊗ ∆ ` let (x, y) = t in u : ρ Γ `t:σ wk-unit unit Γ, x : Q1 ` t : σ • ` () : Q1 Table 2: Typing classical terms (Source: [1], p. 29). The definition of this language is the basis for understanding the process of adding measurements, the next section presents a brief introduction about the quantum measurements. 2.2 Quantum measurements 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 |0i + α1 |1i, when applying a measurement, it can collapse to |0i with probability |α0 |2 or |1i with probability |α1 |2 [2]. The measurement of state ψ consists of being exposed P to an observer, with the following conditions [7–9]. Let quantum state |ϕi = i α |ψi i: – The index mi stands for the measurements outcomes that may occur in the experiment: m1 , m2 , . . . , mi (1) – Each mi has an associated matrix Mmi , where Mmi are called measurement operators: Mm1 , Mm2 , . . . , Mmi (2) 161 4 – The operators Mmi must satisfy: ∗ ∗ ∗ Mm 1 Mm 1 + Mm 2 Mm 2 + · · · + Mm n Mmn = I called completeness or completeness equation. This equation guarantees that the sum of the probabilities of the state is 1. – Let |ϕi be the current state of the system, if it is observed then it collapses Mmi |ϕi ∗ to: , with probability P (mi ), where: P (mi ) = hϕ| Mm Mmi |ϕi. ||Mmi |ϕi || i Definition 1 (Operator). An operator of C2 is a square matrix of dimension n with complex coefficients. Definition 2 (Projection operator). A projection or measurement matrix, are operators of the form P = |ψi hψ|. If P = |ψi hψ| is a projection operator and is applied to the |ϕi state, then: P |ϕi = (|ψi hψ|) |ϕi = |ψi hψ |ϕi = α |ψi where α ∈ hψ |ϕi These measurement operators will be considered to incorporate them into the QML language.     1 0 Example 1. The base is {|0i , |1i}, with |0i = , |1i = , the operators 0 1 are:         1 10 0 00 P0 = |0i h0| = (1 0) = , P1 = |1i h1| = (0 1) = . Suppose 0 00 1 01 |ψi = α |0i + β |1i, if we apply P0 , then:           10 1 0 1 0 P0 |ψi = α +β =α +β = α |0i 00 0 1 0 0   Also developed as: P0 |ψi = |0i h0| α |0i + β |1i = |0i αh0 |0i + βh0 |1i = α |0i M Therefore, the application of a measurement operator is conceived as:|ψi →i |ψ 0 i. 3 Measurements in Quantum Lambda Calculi Quantum lambda calculus is a functional language that is not typed and with- out measurements, which allows operations and analysis of properties of this and other languages. After this, a way of adding quantum measurements is incorpo- rated, 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. 162 Measurements in quantum programming language QML 5 Next we will describe important information and the procedure for adding measurement operators to the quantum lambda calculi language λq [5, 10]. λq calculus carries a history track to preserve the information needed to reverse reductions, ensuring that the computing process satisfies quantum prop- erties. A state of this language, after the measurement is irreversibly changed, even retaining the history track. Lambda calculus λ was developed with classical data [4], subsequently, quan- tum data is added resulting in λq [10]. Of λq its syntax is reconsidered, which extends with a family of measurement operators. Of the most significant modifications, qubits are defined explicitly, the con- stants (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): t::= pre-terms: x variable (λx.t) abstraction (t t) application !t nonlinear term (λ!x.t) nonlinear abstraction (cU ) gate-constant q qubit-constant MI measurement-constant q::= Qubit-constants: (|0i, |1i) base-qubit (q ⊗ q) tensorial product (q + q) superposition α(q) scalar product CU ::= Gate-constants: H | | X | cnot | . . . Table 3: Modified syntax of λq . The rules for well-formed terms are found in Fig. 3 of the following article [5]. With the previous content, we proceed with the description of quantum measurements in λq . The corresponding rule is initially mentioned, and then its components and functionality will be explained. The measurement rule is defined as: m 2X −1 q= αu q (u) u=0 X αu ∀i ∈ I, 1 ≤ i ≤ m H; (MI q) →pw √ q (u) pw u∈C(w,m,I) where: – w = 0, . . . , 2|I| − 1 corresponds to the expected value in a measurement, that is, w has associated the possible values mi that were mentioned in the equation 1. The w value must be converted to its binary number, for example, w = 2, corresponds to 010. 163 6 – I indicates the indices or positions that are observed in a measurement. For example, if I = {2, 3, 5}, the positions 2, 3 and 5 will be observed. (u) (u) (u) (u) – q (u) =!q1 ⊗!q2 ⊗ · · · ⊗!qm , with !qk =! |0i or ! |1i, 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 |101i state in terms of this rule is written as: q (5) = ! |1i ⊗! |0i ⊗! |1i). – 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 = {2, 3, 5}, in each qubit you will look for the first 0 (of w) in index 2, 1 in position 3 and 0 in index 5: q1 0 1 q4 0 . X – pw = |αu |2 , is the probability of collapsing to the state w. u∈C(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 = {1, 3} and w = 01. 1   1   q = √ ! |0i ⊗! |0i ⊗! |0i + √ ! |0i ⊗! |0i ⊗! |1i 8 8 1   1   + √ ! |0i ⊗! |1i ⊗! |0i + √ ! |0i ⊗! |1i ⊗! |1i 8 8 1   1   + · · · + √ ! |1i ⊗! |0i ⊗! |1i + √ ! |1i ⊗! |1i ⊗! |1i 8 8 Considering C(w, m, I) = C(01, 3, {1, 3}), of the states in q (0 is in index 1, and 1 in the index 3) you get the following: 1   1   √ !|0i⊗! |0i ⊗!|1i + √ !|0i⊗! |1i ⊗!|1i 8 8 The probability of collapsing with w = 01 in q is given by: pw = | √18 |2 + | √18 |2 = 1 4 . With this, when measuring we get: √1   √1   H; (M{1,3} q) = q8 ! |0i ⊗! |0i ⊗! |1i + q8 ! |0i ⊗! |1i ⊗! |1i 1 1 4 4 1   1   = √ ! |0i ⊗! |0i ⊗! |1i + √ ! |0i ⊗! |1i ⊗! |1i 2 2 With probability 14 . 4 Measurements in QML 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σ ⊗ τ K = JσK × Jτ K, the projections are used which will allow to access to the first or second element of the projection. 164 Measurements in quantum programming language QML 7 Definition 3 (Projections). – f st : A × B → A, where f st(a, b) 7→ a. – snd : A × B → B, where snd(a, b) 7→ b. For every x ∈ A × B you have x = (f st(x), snd(x)). In a category with finite products, the object ×(A1 , . . . , An ) is inductively defined as: ×() ×(A) = 1 × A ×(A1 . . . , An ) = (×(A1 . . . , An−1 )) × An With this, the projection πin : ×(A1 . . . , An ) → Ai is generalized, establishing: πnn = snd and πin = πin−1 ◦ f st, when i < n [6]. This definition applies in QML to the rules of well-formed terms: Γ ⊗∆`t:σ⊗τ Γ ⊗∆`t:σ⊗τ f irst snd Γ ` f irst t : σ ∆ ` snd t : τ Table 4: Typing quantum data. It is also required to define a grouping when you have a σ⊗τ type, inductively applying the following (for associative purposes ⊗): σ = Q1 ⊗ σ σ ⊗ (τ1 ⊗ τ2 ) = (σ ⊗ τ1 ) ⊗ τ2  (σ1 ⊗ σ2 ) ⊗ (τ1 ⊗ τ2 ) = (σ1 ⊗ σ2 ) ⊗ τ1 ⊗ τ2    For example, be type σ = (Q1 ⊗ σ1 ) ⊗ σ2 ⊗ σ3 ⊗ σ4 . The projection π14 is: π14 = (((snd ◦ f st) ◦ f st) ◦ f st)    = ((snd ◦ f st) ◦ f st) ◦ f st (Q1 ⊗ σ1 ) ⊗ σ2 ⊗ σ3 ⊗ σ4   = (snd ◦ f st) ◦ f st (Q1 ⊗ σ1 ) ⊗ σ2 ⊗ σ3 = snd ◦ f st (Q1 ⊗ σ1 ) ⊗ σ2 = snd (Q1 ⊗ σ1 ) = σ1 With the above rules, we proceed with the incorporation of quantum measure- ments. 4.1 Quantum Measurement Rule The components that will integrate the rule are listed below. 165 8 – m, is the number of sub-terms that compose the qubit q1 . For example, in the following state q1 , m = 2: 1 1 1 q1 = √ ∗ ( √ ∗ (f alse, f alse) + √ ∗ (f alse, true)) 2 2 2 (3) 1 1 1 + √ ∗ ( √ ∗ (true, f alse) + √ ∗ (true, true)) 2 2 2 – The quantum states in superposition should be expressed in conventional P2m −1 manner as: i=0 αi ∗ qi , however, the rule (by definition) to form super- positions 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 su- perpositions. What it means is that the sub-terms t0 can be defined in terms of others and successively; once these t0 have the desired type, then they will have P2m −1 the form i=0 αi ∗ qi to perform a quantum measurement, for which this should be apply the red◦ rule in the Table 5. – The definition of I is still conceived as the set of indexes or positions to consider when measuring q. Defined as: I = { i | i ∈ N, 1 ≤ i ≤ m} In practical terms this means that if I = {2} in a q state, the indexes to be observed are identified as: √12 ∗ √12 ∗(f alse, f alse)+ √12 ∗(f alse, true √1 |{z} )+ 2 ∗ | {z } I={2} I={2} √1 ∗ (true, f alse) + √1 ∗ (true, true ). The elements of I will determine the 2 | {z } 2 |{z} I={2} I={2} projections πim (Definition 3) that will be accessed in each state of a qubit. |I| – With respect to w, it is necessary that w = 0, . . . , 2 − 1, being the ex- pected value when measuring. The chosen value w, must be coded in bi- nary (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 = {1, 3}, 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 defined as: ∀i ∈ I, ∀αt0 ∗ t0 in q, if αt0 ∗ πim (t0 ) = αt0 ∗ wi ⇒ αt0 ∗ t0 ∈ C(w, m, I) where t0 is an irreducible term. For example, taking the equation 3, with true, m = 3, if it is verified that: ∀i ∈ {1, 3}, ∀αt0 ∗ t0 I = {1, 3}, w = f alse, |{z} | {z } w1 w3 in q, satisfy αt0 ∗ πi3 (t0 ) = αt0 ∗ wi , then t0 belongs to that function: 166 Measurements in quantum programming language QML 9 • √18 ∗ π13 (f alse, (f alse, true)) = √18 ∗ f alse = √18 ∗ w1 , and √1 ∗ π 3 (f alse, (f alse, true)) = √1 ∗ true = √1 ∗ w3 8 3 8 8 • √18 ∗ π13 (f alse, (true, true)) = √18 ∗ f alse = √18 ∗ w1 , and √1 ∗ π 3 (f alse, (true, true)) = √1 ∗ true = √1 ∗ w3 8 3 8 8 ∴ C(w, m, I) = { √18 ∗ (f alse, (f alse, true)) + √18 ∗ (f alse, (true, true))} With the above, the rules for reducing terms described in superpositions and the measurement rule in QML are deduced. q = α1 ∗ t1 + α2 ∗ t2 t1 = α11 ∗ t11 + α12 ∗ t12 t2 = α21 ∗ t21 + α22 ∗ t22 q 0 = α1 ∗ α11 ∗ t11 + α1 ∗ α12 ∗ t12 + α2 ∗ α21 ∗ t21 + α2 ∗ α22 ∗ t22 (MI q)−→(MI q0 ) red◦ q = λ1 ∗ t1 + λ2 ∗ t2 M◦ ∀i ∈ I, 1 ≤ i ≤ m X 1 0 (MI q) →pw √ ∗t 0 pw αt0 ∗t ∈C(w,m,I) Table 5: Quantum measure rule for quantum data. 4.2 Example Let I = {2}, m = 2, w = true and the state q: 1 1 1 1 1 1 q = √ ∗ √ ∗ (f alse, f alse) + √ ∗ √ ∗ (f alse, true) + √ ∗ √ ∗ (true, f alse) 2 2 2 2 2 2 1 1 + √ ∗ √ ∗ (true, true) 2 2 X 1 where C(w, m, I) = {(f alse, true), (true, true)}, ptrue = |λu |2 = . 2 u∈C(w,m,I) Performing the measurement with respect to w = f alse: α p u ∗ tu X MI q → 1/2 u∈C(w,m,I) 1/2 1/2 1/2 →p ∗ (f alse, true) + p ∗ (true, true) 1/2 1/2 1/2 1 1 1 → √ ∗ (f alse, true) + √ ∗ √ ∗ (true, true) 1/2 2 2 2 167 10 5 Conclusions 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 final state. References 1. Thorsten Altenkirch, Jonathan Grattage, Juliana K. Vizzotto, and Amr Sabry. An algebra of pure quantum programming. Electronic Notes in Theoretical Computer Science, 170:23 – 47, 2007. Proceedings of the 3rd International Workshop on Quantum Programming Languages (QPL 2005). 2. Guido Bacciagaluppi. Is logic empirical? In Kurt Engesser, Dov M. Gabbay, and Daniel Lehmann, editors, Handbook of Quantum Logic and Quantum Structures, pages 49 – 78. Elsevier, Amsterdam, 2009. 3. Paul Bernays. Alonzo church. an unsolvable problem of elementary number the- ory. american journal of mathematics, vol. 58 (1936), pp. 345 Äı̀363. Journal of ’ Symbolic Logic, 1(2):73 Äı̀74, 1936. ’ 4. A. Church. The Calculi of Lambda-conversion. Annals of Mathematics Studies. Princeton University Press, 1941. 5. Alejandro Dı́az-Caro, Pablo Arrighi, Manuel Gadella, and Jonathan Grattage. Measurements and confluence in quantum lambda calculi with explicit qubits. Elec- tronic Notes in Theoretical Computer Science, 270(1):59 – 74, 2011. Proceedings of the Joint 5th International Workshop on Quantum Physics and Logic and 4th Workshop on Developments in Computational Models (QPL/DCM 2008). 6. C.A. Gunter. Semantics of Programming Languages: Structures and Techniques. Foundations of Computing. MIT Press, 1992. 7. S. Imre and F. Balazs. Quantum Computing and Communications: An Engineering Approach. Wiley, 2005. 8. N. David Mermin. From cbits to qbits: Teaching computer scientists quantum mechanics. American Journal of Physics, 71(1):23–30, 2003. 9. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. 10. André van Tonder. A lambda calculus for quantum computation. SIAM J. Com- put., 33(5):1109–1135, 2004. 168