Haar-distributed unitary operators have recently found a number of applications in quantum information theory, from the quantum channel capacity theorem and fidelity decay measurements to remote state preparation, data hiding, locking and encryption. Unfortunately, protocols depending on the use of such operators will never be practical because the operators generally have exponentially long descriptions and take exponential time to implement. The goal of this workshop will be to explore notions of pseudo-randomness appropriate to the setting of quantum information processing and to replace the Haar-distributed unitary operators in as many applications as possible with more practical alternatives.

Some progress in this direction has already been made. Ambainis and Smith have developed an approach to approximate encryption of quantum states that runs in polynomial time. Emerson, Weinstein, Saraceno, Lloyd and Cory have explored the possibility of approximating the Haar measure by randomly applying gates drawn from a universal set. Recently, Buhrman, Hayden and Christandl have shown that the correlation locking effect can be implemented against an adversary with a polynomial time quantum computer using mutually unbiased bases instead of random unitary encodings.

In keeping with the objective of the workshop, there will be two sets of lectures, one a crash course in classical pseudo-randomness and the other devoted to proposals for quantum pseudo-random operators and their applications. These lectures will occupy about two to three hours a day with the rest of the time devoted to brainstorming solutions.

Organiser: Patrick Hayden

Time: March 14-18, 2005

  Place: Bellairs Research Institute                         Barbados

Confirmed Partipants:
     Mehmet Akcakaya
     Richard Cleve
     Wim van Dam
     Simon Pierre Desrosiers
     Joe Emerson
     Patrick Hayden
     Debbie Leung
     Etera Livine
     Graeme Smith
     Andreas Winter