Ivan Bardet

Denis Bernard

Yan Pautrat

Passage times, exit times and Dirichlet problems for open quantum walks

We consider open quantum walks on a graph, and consider the random variables defined as the passage time and number of visits to a given point of the graph. We study in particular the probability that the passage time is finite, the expectation of that passage time, and the expectation of the number of visits, and discuss the notion of recurrence for open quantum walks. We also study exit times and exit probabilities from a finite domain, and use them to solve Dirichlet problems and to determine harmonic measures. We consider in particular the case of irreducible open quantum walks. The results we obtain extend those for classical Markov chains.

Introduction

Open quantum walks were defined in [START_REF] Attal | Open quantum random walks[END_REF]. They are extensions of (discretetime) Markov chains, where the process retains some amount of memory, and this memory is encoded by a quantum state. Open quantum walks are a simple model, which has stirred interest because of their various possible applications (see [START_REF] Sinayskiy | Open Quantum Walks: a short introduction[END_REF] and references therein for models based on open quantum walks, and [START_REF] Zhang | Quantum feedback: theory, experiments, and applications[END_REF] on the general topic of control of quantum trajectories) and interesting features and extensions (see [START_REF] Bauer | Open quantum random walks: Bistability on pure states and ballistically induced diffusion[END_REF][START_REF] Bauer | The open quantum Brownian motions[END_REF][START_REF] Pellegrini | Continuous time open quantum random walks and non-Markovian Lindblad master equations[END_REF]). They have therefore given rise to various theoretical studies, investigating e.g. ergodic properties, central limit theorems and large deviations properties (see [START_REF] Attal | Central limit theorems for open quantum random walks and quantum measurement records[END_REF][START_REF] Carbone | Homogeneous open quantum random walks on a lattice[END_REF][START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF][START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF][START_REF] Lardizabal | Open Quantum Random Walks: Ergodicity, Hitting Times, Gambler's Ruin and Potential Theory[END_REF]). The approach of [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF] was to give analogues for open quantum walks of notions usually associated with Markov chains, such as irreducibility and period, and to investigate their consequences. In this article, we continue this program of studying open quantum walks in analogy with Markov chains, and investigate other notions: the probability of visiting a given site in finite time, the expected number of visits, the expected return time, and their relation with the Dirichlet problem. Some of these notions were discussed in e.g. [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF][START_REF] Dhahri | Open Quantum Random Walks and associated Quantum Markov Chains[END_REF], but our study is the first systematic exploration of these concepts and their behavior for irreducible open quantum walks.

The first standard question one may ask about Markov chains treats recurrence problems. Let (x n ) n be a Markov chain on a discrete set V . For any i in V we define

t i = inf{n ≥ 1 | x n = i}, n i = card{n ≥ 1 | x n = i},
The classical results (see e.g. [START_REF] Durrett | Probability: theory and examples[END_REF][START_REF] Norris | Markov chains, volume 2 of Cambridge Series in Statistical and Probabilistic Mathematics[END_REF]) concerning return times (t i ) i∈V and number of visits (n i ) i∈V imply that for any i in V

P i (t i < ∞) = 1 ⇔ E i (n i ) = ∞. (1)
Therefore, this equivalence allows to define the notion of recurrence using either quantity P i (t i < ∞) or E i (n i ). In addition, if the Markov chain is irreducible,

P i (t i < ∞) < 1 for all i ∈ V, or P i (t i < ∞) = 1 for all i ∈ V, (2)
E i (n i ) < ∞ for all i ∈ V, or E i (n i ) = ∞ for all i ∈ V. (3)
Similarly, for an irreducible Markov chain,

E i (t i ) < ∞ for all i ∈ V, or E i (t i ) = ∞ for any i ∈ V. (4)
In addition, if the Markov chain admits an invariant probability measure (π i ) i∈V , then

E i (t i ) = π -1 i < ∞ for any i ∈ V. (5)
The second standard question concerns exit times and exit probabilities. If D is a finite subset of V , we define t ∂D as its exit time

t ∂D = inf{n ≥ 1 | x n ∈ ∂D}
where ∂D is the boundary of D (we give a precise definition later on), and for i ∈ D, j ∈ ∂D define the harmonic measure at i relative to j by

µ D i (j) = P(x t ∂D = j | x 0 = i) (6)
which represents the probability of exiting D through j when starting from i.

It is known that the map i → µ i (j) is harmonic on D for any j ∈ ∂D, and is an important tool in solving Dirichlet problems. In addition, the solution of a Dirichlet problem can be characterized as the minimizer of some functional, related to a Dirichlet form (see [START_REF] Revuz | Markov chains[END_REF]).

In this article we investigate similar relations to (1)-( 5), and study an analogue of Dirichlet problems for open quantum walks. We also look at the notion of harmonic measures for open quantum walks. These measures, as well as the Dirichlet problems for open quantum walks, provide simple examples of non-commutative extensions of standard geometrical structures.

This article is organized as follows: in Section 2 we recall the definitions of open quantum walks and various notions, including irreducibility and harmonicity. In Section 3 we study the relation between return times and number of visits and in particular analogues for OQW of (1), ( 2) and (3), and discuss the literature on the subject of recurrence for open quantum walks. In Section 4 we study the expected values of return times, prove an analogue of (4), and relate these expected values to invariant measures, similar to [START_REF] Attal | Open quantum random walks[END_REF]. In Section 5 we describe various examples that serve in particular as counterexamples to various possible conjectures. In Section 6 we define Dirichlet problems for open quantum walks and characterize their solutions. In Section 7 we discuss extensions of various results to reducible open quantum walks. In Section 8 we introduce Dirichlet forms for open quantum walks and use them to characterize solutions of Dirichlet problems. In every section, a non-optimal but nevertheless satisfactory result is given early in the introductory part, and the intermediate results necessary for the proof (most of which have weaker assumptions than necessary for the results stated earlier) are detailed in the rest of the section. The proofs are given in the Appendix, unless they contain elements necessary to the comprehension of the text.

Acknowledgements. All three authors acknowledge the support of ANR project StoQ "Stochastic Methods in Quantum Mechanics", n • ANR-14-CE25-0003. They also want to thank Stéphane Attal for discussions at an early stage of this project.

Open quantum walks: definitions and notation

We start this section with a short presentation of open quantum walks and the associated notion of irreducibility. We follow the notation of [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF] and refer the reader to that article for more details. We consider a Hilbert space H of the form H = i∈V h i where V is a countable set of vertices, and each h i is a separable Hilbert space. We view H as describing the degrees of freedom of a particle constrained to move on V : the "V -component" describes the spatial degrees of freedom (the position of the particle) while h i describes the internal degrees of freedom of the particle, when it is located at site i ∈ V .

For book-keeping purposes we denote the subspace h i of H by h i ⊗|i . Therefore, whenever a vector ϕ ∈ H belongs to the subspace h i , we will denote it by ϕ⊗|i and drop the (implicit) assumption that ϕ ∈ h i . Similarly, when an operator A on H satisfies h ⊥ j ⊂ Ker A and Ran A ⊂ h i , we denote it by A = L i,j ⊗|i j| where L i,j is viewed as an operator from h j to h i . This will allow us to use the same notation as in e.g. [START_REF] Attal | Central limit theorems for open quantum random walks and quantum measurement records[END_REF][START_REF] Attal | Open quantum random walks[END_REF][START_REF] Konno | Limit Theorems for Open Quantum Random Walks[END_REF][START_REF] Lardizabal | On a class of quantum channels, open random walks and recurrence[END_REF][START_REF] Pellegrini | Continuous time open quantum random walks and non-Markovian Lindblad master equations[END_REF]. Consistently with this notation, for W a subset of V we denote

H W = i∈W h i ⊗ |i .
and Id W = i∈W Id hi ⊗ |i i|. We identify H W (respectively B(H W )) with a subspace of H (respectively B(H)

).

An open quantum walk (or OQW) is a map on the Banach space I 1 (H) of trace-class operators on H, given by

M : τ → i,j∈V A i,j τ A * i,j (7)
where, for any i, j in V , the operator A i,j is of the form L i,j ⊗ |i j| and the operators L i,j satisfy

∀j ∈ V, i∈V L * i,j L i,j = Id hj , (8)
(this series is meant in the strong convergence sense). The operators L i,j represent the effect of a transition from site j to site i, encoding both the probability of that transition and its effect on the internal degrees of freedom. Equation ( 8) therefore encodes the "stochasticity" of the transitions L i,j , and immediately implies that Tr M(τ ) = Tr τ for any τ in I 1 (H).

Recall that an operator X on H is called positive (respectively definite positive) if ϕ, Xϕ ≥ 0 (respectively ϕ, Xϕ > 0) for any ϕ ∈ H \ {0}. We define a state on H to be a positive operator in I 1 (H) with trace one, and call a state faithful if it is definite positive. We denote the set of states on H (respectively h i ) by S(H) (respectively S(h i )). The map defined by [START_REF] Bauer | The open quantum Brownian motions[END_REF] maps a state to a state. It actually has the stronger property of being trace-preserving and completely positive, i.e. for any n ∈ N, M ⊗ Id B(C n ) acting on I 1 (H) ⊗ B(C n ) is positive; such an operator is commonly called a quantum channel, see e.g. [START_REF] Wolf | Quantum channels & operations: Guided tour[END_REF]. In addition, the topological dual I 1 (H) * can be identified with B(H) through the linear form (τ, X) → Tr(τ X), so that the dual M * of M acts on B(H). By the Russo-Dye Theorem (see [START_REF] Russo | A note on unitary operators in C * -algebras[END_REF]), we have the relation1 M * = M * (Id H ) , so that relation [START_REF] Brezis | Functional analysis, Sobolev spaces and partial differential equations[END_REF] implies that M = 1 as an operator on I 1 (H). A crucial remark is that the range of M is a subset of the class of "diagonal" states, i.e. states of the form

i∈V τ (i) ⊗ |i i|, (9)
where each τ (i) is in I 1 (h i ). In addition, even if τ is not diagonal, i.e. is of the form τ = i,j∈V τ (i, j) ⊗ |i j|, then M(τ ) depends only on its diagonal elements τ (i, i). Therefore, from now on, we will only consider states of the form [START_REF] Carbone | Homogeneous open quantum random walks on a lattice[END_REF]. The action of M on such states takes the form

M(τ ) = i∈V j∈V L i,j τ (j) L * i,j ⊗ |i i|. (10)
As argued in [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF] (see in particular section 8), a natural extension of the above framework is to encode the transition from site j to site i not by τ (j) → L i,j τ (j) L * i,j , but by a more general, completely positive map τ (j) → Φ i,j τ (j) . We will not discuss these generalized open quantum walks any further.

We now describe a family of classical random processes associated with M. Let Ω = V N and for any state ρ on H of the form [START_REF] Carbone | Homogeneous open quantum random walks on a lattice[END_REF], define on Ω a probability by defining its restrictions to V n+1 for n ≥ 0:

P τ (i 0 , . . . , i n ) = Tr L in,in-1 . . . L i1,i0 τ (i 0 ) L * i1,i0 . . . L * in,in-1 . (11)
Relation 8 ensures the consistency of these restrictions, and the Daniell-Kolmogorov extension Theorem ensures that P τ defines a unique probability on Ω. We will mostly consider initial states of the form ρ ⊗ |i i| with ρ ∈ S(h i ), i.e. with initial position i and initial internal state ρ; for notational simplicity, the corresponding probability P τ will then be denoted by P i,ρ . We will consider two random processes (x n ) n and (ρ n ) n defined on ω = (i 0 , i 1 , . . .) ∈ Ω by

x n (ω) = i n , ρ n (ω) = L in,in-1 . . . L i1,i0 τ (i 0 ) L * i1,i0 . . . L * in,in-1 Tr L in,in-1 . . . L i1,i0 τ (i 0 ) L * i1,i0 . . . L * in,in-1 . ( 12
)
Note that the variable ρ n is a state on h xn . Besides, the process (x n , ρ n ) n is Markov, corresponding to the transitions defined loosely as follows: conditionally on (x n = j, ρ n = ρ), one has

(x n+1 , ρ n+1 ) = (i, L i,j ρL * i,j Tr L i,j ρ L * i,j
) with probability Tr( L i,j ρ L * i,j ). [START_REF] Cipriani | Dirichlet forms on noncommutative spaces[END_REF] Remark that (x n ) n or (ρ n ) n considered separately are not Markov processes. Note that open quantum walks include classical Markov chains. More precisely, consider a Markov chain (M n ) n on the vertex set V , with probability t i,j of transition from j to i and initial distribution (p i ) i∈V . Define an open quantum walk M with h i ≡ C and

L i,j = √ t i,j . If the initial state is τ = i∈V p i ⊗ |i i| then M(τ ) is of the form M(τ ) = i∈V ( j∈V t i,j p j ) ⊗ |i i|.
Therefore, x 0 has the same law as M 0 and x 1 has the same law as M 1 , etc. This open quantum walk will be called the minimal dilation of the Markov chain (because it is an OQW implementation of the Markov chain with minimal spaces h i , see [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF] for more details).

We now introduce the notion of irreducibility for open quantum walks. For i, j in V we call a path from i to j any finite sequence i 0 , . . . , i ℓ in V with ℓ ≥ 1, such that i 0 = i and i ℓ = j. Such a path is said to be of length ℓ, and we denote the length of a path π by ℓ(π). We denote by P ℓ (i, j) the set of paths from i to j of length ℓ, and by

P(i, j) = ∪ ℓ≥1 P ℓ (i, j).
For a fixed OQW M and π = (i 0 , . . . , i ℓ ) in P(i, j) we denote by L π the operator from h i to h j defined by:

L π = L i ℓ ,i ℓ-1 . . . L i1,i0 = L j,i ℓ-1 . . . L i1,i . Definition 2.
1. An open quantum random walk M as above is irreducible if for any i, j in V and for any ϕ in h i \ {0}, the set

{L π ϕ | π ∈ P(i, j)} ( 14
)
is total in h j .
This definition (which is a special case of Davies irreducibility as defined in [START_REF] Davies | Quantum stochastic processes[END_REF]) and its consequences were introduced in [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF]. The main consequence is that for M an irreducible open quantum walk, the set of solutions of M(τ ) = τ is a space of dimension at most one, and one solution is a faithful. Remark 2.2. There was a slight ambiguity in the definition of irreducibility as given in [START_REF] Carbone | Homogeneous open quantum random walks on a lattice[END_REF][START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF], where the paths "of length zero" π = {i} with associated transition L {i} = Id hi was allowed in [START_REF] Davies | Quantum stochastic processes[END_REF]. In other words, irreducibility was defined by the fact that for any i, j in V and ϕ in h i \ {0}, the set

{ϕ} ∪ {L π ϕ | π ∈ P(i, j)} (15)
(with π of length at least one) is total. It is easy, however, to see that this second definition is equivalent to Definition 2.1. Therefore, even though we define irreducibility by Definition 2.1, we can still apply the results of [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF].

The following class of open quantum walks will be relevant, and in particular will have properties closer to those of (classical) Markov chains. Definition 2.3. We say that an open quantum walk M is semifinite if for any i in V , dim h i < ∞. We say that it is finite if it is semifinite and V is a finite set.

Non-semifinite open quantum walks, i.e. those that can have an infinite number of degrees of freedom at a given site i ∈ V , can exhibit local degeneracies that will make them less interesting to us.

One of the topics of interest in the present paper is that of quantum harmonic operators:

Definition 2.4. An operator A = i∈V A i ⊗|i i| with A i ∈ B(h i ) for each i ∈ V is called quantum harmonic if it satisfies M * (A) = A, or equivalently if for any j ∈ V, one has A j = i∈V L * i,j A i L i,j .
Remark that any operator λId H , λ in C, is quantum harmonic. In the case of a minimal dilation of a classical Markov chain, this definition is equivalent to the classical definition of harmonicity. An immediate property of quantum harmonic operators is the following: Lemma 2.5. Let M be an open quantum walk and A a quantum harmonic operator for M. Then for any initial (x 0 , ρ 0 ), the Markov chain (x n , ρ n ) n , with transition probabilities given by Equation [START_REF] Cipriani | Dirichlet forms on noncommutative spaces[END_REF], is such that m n = Tr(ρ n A xn ) n is a P x0,ρ0 -martingale.

Before we move on to the next section, it will be convenient to introduce some additional notation for specific paths. For any i and j in V , and for W a subset of V , we define P W (i, j) to be the set of paths in P(i, j) that remain in W except possibly for their start-and endpoint. More precisely: (i 0 , . . . , i ℓ ) ∈ P W ⇔ (i 0 , . . . , i ℓ ) ∈ P with i 1 , . . . , i ℓ-1 ∈ W.

We denote for any ℓ ≥ 1 by e.g. P W ℓ the subset of P W consisting of paths of length ℓ, etc.

Passage times and number of visits

In this section we consider the passage times t j to a given point j ∈ V and the number of visits n j to that point. We define

t j = inf{n ≥ 1 | x n = j}, n j = card{n ≥ 1 | x n = j},
Recall the standard results (1), ( 2), (3) in the case where the OQW is a minimal dilation of a Markov chain. The equivalence (1) follows from the markovianity of the process (x n ) n . However, in the general OQW case, the process (x n ) n alone is not markovian and at least some of the above relations will fail. Indeed, Example 5.1 below with i = 0 and ρ = |e

1 e 1 |, |e 2 e 2 | is such that P i,ρ (t i < ∞) < 1 and E i,ρ (n i ) = ∞,
showing that (1) does not hold. Example 5.2, which displays an irreducible OQW, is such that

P i,ρ (t i < ∞) = 1 and E i,ρ (t i ) < ∞ for p < 1/2 and i = 0, ρ = |e 2 e 2 |.
Consequently it shows that (1) may not even hold for irreducible OQWs.

We therefore have to work some more in order to obtain nontrivial connections between P i (t i < ∞) and E i (n i ) and then to obtain universality results in the irreducible case. This will be done in the next two subsections. As a corollary of our investigation, a clear conclusion can be drawn for semifinite irreducible open quantum walks, which we give in Theorem 3.1 below. Its proof, however, relies on all results given in those two subsections. We will finish this section with a discussion of the notion of recurrence for open quantum random walks.

Theorem 3.1. Let M be a semifinite irreducible open quantum walk. We are in one (and only one) of the following situations:

1. for any i, j in V, ρ in S(h i ), one has E i,ρ (n j ) = ∞ and P i,ρ (t j < ∞) = 1;

2. for any i, j in V, ρ in S(h i ), one has E i,ρ (n j ) < ∞ and P i,ρ (t j < ∞) < 1;

3. for any i, j in V, ρ in S(h i ), one has E i,ρ (n j ) < ∞, but there exist i in V , ρ, ρ ′ in S(h i ) (ρ necessarily non-faithful) with P i,ρ (t i < ∞) = 1 and P i,ρ ′ (t i < ∞) < 1.

Remark 3.2.

Passage time vs. number of visits: general results

In this section we investigate the quantities P i,ρ (t j < ∞) and E i,ρ (n j ), and the relation betwen them. The proofs relating the two quantities P i,ρ (t j < ∞) and E i,ρ (n j ) in the classical case are based on the fact that any path π ∈ P(j, j) can be written uniquely as a concatenation of paths π ∈ P V \{j} (j, j). We will use this simple idea in the present case. This is summarized in Proposition 3.3: Proposition 3.3. There exists a family (P j,i ) i,j∈V , where P j,i is a completely positive linear contraction from I 1 (h i ) to I 1 (h j ), such that for any i, j in V and any ρ in S(h i ),

P i,ρ (t j < ∞) = Tr P j,i (ρ) , E i,ρ (n j ) = k≥0 Tr P k j,j • P j,i (ρ) ,
(where the second expression is possibly ∞).

Remark 3.4.

1. The map P j,i can be expressed by:

P j,i (ρ) = π∈P V \{j} (i,j) L π ρL * π
(see the proof of Proposition 3.3 to see that this expression is meaningful).

2. An immediate consequence of Proposition 3.3 is that

P j,i = sup ρ∈S(hi) P i,ρ (t j < ∞),
where the norm is the operator norm on I 1 (H).

It is immediate from the proof that

E i,ρ (ρ tj | t j < ∞) = P j,i (ρ) Tr P j,i (ρ) . ( 16
)
We have the following corollary:

Corollary 3.5. Let i, j be in V .

1. One has P i,ρ (t j < ∞) = 1 if and only if P * j,i (Id hj ) has the form

Id 0 0 * in the decomposition h i = Ran ρ ⊕ (Ran ρ) ⊥ . In particular, if there exists a faithful ρ in S(h i ) such that P i,ρ (t j < ∞) = 1, then P i,ρ ′ (t j < ∞) = 1 for any ρ ′ ∈ S(h i ).

If there exists a faithful ρ in S(h

i ) such that P i,ρ (t i < ∞) = 1, then one has E i,ρ ′ (n i ) = ∞ for any ρ ′ ∈ S(h i ). 3. If there exists a faithful ρ in S(h i ) such that E i,ρ (n j ) < ∞ and h i is finite-dimensional, then one has E i,ρ ′ (n j ) < ∞ for any ρ ′ in S(h i ). 4. If E i,ρ (n j ) < ∞ for every ρ in S(h i ),
then there exists a completely positive linear bounded map N j,i from

I 1 (h i ) to I 1 (h j ) such that E i,ρ (n j ) = Tr N j,i (ρ), ( 17
)
and one has the expression

N j,i (ρ) = π∈P(i,j) L π ρL * π . (18)
Remark 3.6.

1. The second part of the first statement, and the second statement, do not hold without the faithfulness assumption, as shown by Examples 5.1 and 5.2.

2. Since P i,j is a completely positive contraction, one has P * j,i (Id hj ) ≤ Id hi . In addition, by the Russo-Dye Theorem [START_REF] Russo | A note on unitary operators in C * -algebras[END_REF], P * j,j = P * j,j (Id hj ) so that if P * j,j (Id hj ) < 1, then E i,ρ (n j ) < ∞ for every ρ in S(h i ) and:

N j,i = (Id -P j,j ) -1 • P j,i .
3. Again, under the assumptions of point 4, an immediate consequence is

N j,i = sup ρ∈S(hi) E i,ρ (n j ),
and

N (α) j,i introduced in Section B satisfies N j,i = lim α→1 N (α) j,i . 4. If E i,|ϕ ϕ| (n j ) < ∞ for a total set of unit vectors ϕ of h i , then N j,i can
still be constructed as a densely defined (a priori unbounded) selfadjoint operator, thanks to the representation theory for closed quadratic forms (see e.g. Theorem VIII.3.13a in [START_REF] Kato | Perturbation Theory for Linear Operators[END_REF]).

We have an easy partial converse to the third statement of Corollary 3.5 (a stronger result will be given under the additional assumption of irreducibility). Proposition 3.7. Let i be in V and assume that h i is finite-dimensional. If

P i,ρ (t i < ∞) < 1 for every ρ in S(h i ), then E i,ρ ′ (n i ) < ∞ for every ρ ′ in S(h i ).
Remark 3.8. Proposition 3.7 implies in particular that, if h i is finite-dimensional and there exists ρ in S(h i ) such that E i,ρ (n i ) = ∞, then there exists ρ ′ in S(h i ) such that P i,ρ ′ (t i < ∞) = 1. Note that this does not necessarily hold with ρ ′ = ρ, as Examples 5.1 and 5.5 show.

The irreducible case

We now turn to the "universality" properties analogous to (2) and (3) that are expected in the irreducible case. We will prove the following: Proposition 3.9. Let M be an irreducible open quantum walk and let j be in V . We are in one (and only one) of the following situations:

1. for every i in V there exists a domain d n j,i , dense in h i , such that the quantity E i,ρ (n j ) is finite for any ρ that has finite range contained in d n j,i , 2. for every i in V , for any ρ in S(h i ), the quantity E i,ρ (n j ) is infinite.

For semifinite OQW, the picture is simpler. We have the following corollary:

Corollary 3.10. Let M be a semifinite irreducible open quantum walk. We are in one (and only one) of the following situations:

1. the quantity E i,ρ (n j ) is finite for any i, j in V and any ρ in S(h i ), 2. the quantity E i,ρ (n j ) is infinite for any i, j in V and any ρ in S(h i ).

Remark 3.11.

1. Example 5.1 shows that the above statements do not hold without the irreducibility assumption.

2. Example 5.3 shows that any irreducible open quantum walk that admits an invariant state (and in particular a finite OQW) is in case 2 of Corollary 3.10.

The next proposition is the last ingredient to prove Theorem 3.1.

Proposition 3.12. Let M be an irreducible open quantum walk. Assume that there exists i, j in

V with dim h i < ∞, dim h j < ∞ and E i,ρ (n j ) = ∞ for some ρ in S(h i ). Then P j,ρ ′ (t j < ∞) = 1 for every ρ ′ in S(h j ).
The proof of Theorem 3.1 follows immediately from Corollary 3.5, Proposition 3.7, Corollary 3.10 and Proposition 3.12.

Notions of recurrence for open quantum walks

In view of Corollary 3.10, we propose the following terminology: In other words, our classification depends on the quantity E i,ρ (n i ) being finite or infinite. Thanks to Corollary 3.10, for a semifinite irreducible open quantum walk this quantity is universal in the sense that it is either finite for all i and ρ, or infinite for all i and ρ. We now compare this with existing definitions of recurrence for open quantum walks and related objects.

First of all, if the open quantum walk M is the minimal dilation of a classical Markov chain, then M is recurrent in our sense if and only if the Markov chain is recurrent in the classical sense.

Fagnola and Rebolledo defined in [START_REF] Fagnola | Transience and recurrence of quantum Markov semigroups[END_REF] a notion of recurrence for (continuoustime) quantum dynamical semigroups. When applied to the (discrete-time) quantum dynamical semigroup (M n ) n , this definition of recurrence is that for any operator A of B(H) that satisfies ϕ, Aϕ > 0 for any ϕ ∈ H \ {0}, the set

D(U(A)) = ϕ = i∈V ϕ i ⊗ |i s.t. k≥0 ϕ, (M * ) k (A) ϕ < ∞ .
equals {0}. We call this notion FR-recurrence. Our definition of a recurrent OQW, as can be seen from Section B, is equivalent to the fact that for any j ∈ V , D(U(A j )) = {0} for A j = Id hj ⊗ |j j|. It is clear that if the OQW is FR-recurrent, then it is recurrent in our sense. If the OQW is not FRrecurrent, then there exists A as above such that k≥0 ϕ, (M * ) k (A) ϕ < ∞, and if the OQW is semifinite, then for any j in V there exists λ j > 0 such that λ j Id hj ⊗ |j j| ≤ A and the OQW is not recurrent. Therefore, for semifinite OQWs, our notion of recurrence and FR-recurrence are equivalent.

A series of results investigating recurrence of open quantum walks can be found in [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF][START_REF] Lardizabal | On a class of quantum channels, open random walks and recurrence[END_REF][START_REF] Lardizabal | Open Quantum Random Walks: Ergodicity, Hitting Times, Gambler's Ruin and Potential Theory[END_REF]. In particular, in [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF][START_REF] Lardizabal | On a class of quantum channels, open random walks and recurrence[END_REF][START_REF] Lardizabal | Open Quantum Random Walks: Ergodicity, Hitting Times, Gambler's Ruin and Potential Theory[END_REF], a site i ∈ V is called (LS)recurrent if (in our terms) one has P i,ρ (t i < ∞) = 1 for any ρ in S(h i ). The OQW is called (LS)-site-recurrent if every site i in V is LS-recurrent. In other words, LS-recurrence classifies sites depending on the quantity inf ρ∈S(hi)

P i,ρ (t i < ∞) (19)
being equal to 1 or not. Corollary 3.10 shows that, for a semifinite irreducible open quantum walk, inf ρ∈S(hi) P i,ρ (t i < ∞) = 1 for some i if and only if it is true for all i (a fact which is not proved in [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF][START_REF] Lardizabal | On a class of quantum channels, open random walks and recurrence[END_REF][START_REF] Lardizabal | Open Quantum Random Walks: Ergodicity, Hitting Times, Gambler's Ruin and Potential Theory[END_REF]), and also that this is equivalent with recurrence in the sense of Definition 3.13. Therefore, an irreducible semifinite OQW is LS-site-recurrent if and only if it is recurrent in our sense. Without the irreducibility assumption, point 2 of Corollary 3.5 shows that if i is LS-recurrent then E i,ρ (n i ) = ∞ for any ρ in S(h i ); the converse does not hold, as shown by Example 5.4. Note, however, that the quantity E i,ρ (n i ) has the advantage of being universal in i and ρ, in the sense that (for a semifinite irreducible OQW) it is either finite for every i and ρ, or infinite for every i and ρ. This is not true of P i,ρ (t i < ∞) = 1, as Examples 5.2 and 5.5 show. The reason can be traced back to the fact that the set of "diagonal" ϕ = i∈V ϕ i ⊗ |i such that P |ϕ ϕ| (t j < ∞) = 1, even though stable by any L π ⊗ |j i| with π ∈ P(i, j), is not a vector space, and therefore cannot be an enclosure (see the proof of Proposition 3.9 in Section B).

Recently, Dhahri and Mukhamedov discussed a notion of recurrence in [START_REF] Dhahri | Open Quantum Random Walks and associated Quantum Markov Chains[END_REF]. That notion actually concerns quantum Markov chains (objects that originate in [START_REF] Accardi | The noncommutative Markov property[END_REF][START_REF] Accardi | Markovian cocycles[END_REF]), and was defined in [START_REF] Accardi | Stopping times for quantum Markov chains[END_REF]. The connection with open quantum walks is established by associating a quantum Markov chain to an open quantum walk. This can be done, however, in different ways, and the property of recurrence depends on the choice of the associated quantum Markov chain. In addition, it is not clear what this notion of recurrence has to do with the properties of the random variables (x n ) n . A major setback, making the associated quantum Markov chains non-canonical, is that they are constructed over the algebra B( i∈V h i )

⊗N ; a more direct connection could probably be obtained, at least when h i ≡ h, by a construction over B(h) ⊗ B(C V ) ⊗N , as can be done using the theory of finitely correlated states (see [START_REF] Fannes | Finitely correlated states on quantum spin chains[END_REF]) which extends that of quantum Markov chains.

Last, remark that, inspired by [START_REF] Grünbaum | Recurrence for discrete time unitary evolutions[END_REF], the authors of [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF] discuss an alternate notion of recurrence to a site i ∈ V . In that new notion, physically speaking, the observer does not at every time n measure the position x n of the particle, but measures only whether the particle has returned to i or not. Mathematically, this amounts to considering the probability space defined by Ω = {0, 1} N , and probability

Pi,ρ (ĩ 1 , . . . , ĩn ) = Tr Φ ĩn,ĩn-1 • . . . • Φ ĩ1,1 (ρ ⊗ |i i|)
where we have, for τ a state on H,

Φ 0,0 (τ ) = A i,i τ A * i,i Φ 0,1 (τ ) = j =i A i,j τ A * i,j Φ 1,0 (τ ) = j =i A j,i τ A * j,i Φ 1,1 (τ ) = j,k =i A j,k τ A * j,k
The new notion of recurrence is then related to the first time ti ≥ 1 for which the process defined by xn (ω) = ĩn takes the value 1. It is easy to verify, however, that this ti has the same law under Pi,ρ as t i under P i,ρ , so that this alternate notion of recurrence is identical to LS-recurrence, as was noted in [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF].

Expectation of return times

We now turn to results analogous to (4). Our first statement is a representation result.

Proposition 4.1. For any i, j in V and ρ in S(h i ), we have

E i,ρ (t j ) =    π∈P V \{j} (i,j) ℓ(π) Tr L π ρL * π if P i,ρ (t j < ∞) = 1, +∞ if P i,ρ (t j < ∞) < 1. ( 20
)
If E i,ρ (t j ) < ∞ for every ρ ∈ S(h i ), then there exists a bounded operator T j,i from I 1 (h i ) to I 1 (h j ) such that E i,ρ (t j ) = Tr T j,i (ρ). ( 21
)
Remark 4.2.

1. In the case where E i,ρ (t j ) < ∞ for every ρ ∈ S(h i ) we have the expression

T j,i (ρ) = π∈P V \{j} (i,j) ℓ(π) L π ρL * π 2.
We have in addition the identity (with both sides possibly ∞).

E i,ρ (t i ) = d dα Tr P (α) i,i (ρ)| α=1 .
The operators P (α)

i,i are defined in Section B. Our first relevant theorem is a universality result in the irreducible case: Theorem 4.3. Let M be a semifinite irreducible open quantum walk. We are in one (and only one) of the following situations:

1. for any i in V and ρ in S(h i ), one has E i,ρ (t i ) < ∞, 2. for any i in V and ρ in S(h i ), one has E i,ρ (t i ) = ∞.
Our proof uses the following intermediate universality result, similar to Proposition 3.9 and which can be useful in a wider setting: Proposition 4.4. Let M be an irreducible open quantum walk and let j be in V . We are in one (and only one) of the following situations:

1. for every i in V , there exists a domain d t j,i , dense in h i , such that the quantity E i,ρ (t j ) is finite for any ρ in S(h i ) that has finite range contained in d t j,i ; 2. for every i in V and ρ in S(h i ), the quantity E i,ρ (t j ) is finite.

Our second result relates the invariant state with the expectation of return times. To state it, for j ∈ V , we define by induction for k ∈ N the k-th return time t

(k) j = inf{n > t (k-1) j | x n = j}.
Theorem 4.5. Let M be a semifinite irreducible open quantum walk with an invariant state τ inv = i∈V τ inv (i) ⊗ |i i|. Then we are in situation 1 of Theorem 4.3, and for any i, j in V and ρ in S(h i ), the sequence (t (k) j /k) k converges, with respect to P i,ρ , both almost-surely and in the L 1 sense, to

E i, τ inv (i) Tr τ inv (i) (t i ) = Tr τ inv (i) -1 . ( 22
)
The proof is based on the Kümmerer-Maassen ergodic Theorem and Birkhoff's ergodic Theorem. Note that Theorem 1.6 in [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF] shows a result of the same type, but with less explicit assumptions.

L 1,0 = 1 0 0 0 L 2,0 = 0 0 0 1 L 0,1 = 1 0 0 1 L 2,2 = 1 0 0 1 ,
all other transitions being zero. This OQW is obviously not irreducible. Denote by e 1 , e 2 the canonical basis of C 2 . For ρ = 1r s s r (with r ∈ [0, 1] and |s| 2 ≤ r(1r), so that r = 1 if and only if ρ = |e 2 e 2 |) one has P 0,ρ (t 0 < ∞) = 1r, and E 0,ρ (n 0 ) = 0 if r = 1, and ∞ otherwise. One therefore has

P 0,ρ (t 0 < ∞) = 1, E 0,ρ (n 0 ) = ∞, E 0,ρ (t 0 ) = 2 for ρ = |e 1 e 1 |; P 0,ρ (t 0 < ∞) = 0, E 0,ρ (n 0 ) = 0, E 0,ρ (t 0 ) = ∞ for ρ = |e 2 e 2 |; P 0,ρ (t 0 < ∞) ∈]0, 1[, E 0,ρ (n 0 ) = ∞, E 0,ρ (t 0 ) = ∞ otherwise.
In this case, it is easy to compute the operator P 0,0 :

P 0,0 (ρ) = 1 0 0 0 ρ 1 0 0 0 .
Therefore, P * k 0,0 (Id h0 ) = 1 0 0 0 for any k ≥ 1, so that loosely speaking, one has k≥0 P * k 0,0 (Id h0 ) = ∞ 0 0 0 , consistently with Proposition 3.3.

L 0,0 = 0 1 0 0 L 1,0 = 1 0 L 0,1 = p/2 1 1
and L i,i+1 = √ p, L i+1,i = √ q for i ≥ 1, with p + q = 1 (all other transitions being zero). This OQW is semifinite and irreducible, independently of the value of p. However, it is a simple exercise to see that, depending on the value of p, one has different behaviors for P 0,ρ (t 0 < ∞) and E 0,ρ (n 0 ): defining for p ≥ 1/2 the quantity λ = 8p 3 -8p 2 +6p-1 4p(2p-1)

∈ [0, ∞], one has

• for p ≥ 1/2 one has P 0,ρ (t 0 < ∞) = 1 ∀ρ ∈ S(h i ) E 0,ρ (n 0 ) = ∞ ∀ρ ∈ S(h i ); E 0,ρ (t 0 ) = r + 2λ(1 -r) for ρ = 1 -r s s r .
• for p < 1/2 one has

P 0,ρ (t 0 < ∞) = 1 and E 0,ρ (t 0 ) = 1 if ρ = |e 2 e 2 | P 0,ρ (t 0 < ∞) < 1 and E 0,ρ (t 0 ) = ∞ if ρ = |e 2 e 2 |, E 0,ρ (n 0 ) < ∞ ∀ρ ∈ S(h i ).
Here again it is easy to compute the operator P 0,0 : for any ρ in I 1 (h 0 ) we have

P 0,0 (ρ) = 0 1 0 0 ρ 0 0 1 0 + 1 2 inf(p/q, 1) 1 0 1 0 ρ 1 1 0 0 .
In particular, for p ≥ 1/2, one has P * k 0,0 (Id h0 ) = Id h0 , and for p < 1/2 one has P * k 0,0 (Id h0 ) = u k+1 0 0 u k with u k → 0 exponentially fast, so that P * k 0,0 (Id h0 ) is summable. This is consistent with Corollary 3.5. In addition, for p ≥ 1/2 one has

T 0,0 (ρ) = 0 1 0 0 ρ 0 0 1 0 + λ 1 0 1 0 ρ 1 1 0 0 . Example 5.3.
In the case of an irreducible open quantum walk which admits a faithful invariant state (for example a finite irreducible open quantum walk), the Kümmerer-Maassen Theorem (proved originally in [START_REF] Kümmerer | A pathwise ergodic theorem for quantum trajectories[END_REF], see [START_REF] Lim | Frontières de Poisson d'opération quantiques et trajectoires quantiques[END_REF] for an infinitedimensional extension and [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF] for an application to the case of open quantum walks) immediately implies that, for any initial position i in V and any state ρ in S(h i ), any point j is almost-surely visited infinitely often:

P i,ρ (n j = ∞) = 1.
A fortiori, one has P i,ρ (t j < ∞) = 1 and E i,ρ (n j ) = ∞, and therefore the OQW is always recurrent. This is the same as in the classical case, where an irreducible Markov chain on a finite set is always recurrent.

L 0,0 = 1, L 0,1 = 1/2 0 L 2,1 = √ 3/2 0 0 1 L 1,2 = 0 0 0 1 L 3,2 = 1 0 0 0 L 2,3 = 0 1 1 0 ,
all other transitions L i,j being zero. One checks by examination that, starting from i = 1 and ρ = 1r s s r : with probability (1r)/2 the first step goes to 0 and then the walk stays there and, with probability (1 + r)/2 the first step goes to 2 and then, after a finite number of steps, goes back and forth between 1 and 2. Therefore, for any ρ, one has

P 1,ρ (t 0 < ∞) = (1+r)/2 but E 1,ρ (n 0 ) = ∞.
Again it is easy to compute P 1,1 :

P 1,1 (ρ) = 0 0 0 1 ρ 0 0 0 1 + 0 0 √ 3/2 0 ρ 0 √ 3/2 0 0 . One then has P * k 1,1 (Id h0 ) = 3/4 0 0 1 , so that loosely speaking, k P * k 1,1 (Id h0 ) = ∞ 0 0 ∞
, consistently with Corollary 3.5.

Example 5.5. We consider now the case of (space) homogeneous nearestneighbor random walks on V = Z with h i ≡ h = C 2 for all i ∈ Z. This OQW is entirely determined by two operators L + and L -on C 2 satisfying L * + L + + L * -L -= Id h . We call such an open quantum walk a (Z, C 2 )-simple OQW. It is proven in [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF] that:

1. if Sp L * + L + = Sp L * -L -= {1/2} then P i,ρ (t i < ∞) = 1
for any i and ρ, 2. if P i,ρ (t i < ∞) = 1 for any i and ρ with L + , L -normal, then Sp L * + L + = Sp L * -L -= {1/2}. With the tools developed in this section, we can recover the first point and make the second more precise. First, if Sp

L * + L + = Sp L * -L -= {1/2} then P * i,i (Id h ) = π∈P V \{i} (i,i) 1 2
) ℓ(π) Id h which, by the results on (classical) simple random walks, is just Id h , and by Corollary 3.5, P i,ρ (t i < ∞) = 1 for any ρ. Second, assume that L + and L -are normal, and consider a diagonal basis for L * + L + (and therefore for L * -L -). In this basis, one has

L * + L + = p 1 0 0 p 2 L * -L -= q 1 0 0 q 2 (23) with p k + q k = 1, k = 1, 2.
It is then easy to show that if a path π is made of n + (π) "up" steps, and n -(π) "down" steps, then

L * π L π = (L * + L + ) n+(π) (L * -L -) n-(π) = p n+(π) 1 q n-(π) 1 0 0 p n+(π) 2 q n-(π) 2
, and using again standard results on simple random walks we have

P * 0,0 (Id h ) = inf(2p 1 , 2q 1 ) 0 0 inf(2p 2 , 2q 2 ) .
Therefore, if L + and L -are normal, then:

• if p 1 = p 2 = 1/2, then P i,ρ (t i < ∞) = 1 for any i and ρ, and therefore

E i,ρ (n i ) = ∞;
• if p 1 and p 2 are both = 1/2, then P i,ρ (t i < ∞) < 1 for any i and ρ, and therefore E i,ρ (n i ) < ∞;

• if e.g. p 1 = 1/2 and p 2 = 1/2 then P i,ρ (t i < ∞) = 1 for ρ = |e 1 e 1 | and < 1 otherwise. If furthermore the OQW is irreducible (see Proposition 6.12 in [START_REF] Carbone | Homogeneous open quantum random walks on a lattice[END_REF] for a necessary and sufficient condition), then by Theorem 3.1 one has E i,ρ (n i ) = ∞ for any i and ρ.

A natural question is what happens when we drop the assumption of normality for L + and L -. We can still assume the form [START_REF] Grünbaum | Recurrence for discrete time unitary evolutions[END_REF]; if sup(p 1 , p 2 ) < 1/2 or inf(p 1 , p 2 ) > 1/2 and L + , L -do not have an eigenvector in common, then Theorem 5.4 in [START_REF] Carbone | Homogeneous open quantum random walks on a lattice[END_REF] implies that the process satisfies a law of large numbers x n /n → m = 0 almost-surely, and satisfies a large deviations principle with respect to any P i,ρ . This is enough to show that E i,ρ (n i ) < ∞ for any i and ρ. On the other hand, if e.g. p 1 > 1/2 and p 2 < 1/2 then we can still have P i,ρ (t i < ∞) = 1 for any i and ρ: consider (as suggested by [START_REF] Carvalho | Site recurrence of open and unitary quantum walks on the line[END_REF]) the case

L + = 1 √ 2 1 1 0 0 L -= 1 √ 2 0 0 1 -1
where Sp L * + L + = Sp L * -L -= {0, 1}. By Proposition 6.12 in [START_REF] Carbone | Homogeneous open quantum random walks on a lattice[END_REF], this open quantum walk is irreducible. In addition, for any π = (i 0 , . . . , i ℓ ), denoting ε = i 1i 0 , one shows that 2 ℓ(π)/2 L π equals

± 1 ε 0 0 if i ℓ -i ℓ-1 = +1, ± 0 0 1 ε if i ℓ -i ℓ-1 = -1.
We can therefore compute, again using results for simple random walks,

P 0,0 (ρ) = 1 2 1 -1 0 0 ρ 1 0 -1 0 + 1 2 0 0 1 1 ρ 0 1 0 1 .
We therefore have P * 0,0 (Id h0 ) = Id h0 , so that P i,ρ (t j < ∞) = 1 and E i,ρ (n j ) = ∞ for any i, j and ρ. In addition, E i,ρ (t i ) = ∞ for any i and ρ.

Exit times and Dirichlet problems on finite domains

In this section, we consider a finite subset D of V and study whether, conditionally on starting with x 0 in D, the position process (x n ) n reaches the boundary ∂D of D (which we define below) in finite time. We then study the related problem of solving Dirichlet problems of the type (Id -M * )(Z) i = A i for every i in D, with a boundary condition Z j = B j for j ∈ ∂D. Before we start, however, let us discuss shortly the Dirichlet problem on V . We consider an irreducible open quantum walk M, fix A = i∈V A i ⊗ |i i| with A i in B(h i ) for all i, and look for a solution Z of the equation (Id -M * )(Z) = A. As in the classical case (see e.g. [START_REF] Lawler | Random walk: a modern introduction[END_REF]), the form of the solution differs, depending on the recurrence or transience of the OQW. We give here only a simple result in the transient case.

We define the Dirichlet problem on V with data A as the following equation with unknown Z:

(Id -M * )(Z) = A. (24)
The operators N j,i as defined in ( 18) play a central role in this section.

Proposition 6.1. Let M be an open quantum walk such that E i,ρ (n j ) < ∞ for any i, j in V and ρ in S(h i ). If we assume that A = i∈V A i ⊗ |i i| is such that for any i in V , j∈V N * j,i A j < ∞, then the operator

Z = A + i∈V j∈V N * j,i (A j ) ⊗ |i i| (25)
satisfies [START_REF] Kato | Perturbation Theory for Linear Operators[END_REF]. If in addition M is irreducible, then any two solutions of (24) differ only by an operator λId H .

The form of Z can be guessed by analogy with the classical case, so that this result is obtained by direct computation.

We will give analogous results for the Dirichlet problem on a bounded domain. We start by defining precisely the boundary ∂D of D relative to an open quantum walk M:

∂D = {i ∈ V \ D | ∃j ∈ D with L i,j = 0}.
We say that Z = i∈V Z i ⊗ |i i| is a solution to the Dirichlet problem on D with data A and boundary condition B if

(Id -M * )(Z) i = A i for i ∈ D Z j = B j for j ∈ ∂D. (26)
A key step in order to solve explicitly this equation will be to prove that the exit time for D, defined as

t ∂D = inf{n ∈ N | x n ∈ ∂D},
is P i,ρ -almost-surely finite for any i in D and ρ in S(h i ). Our main results are summarized in the following statement: Theorem 6.2. Let M be a semifinite irreducible open quantum walk and let D be a finite subset of V such that ∂D = ∅. Then for any i in D and any state ρ on h i , P i,ρ (t ∂D < +∞) = 1.

In addition, for any A = i∈D A i ⊗ |i i| and B = j∈∂D B j ⊗ |j j|, the Dirichlet problem (26) has a solution, and any two solutions of (26) differ by an operator with support in H V \(D∪∂D) .

The steps in order to prove this, and related results, are described in Subsection 6.1 and Subsection 6.2.

Exit times: the irreducible case

We now focus on the particular case where the OQW is irreducible. Our first technical result, which plays an analogous role to Proposition 3.3, is the following: Proposition 6.3. Let M be an open quantum walk and let D be a finite subset of V such that ∂D = ∅. Then there exists a family (P D j,i ) i∈D,j∈D∪∂D , where P D j,i is a completely positive linear contraction from I 1 (h i ) to I 1 (h j ), such that each

P D i = j∈∂D P D j,i
is again a completely positive linear contraction from I 1 (h i ) to I 1 (h ∂D ). Moreover, for any i in D, j in D ∪ ∂D and any ρ in S(h i ), one has

P i,ρ (t j ≤ t ∂D < ∞) = Tr P D j,i (ρ), P i,ρ (t ∂D < ∞) = Tr P D i (ρ). Remark 6.4.
Again, a byproduct of our proof will be the expression

P D j,i (ρ) = π∈P D\{j} (i,j) L π ρL * π .
We also obtain the relations

E i,ρ (ρ tj | t j ≤ t ∂D ) = P D j,i (ρ) Tr P D j,i (ρ) (27)
E i,ρ (ρ t ∂D ) = P D i (ρ) Tr P D i (ρ) . ( 28
)
The first part of Theorem 6.2 is shown in the following proposition. Apart from having its own interest, it will be a key step in solving the Dirichlet problem: Proposition 6.5. Let M be an irreducible open quantum walk and let D be a finite subset of V such that ∂D = ∅. Then, for any i in D such that dim h i < ∞ and any state ρ on h i , one has

P i,ρ (t ∂D < +∞) = 1.
The main consequence of Proposition 6.5 is the following: Lemma 6.6. Under the assumptions of Proposition 6.5, for any j in D such that dim h j < ∞, the map P D j,j has norm P D j,j < 1. For any i in D one can define N D j,i = (Id -P D j,j ) -1 • P D j,i . Then, defining

n D j = card{n ≤ t ∂D | x n = j}, one has for any ρ in S(h i ) the identity E i,ρ (n D j ) = Tr N D j,i (ρ). ( 29
)
Remark 6.7. Under the assumptions of Lemma 6.6, the operator N D satisfies

N D j,i (ρ) = π∈P D (i,j) L π ρL * π , (30)
which shows in particular the obvious relation N D j,i = P D j,i for i ∈ D, j ∈ ∂D.

Dirichlet problems on D: the irreducible case

We now turn to the Dirichlet problem on a finite domain D. Recall that Z = i∈V Z i ⊗ |i i| is said to be a solution to the Dirichlet problem on D with data A and boundary condition B if it is a solution of Equation ( 26), which we recall:

(Id -M * )(Z) i = A i for i ∈ D Z j = B j for j ∈ ∂D.
The solution to these equations has a very simple form, now that we have introduced the operators N D j,i and P D j,i .

Proposition 6.8. Let M be an irreducible, semifinite open quantum walk and let D be a finite subset of V such that ∂D = ∅. For any

A = i∈D A i ⊗ |i i| and B = j∈∂D B j ⊗ |j j|,
the operator

Z = A + B + i∈D j∈D N D * j,i (A j ) + j∈∂D P D * j,i (B j ) ⊗ |i i|
is well-defined, and is a solution to the Dirichlet problem [START_REF] Kümmerer | A pathwise ergodic theorem for quantum trajectories[END_REF]. Any two solutions of (26) differ by an operator with support in H V \(D∪∂D) .

Harmonic measures: the irreducible case

Given a finite subdomain D of V , the harmonic measure quantifies the probability for an OQW starting in D to escape from D by a given point of its boundary ∂D. It is intimately related to the Dirichlet problem. Definition 6.9. Let D be a finite subset of V such that ∂D = ∅. Let M be an irreducible and semifinite open quantum walk, conditioned to start at i in D with initial state ρ in S(h i ). Let j be in ∂D. Recall the definition of the stopping time t ∂D = inf{n ∈ N | x n ∈ ∂D}. The harmonic measure at j relative to i and ρ is defined as

µ D i,ρ (j) = P i,ρ (x t ∂D = j) .
Recall that for an irreducible and semifinite OQW, the escape time t ∂D is finite with probability 1. The previous propositions directly imply the following: Proposition 6.10. The harmonic measure is linear in ρ. More precisely,

µ D i,ρ (j) = Tr(P D j,i (ρ)), ( 31
)
with P D j,i (ρ) = π∈P D (i,j) L π ρL * π . Moreover, E i,ρ (ρ t ∂D |x t ∂D = j) = P D j,i (ρ) Tr(P D j,i (ρ))
.

Of course by Proposition 6.5, j∈∂D µ D i,ρ (j) = 1, as we assume the OQW to be irreducible. Remark 6.11. The connection with the Dirichlet problem is twofold, as usual. First, by linearity in ρ let us write the harmonic measure as :

µ D i,ρ (j) = Tr(I D j,i ρ), with I D j,i = P D j,i * (Id hj ) = π∈P D (i,j) L * π L π . Let I D j ∈ B (
H) be defined by

I D j = i∈D I D j,i ⊗ |i i| + Id hj ⊗ |j j|. ( 32
)
Then I D j is quantum harmonic in D (i.e (Id -M * )(I D j ) k = 0 for k ∈ D) with boundary condition Id hj ⊗ |j j| on ∂D. Furthermore, one has j∈∂D I D j = Id D∪∂D , so that I D j may be viewed as a non-commutative quantum analogue of a harmonic measure. This link with the Dirichlet problem potentially gives an alternative way to evaluate the harmonic measure. Indeed, assuming the harmonic measure to be linear in ρ (as expected from quantum mechanics), it is then fully determined by solving a Dirichlet problem. Suppose (as we actually proved) that µ D i,ρ (j) is linear in ρ, and let us write µ D i,ρ (j) = Tr(I D j,i ρ) (without knowing the explicit expression of I D j,i ). Then conditioning on the first step of the OQW proves that I D j = i∈D I D j,i ⊗ |i i| + Id hj ⊗ |j j| is quantum harmonic in D with the appropriate boundary conditions. Furthermore, if I D j is quantum harmonic in D with boundary condition Id hj ⊗ |j j| then, by Lemma 2.5, (m D j ) n = Tr((I D j ) xn ρ n ) stopped at n = t ∂D is a P i,ρ -martingale. The optimal sampling Theorem then yields Tr(I D j,i ρ) = E i,ρ (m D j ) t ∂D = P i,ρ x ∂D = j .

Results for reducible open quantum walks

In this section, we collect some results regarding passage times, number of visits and exit times for reducible open quantum walks. We begin by recalling some results regarding decompositions of reducible open quantum walks from [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF].

We fix an open quantum walk M. By Proposition 7.11 in [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF], there exists an orthogonal decomposition of

H H = D ⊕ κ∈K H κ ( 33
)
where we have κ∈K

H κ = sup{supp ρ | ρ a M-invariant state}. ( 34
)
We denote the space (34) by R; we also let D = R ⊥ . The restriction M κ of M to I 1 (H κ ) is an irreducible OQW, and D = {0} if and only if M has a faithful invariant state. In addition, each H κ is an enclosure, i.e. has a decomposition

H κ = i∈V h κ i
where every h κ i is a subspace of h i , and for any i, j in V one has L i,j h κ j ⊂ h κ i . The decomposition [START_REF] Revuz | Markov chains[END_REF] is non-unique, as is discussed in sections 6 and 7 of [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF]; we fix, however, one such decomposition, and denote by M κ the open quantum walk induced by M on I 1 (H κ ). We define for every κ in K the set

V κ = {i ∈ V | h κ i = {0}}. For any i in V , h i has a decomposition h D ⊕ κ∈K h κ i .
Then, any state ρ i on h i can be written in block matrix form ρ = (ρ κ,κ ′ i ) κ,κ ′ ∈K∪{0} , where the index 0 corresponds to D. We denote by ρ κ i the diagonal blocks:

ρ κ i = ρ (κ,κ) i
. The main tool in this section is a simple observation: for any path π ∈ P ℓ (i, j) starting at i, the probability of observing, as ℓ first steps, the trajectory π = (i 0 , . . . , i ℓ ) with initial conditions (i, ρ) satisfies

P i,ρ (i 0 , . . . , i ℓ ) ≥ κ∈K Tr (L π ρL * π ) κ ≥ κ∈K Tr(L π ρ κ L * π ). (35)
In addition, if ρ has support in R, then inequalities in ( 35) become an equality. If we denote by e.g. P κ j,i the operator P j,i associated with the OQW M * , etc. then we have the following result: Proposition 7.1. Assume that the open quantum walk M admits a decomposition [START_REF] Revuz | Markov chains[END_REF]. Then, for any ρ in S(H),

P i,ρ (t j < ∞) ≥ κ∈K Tr ρ κ × Tr P j,i ρ κ Tr ρ κ ½ i,j∈V κ , E i,ρ (n j ) ≥ κ∈K Tr ρ κ × Tr N j,i ρ κ Tr ρ κ ½ i,j∈V κ , E i,ρ (t j ) ≥ κ∈K Tr ρ κ × Tr T j,i ρ κ Tr ρ κ ½ i,j∈V κ , P i,ρ (t ∂D ) ≥ κ∈K Tr ρ κ × Tr P D j,i ρ κ Tr ρ κ ½ i∈V κ , ∂D∩V κ =∅ .
(where as before we assume that D is a finite domain such that ∂D = ∅), and each of these inequalities becomes an equality if we assume that ρ has support in R.

If the support of ρ is contained in R (in particular if D = {0}) then since κ∈K Tr ρ κ = 1, it is easy to characterize e.g. the equality P i,ρ (t j < ∞) = 1, or the finiteness of E i,ρ (n j ), in terms of the sub-open quantum walks M κ (to which our various results for irreducible open quantum walks apply).

Variational approach to the Dirichlet problem

We assume throughout this section that τ inv = i∈V τ inv (i) ⊗ |i i| is an invariant state for the OQW M, which furthermore is faithful. In all of this section we write τ ⋄ instead of τ inv , i.e. we let

τ ⋄ := τ inv .
Our goal in this section is to characterize the solutions of the Dirichlet problem given by Equation ( 26) as minimizers of a certain functional, involving the Dirichlet form associated to the OQW. The present Dirichlet forms are simple, discrete-time versions of the non-commutative extensions of classical Dirichlet forms (such extensions were studied first by Davies and Lindsay in [START_REF] Davies | Non-commutative symmetric Markov semigroups[END_REF], see also [START_REF] Cipriani | The variational approach to the Dirichlet problem in C *algebras[END_REF][START_REF] Cipriani | Dirichlet forms on noncommutative spaces[END_REF][START_REF] Davies | Superderivations and symmetric Markov semigroups[END_REF]).

We first focus on the definition of the Dirichlet form and its properties. Define on B(H) the scalar product

X, Y ⋄ := Tr τ 1/2 ⋄ X * τ 1/2 ⋄ Y . (36)
Definition 8.1. The Dirichlet form associated to the open quantum walk M is the quadratic form

E(X, Y ) := X, (I -M * ) (Y ) ⋄ (37)
We also denote E(X) = E(X, X), for X ∈ B(H).

The central hypothesis in the following is the detailed balance condition.

Definition 8.2. We say that the open quantum walk M satisfies the detailed balance condition with respect to τ ⋄ if M * is selfadjoint with respect to the scalar product • , • ⋄ .

Note that we reserve the notation M * for the adjoint of M with respect to the duality between I 1 (H) and B(H). The detailed balance condition is satisfied, in particular, if

τ ⋄ (i) 1/2 L * j,i = L i,j τ ⋄ (j) 1/2 for all i, j ∈ V. It has two immediate consequences: Lemma 8.3.
If the open quantum walk M satisfies the detailed balance condition, then E(X) ≥ 0 for any X ∈ B(H). If in addition M is irreducible, then E(X) = 0 if and only if X ∈ CId H .

Dirichlet problem on the whole domain

Quantum harmonic operators are easily characterized as minimizers of the Dirichlet form. Indeed, the detailed balance condition implies that E(X) ≥ 0, with equality if and only if (I -M * )(X) = 0, that is, if X is harmonic. Proposition 8.4. Suppose that M satisfies the detailed balance condition. Then X is a quantum harmonic observable if and only if E(X) is minimal, if and only if E(X) = 0.

Dirichlet problem on a sub-domain

We now focus on the Dirichlet problem on a finite domain D ⊂ V , that we suppose to be non-empty. Recall the definition of respectively the inner data A and the outer data B as

A = i∈D A i ⊗ |i i| B = j∈∂D B j ⊗ |j j|,
where A j , B j ∈ h j for all j.

Our theorem is the following. An analogue of this result can be found in [START_REF] Cipriani | The variational approach to the Dirichlet problem in C *algebras[END_REF] for more general non-commutative Dirichlet forms.

(Id -M * )(Z) i = A i for i ∈ D Z j = B j for j ∈ ∂D.
is of the form X 0 + B + Y , where Y has support in H V \(D∪∂D) and X 0 is the unique minimizer over the set B (H D ) of the functional

E(X) = 1 2 E(X) + E(X, B) -A, X ⋄ . (38)

The case of doubly stochastic open quantum walks

In this last section we point out that the Dirichlet form can alternatively be written in terms of first order discrete derivatives (to be defined below) in the special case of doubly stochastic OQW, i.e. for open quantum walks that satisfy M * = M.

Proposition 8.6. Let M be a doubly stochastic open quantum walk satisfying M * = M. Then E(X) equals

1 2 i,j∈V Tr (∇X) i,j (∇X) * i,j =: 1 2 (∇X) 2 V ( 39
)
where (∇X) i,j = X i L i,j -L i,j X j for X = j∈V X j ⊗ |j j| ∈ B(H).

Positivity of the Dirichlet form is then manifest in (39). Notice that the passage from the definition of the Dirichlet form in [START_REF] Wolf | Quantum channels & operations: Guided tour[END_REF] to the formula (39) amounts to an integration by part. This presentation of the Dirichlet form in terms of first order difference operators can easily be extended to finite subdomain if one includes appropriate boundary terms arising from the discrete integration by part.

A Proofs for Section 2

Proof of Lemma 2.5: Conditionally on (x n , ρ n ), one has for all i in V

m n+1 = Tr(ρ n+1 A xn+1 ) = Tr L i,xn ρ n L * i,xn
Tr(L i,xn ρ n L * i,xn )

A i with probability Tr(L i,xn ρ n L * i,xn ), so that

E Tr(ρ n+1 A xn+1 )|x n , ρ n = i∈V Tr L i,xn ρ n L * i,xn A i = Tr ρ n i∈V L * i,xn A i L i,xn = Tr(ρ n A xn ) = m n .

B Proofs for Section 3

We start by computing simple expressions for the quantities P i,ρ (t j < ∞) and E i,ρ (n j ):

Lemma B.1. We have the identities

P i,ρ (t j < ∞) = π∈P V \{j} (i,j) Tr(L π ρL * π ), E i,ρ (n j ) = π∈P(i,j) Tr(L π ρL * π ),
where the second expression is possibly ∞.

Proof. We have P i,ρ (x 1 = i 1 , . . . , x ℓ = i ℓ ) = Tr L π ρL * π where π = (i, i 1 , . . . , i ℓ ). In addition,

P i,ρ (t j < ∞) = k≥0 i1,...,i k ∈V \{j} P i,ρ (x 1 = i 1 , . . . , x k = i k , x k+1 = j)
which leads to the first formula. We also have immediately P i,ρ (x k = j) = π∈P k (i,j) Tr(L π ρL * π ), and the second formula follows from

E i,ρ (n j ) = ∞ k=1 P i,ρ (x k = j).
Proof of Proposition 3.3 We begin with the definition of P i,j . For any ρ in I 1 (h i ) \ {0}, the triangle inequality for the trace norm implies that Tr π∈P V \{j} (i,j)

L π ρL * π ½ ℓ(π)≤n ≤ π∈P V \{j} (i,j) Tr L π ρL * π ½ ℓ(π)≤n = π∈P V \{j} (i,j) Tr (L π |ρ|L * π ) ½ ℓ(π)≤n = Tr|ρ| × P i, |ρ| Tr(|ρ|) (t j ≤ n) ≤ Tr|ρ|, so that sup n Tr π∈P V \{j} (i,j) L π ρL * π ½ ℓ(π)≤n < ∞.
Consequently, by the Banach-Steinhaus Theorem, the operator on I 1 (h i ) defined by P j,i (ρ) = lim n→∞ π∈P V \{j} (i,j)

L π ρL * π ½ ℓ(π)≤n
is everywhere defined and bounded. This proves the first identity in Proposition 3.3. To prove the second we need a series of technical results. Our strategy is the same as in the classical case: we introduce a weight on the length of paths, in order to tame the possible divergence of the series giving E i,ρ (n j ) in Lemma B.1. First note that, for any i, j ∈ V and any α ∈ (0, 1), there exists a bounded, completely positive map N (α) j,i from I 1 (h i ) to I 1 (h j ) such that π∈P(i,j)

α ℓ(π) Tr L π ρL * π = Tr N (α) j,i (ρ).
In particular, the following limit holds in [0, ∞]:

E i,ρ (n j ) = lim α→1 Tr N (α) j,i (ρ).
This operator N (α) j,i is defined by

N (α) j,i (ρ) = lim n→∞ π∈P(i,j) α ℓ(π) L π ρL * π ½ ℓ(π)≤n ,
using the Banach-Steinhaus Theorem and the simple bound Tr π∈P(i,j)

α ℓ(π) L π ρL * π ½ ℓ(π)≤n ≤ π∈P(i,j) α ℓ(π) Tr L π |ρ|L * π ½ ℓ(π)≤n = n k=0 α k P i,ρ (x k = j) ≤ (1 -α) -1 .
We also define

P (α) j,i (ρ) = lim n→∞ π∈P V \{j} (i,j) α ℓ(π) L π ρL * π ½ ℓ(π)≤n .
Since any π ∈ P(i, j) is a concatenation of π 0 ∈ P V \{j} (i, j) and π 1 , . . . , π k in P V \{j} (j, j), and

L π = L π k • . . . • L π1 • L π0 , ℓ(π) = ℓ(π k ) + . . . + ℓ(π 1 ) + ℓ(π 0 ),
we have

π∈P(i,j) α ℓ(π) L π ρL * π ½ ℓ(π)≤n = k≥0 π0∈P V \{j} (i,j), π1,...,π k ∈P V \{j} (j,j) α k r=0 ℓ(πr) L π k . . . L π1 L π0 ρL * π0 L * π1 . . . L * π k ½ k r=0 ℓ(πr)≤n .
Because both sides define bounded operators as n → ∞, we have

N (α) j,i (ρ) = k≥0 P (α) k j,j • P i,j (ρ) = (Id -P (α) j,j ) -1 • P (α) j,i (ρ).
Since α → P (α) j,j (ρ) is monotone increasing for ρ ≥ 0, the right-hand side is monotone increasing as well, and the second identity follows.

Proof of Equation ( 16) By definition, we have

E i,ρ (ρ tj | t j < ∞) = E i,ρ (ρ tj ½ tj <∞ ) P i,ρ (t j < ∞) = 1 P i,ρ (t j < ∞) π∈P V \{j} (i,j) L π ρL * π Tr L π ρL * π Tr L π ρL * π = P j,i (ρ) Tr P j,i (ρ)
.

Proof of Corollary 3.5

1. Let i, j ∈ V and ρ ∈ S(h i ). By Proposition 3.3, we have P i,ρ (t j < ∞) = Tr ρ P * j,i (Id hj ) and, since Tr ρ = 1, we have P i,ρ (t j < ∞) = 1 if and only if P ρ P * j,i (Id hi )P ρ = P ρ , where P ρ is the orthogonal projection on the support of ρ. Write P * j,i (Id hj ) as P * j,i (Id hj ) = Id Ran ρ A A * B in the decomposition h i = Ran ρ ⊕ (Ran ρ) ⊥ . Then the property P * j,i (Id hj ) ≤ Id hi implies that 0 -A -A * Id Ker ρ -B ≥ 0, so that necessarily A = 0. In particular, if ρ is faithful, then P i,ρ (t j < ∞) = 1 if and only if P * j,i (Id hj ) = Id hi . In that case, P i,ρ ′ (t j < ∞) = 1 for any ρ ′ in S(h i ).

2. Consequently, if this is the case for j = i, then for any ρ ′ in S(h i ) one has E i,ρ ′ (n i ) = ∞, since by Proposition 3.3 we have

E i,ρ ′ (n i ) = k≥1 Tr ρ ′ P * k i,i (Id hi ).
3. If E i,ρ (n j ) < ∞ with ρ faithful and dim h i < ∞, then for any α ∈ (0, 1),

Tr N j,i (ρ) ≥ Tr ρN (α) * j,i (Id hj ) ≥ inf Sp (ρ) × N (α) * j,i (Id hi ) , so that N (α) * j,i (Id hj
) is uniformly (in α) bounded in norm. The monotone increasing function α → N (α) * j,i (Id hj ) therefore has a limit and, by Proposition 3.3, E i,ρ ′ (n j ) < ∞ for any ρ ′ .

4. The construction of N j,i when E i,ρ (n j ) < ∞ for any ρ is obtained by a Banach-Steinhaus argument.

Proof of Proposition 3.7 Recall that P i,ρ (t i < ∞) = P i,i (ρ) . By Proposition 3.3, the map P i,i is bounded, and since S(h i ) is compact, the supremum p = sup ρ∈S(hi) Tr P i,i (ρ) satisfies p < 1. A standard application of the strong Markov property for the chain (x n , ρ n ) n shows that P i,ρ (n i = k) ≤ p k and by a direct computation E i,ρ (n i ) ≤ p(1p) -2 , which gives the result.

Proof of Proposition 3.9 and Corollary 3.10 We start with two simple lemmata:

Lemma B.2. Assume that M is an irreducible open quantum walk and let i, j in V be such that dim h i < ∞. Then inf ρ∈S(hi)

P i,ρ (t j < ∞) > 0.
Proof of Lemma B.2. For any ρ in S(h i ), there exists a unit vector ϕ in h i and λ > 0 such that ρ ≥ λ|ϕ ϕ|. By irreducibility, there exists a path π in P(i, j) such that L π ϕ 2 > 0, so that P i,ρ (t j < ∞) > 0. By continuity of P j,i and compactness of S(h j ), one has the result.

Lemma B.3. Assume that M is an irreducible open quantum walk and let i, j be in

V . If dim h j < ∞ and ρ ∈ S(h i ) is such that E i,ρ (n j ) = ∞, then for any j ′ ∈ V one has E i,ρ (n j ′ ) = ∞. Proof of Lemma B.3. By Lemma B.2, one has inf ρ ′ ∈S(hj ) P j,ρ ′ (t j ′ < ∞) > 0 for any j ′ ∈ V . Now, a standard markovianity argument shows that E i,ρ (n j ) = ∞ implies E i,ρ (n j ′ ) = ∞.
Remark B.4. Here we used only a weaker version of irreducibility, namely the fact that for any k, l in V , any ϕ in h k , there exists a path π in P(k, l) such that L π ϕ = 0.

Let us go back to the proof of Proposition 3.9 and Corollary 3.10. Define for j in V

D n (j) = ϕ = i∈V ϕ i ⊗ |i s.t. i∈V π∈P(i,j) L π ϕ i 2 < ∞ . (40)
It is immediate that D n (j) is a vector space, and that (L k,l ⊗ |k l|)D n (j) ⊂ D n (j) for any k, l in V . In the language of [START_REF] Carbone | Open quantum random walks: reducibility, period, ergodic properties[END_REF], this means that D n (j) is an enclosure for M. Moreover, the only possible enclosures for an irreducible M are {0} and H. Therefore, either D n (j) = {0} or D n (j) = H. Define for i in V d n j,i = D n (j) ∩ h i (with a slight abuse of notation). Then either for every i the subspace d n j,i is dense in h i or for every i it is {0}. Remark that by Lemma B.1,

π∈P(i,j) L π ϕ i 2 = E i,|ϕi ϕi| (n j ). By linearity of E i,ρ (n j ) in ρ, if d n j,i = {0} then E i,ρ (n j ) = ∞ for
any ρ in S(h i ), and if d n j,i is dense then E i,ρ (n j ) < ∞ for any ρ with finite range in d n j,i . This concludes the proof of Proposition 3.9. Now, if dim h i < ∞, then in situation 2. of Proposition 3.9 one has E i,ρ (n j ) = ∞ for any i in V and ρ in S(h i Now, Lemma B.3 forbids the situation where for j = j ′ one has E i,ρ (n j ) = ∞ and E i,ρ (n j ′ ) < ∞ for every ρ in S(h i ), and this proves Corollary 3.10.

Remark B.5. This proof is essentially due to [START_REF] Fagnola | Transience and recurrence of quantum Markov semigroups[END_REF].

Proof of Proposition 3.12 By Definition 2.1 of irreducibility, there is no nontrivial invariant subspace of h j left invariant by all L π , π ∈ P(j, j). Since any π ∈ P(j, j) is a concatenation of paths in P V \{j} (j, j), there is also no nontrivial invariant subspace of h j left invariant by all L π , π ∈ P V \{j} (j, j), and this means that P j,j is a completely positive irreducible map on I 1 (h j ). In addition, we know from the Russo-Dye Theorem that P j,j = P * j,j (Id) ≤ 1, so that the eigenvalue λ of P j,j of largest modulus satisfies |λ| ≤ 1. By the Perron-Frobenius Theorem for completely positive maps acting on the set of trace-class operators of a finite-dimensional space (see Theorem 3.1 and Remark 3.1 in [START_REF] Schrader | Perron-Frobenius theory for positive maps on trace ideals[END_REF], which are essentially proven in [START_REF] Evans | Spectral properties of positive maps on CSp * -algebras[END_REF]), there exists a faithful state ρ f on h j such that P j,j (ρ f ) = |λ|ρ f . If |λ| < 1, then by Proposition 3.3 one has E j,ρ f (n j ) < ∞. However, by Proposition 3.9, the assumption E i,ρ (n j ) = ∞ implies E j,ρ f (n j ) = ∞, a contradiction. Therefore |λ| = 1, ρ f is a faithful invariant state and Tr P j,j (ρ f ) = Tr ρ f = 1. By Corollary 3.5, we have that P j,ρ (t j < ∞) = 1 for any ρ in S(h i ).

C Proofs for Section 4

Proof of Proposition 4.1 The expansion of E i,ρ (t j ) and the construction of T j,i are obtained by now standard Banach-Steinhaus arguments.

Proof of Proposition 4.4 Proposition 4.4 is proved like Proposition 3.9, by introducing

D t (j) = ϕ = i∈V ϕ i ⊗ |i s.t. i∈V π∈P V \{j} (i,j) ℓ(π) L π ϕ i 2 < ∞ (41)
and remarking that D t (j) is an enclosure.

Proof of Theorem 4.3 Define d t j,i = D t (j)∩h i . Remark that in the case of a semifinite OQW, by Proposition 4.4, for every j in V either d t j,i = {0} for every i; or d t j,i = h i for every i. If for some j one has d t j,i = h i for every i, then we have in particular E j,ρ (t j ) < ∞ for any ρ in S(h j ); for any j ′ , applying Lemma B.2 again one has inf ρ∈S(hj ) P j,ρ (t j ′ < ∞) > 0. By a markovianity argument, one obtains that E j,ρ ′ (t j ′ ) < ∞ for any j ′ in V and ρ ′ ∈ S(h j ).

Proof of Theorem 4.5 Let τ inv = i∈V τ inv (i) ⊗ |i i| be an invariant state for M. Then by the infinite-dimensional extension of the Kümmerer-Maassen ergodic Theorem (see [START_REF] Lim | Frontières de Poisson d'opération quantiques et trajectoires quantiques[END_REF]), one has, for any i ∈ V and ρ ∈ S(h i ), the P i,ρalmost-sure convergence

1 n n k=1 ρ k ⊗ |x k x k | -→ n→∞ j∈V τ inv (j) ⊗ |j j|, (42)
where convergence is in the weak-* sense. This implies in particular that

n (k) j = card{n ≤ k | x n = j} satisfies, for any j ∈ V , n (k) j /k → k→∞ Tr τ inv (j), P i,ρ -almost-surely. Therefore, t (k) j < ∞ but t (k) j → k→∞ ∞. Considering m = t (k) j , we have n (m) j /m = k/t (k) j
and therefore, P i,ρ -almost-surely, t

j /k → Tr τ inv (j) -1 .

Observe now that, as shown in Example 5.3, our assumptions imply in particular that P j,ρ (t j < ∞) = 1 for any ρ in S(h j ), so that P j,j is a completely positive, trace-preserving map, with Kraus decomposition

P j,j (ρ) = π∈P V \{j} L π ρL * π .
In addition, we have P j,ρ -almost-surely from (42)

1 n k ρ t (k) j ½ t (k) j ≤n -→ n→∞ τ inv (j)
(the convergence needs not be specified, as h j is finite-dimensional), but the Kümmerer-Maassen ergodic Theorem applied to P j,j shows that 1

n (m) j n (m) j k=1 ρ t (k)
i converges almost-surely to an invariant of P j,j . Therefore, τ inv (j) Tr τ inv (j) is an invariant state for P j,j and P j,ρ -almost-surely,

1 n (m) j n (m) j k=1 ρ t (k) i -→ m→∞ τ inv (j) Tr τ inv (j) (43)
In addition, since τ inv (j) is faithful on h j , one has by necessity that P j,j is irreducible: if there existed an invariant subspace for all L π , π ∈ P V \{j} , then there would exist an invariant state ρ ′ j for P j,j with support on this invariant subspace, and considering initial data (j, ρ ′ j ) in (43) above would show that τ inv (j) has support no larger than the support of ρ ′ j , a contradiction. We now define a new probability space by Ω (j) = P V \{j} (j, j)

⊗N , and let P (j) (π 1 , . . . , π m ) = Tr L πm . . . L π1 τ inv (j) Tr τ inv (j) L * π1 . . . L * πm .

The trace-preserving property of P j,j shows that this defines a consistent family and by the Daniell-Kolmogorov extension Theorem this defines a probability P (j) on Ω (j) . In addition, the invariance of τ inv (j) Tr τ inv (j) by P j,j implies π1∈P V \{j} (j,j) P (j) (π 1 , . . . , π m ) = P (j) (π 2 , . . . , π m ), which shows that P (j) is invariant by the left shift Θ : Ω (j) → Ω (j) (π 1 , π 2 , . . .) → (π 2 , π 3 , . . .) Now, the Perron-Frobenius Theorem implies that 1 is a simple eigenvalue for P j,j . This immediately shows that for any two cylinder sets E and F , 1 m m k=1 P (j) E ∩ Θ -k (F ) -→ m→∞ P (j) (E) P (j) (F ), so that (Ω (j) , P (j) ) is ergodic for Θ. Now, if we consider the map ℓ (k) defined by ℓ (k) (π 1 , π 2 , . . .) = ℓ(π 1 ) + . . . + ℓ(π k ), then this map satisfies ℓ (k+k ′ ) = ℓ (k) + ℓ (k ′ ) • Θ k . By Birkhoff's ergodic Theorem one has P (j) -almost-sure convergence of ℓ (k) /k to the expectation of ℓ (1) for P (j) . It is immediate, however, that the distribution of ℓ (k) under P (j) is the same as the distribution of t

D Proofs for Section 6

Proof of Proposition 6.1 Consider A = i∈V A i ⊗ |i i| such that for any i in V , j∈V N * j,i (A j ) < ∞. Then (25) defines an operator Z. Proving that Z satisfies ( 24) is then a straightforward computation. By linearity it is enough to assume that A = A k ⊗ |k k|. We then have

M * (Z) = i∈V j∈V L * j,i ½ j=k A k + π∈P(j,k) L * π A k L π L j,i ⊗ |j j|.
Since the set of paths obtained by concatenating one step from a given i to a variable j, then some π from j to k, is exactly the set of paths from i to k of length ≥ 2, and (i, k) is the only path from i to k of length 1, we obtain M * (Z) = Z -A k ⊗ |k k|, so that (Id -M * )(Z) = A. If Z ′ is another solution of [START_REF] Kato | Perturbation Theory for Linear Operators[END_REF], then Y = Z ′ -Z satisfies M * (Y ) = Y and by the Perron-Frobenius Theorem of [START_REF] Groh | The peripheral point spectrum of Schwarz operators on C *algebras[END_REF] applied to the irreducible map M * , we have Y ∈ CId H .

Proof of Proposition 6.3 It is now a routine argument to construct P D i,j using the Banach-Steinhaus Theorem, as

P D j,i (ρ) = π∈P D (i,j) L π ρL * π .
One then has by definition P i,ρ (t j ≤ t ∂D < ∞) = Tr P D j,i (ρ), and the second identity follows from P i,ρ (t ∂D < ∞) = j∈∂D P i,ρ (t j ≤ t ∂D < ∞). Relations ( 27) and ( 28) are obtained as Equation [START_REF] Davies | Superderivations and symmetric Markov semigroups[END_REF].

Proof of Proposition 6.5 We define p = inf i∈D inf ρ∈S(hi) P i,ρ (t ∂D < +∞).

We will show independently that p > 0 and that p ∈ {0, 1}, therefore proving Proposition 6.5.

To prove that p > 0, we use a simple adaptation of Lemma B.2. Fix some ρ in S(h i ); there exist a unit vector ϕ in h i and λ > 0 such that ρ ≥ λ|ϕ ϕ|. By irreducibility, for any j in ∂D there exists a path π in P(i, j) such that L π ϕ = 0. There exists j ′ in ∂D (the first point of ∂D visited by the trajectory π) and a subpath π ′ of π belonging to P D (i, j ′ ), with necessarily L π ′ ϕ = 0. We have shown Tr P D i (ρ) > 0 and, P D i being continuous, we have by a compactness argument that inf ρ∈S(hi) Tr P D i (ρ) > and therefore p > 0 as D is finite. We next prove that p ∈ {0, 1}. By the strong Markov properrty, for any n one has Proof of Lemma 6.6 Let j in V with dim h j < ∞. By irreducibility, there exists a path π in P D (j, k) for some k ∈ ∂D such that TrL π ρL * π = 0. There exists k ′ in ∂D and a subpath π ′ of π which belongs to P D\{j} (j, k ′ ) such that TrL π ′ ρL * π ′ = 0, which implies that P j,ρ (t j ≤ t ∂D ) < 1. In particular, Tr P D j,j (ρ) < 1 for any ρ in S(h j ), so that P D j,j < 1. The same discussion that allowed us to construct N j,i shows that N D j,i is well-defined by N D j,i = (Id -P D j,j ) -1 • P D j,i and satisfies relations ( 29) and [START_REF] Lim | Frontières de Poisson d'opération quantiques et trajectoires quantiques[END_REF].

Proof of Proposition 6.8 By Lemma 6.6, all operators N D j,i and therefore the operator Z, are well-defined. Obviously Z j = B j for j ∈ ∂D; the proof that (Id -M * )(Z) i = A i for i ∈ D is similar to that for Proposition 6. Since this is true for any ρ in S(h i ), we obtain that Y i = 0, for any i ∈ D.

E Proof for Section 8

Proof of Lemma 8.3 Since M * = 1, the quantum detailed balance condition implies that the spectrum of M * is contained in [-1, +1], so that I -M * is a

Definition 3 .

 3 13. A semifinite irreducible open quantum walk M is called transient if it satisfies property 1. of Corollary 3.10, and recurrent if it satisfies property 2.

5 ExamplesExample 5 . 1 .

 551 Consider the open quantum walk defined by V = {0, 1, 2}, with h i = C 2 for i = 0, 1, 2 and

Example 5 . 2 .

 52 Consider the open quantum walk defined by V = {0, 1, 2, . . .} with h 0 = C 2 and h i = C for i > 0, and transition operators

Example 5 . 4 .

 54 Consider the open quantum walk with V = {0, 1, 2, 3}, h 0 = C and h i = C 2 for i = 1, 2, 3.

Theorem 8 . 5 .

 85 Let M be an irreducible open quantum walk with detailed balance condition and D a finite domain of V such that ∂D = ∅. Then any solution of the Dirichlet problem

  both almost-sure and in the L 1 sense, with respect to P j, τ inv (j)Tr τ inv (j). The first part of the proof shows thatE j, τ inv (j) Tr τ inv (j) (t (1) j ) = Tr τ inv (j) -1 ,and this concludes the proof.

1

  p = sup i∈D sup ρ∈S(hi) P i,ρ (t ∂D = +∞) = sup i,ρ E i,ρ ½ x1,...,xn∈D P xn,ρn (t ∂D = +∞) ≤ (1p) P i,ρ (x 1 , . . . , x n ∈ D),and taking n → ∞ leads to (1p) ≤ (1p) 2 , so that p ∈ {0, 1}. This concludes our proof.

  1. Now consider two solutions Z and Z′ ; then Y = Z -Z ′ satisfies Y j = 0 for j ∈ ∂D and (Id -M * )(Y ) i = 0 for i ∈ D. As in Lemma 2.5 we can prove that, if m n = Tr(ρ n Y xn ) n , then m D n = m inf(n,t ∂D ) is a P i,ρ -martingale for any i in D and ρ in S(h i ). The optional sampling Theorem applied to the bounded martingale Tr(ρ n Y xn ) and the stopping time t ∂D implies that Tr ρ Y i = E i,ρ Tr(ρ t ∂D Y xt ∂D = 0.

Note that the two norms • in this relation are different, the first being the norm for operators acting on B(H), the second the norm for operators acting on H.

positive operator and E(X) ≥ 0 for all X ∈ B(H). In addition, E(X) = 0 if and only if M * (X) = X. If M is irreducible, which by the Perron-Frobenius Theorem for operators on a C*-algebra (see [START_REF] Groh | The peripheral point spectrum of Schwarz operators on C *algebras[END_REF]) applied to the irreducible map M * , the identity M * (X) = X is equivalent with X ∈ CId H .

Proof of Theorem 8.5 Let us write Z = B + X + X ′ with X ∈ B(H D ) and

By Lemma 8.3, E(X, X) is non-negative and vanishes only if X ∈ CId H . However, since ∂D = ∅, Id H ∈ B(H D ) and one has E(X, X) > 0 for any X ∈ B(H D ). Consequently, by a compactness argument, there exists λ > 0 such that E(X, X) ≥ λ X 2 ⋄ for X ∈ B(H D ). One can then apply the Lax-Milgram Theorem (see [START_REF] Brezis | Functional analysis, Sobolev spaces and partial differential equations[END_REF]): there exists a unique X 0 satisfying (44), which in addition is the minimizer of

The solutions of Equation ( 26) are therefore the operators of the form

Proof of Proposition 8. [START_REF] Bauer | Open quantum random walks: Bistability on pure states and ballistically induced diffusion[END_REF] The proof is simply a matter of computation. For doubly stochastic OQW, L ij = L * ji , the invariant state τ ⋄ is the identity and the Dirichlet form reads

On the other hand we have

The two formulas coincide since j∈V L ij L ji = Id for doubly stochastic OQW.


K Kottari

K Delibasis
email: kdelibasis@gmail.com

Multi-pose volume reconstruction across arbitrary trajectory from multiple fisheye cameras

Keywords: Silhouette to shape -S2S, Fisheye camera, Volumetric model, Optic Hull, Multi-pose volume recovery, Computer Vision, Smart Graphics. 1 1 2 2, i j

Volume reconstruction from silhouettes is a known subject in the case of projective cameras. The use of dioptric omni-directional cameras (fisheye) that exhibit semispheric Field of View (FoV) allows simultaneous imaging of the whole available space. In this work we employ two fisheye cameras in order to acquire silhouettes of humans that move within the imaged indoor space without any kind of restriction. We present the basic algorithm for reconstructing the volumetric model of a human in the case of using two images of its silhouette, acquired by the fisheye cameras. Then we extend this algorithm in the case of a human moving along any trajectory a) assuming no pose change and b) considering pose change during motion. Quantitative results from synthetic data indicate that volumes can be reconstructed with high accuracy (error of few cm), from a small number of positions using only two fisheye cameras. The proposed algorithm achieves the same level of accuracy in the case of recovering the volume of multiple poses under same conditions.

Introduction

Given a single silhouette image of an object, we know that the 3D object lies inside the volume generated by backprojecting the silhouette area using the parameterized camera calibration (subsection 3.1). This volume is shaped as a generalized cone. The intersection of the generalized cones generated by each available binary silhouette, builds a volume, which is guaranteed to contain the object. This volume is called visual (optic) hull of the object.

A number of cameras is required for sufficiently accurate volume reconstruction, thus introducing difficulty in accurate positioning and calibration of the cameras. In this work we exploit the main characteristic of the fisheye lens that exhibits a 360 0 azimuthial and 180 0 elevation FoV, in order to obtain simultaneous multiple sihlouettes of an object that moves inside the imaged indoor space. Fisheye cameras are dioptric omni-directional cameras, whose use in computer vision application is becoming popular [START_REF] Kemmotsu | Recognizing human behaviors with vision sensors in a Network Robot System[END_REF], [START_REF] Zhou | Activity Analysis, Summarization and Visualization for Indoor Human Activity Monitoring[END_REF]. In [START_REF] Mei | Single View Point Omnidirectional Camera Calibration from Planar Grids[END_REF], [START_REF] Li | Plane-Based Calibration and Auto-calibration of a Fish-Eye Camera[END_REF], [START_REF] Shah | Intrinsic parameter calibration procedure for a high distortion fisheye lens camera with distortion model and accuracy estimation[END_REF] the calibration of fisheye camera is reported to emulate the strong deformation introduced by the fisheye lens. In [START_REF] Wei | Fisheye Video Correction[END_REF] the authors present a methodology for correcting the distortions induced by the fisheye lens.

Related Work

Recovering 3D structure from multiple binary (2D) shapes (silhouette to shape -S2S, commonly referred as shape from silhouette) by projective cameras is a well-known technique [START_REF] Kutulakos | A theory of shape by space carving[END_REF], [START_REF] Potmesil | Generating Octree Models of 3D Objects from their Silhouettes in a Sequence of Images[END_REF]. The limited field of view (FoV) of the projective cameras requires the object to be imaged in a specific location, rather than anywhere in the FoV. Little work has been reported in shape-from-silhouette using fisheye cameras. In [START_REF] Tsuneo | Shape recognition and grasping by robotic hands with soft fingers and omnidirectional camera[END_REF] the use of an omni-directional camera is proposed for industrial object recognition, employing a simple 2D hull intersection. Epipolar geometry between pairs of catadioptric omni-directional cameras has been established in [START_REF] Svoboda | Epipolar geometry for panoramic cameras[END_REF]. A combination of perspective and para-catadioptric cameras is used to define epipolar geometry and is subsequently applied for camera self-calibration [START_REF] Sturm | Mixing Catadioptric and Perspective Cameras[END_REF]. In the two aforementioned works no application of S2S is reported.

In this work, a volume carving algorithm is presented for recovering the shape of the object using multiple silhouettes acquired by two fisheye cameras, at different times and positions along any path. Initially, single pose reconstruction is performed by a still synthetic human, utilizing two fisheye cameras. This algorithm is further refined to reconstruct the single pose by the two fisheye cameras, whereas the object of interest (synthetic human) moves in an arbitrary path in the imaged room. The proposed S2S algorithm is then extended to reconstruct multiple distinct poses of the imaged person that alternate randomly along the path. Reconstruction of different poses is performed by establishing correspondance between silhouettes and previously reconstructed poses, using similarity measures.

In this study we concentrate in synthetic data, obtained from a number of available three dimentional (3D) human models, in order to quantitavely access the accuracy of the algorithm. The main assumptions of the algorithm are: accurate calibration of the fisheye cameras and orientation estimation using the motion of the object.

Methodology

Calibration of the fisheye cameras

The two fisheye cameras were both calibrated using a set of manually provided points, as described in detail in [START_REF] Delibasis | Refinement of human silhouette segmentation in omni-directional indoor videos[END_REF]. The achieved calibration compares favorably to other state of the art [START_REF] Rufli | Automatic Detection of Checkerboards on Blurred and Distorted Images[END_REF] in terms of accuracy. Let 1 2 , B B be the binary frames containing the silhouette as imaged by the two fisheye cameras. After completion of the calibration process for both fisheye cameras, functions 1 2 , F F are defined. These functions map a real world point ( )

, ,

real real real x y z = real x to coordinates ( ) ( ) ( ) ( ) , , 1, 2 c c c F i j c = = real x (1)
The resulting calibration for one of the cameras is visualized in Fig. 1.

Synthetic data using 3D human model

In this work we utilized a number of 3D models (Fig. 2) with known real-world coordinates obtained from [START_REF] Hasler | Multilinear pose and body shape estimation of dressed subjects from image sets[END_REF], [15]. These models are in the form of triangulated surfaces. However, only the coordinates of the vertices are used for rendering the binary silhouette frames, as described in subsection 3.3. Every model was placed in room along a trajectory at different orientations along a path of arbitrary shape shown in Fig. 3 as described in 3.4. Moreover, models (a) and (b) were placed along the same path alternating each other at varying order, to create the synthetic data used for conducting the multi-pose reconstruction described in 3.5. In order to utilize the available fisheye cameras c=1,2, we modified the classic space carving algorithm [START_REF] Kemmotsu | Recognizing human behaviors with vision sensors in a Network Robot System[END_REF], using the parameterized camera calibration (subsection 3.1). This volume is shaped as a generalized cone, which is guaranteed to contain the object (optic hull). Simple polyhedron-polyhedron intersection algorithms [16 Sub.3.3] are inefficient and produce polyhedral rather than volumetric representations. Therefore, we perform paired intersection of volumes and transformation of pixels of the binary silhouette to voxels through indexing as described below.

Each point of the 3D human model, v k , with k=1,2,…, N m (N m is the number of points of the model) is rendered on a pixel of frames 1 B and 2 B , by cameras 1 and 2, respectively, according to the calibration of each camera (subsection 3.1):

( ) ( ) ( ) ( ) 1 1 2 2 1, 1 B F B F = = k k v v
. Furthermore, a cube C, large enough to include a sufficient portion of the real world space, is initialized and divided into elementary volumes δV of dimensions δl× δl× δl, with δl equal to 1 cm. In order to minimize memory requirements we define cube C sufficiently large around model's position p, rather than covering the whole room, which is imaged by the available fisheye cameras. The employed silhouette-to-shape algorithm returns a binary volume V , which is the discretized cube C and contains the optic hull, as following:

Function V =Create_Hull( 1 2 , B B ,p)

Initialize the cube C around position (p) FOR each camera c

FOR each δV in C //Determine the optic hull for the fisheye camera

IF ( ) ( ) 1 c c B F V δ = THEN Obtain the corresponding indexes (i,j,k) of δV with respect to C Set , , 1 c i j k V = END IF c>1 1 - = ∩ c c c V V V END END V = c V

Utilization of multiple projections at different positions along a trajectory

The larger the number of intersections used, the more accurate becomes the recovered visual hull of the imaged object. The use of the fisheye cameras, instead of perspective ones, allows the simultaneous silhouette acquisition at a large number of different positions (p i ) and orientations. Thus, while the human silhouette is walking along a trajectory, many frames can be acquired by both cameras. With multiple views of the same object, we can intersect the generalized cones generated by each image (as discussed in 3.2), to build a more accurate visual hull of the object.

Generating binary silhouettes along a trajectory.

To simulate the human silhouette trajectory, we place the synthetic model, shown in Fig. 2 (a), at several positions along an arbitrary path shown in Fig. 4. At each one of these positions p i , the tangent vector t indicates the orientation (angle i θ ) of the human silhouette by transforming Cartesian to Polar frame of reference. The placement of the model at the different positions and orientations is illustrated in Fig. 5. The algorithm assumes that the orientation of the silhouette can be obtained by using the tangent vector of its motion. More specifically, we defined N=21 different positions p i in the room and we employed B-splines to simulate smooth motion and to generate a large number of intermediate points (x, y). In order to calculate orientation i θ of the tangent vector linear convolution (denoted by "*") with kernel M is performed.

[ ]

1 1, 0, 1 2 M = - (2) ( ) ( ) ( ) ( ) 1 tan , 1, 2, , i i i M y i N M x θ -   *   = = …   *   (3)
{ } { } 1 2 , i i B B = = 1 2 B B .
We present the pseudocode that accepts as input ,

1 2
B B and the sequence of positions p and returns as output the refined visual hull.

Function V=Create_Hull_MultiPositions( ,

1 2 B B ,p)
FOR each position index i p=p i Obtain the tangent vector t i and its orientation

θ i V i =Create_Hull( 1 2 , i i B B ,p)
Rotate V round the Z-axis by angle -θ i IF i>1

1 i i i V V V - = ∩ END END

3.5

Multi-pose reconstruction using multiple synthetic models

In this subsection, the previously described algorithm is extended so that different poses of human model are recovered. According to our experimental setup, the model of Fig. 2 Bp respectively, for all values of j, by calculating their pairwise similarity S as following:

( ) { } { } { } ( ) # , max # , # i j c c i j c c i j c c B Bp S B Bp B Bp ∩ = (4)
where # indicates the number of pixels of the image in {}. Let J be the set of values of j for which ( )

, i j c c
S B Bp is greater than a predefined threshold T, for both cameras (c=1,2):

( ) { } : , , 1, 2 i j c c J j S B Bp T c = ≥ = (5)
If no value of j satisfies condition (5) ( J = ∅ ), a new pose is introduced:

1 p N i P V + = .
Otherwise, j best is set as the value that maximizes ( ) The value of the threshold of Eq.( 5) is experimentally determined equal to 0.55. A higher threshold value could affect the result of the method by generating new nonexisting poses. On the other hand, a lower value for T would cause the intersection of the wrong selected pose ( j P ) with the current optic hull ( i V ), thus producing inaccurate 3D model. In general, the introduction of a non-existing pose (j) is not crucial since it can be overcome by neglecting it if too few (num j ) optic hulls ( i V ) have been assigned to it. However, merging a pose with a non-corresponding hull produces a wrong pose, which cannot be recovered a-posteriori.

, i j c c c S B Bp ∑ : ( ) , arg max i j best c c c j J j S B Bp ∈   =     ∑ (6)

Results

Calculation of reconstruction error

The use of synthetic data allows the accurate quantification of the error in volume reconstruction. As described above, the optic hull is generated in the form of a volumetric model V. In order to calulate the displacement error with respect to the 3D human model, which is in the form of point cloud, we apply a simple linear transformation from cloud space to voxel space to the points of the 3D human model. Thus, volume V T (of equal dimensions to V) is generated. Subsequently, the distance transform (DT) of V T is computed in 3 dimensions. The average error (err) is computed as the average distance of the non-zero voxels of V from the non-zero voxels of V T as following:

( ) ( ) { } 1 , # , , : 0 ijk ijk err DT V N i j k V N Τ = = > (7)
The error derived is expressed in units of δl, as described in 3.3 (which is set equal to 1 cm for the results presented in this work).

4.2

Quantitative results

The Mobotix Q24 hemispheric camera was used as the fisheye camera, which was installed on the ceiling of the imaged university room. The pixilation of each frame is 480x640.

Single pose volume reconstruction along trajectory.

The single poses of Fig. 2 were placed at different positions and orientations along the path shown in Fig. 4 and5. The algorithm presented in 3.4 was applied and the resulting optic hulls of Fig. 2(a) are presented in Fig. 6 (blue dots) superimposed on the ground truth (3D human model) shown in magenta dots. The reconstruction errors (described in the previous subsection), for all four single poses, are plotted against the number of positions in Fig. 7. As it can be observed, the reconstruction error, in the majority of the executions, approached 2 cm after a few positions.

Conclusion

The use of fisheye cameras for volumetric model reconstruction was investigated in this work, using synthetic data. Initially, a 3D model of a human with known real world coordinates was placed in any location withing the FoV of both fisheye cameras, covering the whole room. The proposed algorithm utilizes the calibration of the fisheye cameras to reconstruct the volumetric model. Synthetic models were used in order to measure the error of reconstructed volume numerically (in cm). This process exploited the placement of the 3D model at different positions and orientations. Finally, the recovery of two poses that alternate between positions along an arbitrary trajectory is also investigated. Quantitative results show the usefulness of the fisheye cameras, since accurate shape (volume) reconstruction of more than one poses of an object is possible with a minimum number of cameras, by using silhouette views at many positions and orientations along any path.

The generation of volumetric models by acquiring silhouettes, utilizing person movements along any path, is a seamless procedure that may find many applications. For instance, it can be further used to recognise an object or to identify the posture of a moving object of interest. Using silhouettes to reconstruct shape is a technic able to be used in smart homes, for surveillance or assisted living, in games, for avatar generation, or even in fashion, for testing design or demonstrating creations. Volume reconstruction execution time was approximately equal to 1 second, for each position, using a volumetric cube C of 1.5×1.5×2.2 meters, with an elementary cube δV of 1×1×1 cm, using Matlab on an Intel(R) Core i5-2430 CPU @ 2.40 GHz Laptop with 4 GB Ram, under Windows 7 Home Premium.

Fig. 1 .

 1 Fig. 1. Visualization of the resulting fisheye model calibration, on the FoV of the indoor environment in which experiments have taken place. The landmark points defined by the user are shown as circles and their rendered position on the frame marked by stars.

Fig. 2 .. 3 3D

 23 Fig. 2. The 3D human model poses used this work

Fig. 3 Fig. 3 .

 33 Fig.3visualizes the experimental setup and the input to the above algorithm. In (a) the geometry of the imaged indoor environment (room) is shown, including the two fisheye cameras 1 and 2 ("Cam 1" and "Cam 2" of figure) at their real positions (0,0,0) and (4,1,0), respectively. One instance of the synthetic 3D model of Fig.2(a) placed at position p = (2.6480, -0.0515) is included in the imaged room (a). (All

Fig. 4 .

 4 Fig. 4. The path of arbitrary shape used in this study.

Fig. 5 .

 5 Fig. 5. Synthetic human model at different positions and orientations of the arbitrary shape.

Fig. 6 .

 6 Fig. 6. Evolution of the volumetric model (optic hull) of a single pose, as a function of different positions used. Blue dots indicate reconstructed volume and magenta indicates the ground truth (3D human model).

Fig. 7 . 2 .

 72 Fig. 7. The evolution of the single pose reconstruction error with the number of positions, for four independent executions using the poses (a), (b), (c) and (d) shown in Fig. 2.

Fig. 8 .

 8 Fig. 8. Evolution of the volumetric model (optic hull) of two distinct poses as a function of different positions used. Blue dots indicate reconstructed volume and magenta indicates the ground truth (3D human model).

Fig. 9 .

 9 Fig. 9. The evolution of the reconstruction error with the number of positions, in the case of two poses.

Further work is required using real data to test the effect of calibration, as well as of the estimation of position and orientation, to the reconstruction of the optic hull of each pose of the object. Acknolegments The authors would like to thank the European Union (European Social Fund ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: \Thalis\ Interdisciplinary Research in Affective Computing for Biological Activity Recognition in Assistive Environments for financially supporting this work.