Divide-and-conquer verification method for noisy intermediate-scale quantum computation

Quantum 6, 758 (2022).

https://doi.org/10.22331/q-2022-07-07-758

Several noisy intermediate-scale quantum computations can be regarded as logarithmic-depth quantum circuits on a sparse quantum computing chip, where two-qubit gates can be directly applied on only some pairs of qubits. In this paper, we propose a method to efficiently verify such noisy intermediate-scale quantum computation. To this end, we first characterize small-scale quantum operations with respect to the diamond norm. Then by using these characterized quantum operations, we estimate the fidelity $langlepsi_t|hat{rho}_{rm out}|psi_trangle$ between an actual $n$-qubit output state $hat{rho}_{rm out}$ obtained from the noisy intermediate-scale quantum computation and the ideal output state (i.e., the target state) $|psi_trangle$. Although the direct fidelity estimation method requires $O(2^n)$ copies of $hat{rho}_{rm out}$ on average, our method requires only $O(D^32^{12D})$ copies even in the worst case, where $D$ is the denseness of $|psi_trangle$. For logarithmic-depth quantum circuits on a sparse chip, $D$ is at most $O(log{n})$, and thus $O(D^32^{12D})$ is a polynomial in $n$. By using the IBM Manila 5-qubit chip, we also perform a proof-of-principle experiment to observe the practical performance of our method.