Randomized Algorithms and Lower Bounds for Quantum Simulation

Abstract

We consider deterministic and {\em randomized} quantum algorithms simulating $e^{-iHt}$ by a product of unitary operators $e^{-i{A}_j{t}_j}$, $j=1,...,N$, where $A_j\in \{H_1,...,H_m\}$, $H={\sum }_{i=1}^m{H}_i$ and $t_j>0$ for every $j$. Randomized algorithms are algorithms approximating the final state of the system by a mixed quantum state. First, we provide a scheme to bound the trace distance of the final quantum states of randomized algorithms. Then, we show some randomized algorithms, which have the same efficiency as certain deterministic algorithms, but are less complicated than their opponentes. Moreover, we prove that both deterministic and randomized algorithms simulating $e^{-iHt}$ with error $\e$ at least have $Ω(t^{3/2}\e^{-1/2})$ exponentials.

6 pages

References in corpus (6)

• Universal computation by quantum walk
• An example of the difference between quantum and classical random walks
• On the relationship between continuous- and discrete-time quantum walk
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Efficient Simulation of Quantum Systems by Quantum Computers
• A Quantum Algorithm for the Hamiltonian NAND Tree