Weak, strong, and uniform quantum simulations

In this work, we introduce different types of quantum simulations according to different operator topologies on a Hilbert space, namely, uniform, strong, and weak quantum simulations. We show that they have the same computational power that the efficiently solvable problems are in bounded-error quantum polynomial time. For the weak simulation, we formalize a general weak quantum simulation problem and construct an algorithm which is valid for all instances. Also, we analyze the computational power of quantum simulations by proving the query lower bound for simulating a general quantum process.

Figure 1

The circuit for the replacement channel $\mathcal{R}$. The leftmost gate with two crosses represents a qudit swap gate. A circle with $i$ in it means an $i$ control, and $X_i$ is the Pauli $X$ operator between states $|0\rangle$ and $|i\rangle$. The controlled $X_i$ represents a qudit controlled-not (cnot) gate, and here there are a sequence of such cnot gates for all $i$. The bottom three ancillas are traced out finally.

Figure 2

The circuit for the generation of a mixed state $\rho$. State $|\mathbf{0}\rangle$ in bold represents a qubit string of $|0\rangle$. $R$ is a multiqubit gate to generate superposition depending on the form of the mixed state. $\mathbf{H}$ is the Walsh-Hadamard gate. $R_y$ is the single-qubit rotation about the $y$ axis. $O_{\alpha }$ and its Hermitian conjugate are queries. $G$ represents the generalized Grover searching algorithm [37, 38, 39]. The controller (a) is traced out at the end. The generation of a pure state is achieved when the controller is omitted, so the query complexities for generation of pure and mixed states are the same.