  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\psi_t|\hat{\rho}_{\rm
out}|\psi_t\rangle$ 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_t\rangle$. 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_t\rangle$. 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.
