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

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 langleψ_t|hatρ_{rm out}|ψ_trangle between an actual n-qubit output state hatρ_{rm out} obtained from the noisy intermediate-scale quantum computation and the ideal output state (i.e., the target state) |ψ_trangle. Although the direct fidelity estimation method requires O\(2ⁿ\) copies of hatρ_{rm out} on average, our method requires only O\(D^3212D\) copies even in the worst case, where D is the denseness of |ψ_trangle. For logarithmic-depth quantum circuits on a sparse chip, D is at most O\(log{n}\), and thus O\(D^3212D\) 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.