Workshop on Distributed Quantum Computing

October  26-29, 2010

 

 

 

 

The workshop will gather a small group of physicists and computer  scientists aiming at investigating issues related to Distributed  Quantum Computing. The workshop will _not_ focus on Quantum Computing  per se, but will be restricted to the understanding of the  relationships between Distributed Computing and Quantum Computing. So,  the workshop will mostly ignore local computational power, and will  restrict its focus to the computational power of distributed  computation enhanced with the ability of using and exchanging qubits  (entangled or not).

 

Quantun computing has been deeply investigated by communities of  physicists and theoretical computer scientists. However, the  distributed computing community has, somewhat surprisingly, not  participated to the recent advances on that topic. Conversely, few of  the major results in quantum computing impact distributed computing,  if one considers distributed computing as computing with _many_  cooperating devices. Many of the participants of the workshop have  recently participated to an attempt of closing the gap between  distributed computing and quantum computing. The main objective of  this workshop is to carry on this effort.

 

The workshop will be organized in few plenary talks, plus long periods  of open discussions gathering all participants. The objective of the  talks will be to survey some of the most significant results related  to Distributed Quantum Computing. The objective of the open  discussions will be to establish a state-of-the-art of the domain,  using a formalism accessible to both communities (physicists and  computer scientists). One possible outcome of both the plenary talks  and the open discussions is the identification of elementary  communication "bricks" that capture the power of quantum communications.

 

 

If you have some trouble :

Patricia Benali-Ristori  : 0039/055-46 31 066

Silvia or Mathieu          : 0039/055-46 31 077

 

 

 

 

 

 

 

Schedule :

 

 

              ROOM GROUND FLOOR

 

 

Tuesday 26 

Wednesday 27

Thursday 28

Friday 29

 

9h30-11h

Round-based models for quantum distributed computing

(LABRI)

Adrian Kosowski talk

 

9h30-11h

Talk

Frederic Grosshans

9h30-11h30 Conclusion

 

11h-11h30

Coffee break

11h-11h30

Coffee break

11h30

Closing buffet

 

11h30-13h

Discussion

11h30-13h

Discussion

12 h Shuttle to Pise Airport

 

13h-14h Lunch

13h-14h lunch

 

 

14h30-16h

Introduction to measurement based quantum computing and an interesting but failed idea for a distributed implementation of Grover's algorithm

Terry Rudolf

 

 

Coffee Break

16h-16h30

Coffee break

 

 

 

17h00-19h00

Distributed Computing :challenges & two examples : graph coloring and consensus (LIAFA)

 Laurent Viennot talk Carole Delporte talk

 

16h30 -18h

 Whatever I know about MBQC that Terry didn't tell you

Elham Khashefi talk

 

 

20h

Diner

19h30

Banquet

 

 

 

 

Accomodation

We will be  villa Finaly (Villa FINALY

Via Bolognese, 134/r

50139 - FIRENZE Italy):

En franšais http://www.villafinaly.sorbonne.fr/

English http://www.villafinaly.sorbonne.fr

 

For your own, it is possible  to stay before or after Villa Finaly.

Please directly contact Patricia Benali-Ristori  (Benali-Ristori {at} villafinaly.sorbonne.fr)

 

How to get to villa Finaly 

 

Organized trip :

Flight Paris/Pise by Easy jet :

October, 26  departure 12:15 p.m  arrival  1:50 p.m

October, 29  departure 2:35 p.m  arrival  4:10 p.m

 

Flight London/Pise by Easy jet :

October, 26   arrival  14 :05 p.m

 

Then  shuttle from/to Pise to/from villa Finaly

From Pise to Villa Finaly : Cyril Gavoille, Frederic Grosshans, Iordanis Kerenidis, Adrian Kosowski, Elham Kashefi, Damian Markham (London), Terry Rudolf, Laurent Viennot

From Villa Finaly to Pise : Thomas Coudreau, Carole Delporte, Hugues Fauconnier,  Pierre Fraigniaud, Cyril Gavoille, Iordanis Kerenidis ,Adrian Kosowski, Damian Markham

 

 

Participants:

Thomas Coudreau <thomas.coudreau  {at} univ-paris-diderot.fr> (Paris)

Carole Delporte   <cd  {at} liafa.jussieu.fr> (Paris)

Eleni Diamanti <eleni.diamanti {at} telecom-paristech.fr>(Paris)

Hugues Fauconnier <hf  {at} liafa.jussieu.fr> (Paris)

Pierre Fraigniaud   <pierre.fraigniaud  {at} liafa.jussieu.fr> (Paris)

Cyril Gavoille <gavoille {at} labri.fr> (Bordeaux)

Frederic Grosshans <frederic.grosshans{at}ens-cachan.fr> (Paris)

Iordanis Kerenidis <jkeren {at} gmail.com> (Paris)

Adrian Kosowski <kosowski {at} labri.fr> (Bordeaux)

Elham Kashefi <ekashefi{at}inf.ed.ac.uk> (Edinburgh)

Damian Markham  <damian.markham {at} gmail.com > (Paris)

Terry Rudolf< tez {at} imperial.ac.uk (Londres)

Laurent Viennot  <Laurent.Viennot {at} inria.fr> (Paris) 

 

 

 

Related papers :

 

A. Broadbent and A. Tapp. Can quantum mechanics help distributed computing?

SIGACT News, 39(3):67–76, 2008 (available at http://arxiv.org/pdf/0810.5317 )

 

H. Buhrman and H. R÷hrig. Distributed quantum computing. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS 2747, pages 1–20, 2003. (available at http://www.springerlink.com/content/1kq4u9qq8c5qpm3h/fulltext.pdf )

 

V. S. Denchev and G. Pandurangan. Distributed quantum computing: a new frontier in distributed systems or science fiction? SIGACT News, 39(3):77–95, 2008 (available at http://sites.google.com/site/gopalpandurangan/dqc.pdf?attredirects=0 )

 

Scalable quantum consensus for crash failures, B. S. Chlebus, D.R. Kowalski, and M. Strojnowski, in Proceedings of the 24th International Symposium on Distributed Computing (DISC), LNCS 6343, pp. 236 - 250, 2010 (available at http://carbon.ucdenver.edu/~bchlebus/Online/ChlebusKS-DISC10.pdf)

 

Cyril Gavoille, Adrian Kosowski, Marcin Markiewicz, What Can be Observed Locally? Round-based Models for Quantum Distributed Computing,  arxiv 0903.1133 (available at http://arxiv.org/pdf/0903.1133v1 )

 

Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto, Exact Quantum Algorithms for the Leader Election Problem, arxiv (available at http://arxiv.org/pdf/0712.4213v1 )