Introduction to Probabilistic and Quantum Programming

Introduction to Probabilistic and Quantum Programming

Part I

Ugo Dal Lago

BISS 2014, Bertinoro

Organization

I Webpage

I http://www.cs.unibo.it/~dallago/BISS2014/

I Email

I dallago@cs.unibo.it

I Schedule

I Monday, March 3rd, 2014: 11.30-13.30

I Monday, March 3rd, 2014: 17.30-19.30

I Tuesday, March 4th, 2014: 11.30-13.30

I Tuesday, March 4th, 2014: 17.30-18.30

I Wednesday, March 5th, 2014: 15.00-17.00

I Friday, March 7th, 2014: 9.00-11.00

I Friday, March 7th, 2014: 15.00-17.00

Organization

I Three Parts

I Probabilistic and Quantum Computation (this file!);

I A Survey on Probabilistic and Quantum Programming;

I Functional Programming in presence of Probabilistic and Quantum Effects.

I Exam

I There will be no written exam.

I If you need to be credited for this course, you can proceed as follows:

1. Choose one among the papers listen in the course’s webpage, and contact the teacher;

2. Read the paper carefully, trying to understand the details of (a part of) it;

3. Write a self-contained essay (10 to 15 pages) in which you

“paraphrase” what you have read.

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 Vectors: Aⁿ;

I Matrices: B^m×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 R^d;

I In classical physics, the state of a system is uniquely determined.

Example: Particle in R

at a Given Time

(1, 1)

Example: Particle in R

at a Given Time

(1, 1, 0, 1) Position

Momentum

Example: Particle in R

Dynamically

Example: Particle in R

Dynamically

Composing Physical Systems

I If the states of two physical systems live in Rⁿe R^m

(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: Rⁿ× R^m=R^n+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 N, which 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 = {x¹, . . . , xn} ⊆ Rⁿ.

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 N, which 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 = {x¹, . . . , xn} ⊆ Rⁿ.

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 N, which 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 = {x¹, . . . , xn} ⊆ Rⁿ.

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 N, which 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 = {x¹, . . . , xn} ⊆ Rⁿ.

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 N, which 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 = {x¹, . . . , xn} ⊆ Rⁿ.

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 N, which 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 = {x¹, . . . , xn} ⊆ Rⁿ.

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 N, which 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 = {x¹, . . . , xn} ⊆ Rⁿ.

I For the sake of simplicity, let us focus our attention on finite state systems.

Example: Particle in R

, Dynamically

Example: Particle in R

, Dynamically

Probabilistic Systems, Statically

I In classical physics, the state of any system is univocally determined.

I For reasons of abstraction and complexity, one ofter uses a probabilistic representation of states.

I Exmple: a dice.

I The state, at a given time, is described by a function P :S → R such thatP

x∈SP(x) = 1, or by a vector inR^|S|:



 P(x₁)

... P(x_n)



 =



 p₁

... p_n





I This is a mixed state.

Probabilistic Systems, Dynamically

I In any given state x_i, the system can evolve into any state xj 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

, 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 states:

S = {x1, . . . , xn} ⊆ R^m.

I The dynamic evolution of the system is described, compactly, by the matrix M inR^n×n:

M =







p₁₁ p₁₂ · · · p1n

p₂₁ p₂₂ · · · p2n

... ... . .. ... p_n1 p_n2 · · · 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

, Dynamically

3 4

3 4 3

4

3 4 1 4

1 4

1 4 1

4

x

x

x

x

M =









0 0 0 ³₄

3 4 1

4 1 4 0 0 ³₄ 0 0

1

4 0 ³₄ ¹₄









Intermezzo: Linearity

I Vectors in Rⁿ 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 puro state is a function P :S → R such that P(xi) = 1 for a given x_i.

I The system is inxi, without any uncertainty.

I If the matrixM = (p_ij) 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 puro state is a function P :S → R such that P(xi) = 1 for a given x_i.

I The system is inxi, without any uncertainty.

I If the matrixM = (p_ij) 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 puro state is a function P :S → R such that P(xi) = 1 for a given x_i.

I The system is inxi, without any uncertainty.

I If the matrixM = (p_ij) 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 puro state is 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 = (p_ij) 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

x

x

x

M =









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

Another Example

I Suppose given a public-key encryption scheme Π = (GEN , ENC , DEC ) and an adversary A.

I Consider the following experiment:

1. GEN(1ⁿ) is run to obtain keys (pk , sk ).

2. AdversaryA is given pk, and outputs a pair of messages m0, m1of the same length.

3. A bitb is chosen and a ciphertext c is computed as ENC(pk , mb) and given back toA.

4. A outputs a bit b⁰.

5. The output of the experiment is defined to be1 if b⁰= b and0 otherwise.

I If the output is1, the adversay wins.

I Is it possible to design Π in such a way that any adversary can win with probability not (too much) bigger than ¹₂.

Another Example

I Suppose given a public-key encryption scheme Π = (GEN , ENC , DEC ) and an adversary A.

I Consider the following experiment:

1. GEN(1ⁿ) is run to obtain keys (pk , sk ).

2. AdversaryA is given pk, and outputs a pair of messages m0, m1of the same length.

3. A bitb is chosen and a ciphertext c is computed as ENC(pk , mb) and given back toA.

4. A outputs a bit b⁰.

5. The output of the experiment is defined to be1 if b⁰= b and0 otherwise.

I If the output is1, the adversay wins.

I Is it possible to design Π in such a way that any adversary can win with probability not (too much) bigger than ¹₂.

Another Example

I Suppose given a public-key encryption scheme Π = (GEN , ENC , DEC ) and an adversary A.

I Consider the following experiment:

1. GEN(1ⁿ) is run to obtain keys (pk , sk ).

2. AdversaryA is given pk, and outputs a pair of messages m0, m1of the same length.

3. A bitb is chosen and a ciphertext c is computed as ENC(pk , mb) and given back toA.

4. A outputs a bit b⁰.

5. The output of the experiment is defined to be1 if b⁰= b and0 otherwise.

I If the output is1, the adversay wins.

I Is it possible to design Π in such a way that any adversary can win with probability not (too much) bigger than ¹₂.

Another Example

I Suppose given a public-key encryption scheme Π = (GEN , ENC , DEC ) and an adversary A.

I Consider the following experiment:

1. GEN(1ⁿ) is run to obtain keys (pk , sk ).

2. AdversaryA is given pk, and outputs a pair of messages m0, m1of the same length.

3. A bitb is chosen and a ciphertext c is computed as ENC(pk , mb) and given back toA.

4. A outputs a bit b⁰.

5. The output of the experiment is defined to be1 if b⁰= b and0 otherwise.

I If the output is1, the adversay wins.

I Is it possible to design Π in such a way that any adversary can win with probability not (too much) bigger than ¹₂.

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 found 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 found 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 found 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 found 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

I It is a vector in Cⁿ:

x =



 c₁

... c_n





I The following condition must hold:

Xn i=1

||ci||² = 1

I We can write

x = c₁x₁+ . . . + c_nx_n,

where thex_i are always0 except in the ith coordinate, which is1 (x₁, . . . , x_n is the computational base of the system).

I What does x_i represent? It is an observable of the system.

I Every orthonormal base forCⁿ corresponds to one such observable property.

Evolution of a Quantum System H

I The system evolves linearly, thus its dynamics can be described by a matrix:



 d₁

... d_n



 =





a₁₁ · · · a1n

... ... a_n1 · · · ann







 c₁

... c_n





I It must be that Pn

i=1||di||²= 1.

I A necessary and sufficient condition is that Q = (a_ij) must be unitary: Q^∗ = Q⁻¹.

I Q^∗ is the conjugate transpose ofQ. As an example,





a11 · · · a1n

... ... an1 · · · aⁿⁿ





∗

=





a^∗₁₁ · · · a^∗_n1 ... ... a^∗_1n · · · a^∗nn





I The product of two unitary matrices is again unitary.

Measurement in a Quantum System H

I Given a Quantum Systemx = (ci), the quantity||ci||² should not be interpreted as the probability of being in state x_i.

I The only way to observe the state of a quantum system is by way of measurements:

I When measuring the state of a system, it goes fromx = (ci) to each of the statesxj with probability equals to||c^j||².

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!

Composing two Quantum Systems H

and H

I Given two quantum systems with computational bases x₁, . . . , x_n;

y₁, . . . , y_m;

their composition has computational basis (x₁, y₁), . . . , (x_n, y_m).

I Thus, we get the system

H_nm = H_n⊗ Hm.

I Let us indicate the pair(x_i, x_j) by x_i⊗ xj;

Composing two Quantum Systems H

and H

I We can extend this operation to all states of H_n and H_m: Xn

i=1

c_ix_i

!

⊗



 Xm j=1

d_jy_j



 = Xn

i=1

Xm j=1

c_id_jx_i⊗ 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 H_n⊗ Hm is such thatx = y⊗ z, then x is said to be decomposable, and otherwise entangled.

I Given two unitary transforms Q_n, Q_m on H_n and H_m (respectively), we can buildQ_n⊗ Qm. . .

Example: H

I The states of the system are the unitary vectors inC².

I The states of the orthonormal base|x¹i, |x²i 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 H₂ are said to be qubits.

Example: H

⊗ H

I States of the systems are the unitary vectors in C⁴ ∼=C²⊗ C².

I Let us consider two example states inH₂⊗ 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 H₂⊗ Hn which cannot be decomposed as two unitary transforms on H₂ is:

CNOT =







1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0







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

−¹2|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

−¹2|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

−¹2|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ρ : C₁ → 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ρ : C₁ → 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ρ : C₁ → 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ρ : C₁ → 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 ¹₂;

I It must be smaller than a given fixed constant ε, itself smaller than ¹₂.

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 H_n with computational basex1, . . . , xn.

I A unitary transformation Q on H_n⊗ 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 H_n with computational basex1, . . . , xn.

I A unitary transformation Q on H_n⊗ 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 H_n with computational basex1, . . . , xn.

I A unitary transformation Q on H_n⊗ 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 H_n with computational basex1, . . . , xn.

I A unitary transformation Q on H_n⊗ 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.

About Measurements, Again

I Suppose we want to work with the system H_n⊗ Hm. A state of the system can be expressed as:

Xn i=1

Xm j=1

c_ij|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|x^ki ⊗ |yi where x^k is an element of the computational base, whiley is not necessarily one such.

I The probability of reaching|x^ki ⊗ |yi is equal to P(k) =

Xm j=1

||c^kj||².

I The state|x^ki ⊗ |yi can be expressed as follows:

p1 P(k)

Xm j=1

ckj|x^ki|y^ji

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 :Fⁿ→ F^m is computable by a boolean circuit C_f.

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: Fⁿ → F^mvs. 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{Cⁿ}ⁿ∈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: Fⁿ → F^mvs. 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{Cⁿ}ⁿ∈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: Fⁿ → F^mvs. 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{Cⁿ}ⁿ∈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: Fⁿ → F^mvs. 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{Cⁿ}ⁿ∈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⊗ . . . ⊗ H².

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⊗ . . . ⊗ H².

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⊗ . . . ⊗ H².

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⊗ . . . ⊗ H².

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:

I We need to allow boolean gates to have more than one outputs.

I Restrict to invertible gates.

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:

I We need to allow boolean gates to have more than one outputs.

I Restrict to invertible gates.

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

/ⁿ H^⊗n

U_f

H^⊗n

H