Abstracts

Scott Aaronson
Quantum Complexity and Fundamental Physics

What are the ultimate limits on what can feasibly computed in the physical world? In this talk, I'll argue that this is one of the great scientific questions of our time, tying together many of the central concerns of math, computer science, and physics. I'll also explain how research in quantum computing has transformed our understanding of the question over the last fifteen years---and how this represents an intellectual payoff from quantum computing, whether or not scalable quantum computers are ever built.

* * * * * *

Andris Ambainis
Quantum Algorithms with Polynomial Speedups

Quantum algorithms provide polynomial speedups over the best classical algorithms for a large variety of problems. The most famous result of this type is Grover's search algorithm which provides quadratic speedup over the classical exhaustive search for any search problem. Other such speedups have been achieved for estimating means and medians and graph and matrix problems. We will survey the main results in this area, from Grover's search to newer quantum algorithms based on quantum walks (quantum counterparts of random walks).

* * * * * *

Alan Aspuru-Guzik
Quantum Computing for Chemistry

It is expected that chemical simulations will be one of the early application of early quantum computers. The simulation of the exact (within a basis) electronic structure and dynamics of mesoscopic quantum systems such as molecules or materials would benefit from an exponential speedup over classical computer algorithms. About 100 quantum bits are required to beat current classical computers. I will summarize the efforts of the theoretical chemists and quantum information scientists in this area. Another area of application of quantum computers would be to problems that are related to statistical mechanics, such as finding the low-energy conformations of random heteropolymers: a problem of interest to the Protein Folding community. I will talk about the recent advances and opportunities in this area. Finally, I will concluded with the description of an early experimental quantum computing calculation for chemistry that was recently completed.

* * * * * *

Charles Bennett
Quantum Information Theory

When classical notions of communication and interaction are generalized to obey the quantum superposition principle, a grander theory emerges, extending the old theory somewhat as the complex numbers extend the reals, and within which entanglement plays a central role as a quantifiable resource in many ways complementary to classical information. In contrast with a classical channel's single capacity, quantum channels have multiple capacities depending on what one is trying to use them for (e.g. classical or quantum communication) and what auxiliary resources (e.g. entanglement) are brought into play. We survey the field, including the recent discovery of pairs of channels, each with no quantum capacity, which nevertheless have positive quantum capacity when used together.

* * * * * *

Anne Broadbent
Universal Blind Quantum Computation

We present a protocol which allows a client to have a server carry out a quantum computation for her such that the client's inputs, outputs and computation remain perfectly private, and where she does not require any quantum computational power or memory. The client only needs to be able to prepare single qubits randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. Our protocol is interactive: after the initial preparation of quantum states, the client and server use two-way classical communication which enables the client to drive the computation, giving single-qubit measurement instructions to the server, depending on previous measurement outcomes. Our protocol works for inputs and outputs that are either classical or quantum. We give an authentication protocol that allows the client to detect an interfering server. We also generalize our result to the setting of a purely classical client who communicates classically with two non-communicating entangled servers, in order to perform a blind quantum computation. By incorporating the authentication protocol, we show that any problem in $\BQP$ has an entangled two-prover interactive proof with a purely classical verifier. The novelty of our approach is in using the unique features of measurement-based quantum computing which allows us to clearly distinguish between the quantum and classical aspects of a quantum computation. (Based on joint work with Joseph Fitzsimons and Elham Kashefi.)

* * * * * *

Isaac Chuang
Quantum Architecture

The road from devices to systems is an established path charted by computer architects, but quantum computation is a new challenge with many striking features. I will survey results from the nascent community of quantum architects, including a tour of unusual models of computation, and new architectural tools for communication and power supplies in quantum processors. These emerging tools suggest that the performance of realistic large-scale quantum computers may be predicted from strategic device measurements made with present quantum technologies.

* * * * * *

Michael Freedman
Topological Quantum Computing

In the topological approach quantum information may be stored in the collective degrees of freedom of a Fractional Quantum Hall Effect system. These degrees are protected from local interaction with the environment but can be acted on by global operations such as braiding or interferometry. I will review some recent experimental and theoretical progress.

* * * * * *

Jeff Kimble
Quantum Networks

Quantum networks offer opportunities for the exploration of physical systems that have not heretofore existed in the natural world, with applications ranging from quantum computation to metrology. To create a quantum network, quantum information is generated and stored locally in quantum nodes. The nodes are linked by quantum channels for teleportation of quantum states across the network. Fundamental to this endeavor are quantum interconnects that convert quantum states from one physical system to those of another in a reversible fashion. Such quantum connectivity can be achieved by optical interactions of single photons and atoms. Within this setting, I will describe ongoing research worldwide and then turn to recent advances in the Caltech Quantum Optics Group related to cavity QED with single atoms strongly coupled to the fields of high-quality optical resonators and collective interactions of atomic ensembles with single photons and entangled states of light. 1. "The Quantum Internet," H. J. Kimble, Nature 453, 1053 (2008).

* * * * * *

Anthony Leggett
Testing Quantum Mechanics Towards the Level of Everyday Life:Recent Results and Current Prospects

I first briefly review and refute the widespread belief that considerations associated with the phenomenon of decoherence enable one to resolve the quantum realization ("measurement") problem. This conclusion provides the motivation for experiments which probe the possible limits of validity of quantum mechanics in the direction of the macroscopic world; I review experiments already conducted in the areas of molecular diffraction, magnetic biomolecules, quantum optics and Josephson devices, as well as some currently planned on nanomechanical and other systems. I discuss the conclusions which may be drawn from existing experiments, and the constraints which decoherence considerations are likely to impose on future progress in this area.

* * * * * *

Norbert Lütkenhaus
Quantum Key Distribution

It is 25 year since the publication of the BB84 protocol. The field has come a long way since then with several start-ups and also major companies being active in the field. In this presentation I will outline the status of QKD, first as point-to-point connections with objectives of rate and coverable distance, but then also as a network applications for a multi-user scenario.

* * * * * *

William Phillips
Quantum Computing and Simulation with Cold Atoms

Single ultra-cold neutral atoms can act as qubits for quantum information (QI) storage and processing. Ensembles of neutral atoms in optical lattices or other potentials can mimic the behavior of electrons in condensed matter systems. A number of key experiments have demonstrated many of the processes needed for quantum computing and quantum simulation. I will briefly describe the use of neutral atoms for such QI applications and review a few of the experiments being done in some of the active laboratories around the world.

* * * * * *

John Preskill
Fault-tolerant Quantum Computation

Will large-scale quantum computers really work? Or will we be unable to overcome the damaging effects of the noise that afflicts quantum hardware? I will review the theory of fault-tolerant quantum computation, which establishes that noisy quantum computers can operate reliably if the noise has suitable properties, and I will explain some of the recently developed ideas that have improved the effectiveness of fault-tolerant schemes.

* * * * * *

John Watrous
Modeling Quantum Interactions As Games

There are several tasks and settings of interest in the theory of quantum information that can be modeled as games. Examples include quantum coin-flipping, generalized Bell inequality tests (which are modeled by nonlocal games), and several variants of quantum interactive proof systems. In this talk I will introduce the general notion of quantum games and discuss their motivation, what is known about them, and future challenges in this area.

* * * * * *

Birgitta Whaley
Quantum Control of Qubits and Quantum Systems

Quantum control has seen tremendous growth due to the emergence of high-profile applications in quantum information science, quantum metrology, spintronics and other advanced nanoscale technologies. For example, realizing quantum information processing poses severe challenges for control and measurement of qubit systems, challenges that demand quantum extension of classical control techniques. I shall provide a brief overview of progress in the field, highlighting both theoretical advances and experimental applications to quantum information.

* * * * * *

Carl Williams
The NSTC, OSTP, and the SQIS

The opening remarks will briefly describe the role of the Office of Science and Technology Policy (OSTP) and the committees and subcommittees of the National Science and Technology Council (NSTC) in setting science policy for the United States government. This will be followed by a brief history of the origin of the Subcommitee for Quantum Information Science (SQIS) under the Committee on Technology of the NSTC. The SQIS was formally established in December 2008 and in January 2009 it published a report entitled "A Federal Vision for Quantum Information Science," that was drafted with the help of program managers across the government. I will highlight the major research challenges describe in that report which has led to this workshop. I will conclude with a few comments on the potential value of what is learned from the workshop and any report that might result.

* * * * * *

David Wineland
Quantum Information Processing and Metrology with Ions

Trapped atomic ions have been a useful system in which to study the elements of quantum information processing (QIP). The basic features of the DiVincenzo criteria have been demonstrated along with simple algorithms. Straightforward approaches exist to realize scalability and fault-tolerant fidelity; however, achieving these goals will be technically very challenging. In the nearer term, it should be possible to extend existing methods to implement quantum communication protocols and perform useful quantum simulations. In addition, some simple elements of QIP are already being applied to metrology. (NIST work supported by IARPA, ONR, and the NIST Quantum Information Program.)

* * * * * *