Abstract:
Call a spectrum of Hamiltonian $H$ sparse if each eigenvalue can be quickly restored within $\varepsilon$ from its rough approximation within $\varepsilon_1$ by means of some classical algorithm. It is shown how a behavior of system with sparse spectrum up to time $T={(1-\rho)}/{14\varepsilon}$ can be predicted on a quantum computer with the time complexity $t={4}/{(1-\rho)\varepsilon_1}$ plus the time of classical algorithm, where $\rho$ 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 an evolution for systems with the 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.
Fulltext:
PDF file (192 kB)