  The computational advantage of noisy quantum computers has been demonstrated
by sampling the bitstrings of quantum random circuits. An important issue is
how the performance of quantum devices could be quantified in the so-called
"supremacy regime". The standard approach is through the linear cross entropy
benchmark (XEB), where the theoretical value of the probability is required for
each bitstring. However, the computational cost of XEB grows exponentially. So
far, random circuits of the 53-qubit Sycamore chip were verified up to 10
cycles of gates only; the XEB fidelities of deeper circuits were approximated
with simplified circuits instead. Here we present a multi-tensor contraction
algorithm for speeding up the calculations of XEB for quantum circuits, where
the computational cost can be significantly reduced through some form of
memoization. As a demonstration, we analyzed the experimental data of the
53-qubit Sycamore chip and obtained the exact values of the corresponding XEB
fidelities up to 16 cycles using only moderate computing resources (few GPUs).
If the algorithm was implemented on the Summit supercomputer, we estimate that
for the supremacy (20 cycles) circuits, it would only cost 7.5 days, which is
several orders of magnitude lower than previously estimated in the literature.
