How behavior of systems with sparse spectrum can be predicted on a quantum computer
Yuri Ozhigov · Journal of Experimental and Theoretical Physics Letters · 2002
Call a spectrum of Hamiltonian H sparse if each eigenvalue can be quickly restored within ε from its rough approximation within ε1 by means of some classical algorithm. It is shown how the behavior of a system with a sparse spectrum up to time T=(1−ρ)/14ε can be predicted on a quantum computer with the time complexity t=4/(1−ρ)ε1 plus the time of classical algorithm, where ρ is the fidelity. The quantum knowledge of Hamiltonian eigenvalues is considered as the new Hamiltonian W H whose action on each eigenvector of H gives the corresponding eigenvalue. Speedup of evolution for systems with a sparse spectrum is possible, because, for such systems, the Hamiltonian W H can be quickly simulated on the quantum computer. For an arbitrary system (even in the classical case), its behavior cannot be predicted on a quantum computer even for one step ahead. By this method, we can also restore the history with the same efficiency.