Randomized Algorithms and Lower Bounds for Quantum Simulation

2009/10/21 by Chi Zhang, Zhang, Chi
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.0910.4145

openalex publication_date 2009/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider deterministic and \em randomized quantum algorithms simulating e^-iHt by a product of unitary operators e^-iA_jt_j, j=1,...,N, where A_j∈\H₁,...,H_m\, H=∑_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.

Citations

• On the Construction and Comparison of Difference Schemes
• Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations
• On the Relationship Between Continuous- and Discrete-Time Quantum Walk

Related

• The Practicality of Randomized Quantum Linear Systems Solvers
• Efficient Simulation of Random Quantum States and Operators
• Randomized and Quantum Algorithms Yield a Speed-Up for Initial-Value Problems
• Quantum supremacy and random circuits
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs