Multi-Tensor Contraction for XEB Verification of Quantum Circuits

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.