CHALLENGES AND OPPORTUNITIES

Quantum information science is a very new field, so new that many promising aspects of it have hardly been explored. Here we compile just a sampling of challenging open questions and problems.

Many of these unsolved problems span the traditional disciplinary boundaries. A common thread is the challenge of characterizing what can be achieved with quantum information processing, and how it can be achieved. We emphasize in particular that the physical requirements for quantum-state manipulation are entirely different from those for classical information processing; therefore it is essential that investigations of the potential physical implementations of quantum information processing be broad-based and exploratory.

New Quantum Algorithms

While the factoring and search algorithms are exciting breakthroughs that hint at the potential of quantum algorithms, our understanding of what quantum computers can do is still quite limited. It is very important to seek new quantum algorithms that can speed up the solutions to interesting problems.

The factoring algorithm makes use of a quantum Fourier transform that can be efficiently computed for any abelian group. The same ideas enable quantum computers to break a wide variety of cryptosystems. In fact, essentially all quantum algorithms that achieve exponential speedups fit into a common general framework: they find a hidden subgroup in an abelian group. Recent work shows that normal hidden subgroups in a non-abelian group can also be found efficiently. A major challenge is to extend this framework to the general non-abelian hidden subgroup problem.

Several problems seem to be excellent candidates to be solved by efficient quantum algorithms, but such algorithms have not yet been found. One example is graph isomorphism: given two graphs, can one be transformed to the other by a permutation of the vertices? Graph isomorphism can be expressed as a hidden subgroup problem in the symmetric group S_n. Other important examples are breaking the Ajtai-Dwork cryptosystem, which involves finding short vectors in certain types of lattices, and breaking cryptosystems based on classical linear error-correcting codes.

Quantum Simulation

In the long run, one of the most important applications of quantum computers is likely to be simulating the dynamics of quantum systems with many degrees of freedom. Much can be done to determine how quantum computers can best be used to address simulation problems of physical interest. Examples include the properties of quantum chromodynamics in real time or at finite nucleon density, or the behavior of quantum antiferromagnets and strongly correlated electron systems.

A particular challenge will be to determine if M-theory is susceptible to efficient simulation on a quantum computer. M-theory has been proposed as a unified description of all of the forces of Nature, including gravity. It can be formulated in terms of the quantum mechanics of very large matrices, but because of the intrinsic nonlocality of the theory, these matrices do not admit an obvious decomposition as a tensor product of smaller systems. It would be exciting to discover that no efficient simulation is possible, which would suggest that the computational power woven into the laws of Nature is even greater than we now suspect.

Quantum simulation may also play an important role in the evolution of new quantum technologies. Validating and characterizing the design of even relatively simple quantum devices will press the limits of conventional digital computing. In particular, a quantum computer would be an extremely valuable tool for the development of practical implementations of quantum feedback control.

Complexity Theory

The class of efficiently solvable problems on a quantum computer, BQP, is known to be contained in PSPACE, and is unlikely to contain NP. However, we do not yet know much about its relationship to other complexity classes. For example, is BQP contained in the polynomial hierarchy? In particular, does the power of approximate counting suffice to simulate quantum computation? There is evidence that BQP is not contained in MA (one-round interactive proofs), since there is an oracle relative to which the recursive Fourier sampling problem is not contained in MA.

The recent developments on the quantum analog of NP and quantum interactive proofs open up a number of fundamental issues. It should now be possible to classify a wide variety of problems about quantum systems as either being efficiently simulable on a quantum computer or BQNP-complete (much like the classification developed by the classical theory of NP-completeness). It is an open question to put the work on quantum interactive proofs in the framework of probabilistically checkable proofs, which is a deep and important part of computational complexity theory.

There are novel computational resources, other than time and space, that should be studied. One interesting question arises in the context of bulk NMR quantum computation with weakly polarized nuclear spins. Consider an n-spin system, which is described as a separable mixed state at every step in its evolution. Thus each instantaneous state is described by a probability distribution over orientations of n classical tops. However, if the evolution of the system is quantum mechanical (described by quantum gates), then it is not known whether such a system can be efficiently simulated on a classical computer, or whether it can simulate a universal quantum computation. Another intriguing question, which can also be posed in the context of bulk NMR quantum computation, is whether it is possible to carry out universal quantum computation if the initial state of the system is highly mixed. One recent result addresses the power of a quantum computer in which all qubits but one are initially in the uniformly mixed state. It was shown that if we restrict our attention to faithful simulations of a universal quantum computation, then such mixed state quantum computers are no more powerful than classical computers.

Apart from being important for a study of quantum computers, there are techniques of a fundamentally quantum nature that have provided new insights into classical complexity theory. Two examples are the linear lower bound on the communication complexity of the inner-product function and the reformulation of the log-rank conjecture for communication complexity. It is quite possible that the new method of quantum adversaries could provide an important new technique for classical computation as well.

Quantum Cryptography

Besides privacy and authentication, conventional cryptography includes other goals. For instance, a digital signature scheme allows Alice to send a message to Bob in such a way that Bob can verify that the message is really from Alice and that it has not been altered at all. A zero-knowledge proof allows Alice to prove to Bob that she knows how to solve a particular problem without Bob learning anything about how Alice’s solution works. One particularly intriguing example is "secure distributed computation," in which two or more cooperating parties evaluate a function of all of their inputs. Though some of the parties may be malicious or unreliable, the computation may nevertheless be reliable (the bad parties cannot alter the result) and discreet (the bad parties cannot learn any more about the others’ inputs than is implied by the value of the function).

There are classical solutions to these problems, but all rely on making some sort of assumption, such as a limitation on the computational power of a cheater. An important goal of QIS is to formulate quantum protocols that might allow us to weaken or remove these assumptions.

Many classical cryptographic protocols are built from simpler ("primitive") protocols. An important ‘primitive for two-party secure distributed computation’ is called bit commitment, the mathematical equivalent of Alice’s locking a bit in a safe and sending it to Bob. Bob cannot open the box until Alice gives him the key, but Alice cannot change her choice once she has given the box to Bob. It has recently been shown that unconditionally secure bit commitment is not allowed by the laws of quantum physics — if Alice and Bob have quantum computers, then whenever Bob is unable to determine the value of Alice’s bit, Alice can safely change her bit without Bob finding out. Still, it is of interest to develop two-party distributed computation schemes in which cheating is computationally difficult (though not absolutely impossible) with a quantum computer.

Complexity-based Cryptography

Since quantum computation compromises the security of much of classical cryptography, it is extremely important to develop a new cryptography that is immune to quantum cryptanalysis. For example, are there one-way functions that are easy for a quantum computer to evaluate, but hard for a quantum computer to invert? To design such primitives, we need to understand the limitations of quantum computation much better than we do today.

So far, three techniques have been developed for proving lower bounds on the running time of quantum algorithms: the hybrid argument, the method of polynomials, and the method of quantum adversaries. Extending this bag of tricks will better enable us to devise new cryptosystems that are invulnerable to a quantum attack.

It has been shown that any quantum algorithm for inverting a random permutation on N elements requires at least of order N^1/2 steps. Since random permutations are regarded as good models for one-way functions, this result provides some positive evidence for the existence of one-way functions immune to quantum cryptanalysis. On the other hand, no non-trivial lower bound is known for the problem of finding a collision in a random 2-1 function. Since random 2-1 functions are regarded as good models for collision intractable hash functions (a fundamental cryptographic primitive), it is very important to understand the complexity of this problem.

Quantum Error Correction and Fault Tolerance

It is of great interest to refine the estimates of the accuracy threshold for quantum computation, as the threshold will define the specifications that must be met by the hardware components of a future quantum computer. Current estimates vary over a broad range, depending on assumptions about what protocol is used and how the noise is modeled; according to the most optimistic estimates, an error probability per gate as high as 10^-3 can be tolerated. It is important to obtain more rigorous estimates that would apply to a broad spectrum of conceivable protocols.

It is also important to optimize the circuitry that implements the error recovery or the fault-tolerant quantum gates. Perhaps an even more promising approach to improving the threshold would be to investigate schemes for fault tolerance beyond the purview of the standard quantum circuit model. Drawing on analogies with classical error correction techniques will very likely be helpful.

Important computational efficiency considerations remain open. Current fault tolerant constructions require polylogarithmic overhead in time and in space. How much can these overhead requirements be reduced? In the classical case, constant overhead in time is sufficient, but it is not known whether this applies in the quantum case.

Also in need of further study are more general noise models. Much work on fault tolerance has focused on the problem of combating uncorrelated stochastic errors, but schemes that can overcome strongly-correlated noise should also be formulated and analyzed. More generally, there is a need to better understand how a quantum code can be devised that is well matched to the expected noise processes in a specific physical system.

Finally, new approaches to fault tolerance should be developed that achieve robustness through the design of the physical hardware. A particularly promising idea is to encode quantum information in the topological properties of the entanglement of many-body systems with local interactions. Topological quantum computation is a rich and promising subject, combining deep questions about topology, quantum error correction, and many-body quantum dynamics.

Precision Measurement and Quantum Control

Quantum information processing and quantum error correction will provide the laboratory scientist with unprecedented tools; these can be exploited to devise new strategies for performing interesting high-precision measurements.

An experimenter detects a time-dependent weak classical force by monitoring the response of a sensitive quantum system. But since observing the quantum system necessarily disturbs it, there are intrinsic limitations on the accuracy of the measurement. Quantum information theory has taught us that strategies that exploit entangled quantum states can collect more information than strategies that do not, so we can anticipate that the most precise measurement methods will require entangled probes (Fig. 7). Much work must be done to infer what resources are required to carry out a measurement of specified accuracy, and how best to deploy those resources under realistic laboratory conditions.

Figure 7: An example illustrating that, in a quantum setting, the best way to measure something can be a subtle issue. Two spins point along the same axis; they are parallel in case (a), anti-parallel in case (b). If the spins were measured one at a time, then the information collected about the spin axis would be the same in both cases. In fact, though, more information about the axis can be collect in case (b), because the optimal quantum measurement is an entangled measurement that acts on both spins at once.

Closely related to the challenge of high-precision measurement is the challenge of controlling quantum states. To control a system effectively, one needs to collect information about its behavior. Hence quantum control is particularly delicate — monitoring a system necessarily exerts back action on the system. Formulating effective protocols for quantum control poses daunting problems for both theorist and experimentalist.

Many-party Quantum Entanglement

The entanglement of a two-part pure quantum state can be conveniently quantified by the number of Bell pairs that can be distilled by local operations and classical communication. But it is still not known if it is possible to express the entanglement of a pure state with more than two parts in terms of some such standard currency. For example, it is unclear whether a three-party "cat" state should be regarded as possessing an entirely different kind of nonlocality than two-party Bell pairs.

A universal measure of many-particle pure-state entanglement, if one can be formulated, would have many applications. It might enable us to identify new kinds of quantum critical points at which the degree of entanglement of the ground state of a Hamiltonian changes discontinuously, or to characterize which kinds of quantum dynamics are hard to simulate on a classical computer.

The Quantum — Classical Boundary

A deep and long-standing fundamental problem is to understand and precisely define the transition from classical to quantum behavior. There are many systems in which quantum effects have a strength that depends on an adjustable parameter. It is usually easy to recognize the difference between a system that behaves very classically and one that behaves very "quantumly," but is there a sharp boundary between the two? And if so, where is the boundary? (Fig. 8)

Figure 8: The quantum--classical boundary. A classical computer can efficiently simulate a system that behaves classically, but not one that behaves "quantumly." Hence it is possible to identify a sharp transition between the quantum and classical phases of some physical systems.

Arguably, the most interesting observation ever made about the difference between quantum and classical is that a classical system cannot efficiently simulate a quantum system. We can try to use this idea to establish a well defined boundary between quantum and classical behavior. Indeed, the intrinsic accuracy threshold for quantum computation can be regarded as just such a phase boundary. Below the critical noise rate, there is long-range entanglement in the system, whereas above the threshold the entanglement between two subsystems decays exponentially as the subsystems are separated. The study of such transitions has barely begun, and there are many open questions. In particular, universality classes and critical exponents associated with long-range entanglement are yet to be identified.

Quantum Information and Fundamental Physics

The Standard Model of particle physics provides a marvelously accurate description of the fundamental constituents and their interactions down to distances of order 10^-16 cm. But the most compelling fundamental questions concern physics at the Planck scale, 10^-33 cm, where spacetime undergoes strong quantum fluctuations. While it seems hopeless to explore physics at these scales directly in high-energy accelerator experiments, a large-scale quantum computer might provide an incisive indirect probe of quantum gravity. At least one proposed model of physics at the Planck scale dictates that the dynamics of the universe actually can be efficiently simulated by a classical Turing machine. Since the factoring of numbers with of order 1000 digits is believed to be beyond the capability of any conceivable classical computer, a quantum computer of the future that achieves such a task will convincingly rule out any such model of Planckian physics!

Another possible way for quantum information science to illuminate the fundamental interactions is suggested by the discovery of fault-tolerant quantum computation. If quantum mechanics breaks down at very short distances, then we might say the "qubits" of the fundamental theory are continually subjected to errors — that is, to deviations from unitary evolution. Yet somehow, these errors are unseen at the larger distance scales we are currently capable of probing. How can it be so? Until quite recently, we lacked the tools to productively investigate this sort of question. But now hierarchical quantum error-correcting techniques have been found that exhibit this kind of behavior: the error rate gets smaller and smaller at higher and higher levels of the hierarchy. Could fault-tolerance be woven into the fundamental laws, so that the error rate flows to zero in the infrared limit? A broadening interface between quantum information science and fundamental physics can be anticipated, with tremendous potential payoffs.

Quantum Information Processing with Atoms and Photons

AMO physics provides powerful laboratory systems for the exploration of quantum information processing, quantum measurement, and quantum information dynamics. Because the relevant physical mechanisms and sources of dissipation can be understood and easily modeled, these systems are especially well suited for testing and developing error correction protocols. Existing experiments have achieved remarkable control of few-qubit systems. Extending this level of control to larger systems will require understanding and eliminating various sources of decoherence such as patch-effect fields and laser intensity and frequency fluctuations. But given the impressive rate of progress to date, it seems reasonable to anticipate that quantum information processing involving tens of qubits will be achieved within a decade.

Apart from their potential relevance to quantum computation and communication, the new capabilities arising from AMO physics will push the science of precision measurement into a radically new domain. Time-frequency standards, gravitational wave detection, and the characterization of solid state devices at low temperature are just a few of the frontiers of advanced metrology that will be affected.

Scaling

For quantum information processing to scale to increasing numbers of qubits, new experimental options must be explored to avoid a debilitating increase in technical overhead. One option in cavity QED is to move from more traditional Fabry-Perot cavities to nano-fabricated cavities in photonic bandgap materials. It might then be possible to trap and manipulate individual atoms by exploiting the powerful tools of lithography, while still maintaining strong coupling between individual atoms and single photons. A different option is to build an array of small traps, where atoms can be shuttled from one trap to another.

Quantum networks

One specific challenge is to combine the complimentary paradigms of flying and standing qubits in the construction of quantum networks for quantum communication and distributed quantum computation. As illustrated in Fig. 9, multiple atom-cavity systems located at spatially separated "nodes" could be linked via optical fibers to create a network of quantum information processors with quantum-coherent interconnects. A complete set of elementary network operations has been proposed and analyzed, including fault-tolerant local processing of quantum information, transmission of quantum states between nodes, and the distribution of quantum entanglement. If it could be realized, such a quantum Internet might support a wide range of quantum protocols.

Figure 9: Illustration of a protocol for the realization of a quantum network. An applied laser beam ((t)) transfers quantum information from the internal state of an atom in one cavity to a photon state, via the atom-cavity coupling g. The photon travels along an optical fiber, enters a second cavity, and the information is transferred to an atom in that cavity. Nonlocal entanglement can be created among the atoms in the two cavities. By expanding from two cavities to a larger set interconnected by optical fiber, complex quantum networks can be realized.

Optical lattices

Beyond ions traps and cavity QED, another system with promise for quantum information processing is an "optical lattice," in which neutral atoms are trapped by the AC-Stark shift produced by a set of intersecting laser beams. Because the atoms are neutral, they interact very weakly with the environment. Dissipation arising from inelastic photon scattering can be suppressed, as can other forms of dissipation such as coupling to phonons, defects, and impurities. Optical lattices have tremendous flexibility — a wide range of properties characterizing the lattice potential can be adjusted through laser beam geometry, polarization, intensity, and frequency. These adjustable "knobs" permit one to design interactions such that atoms interact strongly only during logic operations (e.g., via dipole-dipole interactions), but otherwise are isolated from each other and the environment. Substantial theoretical work needs to be done to assess the long-term potential of optical lattices as quantum information processing systems.

Quantum Information Processing in Condensed Matter

The ideas of quantum information processing are beginning to influence the agenda of condensed matter physics and materials science. A remarkable variety of proposed implementations of quantum bits and gates have been put forward, and their implications for experimental directions in these fields are being actively assessed by workers in the community.

Having been concerned for most of its history with bulk or collective properties, condensed matter physics is now beginning to address the behavior of systems where individual quantum properties are important. Qubits might conceivably be implemented in any of these systems, although so far only the rudiments of quantum gate operations have been achieved. The continuing quest for coherent information processing in a condensed matter setting will address some of the most fundamental problems in the quantum mechanics of individual systems.

Many specific quantum-gate technologies based on solid-state physics have been proposed. They include:

Ultra-small superconducting structures. In these, the qubit can be embodied either in the quantum state of flux of a SQUID (superconducting quantum interference device) or in the quantized Cooper-pair number of a small superconducting island. Single-qubit rotation has recently been observed (Fig. 10).

Figure 10: Quantum coherence in a superconducting Cooper-pair box. Cooper pairs of electrons can tunnel through the Josephson junction barrier onto the island electrode, and quantum information can be encoded in the number of Cooper pairs on the island. Coherent oscillations in the number of pairs were recently observed.

Quantum dots. Such structures have been the focus of nano-device technology both as optical and electronic devices. As quantum gates, their quantized electron number or spin can function as the qubit; switching of the quantum state might be achieved either by optical or electrical means.

Semiconductor optical microcavities. These devices, long researched for their applications in solid-state microlasers, are approaching the point at which the coherent manipulation of single photons is becoming a possibility. In addition, these can be coupled to atomic-like qubits in the form of embedded single-electron quantum dots. This proposal has many contacts with existing thrusts in optoelectronics.

Impurities in semiconductors. Integrated-circuit technology demands greater and greater control over the precise profile of dopant impurity concentrations in semiconductor devices. If this technology is developed to the extent that control of impurities atom-by-atom is achieved, quantum computation might become possible. The nuclear or electronic spins of individual phosphorus impurities are the qubits in this scheme, and transistors control operations between these qubits.

Various other systems, which are conceivable only because of the long development of science and technology in condensed-matter physics, have been proposed for implementing quantum computing devices — for example, using the orbital states of electrons floating on the surface of liquid helium, or the edge states of the quantum Hall effect. Undoubtedly, many other proposals will emerge as the workers in the various subfields of condensed-matter physics turn their imagination to the problem.

We envision a variety of specific ways in which quantum information science will influence the agenda of research in condensed-matter materials science in the coming years:

Phase coherence

The observation and characterization of quantum phase coherence has been a long-standing theme of mesoscopic physics; quantum computing gives a definite focus to this theme and asks new questions about how systems can be tailored to exhibit a high degree of coherence. In the superconducting community, the achievement of controlled single-qubit operations will be tantamount to achieving the long-standing goal of Macroscopic Quantum Coherence (MQC) in SQUIDs and related structures.

Entanglement

Some much-studied condensed matter systems, such as highly correlated electron systems and frustrated anti-ferromagnets, have very highly entangled many-body ground states, and the properties of the quasiparticle excitations of these systems reflect that underlying entanglement. But quantum entanglement among quasiparticles has had only a limited role in the description of solid-state phenomena, where single-particle descriptions have held the dominant place. (In certain subfields, such as in the optical physics of highly excited semiconductors, correlations among particles have received prominent attention.) New structures being proposed will result in the controlled generation of two-particle and eventually many-particle entanglement in a large variety of solid-state systems; this will require theory to explore how these various forms of entanglement can be characterized, and how well they can survive interaction with the various types of solid-state environments.

Readout

The "readout" requirements of quantum computing will provide additional impetus behind the drive to achieve high quantum efficiency measurements of, for example, single spins in solids; it will require the mastery of the subtle and counterintuitive issues of the quantum measurement problem, such as the construction of non-demolition measurements. Solid state researchers will have to travel the road now being explored in atomic physics, in which Schrödinger cat states are controllably created and undone, and measurements can be performed and then reversed again.

Fabrication and control

The structures that are proposed and that will be needed for this fundamental research will require a close encounter with state-of-the-art materials science and applied research in fabrication and in device physics. In a few of the proposals, individual dopant impurities in a semiconductor must be placed, one at a time, with unprecedented accuracy; new ion-beam or scanned probe deposition techniques will have to be developed to address this requirement. Some of the proposals for sensitive quantum measurement require the construction of magnetic-semiconducting heterostructures that have not been previously contemplated. The specifications of quantum gate operations put unprecedented demands on the bandwidth and precision of high-frequency gated control of microstructures. 1/f noise phenomena must be completely understood and suppressed in these structures. Many of these directions are ones that are already part of the agenda of advanced device technologies, but quantum computing probably pushes some of these technologies harder than any other computing schemes.

Communication

Quantum communications has engendered further thinking about how a solid state bit can be made mobile, and this has brought solid-state optics into the picture. Several proposals focus on the existence of various technologies, arising out of work on solid-state lasers, for the production of high quality-factor microcavities; it is known that quantum dots and other small quantum structures can be grown inside such cavities, and proposals for quantum gate operations, and for the transmission of a qubit as a photon emitted by the cavity, have been developed and will be the subject of future experimental research. Finally, there is even the possibility of using electrons themselves as mobile qubits; several proposals have been made for a Bell-type experiment, in which all steps — creation of entanglement, separation of the two particles, detection of the quantum states — are done electronically in a mesoscopic device.

Unorthodox implementations

Solid state physics is very versatile, and while the above survey can give some idea of how quantum information science and solid state physics may develop together in the future, it should not preclude an unforeseen departure from this "orthodox" view. For example, there is some discussion indicating that a recently identified gapped, fractional quantum Hall state (the "=5/2" state) may be the first "nonabelionic" state of matter, exhibiting quasiparticles with non-abelian, anyonic statistics. This discovery may actually have a real bearing on quantum information processing: calculations have indicated that nonabelionic matter may be uniquely suited as a medium for fault tolerant quantum computation. Will the =5/2 state be the basis of a quantum computer? Probably not; but we should be open to possibilities like this, and to even more exotic-sounding ones.

Toward Scalable NMR Quantum Computation

Many groups around the world are now using NMR to investigate small quantum computers, because of the familiarity and availability of the required spectrometers. A fundamental limitation will come in, however, beyond roughly 10 qubits. This is because room-temperature NMR uses a very weakly polarized sample, which leads to a partition function normalization that decreases exponentially as qubits are added. Although experimental refinements might reach the classical simulation limit of tens of qubits, it cannot scale beyond that. To go further, near-unity spin polarization is needed. Although this might be achieved by cooling the entire sample to millikelvin temperatures, that would eliminate the beneficial protection of intra-molecular coherence through translational thermalization. A more promising alternative is to cool just the nuclear spin system, which is routinely accomplished with optical pumping of rare-gas atoms. An open question is whether this will be possible with more complex molecules and in solids; if it is, the other parameters of this system are already close to what is needed for scaling to significant sizes.

It is important to view this scaling effort in the context of the complementary experimental approaches; as they progress they are all likely to grow together. Optical pumping for NMR draws on insights from AMO physics, and, in turn, NMR points to techniques for manipulating ensembles and effective Hamiltonians that are applicable to the alternatives. And the experimental progress in NMR to date has been driving the development of higher-level quantum programming tools that will be needed in any quantum computer.

QUANTUM INFORMATION, CURIOSITY, AND COMMUNITY

The development of conventional information technology has been neatly separated into physical scientists investigating underlying devices, and computer scientists working on architectures and applications. This division in both academia and industry has resulted in many of the most compelling questions about the meaning and manipulation of information being left neglected at the interface between hardware and software.

In contrast, one of the most striking features of the emerging science of quantum information is its transcendence of the division between abstract bits and physical quanta. To contribute in an arena where information content and physical embodiment are so intimately integrated, the early investigators needed mastery of many aspects of physics, computer science, engineering, and mathematics. An example that illustrates the symbiosis of computer science and physics is the successful adaptation of classical error correction ideas to quantum systems, an advance critical to the long-term viability of the field.

QIS has stimulated strong cross links between computation science and mathematical physics, and among areas such as AMO physics (e.g., NMR, cavity-QED, ion traps), condensed matter physics (e.g., electron/nuclear spins in semiconductors, single-electron transistors, coupled super-conducting systems), and engineering (e.g., nanotechnology, feedback, scalability, quantum-limited metrology). Direct evidence of these vibrant interfaces can be seen from the makeup of attendees at conferences and workshops on QIS.

Quantum information science is a field whose initial and future successes are clearly tied to its interdisciplinary nature. And, as is often the case in a scientific revolution, many researchers in QIS find themselves at the margins of their home disciplines, with their activities stretching the conventional limits of physics, computer science, mathematics, or electrical engineering. Indeed, a remarkable new generation of young researchers is growing up in an intellectual environment in which the traditional distinctions of discipline make less and less sense.

These developing cross links between diverse communities can be expected to directly benefit not only QIS, but science and technology more broadly, by catalyzing connections between various subfields of mathematics, physics, and engineering that might otherwise go unexplored. A principal benefit to industry is the cadre of young scientists and engineers who are being trained in new ways to help confront the challenges that lie beyond the end of VLSI scaling. For example, experimental investigations of possible physical implementations have nearly always been carried out in small laboratories, enabling students to be involved in all aspects of the research, from nano-fabrication to control theory to quantum algorithms.

Many of the best upcoming students are attracted to the study of quantum information because of its intellectual and technological impact. For them, QIS is not a specialized application to be encountered late in their education, but an organizing principle that drives an enormous appetite for learning about quantum systems and about the tools relevant for manipulating them. This ground swell among young people manifests itself in enormously over-subscribed new courses taught across disciplinary boundaries. Courses in QIS can be aimed at the early undergraduate level, enabling an education in physics and other technical fields to reach a broader and more enthusiastic audience.

The continuing investigation of the intimate connections between information and physical systems may also enhance the role of science in society. Numerous magazines and newspaper articles have already been published in response to the lay-person’s fascination with computers and quantum physics. As quantum mechanics and information science continue to meld, this broad interest in QIS will help to bring science to a growing portion of the populace.

FOSTERING THE CONTINUED SUCCESS OF QUANTUM INFORMATION SCIENCE

Quantum information science has emerged as one of the most exciting scientific developments of the past decade. As described in the preceding sections, initial advances in QIS have encompassed a broad and remarkable landscape, ranging from super-fast quantum algorithms for computation and communication to fault tolerant architectures for quantum computers to the realization of quantum gates for the physical implementation of quantum logic. Beyond contributions to fundamental knowledge, these advances in QIS are of great potential technological significance to our society as information processing and communication march inexorably into the quantum realm.

In attempting to understand how best to foster the continued success of QIS, one should recognize that the most spectacular advances in the field have largely sprung from individual "zealots" who ventured beyond the boundaries of traditional disciplines and who did so without dedicated support for their activities (and in some cases, with active discouragement). The QIS community is largely a self-organized group of otherwise independent researchers drawn together by the intellectual excitement and potential of the field, sharing a strong incentive to learn as much as possible across a broad front, since no one can say from where the next great discovery will emerge. Moreover, the tools forged on one front are as likely as not to be employed on another, whether in investigations of physical dynamics with intrinsic fault tolerance, of new quantum algorithms, or of the engineering of materials for the new quantum components.

The brief history of QIS points to the essential role of "small science" driven by individual investigators. It is very important to continue to foster the research of individuals, and to encourage interactions across the traditional boundaries in physics, computer science, and engineering. Significant advances have sprung from unexpected quarters in the past, and further surprises should be expected — not just the emergence of new research directions but also the appearance of talented new people working in the field.

These considerations argue for stable long-term support of multidisciplinary research carried out by investigators either individually or in small collaborations. In the current scheme of things, there is a dearth of support for scientists and engineers whose research is aimed at foundational issues. Moreover, there is a pressing need to overcome structural problems of "dislocation." That is, students who are interested in quantum information science cannot be sure in which department to pursue that interest. Having nonetheless succeeded, these young graduates face yet another hurdle in that universities are reluctant to hire faculty working in a new and less established area that is not well matched to the department structure in academia.

In the end, there is no simple and obvious strategy for best fostering the continued advancement of a new field as diverse and dynamic as QIS. For each prescription for success there are conflicts and contradictions. For example, on the experimental front, the "individual PI" model will become increasingly difficult to sustain since the technical requirements for most experiments in QIS continue to become ever more daunting. There is thus a tension between maintaining diversity in investigations of physical systems and pursuing such investigations at the cusp of technical capability. Certainly instrumentation programs to support technically intensive research in QIS are vital to success. But equally certain is that the demand will greatly exceed the supply of funding for such programs. In concert with the various government agencies, industrial research laboratories, and national laboratories, the community will have to devise new research strategies that, on the one hand, foster the contributions of individual PIs and, on the other hand, address the question of optimal resource utilization.

THE ROLE OF NSF

The NSF can meet the need for stable, long-term support aimed at laying the foundations for a new science in a way that more mission-oriented agencies cannot (and have not). Although arguably the most spectacular results in QIS to date relate to large-scale quantum computation for cryptanalysis, NSF programs should be much more broadly based and should emphasize the development of a whole new area of science. As highlighted in preceding sections, promising topics "beyond the Shor" include quantum metrology, quantum networks and communication, and quantum components at the nanoscale. We note that, while the US (via the NSA in particular) has taken the lead in the effort to develop a large-scale quantum computer, we lag far behind the European community in establishing collaborations and research programs directed toward the broader foundations of QIS.

Much work in QIS will be hard to fund through traditional mechanisms because it is speculative and far from mainstream activities. An important role for NSF is to encourage "far out ideas" in new areas and to sustain long-term support directed toward "hard problems." However, the cycle of peer review and the organization of programs tend to favor incremental progress in well established areas instead. Furthermore, in the emerging arena of QIS, the traditional discipline-based organization of education and research may not be appropriate. Thus meeting the needs of the QIS community poses special problems, and we do not pretend to know the answers. Central issues are that support for QIS research should be coordinated among the NSF divisions, and that advocacy for QIS at NSF should be vested in some tangible form — advocates are essential to provide institutional memory at NSF and to ensuring long-term stability.

We favor support directed toward individual investigators engaged in "small science," which we feel will be more productive than funding concentrated in large centers. However, we do not preclude the concept of centers altogether; the cost of infrastructure and the benefits of collaboration could lead to a persuasive case that a portion of funding should be directed to center support. Novel concepts may be effective, such as "virtual centers" that promote exchanges of students and post-doctoral scholars. NSF-sponsored workshops might also help to foster productive interdisciplinary collaborations.

Especially important is the development of the careers of young people. Although QIS attracts the very best students, it is difficult for these students to continue to advance their careers after graduate school. While in part this is an unavoidable situation in a rapidly developing new field, the NSF can play an indispensable role by providing funding opportunities to help establish and maintain young careers. These young people are a vital resource not only for QIS but for the nation, in view of the ever increasing impact of information technology on our society.

Day 1, October 28, 1999

Morning Session

Overview talks
A. Ekert, Chair

Afternoon Session – Physical Systems
B. Whaley, Chair

8:00 – 10:00 Town Meeting

J. Dehmer, M. Foster, L. Goldberg, Jack Lightbody, Art Sanderson, Hollis Wickman
NSF Representatives

Day 2, October 29, 1999

Morning Session
C. Caves, Chair

Quantum Information and Algorithms

Group II – Quantum Information and the Physical Sciences, Leader: J. Preskill (with C. Hood as scribe)

Group III – Physical Implementations, Leader: J. Kimble (with N. Amer as scribe)

4:00 – 5:00 Joint session with feedback from breakout groups, including recommendations for workshop report

5:00 Adjourn