A Brief Introduction to Probabilistic and Quantum Programming
Part I
Ugo Dal Lago
Universidade do Minho, Thursday May 4, 2017
Section 1
Classical and Probabilistic Systems
Notation
I Sets: A, B, C, . . .;
I Cartesian Products: A× B;
I Natural Numbers: 1,2,3,. . .
I Real Numbers: R;
1,3
7, 17463, π, . . .
I Complex Numbers: C;
1 + 5i, 1
√2i, . . .
I Bits: F = {0, 1};
I Vectors: An;
I Matrices: Bm×n.
State of a Physical System
I Instantaneous description of the physical entities forming the system;
I Can change over time;
I Is very often an element of Rd;
I In classical physics, the state of a system is uniquely determined.
Example: Particle in R
2at a Given Time
(1, 1)
Example: Particle in R
2at a Given Time
(1, 1, 0, 1) Position
Momentum
Example: Particle in R
2Dynamically
Example: Particle in R
2Dynamically
Composing Physical Systems
I If the states of two physical systems live in Rne Rm
(respectively), how should we represent the physical system obtained by composing the two systems?
I We should keep track of the first and the second state.
I Solution: Rn× Rm=Rn+m.
How to Discretize Time (and the State Space)
I Traditionally, time is just a number from R.
I But sometimes, it suffices to consider the state of the system only at certain instants.
0,α, 2α, 3α, 4α, . . .
I Time becomes an element of N, i.e., it is discrete.
I Why?
I Abstraction;
I Simulation.
I Sometimes also states become discrete. . .
I E.g., in Turing Machines.
I Often one can also assume that there are finitely many states.
I The system is in one of then states S = {x1, . . . , xn} ⊆ Rn.
I For the sake of simplicity, let us focus our attention on finite state systems.
How to Discretize Time (and the State Space)
I Traditionally, time is just a number from R.
I But sometimes, it suffices to consider the state of the system only at certain instants.
0, α,2α, 3α, 4α, . . .
I Time becomes an element of N, i.e., it is discrete.
I Why?
I Abstraction;
I Simulation.
I Sometimes also states become discrete. . .
I E.g., in Turing Machines.
I Often one can also assume that there are finitely many states.
I The system is in one of then states S = {x1, . . . , xn} ⊆ Rn.
I For the sake of simplicity, let us focus our attention on finite state systems.
How to Discretize Time (and the State Space)
I Traditionally, time is just a number from R.
I But sometimes, it suffices to consider the state of the system only at certain instants.
0, α, 2α,3α, 4α, . . .
I Time becomes an element of N, i.e., it is discrete.
I Why?
I Abstraction;
I Simulation.
I Sometimes also states become discrete. . .
I E.g., in Turing Machines.
I Often one can also assume that there are finitely many states.
I The system is in one of then states S = {x1, . . . , xn} ⊆ Rn.
I For the sake of simplicity, let us focus our attention on finite state systems.
How to Discretize Time (and the State Space)
I Traditionally, time is just a number from R.
I But sometimes, it suffices to consider the state of the system only at certain instants.
0, α, 2α, 3α,4α, . . .
I Time becomes an element of N, i.e., it is discrete.
I Why?
I Abstraction;
I Simulation.
I Sometimes also states become discrete. . .
I E.g., in Turing Machines.
I Often one can also assume that there are finitely many states.
I The system is in one of then states S = {x1, . . . , xn} ⊆ Rn.
I For the sake of simplicity, let us focus our attention on finite state systems.
How to Discretize Time (and the State Space)
I Traditionally, time is just a number from R.
I But sometimes, it suffices to consider the state of the system only at certain instants.
0, α, 2α, 3α, 4α, . . .
I Time becomes an element of N, i.e., it is discrete.
I Why?
I Abstraction;
I Simulation.
I Sometimes also states become discrete. . .
I E.g., in Turing Machines.
I Often one can also assume that there are finitely many states.
I The system is in one of then states S = {x1, . . . , xn} ⊆ Rn.
I For the sake of simplicity, let us focus our attention on finite state systems.
How to Discretize Time (and the State Space)
I Traditionally, time is just a number from R.
I But sometimes, it suffices to consider the state of the system only at certain instants.
0, α, 2α, 3α, 4α, . . .
I Time becomes an element of N, i.e., it is discrete.
I Why?
I Abstraction;
I Simulation.
I Sometimes also states become discrete. . .
I E.g., in Turing Machines.
I Often one can also assume that there are finitely many states.
I The system is in one of then states S = {x1, . . . , xn} ⊆ Rn.
I For the sake of simplicity, let us focus our attention on finite state systems.
How to Discretize Time (and the State Space)
I Traditionally, time is just a number from R.
I But sometimes, it suffices to consider the state of the system only at certain instants.
0, α, 2α, 3α, 4α, . . .
I Time becomes an element of N, i.e., it is discrete.
I Why?
I Abstraction;
I Simulation.
I Sometimes also states become discrete. . .
I E.g., in Turing Machines.
I Often one can also assume that there are finitely many states.
I The system is in one of then states S = {x1, . . . , xn} ⊆ Rn.
I For the sake of simplicity, let us focus our attention on finite state systems.
Example: Particle in R
2, Dynamically
Example: Particle in R
2, Dynamically
Probabilistic Systems, Statically
I In classical physics, the state of any system is uniquely determined.
I For reasons of abstraction and complexity, one ofter uses a probabilistic representation of states.
I Example: a dice.
I If there is no uncertainty about a state, the latter is said to be pure.
I Elements ofS = {x1, . . . , xn} are precisely the pure states.
I In general, however, a state (at any given time) is described as a function P :S → R such that P
x∈SP(x) = 1, or by a vector in R|S|:
P(x1)
... P(xn)
=
p1
... pn
I This is a mixed state.
Probabilistic Systems, Dynamically
I In any given pure state xi, the system can evolve into any pure statexj with probabilitypij.
I As an example:
1 2 1 2
1 2
1 2
1 2 1 2
tt tc ct cc
Example: Particle in R
2, Dynamically
3 4
3 4 3
4 3 4 1 4
1 4
1 4 1
4
Dynamics: Matrix Representation
I Suppose we work in a system withn pure states:
S = {x1, . . . , xn} ⊆ Rm.
I The dynamic evolution of the system is described, compactly, by the matrix M inRn×n:
M =
p11 p12 · · · p1n
p21 p22 · · · p2n
... ... . .. ... pn1 pn2 · · · pnn
I A transition step corresponds to multiplying M and P (the latter seen as a vector).
I In other words, the system can be seen as a so-called Markov Chain.
Example: Particle in R
2, Dynamically
3 4
3 4 3
4
3 4 1 4
1 4
1 4 1
4
x
1x
2x
3x
4M =
0 0 0 34
3 4 1
4 1 4 0 0 34 0 0
1
4 0 34 14
Example: Particle in R
2, Dynamically
3 4
3 4 3
4
3 4 1 4
1 4
1 4 1
4
x
1x
2x
3x
4(1, 0, 0, 0)
⇒
0,3
4, 0,1 4
⇒
3 16, 3
16, 9 16, 1
16
...
Example: Particle in R
2, Dynamically
3 4
3 4 3
4
3 4 1 4
1 4
1 4 1
4
x
1x
2x
3x
4(1, 0, 0, 0)
⇒
0,3
4, 0,1 4
⇒
3 16, 3
16, 9 16, 1
16
...
Intermezzo: Linearity
I Vectors in Rn support:
I Binary Sums:
x1
... xn
+
y1
... yn
=
x1+ y1
... xn+ yn
I Products by Scalars inR:
α
x1
... xn
=
αx1
... αxn
I Multiplication with a matrix gives rise to a linear map:
M(αx) = α(Mx);
M(x + y) = Mx + My.
Classical Systems as Specific Probabilistic Systems
I A pure state can be seen as a function P :S → R such that P(xi) = 1 for a given xi.
I The system is inxi, without any uncertainty.
I If the matrixM = (pij) is such that for every i∈ {1, . . . , n}
there isj∈ {1, . . . , n} such that pij = 1, then M is classical.
I A classical matrix turns pure states into pure states!
I As an example:
Classical Systems as Specific Probabilistic Systems
I A pure state can be seen as a function P :S → R such that P(xi) = 1 for a given xi.
I The system is inxi, without any uncertainty.
I If the matrixM = (pij) is such that for every i∈ {1, . . . , n}
there isj∈ {1, . . . , n} such that pij = 1, then M is classical.
I A classical matrix turns pure states into pure states!
I As an example:
Classical Systems as Specific Probabilistic Systems
I A pure state can be seen as a function P :S → R such that P(xi) = 1 for a given xi.
I The system is inxi, without any uncertainty.
I If the matrixM = (pij) is such that for every i∈ {1, . . . , n}
there isj∈ {1, . . . , n} such that pij = 1, then M is classical.
I A classical matrix turns pure states into pure states!
I As an example:
Classical Systems as Specific Probabilistic Systems
I A pure state can be seen as a function P :S → R such that P(xi) = 1 for a given xi.
I The system is inxi, without any uncertainty.
I If the matrixM = (pij) is such that for every i∈ {1, . . . , n}
there isj∈ {1, . . . , n} such that pij = 1, then M is classical.
I A classical matrix turns pure states into pure states!
I As an example:
1
1
1
1 x
1x
2x
3x
4M =
0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0
Section 2
Probabilistic Computational Models
Incepting Probability into Algorithms
I In what we have seen so far, probability has been seen a way to facilitate modeling of existing systems, e.g.
Modeling Model ?
System
I Probability, however, can also be seen as a very powerful way to compute.
I Algorithms can “flip a coin”.
I This is somehow a paradigm shift: probabilism is not there for modeling uncertainty, but rather for the purpose of relaxing determinism as an algorithm design principle.
I This “new” computation paradigm is called probabilistic computation.
I Your algorithms (then your programs) can be seen and treated as probabilistic systems.
Incepting Probability into Algorithms
I In what we have seen so far, probability has been seen a way to facilitate modeling of existing systems, e.g.
Modeling Model Verification
System
I Probability, however, can also be seen as a very powerful way to compute.
I Algorithms can “flip a coin”.
I This is somehow a paradigm shift: probabilism is not there for modeling uncertainty, but rather for the purpose of relaxing determinism as an algorithm design principle.
I This “new” computation paradigm is called probabilistic computation.
I Your algorithms (then your programs) can be seen and treated as probabilistic systems.
Incepting Probability into Algorithms
I In what we have seen so far, probability has been seen a way to facilitate modeling of existing systems, e.g.
Modeling Model Verification
System
I Probability, however, can also be seen as a very powerful way to compute.
I Algorithms can “flip a coin”.
I This is somehow a paradigm shift: probabilism is not there for modeling uncertainty, but rather for the purpose of relaxing determinism as an algorithm design principle.
I This “new” computation paradigm is called probabilistic computation.
I Your algorithms (then your programs) can be seen and treated as probabilistic systems.
But Why?
I Achieving Better Performances
I Allowing computation to proceed probabilistically somehow allows to exploit different computation paths at the same time.
I Of course, each computation path comes with its own probability.
I . . . but all this can (sometime) be turned into a way to alleviate exponential blowups.
I Allowing a Form of “Confusion” in Computation
I Deterministic computation has its own shortcomings.
I In particular, in some interactive scenarios probabilistic computation is a way to make computation unpredictable.
But Why?
I Achieving Better Performances
I Allowing computation to proceed probabilistically somehow allows to exploit different computation paths at the same time.
I Of course, each computation path comes with its own probability.
I . . . but all this can (sometime) be turned into a way to alleviate exponential blowups.
I Allowing a Form of “Confusion” in Computation
I Deterministic computation has its own shortcomings.
I In particular, in some interactive scenarios probabilistic computation is a way to make computation unpredictable.
Example
Example
Section 3
Quantum Systems
Quanta and Computation
I Starting from the beginning of the XX century, physical sciences faced a series of revolutions.
I The principles of classical physics were proved not to hold when the involved magnitudes become as little as those in atoms, or as big as those in astrophysics.
I One of the answers to the subsequent crisis was the introduction of quantum mechanics.
I It is a complex, non-intuitive, theory;
I Mathematically, it is highly not trivial;
I In 1982, Richard Feynman suggests, for the first time, that quantum mechanics can form the basis of a new model of computation, more efficient than the one introduced by Turing and later generalized to a proper model of
computation.
Quanta and Computation
I Starting from the beginning of the XX century, physical sciences faced a series of revolutions.
I The principles of classical physics were proved not to hold when the involved magnitudes become as little as those in atoms, or as big as those in astrophysics.
I One of the answers to the subsequent crisis was the introduction of quantum mechanics.
I It is a complex, non-intuitive, theory;
I Mathematically, it is highly not trivial;
I In 1982, Richard Feynman suggests, for the first time, that quantum mechanics can form the basis of a new model of computation, more efficient than the one introduced by Turing and later generalized to a proper model of
computation.
Quanta and Computation
I Starting from the beginning of the XX century, physical sciences faced a series of revolutions.
I The principles of classical physics were proved not to hold when the involved magnitudes become as little as those in atoms, or as big as those in astrophysics.
I One of the answers to the subsequent crisis was the introduction of quantum mechanics.
I It is a complex, non-intuitive, theory;
I Mathematically, it is highly not trivial;
I In 1982, Richard Feynman suggests, for the first time, that quantum mechanics can form the basis of a new model of computation, more efficient than the one introduced by Turing and later generalized to a proper model of
computation.
Quanta and Computation
I Starting from the beginning of the XX century, physical sciences faced a series of revolutions.
I The principles of classical physics were proved not to hold when the involved magnitudes become as little as those in atoms, or as big as those in astrophysics.
I One of the answers to the subsequent crisis was the introduction of quantum mechanics.
I It is a complex, non-intuitive, theory;
I Mathematically, it is highly not trivial;
I In 1982, Richard Feynman suggests, for the first time, that quantum mechanics can form the basis of a new model of computation, more efficient than the one introduced by Turing and later generalized to a proper model of
computation.
State of a Quantum System H
nI It is a vector in Cn:
x =
c1
... cn
I The following condition must hold:
Xn i=1
||ci||2 = 1
I We can write
x = c1x1+ . . . + cnxn,
where thexi are always0 except in the ith coordinate, which is1 (x1, . . . , xn is the computational base of the system).
I What does xi represent? It is an observable of the system.
I Every orthonormal base forCn corresponds to one such observable property.
Evolution of a Quantum System H
nI The system evolves linearly, thus its dynamics can be described by a matrix:
d1
... dn
=
a11 · · · a1n
... ... an1 · · · ann
c1
... cn
I It must be that Pn
i=1||di||2= 1.
I A necessary and sufficient condition is that Q = (aij) must be unitary: Q∗ = Q−1.
I Q∗ is the conjugate transpose ofQ. As an example,
a11 · · · a1n
... ... an1 · · · ann
∗
=
a∗11 · · · a∗n1 ... ... a∗1n · · · a∗nn
I The product of two unitary matrices is again unitary.
Measurement in a Quantum System H
nI Given a Quantum Systemx = (ci), the quantity||ci||2 should not be interpreted as the probability of being in state xi.
I The only way to observe the state of a quantum system is by way of measurements:
I When measured, the state of a system goes fromx = (ci) to each of the statesxj with probability equals to||cj||2.
I At that point the system is in a classical state, i.e., it can be observed without being altered.
I Everything depends on the chosen base, which corresponds to the desired observable.
I Again: measuring a quantum system can alter its state!
Measurement in a Quantum System H
nx = P n
i=1 c i x i
x 1 x 2
x n .. .
||c
1||
2||c
2||
2||c
n||
2Composing two Quantum Systems H
nand H
mI Given two quantum systems with computational bases x1, . . . , xn;
y1, . . . , ym;
their composition has computational basis (x1, y1), . . . , (xn, ym).
I Thus, we get the system
Hnm = Hn⊗ Hm.
I Let us indicate the pair(xi, xj) by xi⊗ xj;
Composing two Quantum Systems H
nand H
mI We can extend this operation to all states of Hn and Hm: Xn
i=1
cixi
!
⊗
Xm j=1
djyj
= Xn
i=1
Xm j=1
cidjxi⊗ yj.
I A quantum statex is sometimes indicated as|xi.
I Another notational abuse:
|xi ⊗ |yi = |xi|yi = |xyi.
I If a state x of Hn⊗ Hm is such thatx = y⊗ z, then x is said to be decomposable, and otherwise entangled.
I Given two unitary transforms Qn, Qm on Hn and Hm (respectively), we can buildQn⊗ Qm. . .
Example: H
2I The states of the system are the unitary vectors inC2.
I The states of the orthonormal base|x1i, |x2i are sometime denoted with|0i e |1i.
I Unitary transforms: examples:
I =
1 0 0 1
X =
0 1 1 0
Y =
0 −i i 0
Z =
1 0
−1 0
H = 1
√2
1 1 1 −1
I States of H2 are said to be qubits.
Example: H
2⊗ H
2I States of the systems are the unitary vectors in C4 ∼=C2⊗ C2.
I Let us consider two example states inH2⊗ H2.
I The state|01i is decomposable: |01i = |0i ⊗ |1i.
I The state
√1
2|00i + 1
√2|11i is entangled
I A unitary transform on H2⊗ H2 which cannot be decomposed as two unitary transforms on H2 is:
CNOT =
1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0
An Example
(CNOT◦ (H ⊗ I))|00i
= CNOT((H⊗ I)(|00i))
= CNOT(H(|0i) ⊗ I(|0i))
= CNOT(H(|0i) ⊗ |0i)
= CNOT
1
√2|0i + 1
√2|1i
⊗ |0i
= CNOT
1
√2|00i + 1
√2|10i
= 1
√2CNOT|00i + 1
√2CNOT|10i
= 1
√2|00i + 1
√2|11i
An Example
(CNOT◦ (H ⊗ I))|00i
= CNOT((H⊗ I)(|00i))
= CNOT(H(|0i) ⊗ I(|0i))
= CNOT(H(|0i) ⊗ |0i)
= CNOT
1
√2|0i + 1
√2|1i
⊗ |0i
= CNOT
1
√2|00i + 1
√2|10i
= 1
√2CNOT|00i + 1
√2CNOT|10i
= 1
√2|00i + 1
√2|11i
An Example
(CNOT◦ (H ⊗ I))|00i
= CNOT((H⊗ I)(|00i))
= CNOT(H(|0i) ⊗ I(|0i))
= CNOT(H(|0i) ⊗ |0i)
= CNOT
1
√2|0i + 1
√2|1i
⊗ |0i
= CNOT
1
√2|00i + 1
√2|10i
= 1
√2CNOT|00i + 1
√2CNOT|10i
= 1
√2|00i + 1
√2|11i
An Example
(CNOT◦ (H ⊗ I))|00i
= CNOT((H⊗ I)(|00i))
= CNOT(H(|0i) ⊗ I(|0i))
= CNOT(H(|0i) ⊗ |0i)
= CNOT
1
√2|0i + 1
√2|1i
⊗ |0i
= CNOT
1
√2|00i + 1
√2|10i
= 1
√2CNOT|00i + 1
√2CNOT|10i
= 1
√2|00i + 1
√2|11i
An Example
(CNOT◦ (H ⊗ I))|00i
= CNOT((H⊗ I)(|00i))
= CNOT(H(|0i) ⊗ I(|0i))
= CNOT(H(|0i) ⊗ |0i)
= CNOT
1
√2|0i + 1
√2|1i
⊗ |0i
= CNOT
1
√2|00i + 1
√2|10i
= 1
√2CNOT|00i + 1
√2CNOT|10i
= 1
√2|00i + 1
√2|11i
An Example
(CNOT◦ (H ⊗ I))|00i
= CNOT((H⊗ I)(|00i))
= CNOT(H(|0i) ⊗ I(|0i))
= CNOT(H(|0i) ⊗ |0i)
= CNOT
1
√2|0i + 1
√2|1i
⊗ |0i
= CNOT
1
√2|00i + 1
√2|10i
= 1
√2CNOT|00i + 1
√2CNOT|10i
= 1
√2|00i + 1
√2|11i
An Example
(CNOT◦ (H ⊗ I))|00i
= CNOT((H⊗ I)(|00i))
= CNOT(H(|0i) ⊗ I(|0i))
= CNOT(H(|0i) ⊗ |0i)
= CNOT
1
√2|0i + 1
√2|1i
⊗ |0i
= CNOT
1
√2|00i + 1
√2|10i
= 1
√2CNOT|00i + 1
√2CNOT|10i
= 1
√2|00i + 1
√2|11i
An Example
(CNOT◦ (H ⊗ I))|00i
= CNOT((H⊗ I)(|00i))
= CNOT(H(|0i) ⊗ I(|0i))
= CNOT(H(|0i) ⊗ |0i)
= CNOT
1
√2|0i + 1
√2|1i
⊗ |0i
= CNOT
1
√2|00i + 1
√2|10i
= 1
√2CNOT|00i + 1
√2CNOT|10i
= 1
√2|00i + 1
√2|11i
About Measurements, Again
I Suppose we want to work with the system Hn⊗ Hm. A state of the system can be expressed as:
Q = Xn i=1
Xm j=1
cij|xii|xji.
I If we observe the first component of the system (the
“rightmost” component of the tensor product), we get that:
I We will end up in a state|xki ⊗ |yi where xk is an element of the computational base, whiley is not necessarily one such.
I The probability of reaching|xki ⊗ |yi is equal to Ξk(Q) =
Xm j=1
||ckj||2.
I The state|xki ⊗ |yi can be expressed as follows:
Πk(Q) = 1 pP(k)
Xm j=1
ckj|xki|yji = |xki pP(k)
Xm j=1
ckj|yji
About Measurements, Again
Q
Π 1 (Q) Π 2 (Q)
Π n (Q)
Ξ 1 (Q)
Ξ 2 (Q)
Ξ n (Q)
. .
.
About Measurements, Again
√ 1
2 |00i + √ 1
2 |11i
|00i
|11i
1 2
1
2
A Game
A B C
A Game
A
B C
A Game
A
B C
A Game
A
B C
A Game
A
B C
A Game
A
B C
A Game
A B C
0 1 0 0
1 0
A Game
A
B C
0 1
0 0
1 0
A Game
A
B C
0 1
0 0
1 0
A Game
A
B C
0 1
0 0
1 0
A Game
A
B C
0 1
0 0
1 0
A Game
A
B C
0 1
0 0
1 0
When do A, B and C Win?
A B C
Even
Odd
When do A, B and C Win?
A B C
1 0 0 1
0
1
When do A, B and C Win?
A B C
1 0 0 1
0
1
A
When do A, B and C Win?
A B C
1 0 0 1
0 1 A
A
+ B
+ C
= Odd
A
+ B
+ C
= Even
A
+ B
+ C
= Even
A
+ B
+ C
= Even
A, B e C Cannot Win!
2A
+2A
+2B
+2B
+2C
+2C
= Odd
A, B e C Cannot Win!
2A
+2A
+2B
+2B
+2C
+2C
= Odd
Quantum Strategies
A
|1yzi →q
1
2|1yzi +q
1 2|0yzi
|0yzi →q
1
2|1yzi −q
−12|0yzi
|1yzi →q
1
2|1yzi +q
1 2|0yzi
|0yzi →q
1
2|1yzi −q
1 2|0yzi
If arrives. . . r1
2|111i + r1
2|000i → 1
2|111i +1
2|011i +1
2|100i −1 2|000i
Quantum Strategies
A
|1yzi →q
1
2|1yzi +q
1 2|0yzi
|0yzi →q
1
2|1yzi −q
−12|0yzi
|1yzi →q
1
2|1yzi +q
1 2|0yzi
|0yzi →q
1
2|1yzi −q
1 2|0yzi
If arrives. . . r1
2|111i + r1
2|000i → 1
2|111i +1
2|011i +1
2|100i −1 2|000i
Quantum Strategies
A
|1yzi →q
1
2|1yzi +q
1 2|0yzi
|0yzi →q
1
2|1yzi −q
−12|0yzi
|1yzi →q
1
2|1yzi +q
1 2|0yzi
|0yzi →q
1
2|1yzi −q
1 2|0yzi
If arrives. . . r1
2|111i + r1
2|000i → 1
2|111i +1
2|011i +1
2|100i −1 2|000i
Suppose that A, B, C Receive . . .
r1
2|111i + r1
2|000i → 1
4|111i +1
4|110i +1
4|111i −1 4|110i +1
4|101i + 1
4|100i −1
4|101i +1 4|100i +1
4|011i + 1
4|010i −1
4|011i +1 4|010i +1
4|001i + 1
4|000i +1
4|001i −1 4|000i
= 1
2|111i +1
2|100i +1
2|010i −1 2|001i
Suppose that A, B, C Receive . . .
r1
2|111i + r1
2|000i → 1
4|111i +1
4|110i +1
4|111i −1 4|110i +1
4|101i + 1
4|100i −1
4|101i +1 4|100i +1
4|011i + 1
4|010i −1
4|011i +1 4|010i +1
4|001i + 1
4|000i +1
4|001i −1 4|000i
= 1
2|111i +1
2|100i +1
2|010i −1 2|001i
Section 4
Probabilistic Computational Models
Probabilistic Turing Machines
I Generalizing ordinary Turing Machines to the probabilistic setting is a relatively easy task.
I A Turing Machine is a quadruple(Q, Σ, δ, F ).
I In presence of determinism,
δ : Q× Σ → Q × Σ × {←, ↓, →}.
I When evolution is nondeterministic,
δ : Q× Σ → P(Q × Σ × {←, ↓, →}).
I When evolution is probabilistic,
δ : Q× Σ → D(Q × Σ × {←, ↓, →}).
whereD(A) is the set of all functions f from A to R such thatP
a∈Af (a) = 1.
I In PTMs, any computationρ : C1 → C2 → . . . → Cn has a probability.
Probabilistic Turing Machines
I Generalizing ordinary Turing Machines to the probabilistic setting is a relatively easy task.
I A Turing Machine is a quadruple(Q, Σ, δ, F ).
I In presence of determinism,
δ : Q× Σ → Q × Σ × {←, ↓, →}.
I When evolution is nondeterministic,
δ : Q× Σ → P(Q × Σ × {←, ↓, →}).
I When evolution is probabilistic,
δ : Q× Σ → D(Q × Σ × {←, ↓, →}).
whereD(A) is the set of all functions f from A to R such thatP
a∈Af (a) = 1.
I In PTMs, any computationρ : C1 → C2 → . . . → Cn has a probability.
Probabilistic Turing Machines
I Generalizing ordinary Turing Machines to the probabilistic setting is a relatively easy task.
I A Turing Machine is a quadruple(Q, Σ, δ, F ).
I In presence of determinism,
δ : Q× Σ → Q × Σ × {←, ↓, →}.
I When evolution is nondeterministic,
δ : Q× Σ → P(Q × Σ × {←, ↓, →}).
I When evolution is probabilistic,
δ : Q× Σ → D(Q × Σ × {←, ↓, →}).
whereD(A) is the set of all functions f from A to R such thatP
a∈Af (a) = 1.
I In PTMs, any computationρ : C1 → C2 → . . . → Cn has a probability.
Probabilistic Turing Machines
I Generalizing ordinary Turing Machines to the probabilistic setting is a relatively easy task.
I A Turing Machine is a quadruple(Q, Σ, δ, F ).
I In presence of determinism,
δ : Q× Σ → Q × Σ × {←, ↓, →}.
I When evolution is nondeterministic,
δ : Q× Σ → P(Q × Σ × {←, ↓, →}).
I When evolution is probabilistic,
δ : Q× Σ → D(Q × Σ × {←, ↓, →}).
whereD(A) is the set of all functions f from A to R such thatP
a∈Af (a) = 1.
I In PTMs, any computationρ : C1 → C2 → . . . → Cn has a probability.
PTMs, Languages and Functions
I In PTM, termination and acceptance of a string become probabilistic events.
I A PTM can terminate with probability1 even if there is the possibility of nontermination.
I A given string s∈ Σ∗ is accepted with a probability between 0 and 1, included.
I How can we define language recognition?
I One can consider different, alternative, constraints on the error probability:
I It must be 0.
I It must be smaller than 12;
I It must be smaller than a given fixed constant ε, itself smaller than 12.
I One can stipulate that the given result is the one with highest probability.
Section 5
Quantum Computational Models
No-Cloning Theorem
I Let us consider a quantum system Hn with computational basex1, . . . , xn.
I A unitary transformation Q on Hn⊗ Hnis a cloning map if Q|xi|x1i = |xi|xi.
Theorem (No-Cloning)
For n≥ 2, there is no cloning map.
I This does not mean that states of the computational base cannot be cloned.
I There is an analogous theorem about erasing maps.
No-Cloning Theorem
I Let us consider a quantum system Hn with computational basex1, . . . , xn.
I A unitary transformation Q on Hn⊗ Hnis a cloning map if Q|xi|x1i = |xi|xi.
Theorem (No-Cloning)
For n≥ 2, there is no cloning map.
I This does not mean that states of the computational base cannot be cloned.
I There is an analogous theorem about erasing maps.
No-Cloning Theorem
I Let us consider a quantum system Hn with computational basex1, . . . , xn.
I A unitary transformation Q on Hn⊗ Hnis a cloning map if Q|xi|x1i = |xi|xi.
Theorem (No-Cloning)
For n≥ 2, there is no cloning map.
I This does not mean that states of the computational base cannot be cloned.
I There is an analogous theorem about erasing maps.
No-Cloning Theorem
I Let us consider a quantum system Hn with computational basex1, . . . , xn.
I A unitary transformation Q on Hn⊗ Hnis a cloning map if Q|xi|x1i = |xi|xi.
Theorem (No-Cloning)
For n≥ 2, there is no cloning map.
I This does not mean that states of the computational base cannot be cloned.
I There is an analogous theorem about erasing maps.
Boolean Circuits
I As we all know, they are networks of gates which compute very simple functions onF = {0, 1}.
I Example:
∧
∧
∨
¬ x
y
I Every function f :Fn→ Fm is computable by a boolean circuit Cf.
I Could we have finite, universal, set of gates?
I Yes, e.g.,{∧, ∨, ¬}.
But... How About Turing Machines?
I Boolean circuits can be seen as a minimal computational model, whose expressive power turns out to be very poor.
I There are fundamental differences with Turing Machines:
I In boolean circuits, everything is (even potentially) finite.
I Functions computed by circuits and by TM are functions from different domains: Fn → Fmvs. F∗→ F∗.
I Boolean circuits are somehow complete, while TM are not, as we all know.
I Can we somehow reconcile the two worlds?
I A circuit family is a collection{Cn}n∈N.
I A circuit family computes a function fromF∗ toF∗.
I A circuit family is said to be uniform if there is a TM which, on inputn, outputs (an enconding) of Cn.
Theorem
The class of functions computed by TMs equals the class of functions computed by uniform circuit families.
But... How About Turing Machines?
I Boolean circuits can be seen as a minimal computational model, whose expressive power turns out to be very poor.
I There are fundamental differences with Turing Machines:
I In boolean circuits, everything is (even potentially) finite.
I Functions computed by circuits and by TM are functions from different domains: Fn → Fmvs. F∗→ F∗.
I Boolean circuits are somehow complete, while TM are not, as we all know.
I Can we somehow reconcile the two worlds?
I A circuit family is a collection{Cn}n∈N.
I A circuit family computes a function fromF∗ toF∗.
I A circuit family is said to be uniform if there is a TM which, on inputn, outputs (an enconding) of Cn.
Theorem
The class of functions computed by TMs equals the class of functions computed by uniform circuit families.
But... How About Turing Machines?
I Boolean circuits can be seen as a minimal computational model, whose expressive power turns out to be very poor.
I There are fundamental differences with Turing Machines:
I In boolean circuits, everything is (even potentially) finite.
I Functions computed by circuits and by TM are functions from different domains: Fn → Fmvs. F∗→ F∗.
I Boolean circuits are somehow complete, while TM are not, as we all know.
I Can we somehow reconcile the two worlds?
I A circuit family is a collection{Cn}n∈N.
I A circuit family computes a function fromF∗ toF∗.
I A circuit family is said to be uniform if there is a TM which, on inputn, outputs (an enconding) of Cn.
Theorem
The class of functions computed by TMs equals the class of functions computed by uniform circuit families.
But... How About Turing Machines?
I Boolean circuits can be seen as a minimal computational model, whose expressive power turns out to be very poor.
I There are fundamental differences with Turing Machines:
I In boolean circuits, everything is (even potentially) finite.
I Functions computed by circuits and by TM are functions from different domains: Fn → Fmvs. F∗→ F∗.
I Boolean circuits are somehow complete, while TM are not, as we all know.
I Can we somehow reconcile the two worlds?
I A circuit family is a collection{Cn}n∈N.
I A circuit family computes a function fromF∗ toF∗.
I A circuit family is said to be uniform if there is a TM which, on inputn, outputs (an enconding) of Cn.
Theorem
The class of functions computed by TMs equals the class of functions computed by uniform circuit families.
Quantum Circuits
I They themselves consist in gate networks, which can be of three different kinds:
I Quantum gates, which compute unitary transforms on H2⊗ . . . ⊗ H2.
I Measurement gates, which observe the value of one qubit.
I The wires connecting gates are themselves of two types:
I Quanum channels, which connect quantum gates to other quantum gates or to measurement gates.
I Classic channels, which are the output wires of measurement gates and which control the application of quantum gates.
I Qubits cannot be duplicated.
I Example:
H • •
X
Quantum Circuits
I They themselves consist in gate networks, which can be of three different kinds:
I Quantum gates, which compute unitary transforms on H2⊗ . . . ⊗ H2.
I Measurement gates, which observe the value of one qubit.
I The wires connecting gates are themselves of two types:
I Quanum channels, which connect quantum gates to other quantum gates or to measurement gates.
I Classic channels, which are the output wires of measurement gates and which control the application of quantum gates.
I Qubits cannot be duplicated.
I Example:
H • •
X
Quantum Circuits
I They themselves consist in gate networks, which can be of three different kinds:
I Quantum gates, which compute unitary transforms on H2⊗ . . . ⊗ H2.
I Measurement gates, which observe the value of one qubit.
I The wires connecting gates are themselves of two types:
I Quanum channels, which connect quantum gates to other quantum gates or to measurement gates.
I Classic channels, which are the output wires of measurement gates and which control the application of quantum gates.
I Qubits cannot be duplicated.
I Example:
H • •
X
Quantum Circuits
I They themselves consist in gate networks, which can be of three different kinds:
I Quantum gates, which compute unitary transforms on H2⊗ . . . ⊗ H2.
I Measurement gates, which observe the value of one qubit.
I The wires connecting gates are themselves of two types:
I Quanum channels, which connect quantum gates to other quantum gates or to measurement gates.
I Classic channels, which are the output wires of measurement gates and which control the application of quantum gates.
I Qubits cannot be duplicated.
I Example:
H • •
X
Quantum Teleportation
• H •
•
•
Boolean Circuits as Quantum Circuits
I When can a boolean gate be considered a quantum gate?
I How to simulate copying?
I First of all, we need to allow boolean gates to have more than one outputs.
I Restrict to invertible gates.
I Indeed, every unitary transform Q has an inverse!
I Every boolean circuit can then be seen as a quantum circuit.
I Are we loosing anything?
Theorem
Every boolean function can be computed by a quantum circuit.
Boolean Circuits as Quantum Circuits
I When can a boolean gate be considered a quantum gate?
I How to simulate copying?
I First of all, we need to allow boolean gates to have more than one outputs.
I Restrict to invertible gates.
I Indeed, every unitary transform Q has an inverse!
I Every boolean circuit can then be seen as a quantum circuit.
I Are we loosing anything?
Theorem
Every boolean function can be computed by a quantum circuit.
Deutsch-Jozsa Algorithm
/n H⊗n
Uf
H⊗n
H