Algorithmic quantum channel simulation

Quantum simulation is one of the earliest motivations for quantum computing, and has been established as an important application of quantum computers. So far the focus of quantum simulation is mainly on Hamiltonian-driven evolution for locally interacting systems, here we extend the quantum simulation tasks to more general quantum dy- namics described as quantum channels, and establish the novel framework of algorithmic quantum channel simulation. Particularly, we employ the simulation algorithm based on quantum channel decomposition in terms of convex com- bination of extreme channels, which has been an open problem for quite a long time and seldom investigated. Our classical optimization algorithm for channel decomposition employs the Kraus operator and quantum circuit represen- tations for arbitrary extreme channels and generalized extreme channels with circuit cost achieving the circuit lower bound. Besides, for deeper understanding of quantum simulation problems and algorithms, and also the difference between computation and simulation, we further consider more general quantum simulation tasks by providing defi- nitions of various quantum simulation problems. The quantum query lower bound for simulating a general quantum process in the query model is also proved.