=Paper=
{{Paper
|id=Vol-2585/paper15
|storemode=property
|title=Measurements in quantum programming language QML
|pdfUrl=https://ceur-ws.org/Vol-2585/paper15.pdf
|volume=Vol-2585
|authors=Nely Plata Cesar,J. Raymundo Marcial-Romero,J. Antonio Hernández Servı́n
|dblpUrl=https://dblp.org/rec/conf/lanmr/CesarMS19
}}
==Measurements in quantum programming language QML==
https://ceur-ws.org/Vol-2585/paper15.pdf
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