Quantum Computation and Information Seminar 

01/04/2005, 15:00 — 16:00 — Room P4.35, Mathematics Building
Paulo Mateus, Instituto Superior Técnico

Minimization of quantum automata

A new notion of quantum automaton, which generalizes that of Chris Moore, is given. The automata states are density operators on a Hilbert space and its outputs are probability spaces over the spectrum of an observable. A suitable notion of quantum behaviour is introduced and the problem of finding its minimimal realization is addressed using techniques from linear automata theory. Joint work with A. M. Martins and A. Sernadas.

11/03/2005, 15:00 — 16:00 — Room P4.35, Mathematics Building
Amílcar Sernadas, Instituto Superior Técnico

Proof of the weak completeness of EQPL (conclusion)

Conclusion of the previous talk.

04/03/2005, 16:30 — 17:30 — Room P3.10, Mathematics Building
Amílcar Sernadas, Instituto Superior Técnico

Proof of the weak completeness of EQPL

After a brief review of the language and semantics of EQPL (exogenous quantum propositional logic), a weak complete axiomatization is presented. The proof of completeness is achieved by extending the Fagin-Halpern-Megiddo technique originally proposed in the context of probabilistic logic. Joint work with P. Mateus.

18/02/2005, 15:00 — 16:00 — Room P4.35, Mathematics Building
Beatrix Hiesmayr, U Vienna

Thermodynamical versus optical complementarity

The complementarity principle and the closely related concept of duality in interferometric devices was phrased by Niels Bohr in an attempt to express the most fundamental difference between classical and quantum physics. The well known statement that “the observation of an interference pattern and the acquisition of which–way information are mutually exclusive”, has been discussed for many years at a qualitative level. But only recently, quantitative statements for this long known “interferometric duality” have become available. In this talk I am going to investigate physical situations for which the visibility ("the wave-like property") and the predictability ("the particle-like property") can be analytically computed. This includes interference pattern of various types of double-slit experiments, but also oscillations due to particle mixing (e.g. the neutral kaon system) and also Mott scattering experiments of identical particles or nuclei. All these two-state systems belonging to distinct fields of physics can be treated via the generalized complementarity relation in a unified way. Surprisingly, this concept can also be applied to thermodynamical systems and thus one obtains new physical insights into usually complicated thermodynamical models, such as viewing a phase transition simply as a change from an effective single slit diffraction to a double slit interference.

04/02/2005, 15:00 — 16:00 — Amphitheatre Va6, Civil Engineering Building
Lov Grover, Bell Labs

Quantum algorithms

Physicists have long known that quantum mechanics leads to paradoxical effects. Recently, it has been realized that these effects can be made use of in expediting certain computations. One application where quantum mechanics gives a significant advantage is the exhaustive search problem where it is possible to search N items in only sqrt(N) steps (a classical computer would need N steps.) This talk introduces quantum algorithms by using the search algorithm as an example.

14/01/2005, 15:00 — 16:00 — Room P4.35, Mathematics Building
Ana Bela Cruzeiro, Instituto Superior Técnico e GFM

On the equations of motion in quantum mechanics

We describe a probabilistic interpretation of the quantum equations of motion for elementary mechanical systems, in the almost-sure sense, i.e., before taking the expectation. The method involves a class of stochastic processes appropriate to those systems. The main tool will be stochastic calculus of variation on the path space (or Malliavin calculus). In this framework a (stochastic) Noether theorem involving the same processes is also available.

07/01/2005, 15:00 — 16:00 — Room P4.35, Mathematics Building
Paulo Mateus, Instituto Superior Técnico

Quantum pattern matching using entanglement

A quantum algorithm for pattern matching is proposed and its complexity is analysed. The time complexity of the algorithm for matching (with nonvanishing probability) a pattern of size $M$ with a sequence of size $N$ is $O(\log (N)\sqrt{N}M)$. Entanglement is essential to attain time complexity and moreover, to consider patterns with gaps. Joint work with Y. Omar.

10/12/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Vítor Rocha Vieira, Instituto Superior Técnico

Quantum stochastic processes

Analysis of a system coupled to a heat bath. Characterization of the resulting quantum stochastic process.

03/12/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Adán Cabello, University of Seville

How much larger than classical correlations are quantum correlations?

It is commonly stated that quantum correlations are "larger" than classical ones. This statement, which has been described as "the most profound discovery of science," is based on the fact that some predictions of quantum mechanics violate Bell's inequalities, derived from some assumptions of classical physics. However, the question of how much larger than classical correlations are quantum correlations did not have a precise answer beyond the fact that quantum mechanics violates the CHSH-Bell inequality up to $2\sqrt{2}$ (Tsirelson's bound), while the classical bound is just 2. We shall show that the volume of the set of quantum correlations is $(3\pi /8{)}^2=1.388$ larger than the volume of the set of correlations obtainable by classical deterministic theories, but is only $3{\pi }^2/32=0.925$ of the volume allowed by probabilistic theories. We use these results to quantify the success of some approximate characterizations of the set of quantum correlations using linear and quadratic inequalities.

Are larger-than-quantum correlations possible? The quantum correlations appearing in the CHSH-Bell inequality can give values between the classical bound and Tsirelson's bound. However, for a given set of local observables, there are values in this range that are unattainable by any quantum state. We provide the analytical expression for the attainable values and the corresponding bound. We also describe how to experimentally trace this bound. Two groups have recently performed experiments to trace this bound, confirming the predictions of quantum mechanics and finding no evidence of larger-than-quantum correlations.

25/11/2004, 14:30 — 15:30 — Room P4.35, Mathematics Building
Antonio Acín, Institute of Photonic Sciences

Secret-key agreement and bound information

The problem of extracting secret and/or entangled bits from quantum states is analyzed. One can establish useful and conceptually interesting parallelisms between these two resources. Exploiting these connections, one can show the existence and activation of the so-called bound information, the cryptographic analog of bound entanglement.

24/11/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building

19/11/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
José Ignacio Latorre, University of Barcelona

Entanglement along quantum computation

We analyze the role of entanglement along adiabatic quantum computation for the 3-SAT NP-complete problem. Numerical evidence shows that entanglement pervades the register as if it were approaching a quantum phase transition. This result is compared to the amount of entanglement present in spin chains.

12/11/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Sonja Smets, Free University of Brussels

On Quantum Propositional Dynamic Logics

Together with A. Baltag I have been working on quantum propositional dynamic logics, i.e. on logical calculi that can handle “quantum information flow”. First, I will present the syntax and relational semantics for the Logic of Quantum Actions (LQA). This logic deals with quantum measurements and evolutions of one physical system. LQA pushes the work on quantum modal logic one step further into an action-labeled version. I will show that LQA yields an obvious candidate for obtaining a completeness result with respect to the lattice of closed linear subspaces of a Hilbert space. What is known as standard quantum logic (SQL), emerges in this framework as the negation free and measurement-only part of LQA. Second, I will focus on compound quantum systems and on the Logic of Quantum Programs (LQP) which in addition to LQA can handle entanglements [1]. I will focus on the specific features of LQP: the presence of an entanglement operator, how to capture Bell states and specific quantum logical gates. Using LQP, a correctness proof for the quantum teleportation protocol can be given.

[1] A. Baltag and S. Smets: "The Logic of Quantum Programs", TUCS General Publication No 33, Turku Center for Computer Science, 2004.

05/11/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Yasser Omar, Instituto Superior Técnico

Introduction to quantum cryptography

A gentle introduction to the main concepts, techniques and issues of quantum cryptography.

15/10/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Paulo Mateus, Instituto Superior Técnico

Observational versus measurement equivalence of quantum automata - Part II

Continuation of the previous talk.

08/10/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Paulo Mateus, Instituto Superior Técnico

Observational versus measurement equivalence of quantum automata

After reviewing some key concepts and results in classical automata theory and categorical automata theory, two notions of equivalence between quantum automata are presented and exemplified. The significance of the result presented in the previous talk by Misha Protin is discussed. Two open problems are identified in the theory of minimization of quantum automata. This reports ongoing discussions with Amilcar Sernadas.

01/10/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Misha Protin, Instituto Superior Técnico

Minimal realization for quantum automata

In this seminar we show how Moore and Crutchfield's concept of quantum automata can be encompassed by Adamek's categorical theory of F-Automata through the consideration of a special subcategory of C-linear spaces with a tensor-product endofunctor. As a consequence, a minimal realization result is derived, answering an open problem posed by Moore and Crutchfield in 2000.

10/09/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Pedro Ribeiro, École Polytechnique

Quantum walks with two quantum coins

This work presents quantum walks which are the quantum counterparts of classical random walks. Quantum walks are first defined on general graphs and the possibility of very different behavior between a classical random walk and its quantum analogue is illustrated with a simple graph. A generalization of the quantum walk protocol for a particle in a one-dimensional chain, by using several types of biased quantum coins, is presented. We study the evolution of the system when different types of sequences are applied. Quasiperiodic sequences, following the Fibonacci prescription, are of particular interest, leading to a sub-ballistic wave function spreading. In contrast, random sequences leads to diffusive spreading, similar to the classical random walk behavior. We describe qualitatively how to experimentally implement these processes.

23/07/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Simon Gay, University of Glasgow

Communicating quantum processes

We define a language CQP (Communicating Quantum Processes) for modelling systems which combine quantum and classical communication and computation. CQP combines the communication primitives of the pi-calculus with primitives for measurement and transformation of quantum state; in particular, qubits can be transmitted from process to process along communication channels. CQP has a static type system which classifies channels, distinguishes between quantum and classical data, and controls the use of quantum state. We formally define the syntax, operational semantics and type system of CQP, prove that the semantics preserves typing, and prove that typing guarantees that each qubit is owned by a unique process within a system. We illustrate CQP by means of several examples, and outline our plans for formal verification of quantum communication and cryptographic systems. This work will also be presented at the Workshop on Quantum Programming Languages in Turku, Finland, 12th-13th July.

02/07/2004, 15:00 — 16:00 — Room P4.35, Mathematics Building
Cristopher Moore, University of New Mexico

A challenge for quantum computing: the non-Abelian hidden subgroup problem

In 1994, Peter Shor showed that quantum computers can factor integers in polynomial time. The security of RSA public-key encryption relies on the fact that (we believe) classical computers are unable to do this. While the emerging consensus is that quantum computers cannot solve $NP$-complete problems in polynomial time, it seems plausible that they can solve a number of other problems which appear to be outside $P$. One such problem is Graph Isomorphism; namely, telling whether two large graphs are simply permutations of each other. Shor's factoring algorithm relies on the fact that we can relate factoring to finding periodicities in a particular series of integers, which is equivalent to finding a "hidden subgroup" of the cyclic group. If we could do the same thing for the symmetric group $S_n$, i.e. the group of permutations of $n$ things, then we could solve Graph Isomorphism on a quantum computer. However, finding hidden subgroups in non-Abelian groups such as $S_n$ seems to be much harder than doing so in Abelian groups. I will describe recent joint work with Alex Russell, Dan Rockmore and Leonard Schulman on the non-Abelian hidden subgroup problem (HSP). Our work relies on the representation theory of finite groups, which is a generalization of Fourier analysis to the non-Abelian case. I will show that by measuring the high-dimensional representations of a group in a well-chosen basis, we can solve the HSP for a family of non-Abelian groups. However, we still seem very far from solving Graph Isomorphism, and I will comment on the long road ahead.