G B Sequentcalculusandquantumparallelism 5thEuropeanCongressofMathematics-Amsterdam,July14-182008

5th European Congress of Mathematics - Amsterdam, July 14-18 2008

Sequent calculus and quantum parallelism

G ^IULIA B ^ATTILOTTI

Department of Philosophy, University of Florence, ITALY

Challenge: find an explanation to the quantum computational speed up (due to superposition and entanglement) in terms of logical proofs.

Proposed tools: a predicative sequent calculus in the frame- work of basic logic ...

The cube of logics

Basic logic B is a core for sequent calculus. Its rules for connectives are given through meta-linguistic links. It is ex- tended to calculi for well-known logics by the addition of structural rules. This is representable in the following cube:

B ∼ Basic Logic

BL ∼ Linear Intuitionistic BR ∼ Dual Linear Intuitionistic BS ∼ Paraconsistent Quantum

BLS ∼ Intuitionistic BRS ∼ Dual Intuitionistic BLR ∼ Linear

BLRS ∼ Classical

We look for a sequent calculus which describes quantum parallelism as an extension of B

Connectives from metalinguistic links

In basic logic we consider the following metalinguistic links between assertions: and, yield, forall.

1. yield links two assertions at a different level, in a sequen- tial way.

2. and links two assertions at the same level, in a parallel way.

3. forall links assertions with a variable in common. The variable is the reason of the link.

Let us represent assertions by sequents. Then logical connec- tives and their rules in sequent calculus are the result of im- porting the links into the object level. This is obtained solving the following definitory equations:

1. Γ ⊢ A → B ≡ Γ, A ⊢ B

where Γ, A ⊢ B represents the sequential link between A and B, in a context Γ. Then implication → is a way to import sequentiality.

2. Γ ⊢ A&B ≡ Γ ⊢ A Γ ⊢ B Γ ⊢ A · B ≡ Γ ⊢ A, B

where the couple of sequents Γ ⊢ A Γ ⊢ B and the comma in the sequent Γ ⊢ A, B are the additive and mul- tiplicative way to represent the parallel link between A and B. Then parallelism is imported in two ways: the additive (by the additive conjunction &) and the multi- plicative (by the multiplicative disjunction, here denoted by ·).

3. Γ ⊢ (∀x ∈ D)A(x) ≡ Γ, z ∈ D ⊢ A(z), z not free in Γ where Γ, z ∈ D ⊢ A(z) gathers all assertions A(z) de- pending on a free variable on the domain D. This is im- ported by the quantifier ∀. Since Γ does not depend on z, ∀ inherits the features of the additive parallelism, en- forced by the common variable.

(Equations corresponding to the additive disjunction ⊕, the multiplicative conjunction ⊗ and the existential quantifier ∃ can be obtained symmetrically).

Combining additive and multiplicative parallelism

The distributive law A · (B&C) = (A&B) · (A&C) is provable in BR.

Distributivity is extended to the predicative case as follows:

(∀x ∈ D

)A(x)·(∀x ∈ D

)B(x) = (∀x ∈ D

)(∀y ∈ D

)A(x)·B(y) This requires independent variables in A, B. Computational disadvantage: exponential increasing of complexity in the number of independent variables.

Distributivity with dependent variables:

(∀x ∈ D)A(x) · (∀x ∈ D)B(x) = (∀x ∈ D)A(x)) · B(x) fails everywhere in the cube. Reason: consistency!!! Compu- tational advantage: no exponential increasing of complexity with dependent variables.

It would be proved by the following parallel rule:

Γ, z ∈ D ⊢ A(z), B(z)

Γ ⊢ (∀x ∈ D)A(x), (∀x ∈ D)B(x) ∀k

which fails due to restriction on variables on the right, neces- sary when formulae can pass from right to left. But this does not happen in B!

A new predicative connective

Idea: good = computationally convenient (in a paraconsistent framework)

Adopting the above ∀k rule in B would cause inconsistency in its extensions. A better idea to obtain a ∀k rule: consider a common variable as a further link. In Γ ⊢ A(z), B(z) the comma says also ”there is a variable in common, or there used to be a variable in common above in the derivation”. So we write ,

for it, and put the definitory equation:

Γ ⊢ A 1 B ≡ Γ ⊢ A,

B

The common link ,

allows the parallel application of the ∀- rule:

Γ, z ∈ D ⊢ A(z),

B(z)

Γ ⊢ (∀x ∈ D)A(x),

(∀x ∈ D)B(x) ∀k It allows to prove distributivity in the following form:

(∀x ∈ D)A(x) 1 (∀x ∈ D)B(x) = (∀x ∈ D)A(x)) 1 B(x) This creates a unique multiplicative-additive quantifier ⊲⊳

(A(x); B(x)) ≡ (∀x ∈ D)A(x) 1 (∀x ∈ D)B(x) = (∀x ∈ D)(∀x ∈ D)A(x)) 1 B(x) to exploit dependent variables. It is defined by the equation:

Γ ⊢⊲⊳

(A(x); B(x)) ≡ Γ, z ∈ D ⊢ A(z),

B(z) Substitution of the variable z by a closed term t destroys the ,

-link. Γ ⊢ A(z),

B(z) becomes Γ ⊢ A(t), B(t) where the comma is the usual comma of sequent calculus.

Quantum Computational Speed Up

Quantum computational speed up is due to the so called mas- sive quantum parallelism, that is the parallel computation cre- ated by the peculiar quantum features of information, namely quantum superposition and quantum entanglement. Quan- tum superposition is the co-existence, in the same particle, of different states, one of which will be measured.

A quantum unit of information (qubit) is represented by the vector |qi

|qi = a|0i ⊕ b|1i

where a, b are complex numbers (probability amplitudes) s.t.

|a|

+ |b|

= 1 and |0i, |1i are two orthogonal unitary vectors.

|qi is then the superposition of the two states |0i, |1i, where

|0i will be measured with probability |a|

and |1i with proba- bility |b|

. Two qubits are maximally entangled when they are represented by one of the following four states (Bell’s states)

|q

q

i = 1/ √

2|00i±1/ √

2|11i |q

q

i = 1/ √

2|01i±1/ √ 2|10i This means that the two states |0i and |1i are equally probable after measurement, and that the measurement of one of the two is determined by the measurement of the other.

Interpreting quantum superposition by quantifiers

In probability theory an experiment is a random variable Z with an associ- ated probability measure p^Z.

LetA be a quantum system. A quantum measurement on A is an experi- ment, considering the possible outcomes as a random variable. The set of possible outcomes is an orthonormal basis B of the Hilbert space ofA. Let D= D(Z, p^Z) = {(z, p{Z = z} : z ∈ B} such set. Let Γ a set of hypothesis of the experiment. Of course, they cannot depend on the outcome of the experiment.

The assertion Γ z∈ D ⊢ A(z) is ”forall possible outcomes z in D, in the hyporthesis Γ, the possible result of the measurement ofA is z”. Since Γ does not depend on z, we put

Γ ⊢ (∀x ∈ D)A(x) ≡ Γ z ∈ D ⊢ A(z)

Then the proposition (∀x ∈ D)A(x) represents quantum superposition.

Example:A a particle, D given by the measurement of the spin of A along the z axis. D has got two elements (the two directions of the spin). (∀x ∈ D)A(x) represents the superposed state of the two directions of the spin along the z-axis.

Quantum entanglement

Let A and B be two entangled particles, for example two electrons with opposite spin. A measurement of the spin along the z axis, per- formed onA or on B, is equally described by the assertion Γ z ∈ D ⊢ A(z),^zB(z). The corresponding state is then described by the proposition

⊲⊳x∈D(A(x); B(x)).

Alan Turing wrote:

”. . . if a machine is expected to be infallible, it cannot be also intelli- gent. There are several theorems [Goedel’s incompleteness theorems]

which say almost exactly that. But these theorems say nothing about how much intelligence may be displayed if a machine makes no pre- tence at infallibility.”

References

[1] L. BOS, M. CALIARI, S. DEMARCHI, M. VIANELLO ANDY. XU, Bivariate Lagrange in- terpolation at the Padua points: the generating curve approach, J. Approx. Theory 143 (2006).

[2] L. BOS, S. DEMARCHI, M. VIANELLO ANDY. XU, Bivariate Lagrange interpolation at the Padua points: the ideal theory approach, Numer. Math. 108 (2007).

[3] M. CALIARI, S. DEMARCHI, A. SOMMARIVA ANDM. VIANELLO, Fast interpolation and cubature at the Padua points in Matlab/Octave, in preparation.

[4] M. CALIARI, S. DEMARCHI ANDM. VIANELLO, Bivariate polynomial interpolation on the square at new nodal sets, Appl. Math. Comput. 162 (2005).

[5] M. CALIARI, S. DEMARCHI ANDM. VIANELLO, Padua2D: Lagrange Interpolation at Padua Points on Bivariate Domains, ACM Trans. Math. Software 35-3 (2008).

code available athttp://www.math.unipd.it/∼marcov/CAAsoft.html [6] I.P. OMELYAN ANDV.B. SOLOVYAN, Improved cubature formulae of high degree of exactness

for the square, J. Comput. Appl. Math. 188 (2006).

[7] R.J. RENKA ANDR. BROWN, Algorithm 792: Accuracy tests of ACM algorithms for interpo- lation of scattered data in the plane, ACM Trans. Math. Software 25 (1999).

[8] A. SOMMARIVA, M. VIANELLO ANDR. ZANOVELLO, Nontensorial Clenshaw-Curtis cu- bature, Numer. Algorithms, to appear.

[9] L. SZILI ANDP. VERTESI, On Multivariate Projection Operators, to appear.

[10] L.N. TREFETHEN, Is Gauss quadrature better than Clenshaw-Curtis?, SIAM Rev. 50 (2008).

[11] Y. XU, Lagrange interpolation on Chebyshev points of two variables, J. Approx. Theory 87 (1996).