= ASSESSMENT OF CURRENT RESULTS AND OUTLOOK ON FUTURE EFFORTS =
QUANTUM INFORMATION SCIENCE THEORY
COMPUTATIONAL MODELS & ARCHITECTURES
There are many different ideas of how to make quantum systems compute. While these different computational models are typically equivalent in the sense that one can simulate the other with only polynomial overheads in resources, they may be quite different in practice, when it comes to a particular class of problems. They also suggest different procedures to achieve fault tolerant computation, many of them yet to be explored in detail. At the moment the main contenders of fundamental architectures are:
- The gate or circuit model (computation realized by series of elementary unitary transformations on a few qubits at a time).
- The one-way quantum computer (computation realized by sequence of 1-bit measurements on a pre-entangled cluster state).
- Adiabatic computing (computation realized by smoothly changing a Hamiltonian, whose ground state, at the end of the process, encodes the solution of the given problem).
- Quantum cellular automata (quantum version of classical cellular automata).
- Quantum Turing machine (quantum version of classical Turing machine).
Most recently, we have seen a series of theoretical work analyzing the connection between the different computational models. The benefit of these works lies in a better understanding of the capabilities and advantages of the individual models, and of the essential features of a quantum computer. In the future we expect that optimized models (i.e. taking the best out of the different approaches) will be developed. We also expect that these models will have an increasing impact on (i) the formulation of new quantum algorithms and (ii) the evaluation of physical systems regarding their suitability for fault-tolerant quantum computation. Both of these points are of great importance for the field: While new algorithms will further enlarge the range of applications for quantum computers, new methods for fault-tolerant computation will hopefully make it technologically less challenging to realize scalable quantum computers in the laboratory.
Key references
[1] D. Deutsch, ‘‘Quantum computational networks’’, Proc. R. Soc. Lond. A 425, 73 (1989).
[2] A. Barenco, C.H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J.A. Smolin, and H. Weinfurter, ‘‘Elementary gates for quantum computation’’, Phys. Rev. A 52, 3457 (1995).
[3] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, ‘‘A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem’’, Science 292, 472 (2001).
[4] B. Schumacher and R. Werner, ‘‘Reversible cellular automata’’, quant-ph/0405174, http://xxx.arxiv.org.
[5] R. Raussendorf and H.-J. Briegel, ‘‘A one-way quantum computer’’, Phys. Rev. Lett. 86, 5188 (2001).