Quantum Computation and Information Seminar 

We propose and study a discrete time quantum walk on a line with two particles. We show how the entanglement and the relative phase between the states describing the coin degree of freedom of each particle will influence the evolution of the quantum walk. In particular, the probability to find one particle in a certain position after N steps of the walk, as well as the average distance between the two particles (amongst other variables that we study) can be larger or smaller than the case of two unentangled particles, depending on the initial conditions we choose. This resource can then be tuned according to our needs, in particular to enhance a given application (algorithmic or other) based on a quantum walk. Some examples will be discussed.

Conclusão da sessão anterior.

Apresentação e relacionação de várias formulações da mecânica quântica.

Conclusion of the previous talk.

We will give an idea of some of John Bell's insights into the nature of quantum theory and of his famous inequalities. Then, we will see how string theory might force us to take another look at the Heisenberg uncertainty principle.

Based on a paper of L. Hardy we show that quantum theory can be derived from five reasonable axioms. We gain insight into the need for complex numbers and into the relationship between quantum theory and probability theory.

Quantum versions of finite state automata and push-down automata are presented. Analogs of several classical theorems, including pumping lemmas and closure properties are discussed. The talk is based on the work by C. Moore and J. P. Crutchfield.

Conclusion of the previous talk.

A sketch is made of a new quantum logic endowed with exogenous semantics. We start by presenting the exogenous approach (classical models as outcomes in a probability space) to probabilistic logic and then show how the exogenous idea (quantum superposition of classical models) can be used to devise a suitable quantum propositional logic. The resulting logic supports classical, quantum and probabilistic reasoning. Future work towards a dynamic quantum logic (unitary transformations as transitions) is also discussed. The talk reports ongoing joint work with P. Mateus, A. Pacheco and C. Sernadas.

Conclusion of the previous talk.

We start by presenting the concept of quantum random walk (QRW) and some of its applications. The class of QRW's without destructive interference is studied and several results are obtained by adapting the theory of Markov chains (asymptotic distribution, ergodic theorem). Some of these results are discussed in detail. A sketch of the proof that this class is dense over the class of all QRW's is presented. The talk reports ongoing joint work with Y. Omar, A. Pacheco and A. Sernadas.

The entanglement of quantum states was first pointed out by E. Schrödinger in 1935 as "the characteristic trait of quantum mechanics", but only in the last decade did it start becoming better understood and seen as a resource for many applications. Entanglement offers correlations with no classical equivalent that can be used for quite novel and unique information processing tasks, such as quantum teleportation, quantum dense coding of information and unconditionally secure quantum cryptographic key distribution, amongst others. Entanglement may also be a sufficient condition for the speed-up of certain quantum algorithms over their classical counterpart and is an important tool for quantum error correction. Yet, associated to the issue of non-locality since the EPR problem (Einstein, Podolsky and Rosen, 1935), and despite the progress allowed by Bell's theorem in 1964 and subsequent results, entanglement remains one of the most surprising and mysterious aspects of quantum mechanics. This talk will attempt to introduce the essential ideas concerning entanglement and explain how it can be used for the teleportation of a quantum state.

A follow-up of the presentation and discussion of the quantum Fourier transform and its application to establish a QP algorithm for prime factorization started November 14.

A follow-up of the presentation and discussion of the quantum Fourier transform and its application to establish a QP algorithm for prime factorization started November 14.

Presentation of the quantum Fourier transform and its application to establish a QP algorithm for prime factorization. The talk is based on the work by P. Shor [SIAM J. Comp. 26(5):1484-1509, 1997].

Introduction to the essential results of Quantum Information Theory, discussion of Deutsch's problem and presentation of the Ekert91 quantum cryptographic protocol.

A follow up of the introduction to the essential concepts, properties and formalism of Quantum Mechanics started October 17. Discussion about quantum entanglement and its applications (teleportation, etc.)

Introduction to the essential concepts, properties and formalism of Quantum Mechanics. Discussion about quantum entanglement and its applications (teleportation, etc.).

A follow-up of the presentation and discussion of the paper by David Deutsch [PRSL A 400, 97-117, 1985] on the subject started September 26.

Presentation and discussion of the paper by David Deutsch [PRSL A 400, 97-117, 1985] on the subject.