QUANTUM LOGIC, QUANTUM HISTORIES AND QUANTUM TURING MACHINES

Maria Luisa Dalla Chiara^{∗} and Roberto Giuntini^{∗∗}

∗Dipartimento di Filosofia, Università di Firenze

∗∗Dipartimento di Filosofia e Teoria delle Scienze Umane, Università di Cagliari

e-mail: dachiara@mailserver.idg.fi.cnr.it,  giuntini@philos.unifi.it

Contents 1 Introduction

In his rich research Johan van Benthem has given some important contributions to temporal and dynamic logics. In this paper, we will present the main ideas of a semantic framework, where quantum logic permits us to model some typical temporal and dynamic situations. One is dealing with new quantum logical structures that have been suggested by the consistent histories approach to quantum theory (investigated by Gell-Mann, Hartle ([4]), Isham, Linden ([7], [8]) and many others).

Roughly, the basic idea of this approach is that the fundamental objects of quantum theory are represented by consistent sets of histories, where each history corresponds to a possible temporal evolution of a micro-physical system. Interestingly enough, one can find deep connections between quantum histories and quantum computations.

We propose a general semantics that, in principle, admits a number of possible applications. The basic concept in this semantics is the notion of historical structure.

2 Historical structures

Definition 2.1 A historical structure is structure

M = ⟨T, S, Ev, Histev , Op , D⟩ ,

where

1) T is a linearly ordered set of times. In the following a time-sequence ⟨t_{1}, …, t_{n}⟩ will be always written according to the order ≤.

2) S is a function that assigns to each t ∈ T a set S_{t} of possible states at time t. For simplicity all S_{t} are supposed to be (ontologically distinct) copies of a fixed (timeless) S^{∗}.

¿From an intuitive point of view, states can be regarded as possible worlds of a Kripke-style semantics: pieces of information about possible states of affairs (or fragments of reality).

In the physical applications: S^{∗} will (naturally) contain the possible states of the physical system under investigation. A state is called pure when it represents a maximal information that is consistent with respect to the theory. Non maximal pieces of information correspond to mixed states. In classical mechanics pure states are always logically complete. In other words any pure state can semantically decide any relevant physical property of the system (localization, velocity, energy,...). On the contrary, a characteristic aspect of quantum theory is a divergence between maximality and logical completeness. Owing to the uncertainty relations, any information about a quantum system is necessarily logically incomplete, in the sense that it cannot semantically decide all the physical properties concerning our system. In classical mechanics (CM), pure states are mathematically represented by points of an appropriate phase space Ω. In quantum theory (QT), instead, the pure states of a quantum object are represented by unitary vectors in an appropriate Hilbert space H.

3) Ev is a function that assigns to each t ∈ T a set Ev_{t} of events at time t. For simplicity, all Ev_{t} are supposed to be (ontologically distinct) copies of a fixed (timeless) Ev^{∗}.

In the case of our physical applications: Ev^{∗} will contain the possible physical properties of the physical system. In CM: measurable subsets of the phase space Ω. In QT: closed subspaces (or equivalently, projection operators) in the appropriate Hilbert space H.

Any timeless state s will assign to any timeless event α a value in the interval [0, 1]:

s(α) ∈ [0, 1].

A state s is said to verify an event α (s ⊧ α) iff s(α) = 1. Similarly for all states in S_{t} and all events in Ev_{t}.

The set Ev^{∗} of the timeless events has a structure (for simplicity all Ev_{t} are assumed to be isomorphic to Ev^{∗}). We will consider only examples of structures that are partially ordered by a relation ⊑.

In the case of CM, Ev^{∗} gives rise to a Boolean algebra (a convenient subalgebra of the power-set of Ω). Similarly, in QT, the structure of Ev^{∗} can be identified with the algebra of all closed subspaces of H (a particular example of a non distributive orthomodular lattice). As a consequence one obtains that, differently from the classical mechanical case, quantum events do not have a classical logical behaviour.

We will call historical sequence a sequence of events ⟨α_{t_{1}}, …, α_{t_{n}}⟩, where each α_{t_{i}} is in Ev_{t_{i}}. Of course, the algebraic structure of each Ev_{t_{k}} can be naturally transferred to the set of all historical sequences (∏_{i=1}^{n} Ev_{t_{i}}). We will call temporal support ([7]) of the historical sequence ⟨α_{t_{1}}, …, α_{t_{n}}⟩, the time-sequence ⟨t_{1}, …, t_{n}⟩. Composition between temporal supports and historical sequences with disjoint temporal supports is defined in the expected way.

4) Histev is a function that assigns to each time-sequence ⟨t_{1}, …, t_{n}⟩ the set of the historical events Histev^{⟨t_{1},... ,t_{n}⟩} at time ⟨t_{1}, …, t_{n}⟩. This set is equipped with a structure.

Physical examples:

In CM: Histev^{⟨t_{1},... ,t_{n}⟩} is a σ-field of subsets of the cartesian product of

S_{t_{1}} × … × S_{t_{n}}.

In other words, a historical event (at time ⟨t_{1}, …, t_{n}⟩) is a set of sequences ⟨s_{t_{1}}, …, s_{t_{n}}⟩, where any s_{t_{i}} is a pure state of the system at time t_{i}.

In QT: Histev^{⟨t_{1},... ,t_{n}⟩} can be identified with the set of the closed subspaces of the tensor product

H_{t_{1}} ⊗ … ⊗ H_{t_{n}},

where each H_{t_{i}} represents the Hilbert space of the system at time t_{i}.

Any historical sequence of events must be represented by a historical event. However, not all historical events will represent historical sequences. For instance, in QT the sequence ⟨α_{t_{1}}, …, α_{t_{n}}⟩ (where each α_{t_{i}} is a closed subspace) will be represented by the tensor product α_{t_{1}} ⊗ … ⊗ α_{t_{n}} of the closed subspaces α_{t_{1}}, …, α_{t_{n}}. Such a product is a closed subspace in the tensor-product space H_{t_{1}} ⊗ … ⊗ H_{t_{n}}. Of course, not all the closed subspaces in the tensor-product space will have this factorized form. For instance, the orthocomplement of a factorized historical event α_{t_{1}} ⊗ … ⊗ α_{t_{n}} (which represents the logical negation of the original event) will not generally correspond to any historical sequence of events. Our physical examples naturally suggest to require the following general conditions:

(4.1) For any time t_{k} and any time-sequence ⟨t_{1}, …, t_{k}, …, t_{n}⟩, there exists a function f that maps Ev_{t_{k}} into Histev^{⟨t_{1},... ,t_{n}⟩}:

f : Ev_{t_{k}} → Histev^{⟨t_{1},... ,t_{n}⟩}.

Further, such f is an embedding that preserves the algebraic structure of Ev_{t_{k}}.

This guarantees that any event at time t_{k} is represented by a historical event in any longer time-interval. For instance, in the case of closed subspaces, f(α_{t_{k}}) will be 1_{t_{1}} ⊗ … ⊗ α_{t_{k}} ⊗ … ⊗ 1_{t_{n}} , where 1_{t_{i}} represents the certain event at time t_{i}.

(4.2) For any time sequence ⟨t_{1}, …, t_{n}⟩, there is a function g that transforms any historical sequence ⟨α_{t_{1}}, …, α_{t_{n}}⟩ of events into a historical event η^{⟨t_{1},... ,t_{n}⟩} of Histev^{⟨t_{1},... ,t_{n}⟩}:

g : ⟨α_{t_{1}}, …, α_{t_{n}}⟩ ↦ η^{⟨t_{1},... ,t_{n}⟩}.

Further, such g is a homomorphism of ∏_{i=1}^{n} Ev_{t_{i}} into Histev^{⟨t_{1},... ,t_{n}⟩}.

Definition 2.2 Two historical sequences ⟨α_{t_{1}}, …, α_{t_{n}}⟩ and ⟨β_{t_{1}}, …, β_{t_{n}}⟩ are called equivalent (⟨α_{t_{1}}, …, α_{t_{n}}⟩ ≈ ⟨β_{t_{1}}, …, β_{t_{n}}⟩) iff g(⟨α_{t_{1}}, …, α_{t_{n}}⟩) = g(⟨β_{t_{1}}, …, β_{t_{n}}⟩).

Since g is a homomorphism, the equivalence relation ≈ turns out to be a congruence on the algebraic structure induced on ∏_{i=1}^{n} Ev_{t_{i}}. Further, the relation ≈ is required to satisfy the following condition: let ⟨t_{m}, …, t_{n}⟩ and ⟨t_{i}, …, t_{j}⟩ be two disjoint temporal supports: if ⟨α_{t_{m}}, …, α_{t_{n}}⟩ ≈ ⟨α′_{t_{m}}, …, α′_{t_{n}}⟩ and ⟨β_{t_{i}}, …, β_{t_{j}}⟩ ≈ ⟨β′_{t_{i}}, …, β′_{t_{j}}⟩, then

⟨α_{t_{m}}, …, α_{t_{n}}⟩ ∘ ⟨β_{t_{i}}, …, β_{t_{j}}⟩ ≈ ⟨α′_{t_{m}}, …, α′_{t_{n}}⟩ ∘ ⟨β′_{t_{i}}, …, β′_{t_{j}}⟩.

In other words, the relation ≈ is preserved under composition (∘) of historical sequences.

Any historical event η^{⟨t_{1},... ,t_{n}⟩} that represents (via g) a historical sequence will be called a history ^{1}. We will indicate by Hist^{⟨t_{1},... ,t_{n}⟩} the subset of Histev^{⟨t_{1},... ,t_{n}⟩} that contains all the histories. Instead of g(⟨α_{t_{1}}, …, α_{t_{n}}⟩) we will simply write: η^{⟨α_{t_{1}},... ,α_{tn}⟩}.

On this basis one can naturally define a notion of historical truth. This is a semantic notion that may hold between a sequence of states and a historical event. Let us first consider the case where both the statesequence and the historical event refer to the same temporal support ⟨t_{1}, …, t_{n}⟩.

Definition 2.3 Restricted definition of historical truth

(⟨s_{t_{1}}, …, s_{t_{n}}⟩ verifies η: ⟨s_{t_{1}}, …, s_{t_{n}}⟩ ⊧ η)

We will distinguish the case of histories from that of historical events that do not represent histories.

a) Let η be the history η^{⟨α_{t_{1}},... ,α_{tn}⟩}. Then: ⟨s_{t_{1}}, …, s_{t_{n}}⟩ ⊧ η iff for any sequence ⟨α_{t_{1}}, …, α_{t_{n}}⟩ s.t. g(⟨α_{t_{1}}, …, α_{t_{n}}⟩) = η: s_{t_{i}} ⊧ α_{t_{i}}, for any s_{t_{i}} and α_{t_{i}} (1 ≤ i ≤ n).

b) Let η be a historical event (belonging to Histev^{⟨t_{1},... ,t_{n}⟩}) that is not a history. Then: ⟨s_{t_{1}}, …, s_{t_{n}}⟩ ⊧ η iff for at least one history δ^{⟨α_{t_{1}},... ,α_{tn}⟩}:

i) δ^{⟨α_{t_{1}},... ,α_{tn}⟩} ⊑ η, where ⊑ is the partial order of the event structure;

ii) ⟨s_{t_{1}}, …, s_{t_{n}}⟩ ⊧ δ^{⟨α_{t_{1}},... ,α_{tn}⟩}.

Our truth definition can be naturally extended also to the case where a state-sequence and a historical event refer to different time-sequences. Let us first introduce a procedure that permits us to normalize any history to a given time-sequence.

Definition 2.4 Normalization of a historical-sequence to a given time sequence

Let ⟨α_{t_{m}}, …, α_{t_{n}}⟩ be a historical sequence and let ⟨t_{i}, …, t_{j}⟩ be any time-sequence. The normalization of ⟨α_{t_{m}}, …, α_{t_{n}}⟩ to ⟨t_{i}, …, t_{j}⟩ is the following historical sequence:

⌈⟨α_{t_{m}}, …, α_{t_{n}}⟩⌉^{⟨t_{i},... ,t_{j}⟩} := ⟨β_{t_{i}}, …, β_{t_{j}}⟩ ,

1In [7], historical sequences are called history-filters, while historical events are called history -propositions.

where

β_{t_{k}} = \begin{cases}α_{t_{k}}, & if t_{k} is in ⟨t_{m}, …, t_{n}⟩; \\ 1_{t_{k}} & otherwise. \end{cases}

(1_{t_{k}} is the certain event at time t_{k}).

Accordingly, the normalization of a history will be automatically determined (via g):

Definition 2.5 Normalization of a history to a given time-sequence

Let η^{⟨α_{tm},... ,α_{tn}⟩} be a history and ⟨t_{i}, …, t_{j}⟩ be a time-sequence. The normalization of η^{⟨α_{tm},... ,α_{tn}⟩} to ⟨t_{i}, …, t_{j}⟩ is the history

⌈η^{⟨α_{tm},... ,α_{tn}⟩}⌉^{⟨t_{i},... ,t_{j}⟩}

that is univocally determined by the historical sequence

⌈⟨α_{t_{m}}, …, α_{t_{n}}⟩⌉^{⟨t_{i},... ,t_{j}⟩}.

One can easily prove that Definition 2.5 is a good definition since it is independent of the choice of the representative.

On this basis we can define a general notion of historical truth:

Definition 2.6 General definition of historical truth

(⟨s_{t_{1}}, …, s_{t_{n}}⟩ verifies η^{⟨t_{i},... ,t_{j}⟩}: ⟨s_{t_{1}}, …, s_{t_{n}}⟩ ⊧ η^{⟨t_{t_{i}},... ,t_{t_{j}}⟩})

Let η^{⟨t_{i},... ,t_{j}⟩} be a historical event.

⟨s_{t_{1}}, …, s_{t_{n}}⟩ ⊧ η^{⟨t_{i},... ,t_{j}⟩} iff there is a history δ^{⟨t_{i},... ,t_{j}⟩} s.t.:

i) δ^{⟨t_{i},... ,t_{j}⟩} ⊑ η^{⟨t_{i},... ,t_{j}⟩};

ii) ⟨s_{t_{1}}, …, s_{t_{n}}⟩ ⊧ ⌈δ^{⟨t_{i},... ,t_{j}⟩}⌉^{⟨t_{1},... ,t_{n}⟩}.

A historical sequence will be called normal when all historical events can be normalized to any time sequence.

It turns out that any historical structure where all Histev^{⟨t_{1},... ,t_{n}⟩} are structured as complete lattices is trivially normal.

5) Op, the operation function, is a function that associates to any pair of time t_{i}, t_{j} a set of operations O_{t_{i}}^{t_{j}}

Op : ⟨t_{i}, t_{j}⟩ ↦ O_{t_{i}}^{t_{j}},

where O_{t_{i}}^{t_{j}} is a subset of a set of admissible operations O ⊆ \{f | \overline{S^{∗}} → S^{∗}\} (\overline{S^{∗}} ⊆ S^{∗}). In other words, admissible operations transform states into states.

Some operations in O_{t_{i}}^{t_{j}} may represent spontaneous evolutions whereas other operations may represent state transformations induced by an action. A typical action is a test performed in order to check whether a certain property α holds^{2}. Of course, physical measurements are paradigmatic examples of action of this kind. We will indicate by f^{α}(s) the transformation of a state s induced by an action that has been performed in order to check whether the object in state s satisfies the property α. On this basis a class of accessibility relations can be naturally defined in terms of our operations (differently from Kripke semantics, where accessibility relations are usually dealt with as primitive). Let s, u represent timeless states. States s and u are called accessible in the time interval [t_{i}, t_{j}] (we will write Acc_{t_{i}}^{t_{j}}(s, u)) iff there exists an operation f ∈ O_{t_{i}}^{t_{j}} s.t.

u = f(s).

States s and u are absolutely accessible (Acc(s, u)) iff for at least two times t_{i}, t_{j}:

Acc_{t_{i}}^{t_{j}}(s, u).

Let α be an event. The states s, u are α-accessible (Acc^{α}(s, u)) iff there exists an operation f^{α} s.t.

u = f^{α}(s).

Since all S_{t} are copies of S^{∗} our accessibility relations are automatically transferred to pairs of states that may belong to different S_{t}.

6) D is a (possibly empty) set of decoherence functionals d ([7]). From the intuitive point of view, d(η, δ) measures the degree of interference between the historical events η and δ.

3 Dynamic and temporal operators

Different logical operators that have a temporal or a dynamic meaning can be naturally defined in our semantics.

Definition 3.1 The temporal conjunction and then ⊓↗ Let η^{⟨t_{m},... ,t_{n}⟩}, δ^{⟨t_{i},... ,t_{j}⟩} be two historical events. Generally ⊓↗ is a partial operation that turns out to be always defined in the particular case of a normal historical structure where any Histev^{⟨t_{1},... ,t_{n}⟩} gives rise to a lattice (where ⊓ and ⊔ represent the infimum and the supremum, respectively).

η^{⟨t_{m},... ,t_{n}⟩}⊓↗ δ^{⟨t_{i},... ,t_{j}⟩} := \begin{cases}0^{⟨t_{m},... ,t_{n}⟩∘⟨t_{i},... ,t_{j}⟩}, if ⟨t_{m}, …, t_{n}⟩ does not preceed \\ ⟨t_{i}, …, t_{j}⟩ w.r.t the order ≤; \\ ⌈η⌉^{⟨t_{m},... ,t_{n}⟩∘⟨t_{i},... ,t_{j}⟩} ⊓ ⌈δ⌉^{⟨t_{m},... ,t_{n}⟩∘⟨t_{i},... ,t_{j}⟩}, if this inf \\ exists in Histev^{⟨t_{m},... ,t_{n}⟩∘⟨t_{i},... ,t_{j}⟩}; \\ undefined, otherwise. \end{cases}

2See von Wright [14].

As an example, suppose two histories η^{⟨α_{t_{1}},α_{t_{2}}⟩}, δ^{⟨β_{t_{3}},β_{t_{4}}⟩} (t_{1} < t_{2} < t_{3} < t_{4}). According to our definition we will have:

η^{⟨α_{t_{1}},α_{t_{2}}⟩}⊓↗δ^{⟨β_{t_{3}},β_{t_{4}}⟩} = η^{⟨α_{t_{1}},α_{t_{2}},1_{t_{3}},1_{t_{4}}⟩} ⊓ δ^{⟨1_{t_{1}},1_{t_{2}},β_{t_{3}},β_{t_{4}}⟩}
= γ^{⟨α_{t_{1}}⊓1_{t_{1}},α_{t_{2}}⊓1_{t_{2}},1_{t_{3}}⊓β_{t_{3}},1_{t_{4}}⊓β_{t_{4}}⟩}
= γ^{⟨α_{t_{1}},α_{t_{2}},β_{t_{3}},β_{t_{4}}⟩}.

We obtain in this way the expected meaning of a temporal conjunction: η^{⟨α_{t_{1}},α_{t_{2}}⟩} and then δ^{⟨β_{t_{3}},β_{t_{4}}⟩} is the history determined by the historical sequence ⟨α_{t_{1}}, α_{t_{2}}, β_{t_{3}}, β_{t_{4}}⟩. A dynamic implication

Let us refer to set Ev^{∗} of all timeless events and to the set S^{∗} of all timeless states. Let α ∈ Ev^{∗}. We define first a function α that assign to each β ∈ Ev^{∗} a set of timeless states:

α : Ev^{∗} → P(S^{∗}) (where P(S^{∗}) is the power-set of S^{∗})

satisfying the condition:

s ∈ α β iff ∀u [Acc^{α}(s, u) ⇒ u ⊧ β] .

¿From the intuitive point of view, s ∈ α β has the following meaning: suppose we test α on a state s and we obtain a positive result; then, any state into which s is transformed after such a test verifies β. Of course, α β does not necessarily determine an event. In the case where Ev^{∗} has the structure of a complete lattice, one can easily define the following total operation:

α : Ev^{∗} → Ev^{∗},

where

α β := ⊓ {δ | ∀u ∈ α β : u ⊧ δ}

Otherwise, α will represent a partial operation.

In the particular case of the lattice of all closed subspaces in a Hilbert space H the dynamic implication is always defined and corresponds to the usual quantum logical (material) implication (which is also called Sasaki implication).

As is well known, differently from classical logic, α′ ⊔ β (where ′ is the orthocomplement) does not represent a good conditional operation in quantum logic. Actually, it may happen that in a given orthomodular lattice, α′ ⊔ β is equal to 1, even if α does not preceed β according to the lattice-order. From the logical point of view, this means that a sentence like “not A or B” might be true in a given (algebraic) model, even if A does not imply B in the same model.

However, a particular variant of α′ ⊔ β (which is equivalent to α′ ⊔ β in all Boolean lattices) permits us to define a good quantum logical conditional. It is sufficient to put:

α → β := α′ ⊔ (α ⊓ β).

One can easily show that for closed subspaces α, β:

α β = α → β.

Of course, such a relation holds, only if we interpret the accessibility relation Acc^{α} in the “natural” quantum theoretical way. In other words:

Acc^{α}(s, u) iff u is the result of the projection of s over the closed subspace α.

This shows that the standard logical implication admits a natural dynamic interpretation. In other words, even the orthodox version of quantum logic (which is usually described as a “static logic”) seems to have some ”hidden” dynamic features.

4 Quantum histories and quantum Turing machines

Let us first introduce a definition of quantum Turing machine, following a quite elegant abstract approach, that has been recently proposed by Gudder ([5]).

Definition 4.1 A quantum Turing machine, whose tape is identified with the set of the integers Z, is a structure

M = ⟨I, S, δ, H⟩

where:

1) I is a finite alphabet, containing a blank symbol ♯.

2) S is a set of memory states, containing an initial state s_{0} and a final state s_{f}. Similarly to classical Turing machines, consider the cartesian product

S × I × I × {L, R} × S.

The interpretation of any element ⟨s, x, y, d, r⟩ (where d ∈ {R, L}) of our product will be the following: the machine M is in state s, sees the symbol x, prints the symbol y, goes to d and finally transits to state r. Any ⟨s, x, y, d, r⟩ represents a computational event.

3) δ is the amplitude function that assigns to any computational event ⟨s, x, y, d, r⟩ a complex number. The number | δ(⟨s, x, y, d, r⟩) |^{2} will represent the probability of the computational event ⟨s, x, y, d, r⟩.

M evolves in time assuming different states. A configuration (or basic state) of M is a triplet:

φ = ⟨n, s, w⟩

where n is a location of M on the tape, s is a memory state and w is a word, describing the condition of the tape. Similarly to the classical case, a word w can be described as function

w : Z → I with the usual restriction: for almost all n ∈ Z: w(n) = ♯. Hence, a word corresponds to a finite sequence of symbols labelled by the cells of the tape. Instead of w(n) we will also write w_{n}.

Let B be the set of all possible basic states φ (which describe definite configurations of M).

4) H is a Hilbert space with orthonormal basis B.

The amplitude function δ determines a linear operator

U : H → H.

It is sufficient to define U on B:

for any φ ∈ B, U(φ) will generally be a superposition state:

∑_{i} c_{i}φ_{i}.

Let φ = ⟨n, s, w⟩ and let w_{n} represent the symbol printed in the cell n.

Let us consider the set of all computational events starting with the pair ⟨s, w_{n}⟩ (which is determined by φ):

⟨s, w_{n}, y, d, r⟩

for all possible y, d, r.

For any y, d, r, we define the complex number c_{y,d,r} and the vector φ_{y,d,r} as follows:

c_{y,d,r} = δ(⟨s, w_{n}, y, d, r⟩)
φ_{y,d,r} = ⟨n(d), r, w(y, n)⟩ .

Where:

n(d) = \begin{cases}n + 1, if d = R; \\ n − 1, if d = L, \end{cases}

and:

w(y, n)_{m} = \begin{cases}y, if m = n; \\ w_{m}, otherwise. \end{cases}

Now, let us define:

U(φ) = ∑_{y,d,r} c_{y,d,r}φ_{y,d,r}.

We assume the following restriction: U must be a unitary operator. Obviously, such a restriction represents a constraint on the amplitude function δ.

How can the action of our unitary operator U be interpreted? Let ψ_{0} = ⟨0, s_{0}, w⟩ represent the element of B that is the initial state, where the word w corresponds to the input for M. The state U(ψ_{0}) will represent the evolution of the initial state ψ_{0} after one step. Generally U^{t}(ψ_{0}) will represent the evolution of ψ_{0} after t steps (we might also say: at time t).

What does it mean that our machine M halts at time t with a certain probability value? In order to answer this question, let us first introduce the notion of final basic state.

Definition 4.2 A final basic state is a vector φ ∈ B s.t.:

φ = ⟨n, s_{f}, w⟩ ,

where s_{f} is the final memory state.

We will denote by B^{F} set of all final basic states.

Definition 4.3 The probability that M halts at time t (P rob^{H}(t)) is defined as follows:

P rob^{H}(t) = ∑_{φ∈B^{F}} | (U^{t}(ψ_{0}), φ) |^{2}

(where (U^{t}(ψ_{0}), φ) represents the inner product of U^{t}(ψ_{0}) and φ).

¿From an intuitive point of view, any sequence

⟨ψ_{0}, ...., U^{t}(ψ_{0})⟩

can be regarded as a knowledge path (or an epistemic history) of M. Such a sequence naturally gives rise to a graph, where each branch has the form:

⟨ψ_{0}, φ_{1}, ..., φ_{t}⟩

with φ_{i} ∈ B.

These basic sequences ⟨ψ_{0}, φ_{1}, ..., φ_{t}⟩ are determined as follows. For any k (0 ≤ k ≤ t), consider

U^{k}(ψ_{0}) = ∑_{i} c_{i}φ_{i} (with c_{i} ≠ 0).

We require:

φ_{k} = φ_{i}, for a given φ_{i} occurring in ∑_{i} c_{i}φ_{i}.

Since states correspond to unidimensional closed subspaces of H, any knowledge path of M represents a historical sequence (in the sense of Definition 2.1).

On this basis, one can distinguish at least two different notions of computation.

Definition 4.4 A strong computation of M is a knowledge path

⟨ψ_{0}, ...., U^{t}(ψ_{0})⟩

where M halts at time t with probability 1.

Definition 4.5 A weak computation is a knowledge path

⟨ψ_{0}, ...., U^{t}(ψ_{0})⟩

where M halts at t with probability different from 0.

In this framework, one can naturally introduce some semantic notions (following a standard quantum logical style).

Definition 4.6 A basic state φ knows (or accepts) a word w (φ ⊧ w) iff there is a location n and a memory state s such that

φ = ⟨n, s, w⟩

Definition 4.7 A state ψ possibly knows (or possibly accepts) a word w (ψ ⊪ w) iff ψ = ∑ c_{i}φ_{i} with c_{i} ≠ 0 and for at least one φ_{i},

φ_{i} ⊧ w.

Definition 4.8 M possibly knows a word w at time t (M ⊪_{t} w) iff

U^{t}(ψ_{0}) ⊪ w.

Definition 4.9 M knows a word w at time t (M ⊧_{t} w) iff

1) M ⊪_{t} w;

2) M halts at time t with probability 1.

Definition 4.10 The proposition C(w) of a word w is the smallest closed subspace that includes

{φ ∈ B | φ ⊧ w} .

Suppose we equip our language with the logical connectives ¬ and ∧ (where the atomic formulas can be identified with particular words). Then we can give the usual (quantum logical) semantic definitions:

Definition 4.11

ψ ⊪ ¬α iff ψ ∈ C(α)′;
ψ ⊪ α ∧ β iff ψ ∈ C(α) ∩ C(β).

Suppose M ⊪_{t} α and M ⊧_{t} α are defined as above. It may happen:

∃t : M ⊧_{t} ¬α

And

∃t : M ⊧_{t} α

In other words, the negation ¬ shows in this framework a weak paraconsistent behaviour (similarly to a negation by failure).

References

[1] M. L. Dalla Chiara and R. Giuntini, “A fuzzy dynamic semantics for quantum histories”, Soft Computing, 2 (1997), 137–142.

[2] M.L. Dalla Chiara and R. Giuntini, “Dynamic ideas in quantum logic”, to appear.

[3] A. Dvurečenskij, “Tensor product of difference posets”, Transactions of the American Mathematical Society, 347 (1995), 1043–1057.

[4] M. Gell-Mann and J. Hartle, “Alternative decohering histories in quantum mechanics”, in K.K. Phua and Y. Yamaguchi (eds.), Proceedings of the 25th International Conference on High Energy Physics, World Scientific, Singapore, 1990.

[5] S. Gudder, “Quantum computers”, preprint, 1999.

[6] D. Harel, “Dynamic logic”, in D. Gabbay and F. Guenthner (eds.), Handbook of Philosophical Logic, III, Kluwer, Dordrecht, 1984.

[7] C.J. Isham, “Quantum logic and the histories approach to quantum theory”, Journal of Mathematical Physics, 35 (1994), 2157–2185.

[8] C.J. Isham and N. Linden, “Quantum temporal logic and decoherence functionals in the histories approach to generalized quantum theory”, Journal of Mathematical Physics, 35 (1994), 5452–5475.

[9] P. Mittelstaedt, “Relativistic quantum logic”, International Journal of Theoretical Physics, 22 (1983), 293–314.

[10] P. Mittelstaedt and E.W. Stachow, “Analysis of the EPR-experiment by relativistic quantum logic”, International Journal of Theoretical Physics, 22 (1983), 517–540.

[11] R. Omnès, The Interpretation of Quantum Mechanics, Princeton University Press, 1994.

[12] B. Penther, “A dynamic logic of action”, Journal of Logic, Language, and Information, 3 (1994), 169–210.

[13] S. Pulmannová, “Difference posets and the histories approach to quantum theories”, preprint.

[14] G. von Wright, “The logic of action”, in N. Rescher (ed.), The Logic of Action and Decision, University of Pittsburgh Press, 1967.