Quantum simulation of quantum chaos

Physical Review Letters 86, 2890-2893 (26 March 2001)

The massive parallelism of quantum computers can in principle allow computations to be performed much more quickly than is possible using classical computers. But in practice, it is not trivial to devise quantum algorithms that allow this power to be harnessed. Peter Shor's 1994 algorithm for prime-factorization of integers was the first quantum algorithm to achieve an exponential gain in computation speed relative to classical methods. Lov Grover's well-known quantum algorithm for searching unsorted data (see Phys. Rev. Lett. 79, 325-328; 1997) provides a significant improvement on classical methods, but the gain is only polynomial, rather than exponential.

In 1996, Seth Lloyd showed that quantum computers could be used as efficient simulators of quantum systems: quantum simulation provides exponential speed-up relative to classical computation for any system that evolves according to local interactions (Lloyd, S. Science 273, 1073-1078; 1996). Since then, quantum algorithms have been devised that provide exponential speed-up for simulating fermionic systems, finding eigenvalues and eigenvectors and evaluating partition functions, among other applications.

In a recent issue of Physical Review Letters, B. Georgeot and D. L. Shepelyansky, of the quantum physics laboratory at the University of Toulouse, apply the idea of quantum simulation to a famous model in quantum chaos, the kicked rotator. Their algorithm simulates a kicked rotator with N levels in O ((log₂ N)³) operations, instead of O (N log₂ N) operations for the classical algorithm.

The authors point out that the quantum kicked rotator is a very rich dynamical system; in particular, it exhibits quantum ergodicity, and a dynamical localization phenomenon, analogous to Anderson localization, in which quantum interference suppresses classical chaotic diffusion. If the problem of the precision of quantum computations can be solved (and this is a big problem), the authors suggest that a quantum computer with a few tens of qubits could probe the evolution of such a rich quantum system at the limit of large quantum number — that is, at the interface between quantum and classical mechanics.

Exponential Gain in Quantum Computing of Quantum Chaos and Localization
B. GEORGEOT & D. L. SHEPELYANSKY
We present a quantum algorithm which simulates the quantum kicked rotator model exponentially faster than classical algorithms. This shows that important physical problems of quantum chaos, localization, and Anderson transition can be modeled efficiently on a quantum computer. We also show that a similar algorithm simulates efficiently classical chaos in certain area-preserving maps.
Physical Review Letters 86, 2890-2893 (26 March 2001)
| click here for article |
©2001 The American Physical Society

Quantum simulation of quantum chaos

read more about quantum computing and quantum simulation