Quantum Analog Computation
Research Update: December '96 - September '97
Overview:
A quantum computer is a device that processes information stored on quantum variables such as spins, photons, or atoms. The discrete character of quantum variables makes them natural candidates for storing digital information: a spin can point up or down, and so can register a bit of information. Unlike a bit of classical information, however, which can only register 0 or 1, a quantum bit can in some sense register 0 and 1 at once: a spin can be in a superposition of a (spin up) and b (spin down), where a and b are complex numbers that can vary continuously. That is, quantum information possesses both digital and analog qualities.
The original quantum computer proposed by Benioff [1] stored digital information on quantum bits, but performed computations that were essentially classical: bits were not put in superpositions. In contrast, Shor's algorithm for factoring exploits both digital and analog properties of quantum computers: interference between quantum bits in superpositions of different logical states plays a key role. Since Shor's proposal, a considerable amount of effort has been expended to find other problems that quantum computers might solve more easily than classical computers.
In fact, the first problem posed for quantum computers was entirely analog: in 1982, Feynman [1] asked whether quantum computers might be more efficient than classical computers for providing analog simulations of other quantum systems. Feynman noted that simulating quantum systems on classical computers is hard. Some information about a quantum system's behavior can be extracted from semiclassical approximations or from Monte Carlo methods. (Section v on many-body approaches addresses the question of how such techniques can be applied usefully to quantum computation.) However, Feynman pointed out that the only known way to simulate the full time evolution of a quantum system is to integrate the equations of motion for quantum superpositions in Hilbert space. The size of Hilbert space is exponentional in the number of variables in the system, so that to simulate the time evolution of forty spin-1/2 particles, for example, requires the ability to exponentiate 240 x 240 matrices acting on 240 dimensional vectors. Feynman then conjectured that it might be possible to bypass this exponential explosion by having one quantum system simulate another directly, so that the states of the simulator obey the same equations of motion as the states of the simulated system.
Feynman's conjecture was recently proved by one of us [c]: quantum computers can in principle be programmed to provide analog simulations of arbitrary local quantum systems. We propose to investigate the practical implications of this result for a variety of quantum systems that are hard to simulate classically. Systems to be investigated include: 1) High temperature, high density plasmas; 2) Systems described by lattice gauge theories such as quantum chromodynamics; 3) Lattice solid state models, including solid state fermion systems such as the Hubbard model whose quantum symmetries make them difficult to simulate via Monte Carlo techniques; 4) Solid state models involving long range correlations such as models for high Tc superconductivity; 5) Quantum models of molecular behavior. As noted above, quantum analog computing can effect exponential speed-ups in principle: our aim is to identify the classically intractible problems that can be simulated using just a few quantum bits. The following tasks will be performed: The effects of environmental interactions and of decoherence on quantum analog computers will be explored. The error-correction techniques being developed will be applied to quantum analog computations, in contrast to the absence of error correction in classical analog computation. Quantum programming techniques need to be developed: for example, a set of commands will be developed that when supplied to a quantum computer make its bits imitate the behavior of a quark gluon plasma at very high temperature and pressure. Preliminary results indicate that only a few quantum bits are needed to create and explore the behavior of exotic states of matter: a goal of the program is to identify tests of nonlocality and entanglement that can be carried out by simple networks of quantum logic gates.
References
a. Q. A. Turchette, C. J. Hood, W. Lange, H. Mabuchi, and H. J. Kimble, Phys. Rev. Lett. 75, 4710(1995).
b. S. Lloyd, Phys. Rev. Lett. 75, 346(1995).
c. S. Lloyd, "Quantum Analog Computers," submitted to Science (1996).
d. J. Preskill, "Can Quantum Errors Be Corrected?," unpublished notes (November, 1994).
e. A. Despain et al., JASON Report JSR-95-115, Mitre Corporation, McLean, VA.
f. D. Beckman, A. Chari, S. Devabhaktuni, and J. Preskill, Caltech Preprint CALT-68-2021 (1995).
g. H. Mabuchi and P. Zoller, Phys. Rev. Lett.(1996).
h. N. J. Cerf and C. Adami, "Negative Entropy and Information in Quantum Mechanics," Caltech Preprint (1995), quant-phy/9512022.
1. R. P. Feynman, Intl. J. Theoretical Physics 21, 467 (1982); D. Deutsch, Proc. R. Soc. Lond. A400, 97 (1985); P. Benioff, Phys. Rev. Lett. 48, 1581(1982).
2. P. W. Shor, in 35th Annual Symposium on Foundations of Computer Science: Proceedings, ed. S. Goldwasser, IEEE Computer Society Press (1994).
3. C. Monroe, D. M. Meekhof, B. E. King, W. M. Itano, and D. J. Wineland, Phys. Rev. Lett. 75, 4714(1995).
4. T. Pellizzari, S. A. Gardiner, J. I. Cirac, and P. Zoller, "Decoherence, Continuous Observation, and Quantum Computing: A Cavity QED Model," Phys. Rev. Lett. 75, 3788 (1995).
5. J. I. Cirac and P. Zoller, Phys. Rev. Lett. 74, 4091 (1995).
6. A. Barenco, D. Deutsch, A. Ekert, and R. Jozsa, Phys. Rev. Lett. 74, 4083 (1995); T. Sleator and H. Weinfurter, ibid., 4087; J. I. Cirac and P. Zoller, ibid., 4091.
7. C. W. Gardiner, Phys. Rev. Lett 70, 2269 (1993); H. J. Carmichael, ibid., 2273.
8. A. S. Parkins, P. Marte, P. Zoller, O. Carnal, and H. J. Kimble, Phys. Rev. A 51, 1578 (1995).
9. Z. Hu and H. J. Kimble, Optics Lett. 19,1888 (1994).
10. R. Hughes, et. al., "Quantum Computation and Factoring," Presentation from Los Alamos National Laboratory, (1995).
11. R. Landauer, "Is quantum mechanically coherent computation useful?," in Proceedings of the Drexel-4 Symposium on Quantum Nonintegrability -- Quantum-Classical Correspondence, edited by D. H. Feng and B.-L. Hu (International Press, to appear).
12. P. W. Shor, Phys. Rev. A 52, 2493 (1995); A. R. Calderbank and P. W. Shor, "Good quantum error-correcting codes exist," (1995, unpublished), quant-ph/9512032; A. Steane, "Multiple particle interference and quantum error correction," (1995, unpublished), quant-ph/9601029.
13. For an elementary review see C. H. Bennett, G. Brassard, and A. K. Ekert, Sci. Am. Oct. 1992, 50.
14. C. H. Bennett et al., "Purification of noisy entanglement and faithful teleportation via noisy channels," (1995, unpublished); D. Deutsch et al., "Entanglement-based quantum cryptography is unconditionally secure," (1995, unpublished).
15. V. Vedral, A. Barenco, and A. Ekert, "Quantum networks for elementary arithmetic operations," Oxford preprint (1995), quantu-ph/9511018.
16. C. Miquel, J. P. Paz, R. Perazzo, "Factoring in a dissipative quantum computer," Technical report 9601021 from Los Alamos National Laboratory repository, (1996).
17. C. H. Bennett et al., "Purification of noisy entanglement and faithful teleportation via noisy channels," (1995, unpublished).
18. D. Deutsch et al., "Entanglement-based quantum cryptography is unconditionally secure," (1995, unpublished).
19. H.-K. Lo and H. F. Chau, "Quantum cryptography in noisy channels," (1995, unpublished), quant-ph/9511025.
