A Brief Introduction to Probabilistic and Quantum Programming

A Brief Introduction to Probabilistic and Quantum Programming

Part II

Ugo Dal Lago

Universidade do Minho, Friday May 5, 2017

Section 1

Probabilistic Programming Languages

Flipping a Coin

I Making any programming language probabilistic is relatively easy, at least from a purely linguistic point of view.

I The naïve solution is to endow your favourite language with a primitive that, when executed, “flips a fair coin” returning 0 or 1 with equal probability.

I In imperative programming langauges, this can take the form of a keyword rand, to be used in expressions;

I In functional programming languages, one could also use a form of binary, probabilistic sum, call it ⊕, as follows:

letrec f x = x (+) (f (x+1))

I How do we get the necessary randomness, when executing programs?

I By a source of true randomness, like physical randomness.

I By pseudorandomness (we will come to that later).

Sampling

I If incepted into a universal programming language, binary uniform choice is enough to encode sampling from any computable distribution.

I As an example, if f is defined as follows letrec f x = x (+) (f (x+1))

then f(0) produces the exponential distribution {0¹²,1¹⁴,2¹⁸, . . .}.

I A real number x ∈ R is computable if there is an algorithm A_x outputting, on input n ∈ N, a rational number q_n∈ Q such that |x − qn| < ₂¹n.

I A computable distribution is one such that there is an algorithm B that, on input n, outputs the code of A_pⁿ, where pⁿ is the probability the distribution assigns to n.

Theorem

PTMs are universal for computable distributions.

True Randomness vs. Pseudorandomness

I Having access to a source of true randomness is definitely not trivial.

I One could make use, as an example, of:

I Keyboard and mouse actions;

I External sources of randomness, like sound or movements;

I TRNGs (True Random Number Generators).

I A pseudorandom generator is a deterministic algorithm G from strings in Σ^∗ to Σ^∗ such that:

I |G(s)| > |s|;

I G(s) is somehow indistinguishable from a truly random string t of the same length.

I The point of pseudorandomness is amplification: a short truly random string is turned into a longer string which is not random, but looks so.

Programming vs. Modeling

I Probabilistic models, contrarily to probabilistic languages, are pervasive and very-well studied from decades.

I Markov Chains

I Markov Processes

I Stochastic Processes

I . . .

I A probabilistic program, however, can indeed be seen as a way to concisely specify a model, for the purpose of doing, e.g., machine learning or inference.

I A quite large research community is currently involved in this effort (for more details, see

http://probabilistic-programming.org).

I Roughly, you cannot only “flip a coin”, but you can also incorporate observations about your dataset in your program.

Programming vs. Modeling

I Probabilistic models, contrarily to probabilistic languages, are pervasive and very-well studied from decades.

I Markov Chains

I Markov Processes

I Stochastic Processes

I . . .

I A probabilistic program, however, can indeed be seen as a way to concisely specify a model, for the purpose of doing, e.g., machine learning or inference.

I A quite large research community is currently involved in this effort (for more details, see

http://probabilistic-programming.org).

I Roughly, you cannot only “flip a coin”, but you can also incorporate observations about your dataset in your program.

A Nice Example: FUN

A Nice Example: FUN

Section 2

Quantum Programming Languages

Quantum Data and Classical Control

Classical Control

Quantum Store

Create a New Qubit

Observe the Value of a Qubit

Quantum Data and Classical Control

Classical Control

Quantum Store

Create a New Qubit

Observe the Value of a Qubit

Quantum Data and Classical Control

Classical Control

Quantum Store

Observe the Value of a Qubit Create a New Qubit

Quantum Data and Classical Control

Classical Control

Quantum Store

Apply a Transform

Unitary

Create a New Qubit

Observe the Value of a Qubit

Imperative Quantum Programming Languages

I QCL, which has been introduced by Ömer

I Example:

qufunct set(int n,qureg q) {

int i;

for i=0 to #q-1 {

if bit(n,i) {Not(q[i]);}

} }

I Classical and quantum variables.

I The syntax is very reminiscent of the one of C.

Quantum Imperative Programming Languages

I qGCL, which has been introduced by Sanders and Zuliani.

I It is based on Dijkstra’s predicate transformers and guarded-command language, called GCL.

I Features quantum, probabilistic, and nondeterministic evolution.

I It can be seen as a generalization of pGCL, itself a probabilistic variation on GCL.

I Tafliovich and Hehner adapted predicative programming to quantum computation.

I Predicative programming is not a proper programming language, but rather a methodology for specification and verification.

Quantum Functional Programming Languages

I QPL, introduced by Selinger.

I A very simple, first-order, functional programming language.

I The first one with a proper denotational semantics, given in terms of superoperators, but also handling divergence by way of domain theory.

I A superoperator is a mathematical object by which we can describe the evolution of a quantum system in presence of measurements.

I Many papers investigated the possibility of embedding quantum programming into Haskell, arguably the most successful real-world functional programming language.

I In a way or another, they are all based on the concept of a monad.

Quantum Functional Programming Languages

I QPL, introduced by Selinger.

I A very simple, first-order, functional programming language.

I The first one with a proper denotational semantics, given in terms of superoperators, but also handling divergence by way of domain theory.

I A superoperator is a mathematical object by which we can describe the evolution of a quantum system in presence of measurements.

I Many papers investigated the possibility of embedding quantum programming into Haskell, arguably the most successful real-world functional programming language.

I In a way or another, they are all based on the concept of a monad.

QPL: an Example

Quantum Functional Programming Languages

I In a first-order fragment of Haskell, one can also model a form of quantum control, i.e., programs whose internal state is in superposition.

I This is Altenkirch and Grattage’s QML.

I Operations are programmed at a very low level: unitary transforms become programs themselves, e.g.

I Whenever you program by way of the if construct, you should be careful and check that the two branches are orthogonal in a certain sense.

Quantum Functional Programming Languages

I Most work on functional programming languages has focused on λ-calculi, which are minimalist, paradigmatic languages only including the essential features.

I Programs are seen as terms from a simple grammar M, N ::= x

|

|

|

I Computation is captured by way of rewriting

I Quantum features can be added in many different ways.

I By adding quantum variables, which are meant to model the interaction with the quantum store.

I By allowing terms to be in superposition, somehow diverging from the quantum-data-and-classical-control paradigm:

M ::= . . .

|

i∈I

αiMi

I The rest of this course will be almost entirely devoted to (probabilistic and) quantum λ-calculi.

Quantum Process Algebras

I Process algebras are calculi meant to model concurrency and interaction rather than mere computation.

I Terms of process algebras are usually of the following form;

P, Q::= 0

|

|

|

|

I Again, computation is modeled by a form of rewriting, e.g., a.P ||a.Q → P ||Q

I How could we incept quantum computation? Usually:

I Each process has its own set of classical and quantum (local) variables.

I Processes do not only synchronize, but can also send classical and quantum data along channels.

I Unitary transformations and measurements are done locally.

Other Programming Paradigms

I Concurrent Constraint Programming

I Measurement-Based Quantum Computation

I Hardware Description Languages

I . . .

Section 3

The λ-Calculus as a Functional Language

Minimal Syntax and Dynamics

I Terms:

M ::= x

|

|

I Substitution:

x{x/M } = M y{x/M } = y

N L{x/M } = (N {x/M })(L{x/M }) λy.N {x/M } = λy.(N {x/M })

I CBN Operational Semantics:

(λx.M )N → M {x/N } M → N M L → N L

I Values:

V ::= λx.M

I CBV Operational Semantics:

(λx.M )V → M {x/V } M → N M L → N L

M → N V M → V N

Minimal Syntax and Dynamics

I Terms:

M ::= x

|

|

I Substitution:

x{x/M } = M y{x/M } = y

N L{x/M } = (N {x/M })(L{x/M }) λy.N {x/M } = λy.(N {x/M })

I CBN Operational Semantics:

(λx.M )N → M {x/N } M → N M L → N L

I Values:

V ::= λx.M

I CBV Operational Semantics:

(λx.M )V → M {x/V } M → N M L → N L

M → N V M → V N

Minimal Syntax and Dynamics

I Terms:

M ::= x

|

|

I Substitution:

x{x/M } = M y{x/M } = y

N L{x/M } = (N {x/M })(L{x/M }) λy.N {x/M } = λy.(N {x/M })

I CBN Operational Semantics:

(λx.M )N → M {x/N } M → N M L → N L

I Values:

V ::= λx.M

I CBV Operational Semantics:

(λx.M )V → M {x/V } M → N M L → N L

M → N V M → V N

Minimal Syntax and Dynamics

I Terms:

M ::= x

|

|

I Substitution:

x{x/M } = M y{x/M } = y

N L{x/M } = (N {x/M })(L{x/M }) λy.N {x/M } = λy.(N {x/M })

I CBN Operational Semantics:

(λx.M )N → M {x/N } M → N M L → N L

I Values:

V ::= λx.M

I CBV Operational Semantics:

(λx.M )V → M {x/V } M → N M L → N L

M → N V M → V N

Minimal Syntax and Dynamics

I Terms:

M ::= x

|

|

I Substitution:

x{x/M } = M y{x/M } = y

N L{x/M } = (N {x/M })(L{x/M }) λy.N {x/M } = λy.(N {x/M })

I CBN Operational Semantics:

(λx.M )N → M {x/N } M → N M L → N L

I Values:

V ::= λx.M

I CBV Operational Semantics:

(λx.M )V → M {x/V } M → N M L → N L

M → N V M → V N

Observations

I Not all redexes are reduced.

I For every M there is at most one N such that M → N .

I It is easy to find a term M such that M = N₀ → N₁ → N₂→ . . .

I There is a problem with substitutions:

(λx.λy.x)(yz) →λy.yz.

(λx.λy.x)(yz) →λw.yz.

I The standard solution is to consider terms modulo so-called α-equivalence: renaming bound variables turns a term into one which is indistinguishable.

λx.λy.xxy ≡ λz.λy.zzy.

I α-equivalence is not necessary if we assume to work with closed terms.

Observations

I Not all redexes are reduced.

I For every M there is at most one N such that M → N .

I It is easy to find a term M such that M = N₀ → N₁ → N₂→ . . .

I There is a problem with substitutions:

(λx.λy.x)(yz) →λy.yz.

(λx.λy.x)(yz) →λw.yz.

I The standard solution is to consider terms modulo so-called α-equivalence: renaming bound variables turns a term into one which is indistinguishable.

λx.λy.xxy ≡ λz.λy.zzy.

I α-equivalence is not necessary if we assume to work with closed terms.

Observations

I Not all redexes are reduced.

I For every M there is at most one N such that M → N .

I It is easy to find a term M such that M = N₀ → N₁ → N₂→ . . .

I There is a problem with substitutions:

(λx.λy.x)(yz) →λy.yz.

(λx.λy.x)(yz) →λw.yz.

I The standard solution is to consider terms modulo so-called α-equivalence: renaming bound variables turns a term into one which is indistinguishable.

λx.λy.xxy ≡ λz.λy.zzy.

I α-equivalence is not necessary if we assume to work with closed terms.

Computing Simple Function on N, in CBV

I Natural Numbers

p0q = λx.λy.x;

pn + 1q = λx.λy.ypnq.

I Finite Set A= {a1, . . . , an}

paiq = λx1· · · λx_n.xi.

I Pairs

hM, N i = λx.xM N

I Fixed-Point Combinator

Θ = λx.λy.y(λz.(xx)yz);

H= ΘΘ.

Computing Simple Functions on N, in CBV

I Successor

SUCC= λz.λx.λy.yz Indeed:

SUCCpnq → λx.λy.ypnq

I Projections

PROJ^k_i = λx.x(λy1· λy_k.yi) Indeed:

PROJ^k_ihpn1q, . . . , pnkqi → hpn1q, . . . , pnkqi(λy1· · · λy_k.y_i)

→ (λy₁· · · λy_k.y_i)pn1q · · · pnkq

→^∗ pniq.

Computing Simple Functions on N, in CBV

I Successor

SUCC= λz.λx.λy.yz Indeed:

SUCCpnq → λx.λy.ypnq

I Projections

PROJ^k_i = λx.x(λy1· λy_k.yi) Indeed:

PROJ^k_ihpn1q, . . . , pnkqi → hpn1q, . . . , pnkqi(λy1· · · λy_k.y_i)

→ (λy₁· · · λy_k.y_i)pn1q · · · pnkq

→^∗ pniq.

Computing Simple Functions on N, in CBV

I Successor

SUCC= λz.λx.λy.yz Indeed:

SUCCpnq → λx.λy.ypnq

I Projections

PROJ^k_i = λx.x(λy1· λy_k.yi) Indeed:

PROJ^k_ihpn1q, . . . , pnkqi → hpn1q, . . . , pnkqi(λy1· · · λy_k.y_i)

→ (λy₁· · · λy_k.y_i)pn1q · · · pnkq

→^∗ pniq.

Computing Simple Functions on N, in CBV

I Successor

SUCC= λz.λx.λy.yz Indeed:

SUCCpnq → λx.λy.ypnq

I Projections

PROJ^k_i = λx.x(λy1· λy_k.yi) Indeed:

PROJ^k_ihpn1q, . . . , pnkqi → hpn1q, . . . , pnkqi(λy1· · · λy_k.y_i)

→ (λy₁· · · λy_k.y_i)pn1q · · · pnkq

→^∗ pniq.

A Simple Form of Recursion

I Suppose you have a term M_f which computes the function f : N → N, and you want to iterate over it, i.e. you want to compute g: N × N → N such that

g(0, n) = n;

g(m + 1, n) = f (g(m, n)).

I We need a form of recursion in the language. Observe that:

HV = (ΘΘ)V → (λy.y(λz.Hyz))V → V (λz.HV z)

I The function g can be computed by way of

M_g = H(λx.λy.y(λz.λw.zw(λq.Mf(xhq, wi)))

A Simple Form of Recursion

I Suppose you have a term M_f which computes the function f : N → N, and you want to iterate over it, i.e. you want to compute g: N × N → N such that

g(0, n) = n;

g(m + 1, n) = f (g(m, n)).

I We need a form of recursion in the language. Observe that:

HV = (ΘΘ)V → (λy.y(λz.Hyz))V → V (λz.HV z)

I The function g can be computed by way of

M_g = H(λx.λy.y(λz.λw.zw(λq.Mf(xhq, wi)))

A Simple Form of Recursion

I Suppose you have a term M_f which computes the function f : N → N, and you want to iterate over it, i.e. you want to compute g: N × N → N such that

g(0, n) = n;

g(m + 1, n) = f (g(m, n)).

I We need a form of recursion in the language. Observe that:

HV = (ΘΘ)V → (λy.y(λz.Hyz))V → V (λz.HV z)

I The function g can be computed by way of

M_g = H(λx.λy.y(λz.λw.zw(λq.Mf(xhq, wi)))

Universality

I One could go on, and show that the following schemes can all be encoded:

I Composition;

I Primitive Recursion;

I Minimization.

I This implies that all partial recursive functions can be computed in the λ-calculus.

Theorem

The λ-calculus is Turing-complete, both when CBV and CBN are considered.

Why is This a Faithful Model of Functional Computation?

I Data, conditionals, basic functions, and recursion can all be encoded into the λ-calculus. We can then give programs

“informally”, in our favourite functional language.

I Take, as an example, the usual recursive program computing the factorial of a natural number

let rec fact x = if (x==0) then 1 else x*(fact x-1) I This can indeed be turned into a λ-term (where M_∗ and

M−1 are terms for multiplication and the predecessor, respectively):

let rec fact x = if (x==0) then 1 else x*(fact x-1) H(λfact.λx.if (x==0) then 1 else x*(fact x-1))

H(λfact.λx.x p1q (x*(fact x-1))) H(λfact.λx.x p1q (M^∗x (fact x-1))) H(λfact.λx.x p1q (M^∗x (fact (M−1x))))

Why is This a Faithful Model of Functional Computation?

I Data, conditionals, basic functions, and recursion can all be encoded into the λ-calculus. We can then give programs

“informally”, in our favourite functional language.

I Take, as an example, the usual recursive program computing the factorial of a natural number

let rec fact x = if (x==0) then 1 else x*(fact x-1) I This can indeed be turned into a λ-term (where M_∗ and

M−1 are terms for multiplication and the predecessor, respectively):

let rec fact x = if (x==0) then 1 else x*(fact x-1) H(λfact.λx.if (x==0) then 1 else x*(fact x-1))

H(λfact.λx.x p1q (x*(fact x-1))) H(λfact.λx.x p1q (M^∗x (fact x-1))) H(λfact.λx.x p1q (M^∗x (fact (M−1x))))

Why is This a Faithful Model of Functional Computation?

I Data, conditionals, basic functions, and recursion can all be encoded into the λ-calculus. We can then give programs

“informally”, in our favourite functional language.

I Take, as an example, the usual recursive program computing the factorial of a natural number

let rec fact x = if (x==0) then 1 else x*(fact x-1) I This can indeed be turned into a λ-term (where M_∗ and

M−1 are terms for multiplication and the predecessor, respectively):

let rec fact x = if (x==0) then 1 else x*(fact x-1) H(λfact.λx.if (x==0) then 1 else x*(fact x-1))

H(λfact.λx.x p1q (x*(fact x-1))) H(λfact.λx.x p1q (M^∗x (fact x-1))) H(λfact.λx.x p1q (M^∗x (fact (M−1x))))

Why is This a Faithful Model of Functional Computation?

I Data, conditionals, basic functions, and recursion can all be encoded into the λ-calculus. We can then give programs

“informally”, in our favourite functional language.

I Take, as an example, the usual recursive program computing the factorial of a natural number

let rec fact x = if (x==0) then 1 else x*(fact x-1) I This can indeed be turned into a λ-term (where M_∗ and

M−1 are terms for multiplication and the predecessor, respectively):

let rec fact x = if (x==0) then 1 else x*(fact x-1) H(λfact.λx.if (x==0) then 1 else x*(fact x-1))

H(λfact.λx.x p1q (x*(fact x-1))) H(λfact.λx.x p1q (M^∗x (fact x-1))) H(λfact.λx.x p1q (M^∗x (fact (M−1x))))

Why is This a Faithful Model of Functional Computation?

I Data, conditionals, basic functions, and recursion can all be encoded into the λ-calculus. We can then give programs

“informally”, in our favourite functional language.

I Take, as an example, the usual recursive program computing the factorial of a natural number

let rec fact x = if (x==0) then 1 else x*(fact x-1) I This can indeed be turned into a λ-term (where M_∗ and

M−1 are terms for multiplication and the predecessor, respectively):

let rec fact x = if (x==0) then 1 else x*(fact x-1) H(λfact.λx.if (x==0) then 1 else x*(fact x-1))

H(λfact.λx.x p1q (x*(fact x-1))) H(λfact.λx.x p1q (M^∗x (fact x-1))) H(λfact.λx.x p1q (M^∗x (fact (M−1x))))

More About Semantics

I The semantics we have adopted so far is said to be

small-step, since it derives assertions in the form M → N , each corresponding to one atomic computation step.

I There is an equivalent way of formulating the same concept, big-step semantics, in which we “jump directly to the result”:

I CBN

V ⇓ V

M ⇓ λx.N N {x/L} ⇓ V M L ⇓ V

I CBV

V ⇓ V M ⇓ λx.N L ⇓ V N {x/V } ⇓ W

M L ⇓ W

Theorem

In both CBN and CBV, M →^∗ V if and only if M ⇓ V .

I If M ⇓ V for some V , then we write M ⇓, otherwise M ⇑

More About Semantics

I The semantics we have adopted so far is said to be

small-step, since it derives assertions in the form M → N , each corresponding to one atomic computation step.

I There is an equivalent way of formulating the same concept, big-step semantics, in which we “jump directly to the result”:

I CBN

V ⇓ V

M ⇓ λx.N N {x/L} ⇓ V M L ⇓ V

I CBV

V ⇓ V M ⇓ λx.N L ⇓ V N {x/V } ⇓ W M L ⇓ W

Theorem

In both CBN and CBV, M →^∗ V if and only if M ⇓ V .

I If M ⇓ V for some V , then we write M ⇓, otherwise M ⇑

More About Semantics

I The semantics we have adopted so far is said to be

small-step, since it derives assertions in the form M → N , each corresponding to one atomic computation step.

I There is an equivalent way of formulating the same concept, big-step semantics, in which we “jump directly to the result”:

I CBN

V ⇓ V

M ⇓ λx.N N {x/L} ⇓ V M L ⇓ V

I CBV

V ⇓ V M ⇓ λx.N L ⇓ V N {x/V } ⇓ W M L ⇓ W

Theorem

In both CBN and CBV, M →^∗ V if and only if M ⇓ V .

I If M ⇓ V for some V , then we write M ⇓, otherwise M ⇑

Section 4

Probabilistic λ-Calculi

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Terms: M, N ::= x

|

|

|

I Values: V ::= λx.M ;

I How should we define the semantics of a probabilistic term M ?

I Informally, M ⊕ N rewrites to M or to N with probability

1

2: this is just like flippling a coin and choosing one of the two terms according to the result.

I A value distribution is a functionD from the set V of values to R such X

V ∈V

D(V ) ≤ 1.

I The fact the sum can be strictly smaller than1 is a way to reflect (the probability of) divergence.

I The empty value distribution is denoted as ∅.

I Useful notation for finite distributions: {V₁^p1, . . . , V_n^pn}.

I Value distributions can be ordered, pointwise.

I S(D) is the support of D, i.e. the set of values to which D assigns nonnull probability.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Terms: M, N ::= x

|

|

|

I Values: V ::= λx.M ;

I How should we define the semantics of a probabilistic term M ?

I Informally, M ⊕ N rewrites to M or to N with probability

1

2: this is just like flippling a coin and choosing one of the two terms according to the result.

I A value distribution is a functionD from the set V of values to R such X

V ∈V

D(V ) ≤ 1.

I The fact the sum can be strictly smaller than1 is a way to reflect (the probability of) divergence.

I The empty value distribution is denoted as ∅.

I Useful notation for finite distributions: {V₁^p1, . . . , V_n^pn}.

I Value distributions can be ordered, pointwise.

I S(D) is the support of D, i.e. the set of values to which D assigns nonnull probability.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Terms: M, N ::= x

|

|

|

I Values: V ::= λx.M ;

I How should we define the semantics of a probabilistic term M ?

I Informally, M ⊕ N rewrites to M or to N with probability

1

2: this is just like flippling a coin and choosing one of the two terms according to the result.

I A value distribution is a functionD from the set V of values to R such X

V ∈V

D(V ) ≤ 1.

I The fact the sum can be strictly smaller than1 is a way to reflect (the probability of) divergence.

I The empty value distribution is denoted as ∅.

I Useful notation for finite distributions: {V₁^p1, . . . , V_n^pn}.

I Value distributions can be ordered, pointwise.

I S(D) is the support of D, i.e. the set of values to which D assigns nonnull probability.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Approximation (Big-Step) Semantics, CBN:

M ⇓ ∅ V ⇓ {V¹}

M ⇓D N ⇓E

M ⊕ N ⇓ ¹₂D +¹₂E M ⇓D {P {x/N } ⇓Eλx.P}λx.P ∈S(D)

M N ⇓ P

V ∈S(F)D(V )Eλx.P

I Example: consider M = I ⊕ ((II) ⊕ Ω), where I = λx.x and Ω = (λx.xx)(λx.xx).

M ⇓ ∅ M ⇓ {I¹²} M ⇓ {I³⁴}

I Semantics: [[M ]] = sup_{M ⇓D}D;

I Variations: Small-Step Semantics, CBV.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Approximation (Big-Step) Semantics, CBN:

M ⇓ ∅ V ⇓ {V¹}

M ⇓D N ⇓E

M ⊕ N ⇓ ¹₂D +¹₂E M ⇓D {P {x/N } ⇓Eλx.P}λx.P ∈S(D)

M N ⇓ P

V ∈S(F)D(V )Eλx.P

I Example: consider M = I ⊕ ((II) ⊕ Ω), where I = λx.x and Ω = (λx.xx)(λx.xx).

M ⇓ ∅ M ⇓ {I¹²} M ⇓ {I³⁴}

I Semantics: [[M ]] = sup_{M ⇓D}D;

I Variations: Small-Step Semantics, CBV.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Approximation (Big-Step) Semantics, CBN:

M ⇓ ∅ V ⇓ {V¹}

M ⇓D N ⇓E

M ⊕ N ⇓ ¹₂D +¹₂E M ⇓D {P {x/N } ⇓Eλx.P}λx.P ∈S(D)

M N ⇓ P

V ∈S(F)D(V )Eλx.P

I Example: consider M = I ⊕ ((II) ⊕ Ω), where I = λx.x and Ω = (λx.xx)(λx.xx).

M ⇓ ∅ M ⇓ {I¹²} M ⇓ {I³⁴}

I Semantics: [[M ]] = sup_{M ⇓D}D;

I Variations: Small-Step Semantics, CBV.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Approximation (Big-Step) Semantics, CBN:

M ⇓ ∅ V ⇓ {V¹}

M ⇓D N ⇓E

M ⊕ N ⇓ ¹₂D +¹₂E M ⇓D {P {x/N } ⇓Eλx.P}λx.P ∈S(D)

M N ⇓ P

V ∈S(F)D(V )Eλx.P

I Example: consider M = I ⊕ ((II) ⊕ Ω), where I = λx.x and Ω = (λx.xx)(λx.xx).

M ⇓ ∅ M ⇓ {I¹²} M ⇓ {I³⁴}

I Semantics: [[M ]] = sup_{M ⇓D}D;

I Variations: Small-Step Semantics, CBV.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Approximation (Big-Step) Semantics, CBN:

M ⇓ ∅ V ⇓ {V¹}

M ⇓D N ⇓E

M ⊕ N ⇓ ¹₂D +¹₂E M ⇓D {P {x/N } ⇓Eλx.P}λx.P ∈S(D)

M N ⇓ P

V ∈S(F)D(V )Eλx.P

I Example: consider M = I ⊕ ((II) ⊕ Ω), where I = λx.x and Ω = (λx.xx)(λx.xx).

M ⇓ ∅ M ⇓ {I¹²} M ⇓ {I³⁴}

I Semantics: [[M ]] = sup_{M ⇓D}D;

I Variations: Small-Step Semantics, CBV.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I Approximation (Big-Step) Semantics, CBN:

M ⇓ ∅ V ⇓ {V¹}

M ⇓D N ⇓E

M ⊕ N ⇓ ¹₂D +¹₂E M ⇓D {P {x/N } ⇓Eλx.P}λx.P ∈S(D)

M N ⇓ P

V ∈S(F)D(V )Eλx.P

I Example: consider M = I ⊕ ((II) ⊕ Ω), where I = λx.x and Ω = (λx.xx)(λx.xx).

M ⇓ ∅ M ⇓ {I¹²} M ⇓ {I³⁴}

I Semantics: [[M ]] = sup_{M ⇓D}D;

I Variations: Small-Step Semantics, CBV.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I As an example, consider the following recursive program, and call it M :

let rec fancy x = x (+) (fancy x+1) I One can easily check that:

M p0q ⇓ ∅ M p0q ⇓ {p0q¹²} M p0q ⇓ {p0q¹², p1q¹⁴} · · ·

I As a consequence:

[[M p0q]] = sup

M p0q⇓D

D = {p0q¹², p1q¹⁴, p2q¹⁸, . . .}

Theorem

The probabilistic λ-calculus and PTMs are equiexpressive.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I As an example, consider the following recursive program, and call it M :

let rec fancy x = x (+) (fancy x+1) I One can easily check that:

M p0q ⇓ ∅ M p0q ⇓ {p0q¹²} M p0q ⇓ {p0q¹², p1q¹⁴} · · ·

I As a consequence:

[[M p0q]] = sup

M p0q⇓D

D = {p0q¹², p1q¹⁴, p2q¹⁸, . . .}

Theorem

The probabilistic λ-calculus and PTMs are equiexpressive.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I As an example, consider the following recursive program, and call it M :

let rec fancy x = x (+) (fancy x+1) I One can easily check that:

M p0q ⇓ ∅ M p0q ⇓ {p0q¹²} M p0q ⇓ {p0q¹², p1q¹⁴} · · ·

I As a consequence:

[[M p0q]] = sup

M p0q⇓D

D = {p0q¹², p1q¹⁴, p2q¹⁸, . . .}

Theorem

The probabilistic λ-calculus and PTMs are equiexpressive.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I As an example, consider the following recursive program, and call it M :

let rec fancy x = x (+) (fancy x+1) I One can easily check that:

M p0q ⇓ ∅ M p0q ⇓ {p0q¹²} M p0q ⇓ {p0q¹², p1q¹⁴} · · ·

I As a consequence:

[[M p0q]] = sup

M p0q⇓D

D = {p0q¹², p1q¹⁴, p2q¹⁸, . . .}

Theorem

The probabilistic λ-calculus and PTMs are equiexpressive.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I As an example, consider the following recursive program, and call it M :

let rec fancy x = x (+) (fancy x+1) I One can easily check that:

M p0q ⇓ ∅ M p0q ⇓ {p0q¹²} M p0q ⇓ {p0q¹², p1q¹⁴} · · ·

I As a consequence:

[[M p0q]] = sup

M p0q⇓D

D = {p0q¹², p1q¹⁴, p2q¹⁸, . . .}

Theorem

The probabilistic λ-calculus and PTMs are equiexpressive.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I As an example, consider the following recursive program, and call it M :

let rec fancy x = x (+) (fancy x+1) I One can easily check that:

M p0q ⇓ ∅ M p0q ⇓ {p0q¹²} M p0q ⇓ {p0q¹², p1q¹⁴} · · ·

I As a consequence:

[[M p0q]] = sup

M p0q⇓D

D = {p0q¹², p1q¹⁴, p2q¹⁸, . . .}

Theorem

The probabilistic λ-calculus and PTMs are equiexpressive.

Probabilistic λ-Calculus: Syntax and Operational Semantics

I As an example, consider the following recursive program, and call it M :

let rec fancy x = x (+) (fancy x+1) I One can easily check that:

M p0q ⇓ ∅ M p0q ⇓ {p0q¹²} M p0q ⇓ {p0q¹², p1q¹⁴} · · ·

I As a consequence:

[[M p0q]] = sup

M p0q⇓D

D = {p0q¹², p1q¹⁴, p2q¹⁸, . . .}

Theorem

The probabilistic λ-calculus and PTMs are equiexpressive.

Section 5

Quantum λ-Calculi

A Naïve Attempt

I While looking for a quantum generalization of the λ-calculus, one could be tempted to proceed merely by enriching its syntax of terms as follows:

M, N ::= x

|

|

|

|

|

|

I r is a quantum variable pointing to the quantum store;

I the operator new creates a new qubit;

I the operator meas measures a qubit from the quantum store;

I U applies a unitary transform to one (or more) qubits from the quantum store.

I This would be enough to express, e.g., some simple quantum circuits:

λx.λy.CNOThH x, yi λx.meas(H(new x))

A Naïve Attempt

[∅,(λx.λy.CNOThH x, yi)hnew p0q, new p0qi]

→^∗[|r →0i ⊗ |q → 0i, (λx.λy.CNOThH x, yi)hr, qi]

→ [|r → 0i ⊗ |q → 0i, CNOThH r, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 0i, CNOThr, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 1i, hr, qi]

A Naïve Attempt

[∅,(λx.λy.CNOThH x, yi)hnew p0q, new p0qi]

→^∗[|r →0i ⊗ |q → 0i, (λx.λy.CNOThH x, yi)hr, qi]

→ [|r → 0i ⊗ |q → 0i, CNOThH r, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 0i, CNOThr, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 1i, hr, qi]

A Naïve Attempt

[∅,(λx.λy.CNOThH x, yi)hnew p0q, new p0qi]

→^∗[|r →0i ⊗ |q → 0i, (λx.λy.CNOThH x, yi)hr, qi]

→ [|r → 0i ⊗ |q → 0i, CNOThH r, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 0i, CNOThr, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 1i, hr, qi]

A Naïve Attempt

[∅,(λx.λy.CNOThH x, yi)hnew p0q, new p0qi]

→^∗[|r →0i ⊗ |q → 0i, (λx.λy.CNOThH x, yi)hr, qi]

→ [|r → 0i ⊗ |q → 0i, CNOThH r, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 0i, CNOThr, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 1i, hr, qi]

A Naïve Attempt

[∅,(λx.λy.CNOThH x, yi)hnew p0q, new p0qi]

→^∗[|r →0i ⊗ |q → 0i, (λx.λy.CNOThH x, yi)hr, qi]

→ [|r → 0i ⊗ |q → 0i, CNOThH r, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 0i, CNOThr, qi]

→ [ 1

√2|r → 0, q → 0i + 1

√2|r → 1, q → 1i, hr, qi]

A Naïve Attempt

I This approach has some fundamental problems, however.

I Take the term(λx.CNOThx, xi)new and suppose, as in the previous example, to reduce it in CBV:

[∅,(λx.CNOThx, xi)(newp0q)]

→ [|r → 0i, (λx.CNOThx, xi)r]

→ [|r → 0i, CNOThr, ri]

I Qubits can be freely duplicated or erased!

I And this goes against the principles of quantum mechanics.

I We need a way to force qubits to be used exactly once when passed to functions.

A Naïve Attempt

I This approach has some fundamental problems, however.

I Take the term(λx.CNOThx, xi)new and suppose, as in the previous example, to reduce it in CBV:

[∅,(λx.CNOThx, xi)(newp0q)]

→ [|r → 0i, (λx.CNOThx, xi)r]

→ [|r → 0i, CNOThr, ri]

I Qubits can be freely duplicated or erased!

I And this goes against the principles of quantum mechanics.

I We need a way to force qubits to be used exactly once when passed to functions.

A Naïve Attempt

I This approach has some fundamental problems, however.

I Take the term(λx.CNOThx, xi)new and suppose, as in the previous example, to reduce it in CBV:

[∅,(λx.CNOThx, xi)(newp0q)]

→ [|r → 0i, (λx.CNOThx, xi)r]

→ [|r → 0i, CNOThr, ri]

I Qubits can be freely duplicated or erased!

I And this goes against the principles of quantum mechanics.

I We need a way to force qubits to be used exactly once when passed to functions.

A Naïve Attempt

I This approach has some fundamental problems, however.

I Take the term(λx.CNOThx, xi)new and suppose, as in the previous example, to reduce it in CBV:

[∅,(λx.CNOThx, xi)(newp0q)]

→ [|r → 0i, (λx.CNOThx, xi)r]

→ [|r → 0i, CNOThr, ri]

I Qubits can be freely duplicated or erased!

I And this goes against the principles of quantum mechanics.

I We need a way to force qubits to be used exactly once when passed to functions.

Linearity and the λ-Calculus

I First of all, let us impose that in any abstraction λx.M , the variable x occurs exactly once in M .

I Copying and erasure not possible, anymore.

I But the calculus loses much of its expressive power.

I The idea is to refine the calculus in such a way as to reintroduce erasure and copying, but in a controlled way.

I We mark as!M all those subterms which can be (potentially) copied or erased;

I Besides the usual linear abstraction λx.M , there is a non-linear abstraction λ!x.M .

I Altogether, then, the language of terms becomes:

M, N ::= x

|

|

|

|

|

|

|

where we insist that any term in the form!M does not contain any quantum variable.

Linearity and the λ-Calculus

I First of all, let us impose that in any abstraction λx.M , the variable x occurs exactly once in M .

I Copying and erasure not possible, anymore.

I But the calculus loses much of its expressive power.

I The idea is to refine the calculus in such a way as to reintroduce erasure and copying, but in a controlled way.

I We mark as!M all those subterms which can be (potentially) copied or erased;

I Besides the usual linear abstraction λx.M , there is a non-linear abstraction λ!x.M .

I Altogether, then, the language of terms becomes:

M, N ::= x

|

|

|

|

|

|

|

where we insist that any term in the form!M does not contain any quantum variable.

Operational Semantics

Evaluation Contexts

E::= [·]

|

|

|

|

Small Step Rules [Q, E[(λx.M )N ]] ⇒ {[Q, E[M {x/N }]]¹} [Q, E[(λ!x.M )!N ]] ⇒ {[Q, E[M {x/N }]]¹}

[Q, E[meas r]] ⇒ {[Π⁰_r(Q), E[0]]^Ξ0r(Q), [Π¹_r(Q), E[1]]^Ξ1r(Q)} [Q, E[U r]] ⇒ {[Ur(Q), E[r]]¹}

[Q, E[new 0]] ⇒ {[Q ⊗ |r → 0i, E[r]]¹} [Q, E[new 1]] ⇒ {[Q ⊗ |r → 1i, E[r]]¹}

Operational Semantics

Evaluation Contexts

E::= [·]

|

|

|

|

Small Step Rules [Q, E[(λx.M )N ]] ⇒ {[Q, E[M {x/N }]]¹} [Q, E[(λ!x.M )!N ]] ⇒ {[Q, E[M {x/N }]]¹}

[Q, E[meas r]] ⇒ {[Π⁰_r(Q), E[0]]^Ξ0r(Q), [Π¹_r(Q), E[1]]^Ξ1r(Q)} [Q, E[U r]] ⇒ {[Ur(Q), E[r]]¹}

[Q, E[new 0]] ⇒ {[Q ⊗ |r → 0i, E[r]]¹} [Q, E[new 1]] ⇒ {[Q ⊗ |r → 1i, E[r]]¹}

Operational Semantics

Evaluation Contexts

E::= [·]

|

|

|

|

Small Step Rules [Q, E[(λx.M )N ]] ⇒ {[Q, E[M {x/N }]]¹} [Q, E[(λ!x.M )!N ]] ⇒ {[Q, E[M {x/N }]]¹}

[Q, E[meas r]] ⇒ {[Π⁰_r(Q), E[0]]^Ξ0r(Q), [Π¹_r(Q), E[1]]^Ξ1r(Q)} [Q, E[U r]] ⇒ {[Ur(Q), E[r]]¹}

[Q, E[new 0]] ⇒ {[Q ⊗ |r → 0i, E[r]]¹} [Q, E[new 1]] ⇒ {[Q ⊗ |r → 1i, E[r]]¹}

Operational Semantics

Evaluation Contexts

E::= [·]

|

|

|

|

Small Step Rules [Q, E[(λx.M )N ]] ⇒ {[Q, E[M {x/N }]]¹} [Q, E[(λ!x.M )!N ]] ⇒ {[Q, E[M {x/N }]]¹}

[Q, E[meas r]] ⇒ {[Π⁰_r(Q), E[0]]^Ξ0r(Q), [Π¹_r(Q), E[1]]^Ξ1r(Q)} [Q, E[U r]] ⇒ {[Ur(Q), E[r]]¹}

[Q, E[new 0]] ⇒ {[Q ⊗ |r → 0i, E[r]]¹} [Q, E[new 1]] ⇒ {[Q ⊗ |r → 1i, E[r]]¹}

Operational Semantics

Evaluation Contexts

E::= [·]

|

|

|

|

Small Step Rules [Q, E[(λx.M )N ]] ⇒ {[Q, E[M {x/N }]]¹} [Q, E[(λ!x.M )!N ]] ⇒ {[Q, E[M {x/N }]]¹}

[Q, E[meas r]] ⇒ {[Π⁰_r(Q), E[0]]^Ξ0r(Q), [Π¹_r(Q), E[1]]^Ξ1r(Q)} [Q, E[U r]] ⇒ {[Ur(Q), E[r]]¹}

[Q, E[new 0]] ⇒ {[Q ⊗ |r → 0i, E[r]]¹} [Q, E[new 1]] ⇒ {[Q ⊗ |r → 1i, E[r]]¹}

Expressive Power

Theorem

Any uniform quantum circuit family {C_n}_n∈N is simulated by a meas-free term M .

I Given s, the term M computes a code for C_|s|

I Then, it applies C_|s| to s.

Theorem

Any meas-free term M computes the same function as a uniform quantum circuit family {C_n}_n∈N.

I A term M can be evaluated by first reducing all the

“classical” redexes, and the reducing the “quantum” ones.

I This is possible due to a standardization result.

Expressive Power

Theorem

Any uniform quantum circuit family {C_n}_n∈N is simulated by a meas-free term M .

I Given s, the term M computes a code for C_|s|

I Then, it applies C_|s| to s.

Theorem

Any meas-free term M computes the same function as a uniform quantum circuit family {C_n}_n∈N.

I A term M can be evaluated by first reducing all the

“classical” redexes, and the reducing the “quantum” ones.

I This is possible due to a standardization result.

Expressive Power

Theorem

Any uniform quantum circuit family {C_n}_n∈N is simulated by a meas-free term M .

I Given s, the term M computes a code for C_|s|

I Then, it applies C_|s| to s.

Theorem

Any meas-free term M computes the same function as a uniform quantum circuit family {C_n}_n∈N.

I A term M can be evaluated by first reducing all the

“classical” redexes, and the reducing the “quantum” ones.

I This is possible due to a standardization result.

Expressive Power

Theorem

Any uniform quantum circuit family {C_n}_n∈N is simulated by a meas-free term M .

I Given s, the term M computes a code for C_|s|

I Then, it applies C_|s| to s.

Theorem

Any meas-free term M computes the same function as a uniform quantum circuit family {C_n}_n∈N.

I A term M can be evaluated by first reducing all the

“classical” redexes, and the reducing the “quantum” ones.

I This is possible due to a standardization result.

Wrapping Up

I Probabilistic and quantum programming are both at their infancy.

I A lot of interest.

I Many different proposals.

I Not so many results relating one programming language to the other.

I We have only presented some of the many proposals for models and calculi.

I Very interesting topics we have no time to talk about:

I Denotational semantics.

I Type Systems.

I Implicit Computational Complexity.

I Concrete programming languages: Quipper, Church, Venture, QScript.

Wrapping Up

I Probabilistic and quantum programming are both at their infancy.

I A lot of interest.

I Many different proposals.

I Not so many results relating one programming language to the other.

I We have only presented some of the many proposals for models and calculi.

I Very interesting topics we have no time to talk about:

I Denotational semantics.

I Type Systems.

I Implicit Computational Complexity.

I Concrete programming languages: Quipper, Church, Venture, QScript.

Wrapping Up

I Probabilistic and quantum programming are both at their infancy.

I A lot of interest.

I Many different proposals.

I Not so many results relating one programming language to the other.

I We have only presented some of the many proposals for models and calculi.

I Very interesting topics we have no time to talk about:

I Denotational semantics.

I Type Systems.

I Implicit Computational Complexity.

I Concrete programming languages: Quipper, Church, Venture, QScript.

Thank You!

Questions?