The recent explosion of theoretical, experimental and industrial interest in quantum information processing has been sparked by a series of celebrated and now famous discoveries - among others: secure quantum key distribution, quantum error correction and fault tolerant quantum computation, Shor's factorisation algorithm, quantum teleporation and dense coding. However, and despite some important further positive results and no-go theorems, we still have relatively little firm understanding of the true scope of what can be achieved by quantum information processing in computation, cryptography, communication and coding and other fields. The future commercial evolution of the field will certainly be driven by new applications: everyone realises, for example, that efficient factorisation alone will not create a mass market for quantum computers. The collaborative projects we propose here are directed squarely at finding, developing and implementing important new applications of quantum information processing.

One intriguing set of questions, of considerable theoretical and practical importance, has been raised by recent work by Farhi, Goldstone, Sipser and collaborators at MIT. They have developed novel quantum computing algorithms which, like some successful classical algorithms but unlike almost all quantum algorithms proposed to date, are inspired by insights from theoretical physics rather than pure mathematics and traditional computing theory. FGS et al. show how to address NP and NP-complete classical problems by studying the evolution of a quantum system with a slowly varying Hamiltonian, whose form depends on the problem. They note that the adiabatic theorem guarantees that, so long as there is a gap between the varying ground state and first excited state, a sufficiently slow evolution will keep the system in the ground state. They show how to use this fact to evolve from a known ground state of a fixed Hamiltonian to the ground state of a problem-specific Hamiltonian, from which the solution of the problem can be read off.

They show too that this process can be efficiently simulated, with only polynomial overhead, on quantum computers following the conventional network design. Finally, they demonstrate, by classical simulations of the quantum algorithm, that the time required scales only polynomially in the problem size, for typical problems, when the problem parameter is small.

These results clearly do not logically imply that the FGS algorithms give a polynomial time quantum solution to classical NP-complete problems - a result which would be surprising, and far more dramatic than any to date in quantum algorithm theory. They do, however, suggest a new type of quantum algorithm which works in a very different way from any previously studied, and which is suggestively efficient on small size problems. Further theoretical and computational work is needed, either to identify at least some small subclass of problems on which it fails, or to characterise an interesting general class of problems on which it is expected to succeed, or both.

For instance, one might reasonably hypothesise from FGS's simultations that the algorithm efficiently solves typical randomly generated examples of hard problems, such as clique search in a randomly generated graph, either up to some size threshold or for all problem sizes. Such a result, if verifiable, would be an important development, since no efficient classical algorithms are known even for typical (i.e. not hardest) cases of clique search in random graphs. As well as the original authors, Lloyd at MIT and Kent at Cambridge have been working on these questions, and a more extensive collaboration is developing.

A second, somewhat related, problem arises from the potential threat posed to classical cryptography by quantum computers. Essentially all widely used cryptographic schemes at present rely on the difficulty of factorisation or problems known to be equivalent to factorisation. Since Shor's algorithm shows that quantum computers can factorise efficiently, all existing schemes would be vulnerable if large quantum computers were built.

One response to this problem, of course, is to replace classical cryptographic schemes by quantum schemes. We know, for example, that quantum key distribution is perfectly secure, even against adversaries equipped with quantum computers. Unfortunately, though, there are many important cryptographic tasks (such as bit commitment) for which this is not the case - it can be proved that any quantum scheme would be breakable by an adversary equipped with a quantum computer. Moreover, though quantum information has many advantages over its classical counterpart, it is more fragile and presently much more difficult to transmit or store in bulk. It seems unlikely that classical communication is ever going to become completely redundant.

Another obvious response by classical cryptographers to the quantum threat is thus to devise new classical cryptographic schemes which can with great (if not perfect) confidence be said to be resistant to attack by quantum computers. This is an ambitious program, for two reasons. First, as already noted, quantum complexity theory is still comparatively undeveloped, and it is not clear what class of classical problems is likely to remain resistant to quantum attack. Many experts believe that general NP-complete classical problems will prove to be quantum NP, i.e. effectively unbreakable. However, as the FGS algorithms show, this is far from resolved. And even if true, it will not necessarily help classical cryptographers unless we can identify precisely which classes of instances of a given NP-complete problem are hard. Second, classical cryptography based on NP or NP-complete problems is relatively undeveloped. Moreover, some well-known classical schemes have in the past been claimed to be secure unless NP-complete problems have been solved, but proved on closer analysis to be breakable, relying as they did on special instances which turned out to be atypical.

Nonetheless, work is now underway in this area, and attracting industrial interest (unsurprisingly, since the long term future of secure communication seems likely to depend on the outcome). Part of Kent's work during his present period of leave at Hewlett-Packard's Mathematics, Cryptography and Security research group has been in this area, and together with the classical and quantum cryptography groups at Royal Holloway, London, and colleagues at Hewlett Packard, he is involved in organising two meetings in early 2001 between industrial and academic cryptographers to devise a road map for the development of the subject, with representatives from Abbey National, Baltimore Technologies, Indicii Salus Ltd and Mondex International.

The above-mentioned work of FGS and Lloyd is of obvious relevance, and collaborative investigation of its implications is developing.

As noted above, quantum control is the underlying technology that makes quantum computation possible. In turn, quantum information processing supplies quantum control with a wide variety of novel techniques for performing feedback, modeling, and state estimation. The quantum control group at MIT ( Cory, Lloyd, Mitter, Slotine) has recently developed a novel group of methods for quantum control that exploit quantum information processing techniques, including developing and performing experimental demonstrations of methods for coherent quantum feedback, in which a controller coherently acquires, processes, and feeds back quantum information. Other topics that are under investigation include feedback using weak collective measurements, quantum simulation and quantum analog computation, and the development of quantum observers for the purposes of modeling and control.

The MIT group will interact with the CU group, which has emphasized quantum state estimation. Quantum state estimation (a.k.a. "quantum tomography") is a fundamental problem in quantum information processing, with applications in algorithmics, quantum cryptographic protocols, quantum interrogation (see below) and to a broad range of o applied problems in nano-technology and nano-science.

Researchers from both institutions will collaborate to investigate the problems of

• optimal state estimation, including maximizing information acquisition while minimizing state disturbance;
• quantum observers that use quantum computation to construct and update accurate models of quantum processes.

A few years ago, Elitzur and Vaidman discovered schemes for the quantum measurement of classical bodies that, in a proportion of cases, produced positive results that were, in a certain well-defined sense, obtained by an "interaction-free" process. These schemes were refined further by Kwiat, Zeilinger and collaborators, who produced a beautiful scheme for discriminating between opaque and transparent objects in which the probability of absorption (in the case of opaqueness) can be made arbitrarily small.

These results led their discoverers to the hope that generalised versions of these schemes might have real world imaging applications. In particular, Elitzur and Vaidman espoused the hope that it might be possible to develop a "safe X-ray", which produces the image of a patient (as a normal X-ray photograph does), while allowing little or no absorption of harmful radiation.

This possibility has recently been investigated further by Mitchison and Kent at Cambridge, in collaboration with Massar, Pironoio and Wallace. Their results produce both positive and negative bounds on what can be achieved. On the negative side, Massar-Mitchison obtained a fundamental bound on the probability of discriminating between two semi-transparent objects without absorption, showing in particular that unless one object is completely transparent, the probability of absorption is always non-zero.

On the positive side, Kent-Wallace and Massar-Mitchison-Pironoio have identified a series of quantum interrogation techniques which allow much important information about an image to be obtained while reducing the absorption rate significantly below what is possible by existing techniques. Theoretically, these results imply that, while the "safe X-ray" is impossible, a significantly "safer X-ray" is certainly possible. Optimality questions remain to be resolved, as do the difficult problems of practical implementation. The theoretical problems, on which Kent and Mitchison are already working with collaborators, overlap with Lloyd's research, and wider collaboration is developing.

Quantum communication relies crucially on problems of quantum coding. Quantum coding and signal processing are in turn related to issues of quantum estimation and control, as in the classical case. Joint work on quantum coding and signal processing will concentrate on quantum Bayesian estimation techniques, and on addressing issues of quantum channel capacity.

Specifically, sequential Bayesian methods and particle filters will be applied to a range of problems in signal and data analysis. Bayesian methods will be applied to the two-vector formulation, for example to obtain the posterior distribution for two canonically conjugate variables. Numerical Bayesian methods and particle filters will be applied to estimate parameters and model structure from quantum measurements and to see if Cramer-Rao type bounds exist for Quantum estimation.

These techniques will also be applied to quantum control: the particle filter approach can be used in situations where LQG control does not apply, which must be the case in quantum control. Bayesian particle filters allow one to generalise concepts like the Kalman filter into situations where non-linearities and non-Gaussian assumptions are more realistic.

In addition, classical results concerning data compression will be generalized to the quantum case. Specifically, Schumacher's data compression theorem will be extended to the case of weakly-dependent quantum Gibbs states, where a quantum analogue of the Shannon-McMillan-Breiman Theorem may exist. The next step is to extend the formula for the capacity of a quantum channel from quantum IID to quantum Gibbs sources.

The scope of quantum cryptography beyond key distribution is an area which is only just beginning to be systematically explored. The field has a somewhat colourful history, in which hopes have occasionally been raised by the discovery of ingenious protocols which appear to be demonstrably secure, only to be dashed by the realisation that subtle flaws exist in the proofs. For example, recently, the 1999 Mayers-Salvail-Chiba-Kohno coin-tossing protocol, conjectured by its authors to be secure, was broken. (Coin tossing is a useful cryptographic task whereby two mistrustful parties generate a verifiably random bit by exchanging information.)

Almost always, these flaws derive from the fact that common-sense classical reasoning does not necessarily properly characterise what can be achieving by entangling and manipulating quantum information. Conversely, no-go theorems (such as the famous demonstration by Mayers and by Lo-Chau that unconditionally secure quantum bit commitment is impossible), while extremely important, can themselves contain hidden assumptions (in this case, as Kent showed, that the relative configuration of the parties' laboratories is such that relativistic signalling constraints can play no role), and may not necessarily be quite as large a stumbling-block as they first appear (in this case, the theorem does not exclude novel quantum tasks such as cheat-sensitive bit commitment, which may be adequate for many purposes).

Clearly, we need to develop a systematic understanding of what can be achieved by quantum information, either in creating security or in attacking it. We do not presently know whether many important classical cryptographic tasks (including coin tossing, some weaker variants of bit commitment, authentication over insecure channels, and many types of secure multi-party computation) can or cannot be implemented with unconditional security using quantum information. Nor do we have any real idea of the range of intrinsically quantum cryptographic tasks (that is, tasks which only make sense when applied to quantum information) which can be securely implemented.

The Cambridge-MIT collaboration includes Kent, Lloyd, and, as an industrial participant, Lo. Kent's work in this area includes

• the demonstration that relativistic signalling constraints can be used to implement unconditionally secure bit commitment, using continuing communication over fixed bandwidth channels
• a proof that quantum coin tossing is a strictly weaker task than bit commitment (so that the Mayers-Lo-Chau no-go theorem does not exclude the possibility of an unconditionally secure coin tossing scheme)
• identification of the distinction between simple bit commitment and bit commitment with a certificate of classicality, and a proof that the latter is impossible even if both relativity and quantum theory are used
• the discovery, with Hardy, of cheat-sensitive quantum cryptography, the demonstration of secure cheat-sensitive bit commitment protocols using quantum information and relativity (with no continuing signalling required), and the proposal of non-relativistic cheat-sensitive bit commitment protocols which are conjectured secure.

Lo, currently the Chief Scientific Officer of MagiQ Technologies, has been one of the leading workers in this area in recent years. Besides his work with Chau on the bit commitment no-go theorem, he has proven important no-go results on coin tossing and multi-party computation, produced well-known protocols for quantum secret sharing and key distribution, and proven the unconditional security of quantum key distribution over arbitrary distances.

Lloyd has recently developed novel quantum protocols, and is currently working on security proofs, with contributions from Kent and Lo.

The Cambridge semiconductor physics group is in the process of developing a new technology for a single photon source, based on the surface acoustic wave project outlined above and relying on the group's ability to use a surface acoustic wave to generate photons by forcing trapped electrons into a p-doped semiconductor. In these devices, up and down spins may recombine with holes to produce left and right circular polarised photons. These single photon devices can be used to produce an efficient and robust technology for secure quantum communication with a view to allowing a secure internet, implemented in solid state hardware. This raises the possibility of implementing chip-based short distance quantum cryptography, a potentially alluring commercial prospect.

An ideal single photon source removes a serious security weakness in the implementation of quantum key distribution and other cryptographic schemes. However, hard theoretical questions still have to be addressed. The long-term viability of this technology depends, ultimately, on whether a useful secure bit rate can be generated, allowing for the inevitable imperfections in source, detector, and channel. Depending on the application, one might also need to consider the robustness of the source and/or channel against deliberate sabotage attempts by a malicious adversary. (A bank machine card which offers perfect security in laboratory conditions, but whose security can be compromised by simple physical means, may be worse than useless.)

Addressing these crucial questions requires close collaboration between experimenters and theorists. It needs a clear understanding not only of the source and detector characteristics which can presently be achieved, but, more pertinently, of what could plausibly be achieved in the future, and of what features it would be most useful to refine. It also requires protocols optimally adapted to maximise secure bit rate given these particular characteristics. Theorists are required to address these latter questions, and to translate general security analyses (which are now quite well developed) into the particular experimental circumstances. Haus, Lloyd, Shapiro at MIT, Kent at Cambridge, and Lo, an industrial participant, are well versed in the relevant theory, and our proposal envisages that they will work closely with Barnes and Pepper on these questions.