Verifying Quantum Advantage Experiments with Multiple Amplitude Tensor Network Contraction

The quantum supremacy experiment, such as Google Sycamore [F. Arute et al., Nature (London) 574, 505 (2019).], poses a great challenge for classical verification due to the exponentially increasing compute cost. Using a new-generation Sunway supercomputer within 8.5 d, we provide a direct verification by computing $3\times {10}^6$ exact amplitudes for the experimentally generated bitstrings, obtaining a cross-entropy benchmarking fidelity of 0.191% (the estimated value is 0.224%). The leap of simulation capability is built on a multiple-amplitude tensor network contraction algorithm which systematically exploits the “classical advantage” (the inherent “store-and-compute” operation mode of von Neumann machines) of current supercomputers, and a fused tensor network contraction algorithm which drastically increases the compute efficiency on heterogeneous architectures. Our method has a far-reaching impact in solving quantum many-body problems, statistical problems, as well as combinatorial optimization problems.

Figure 1

Demonstration of the maTNC algorithm. (a) Division of the original tensor network formed in the TNC algorithm into consecutive subtensor networks, where each subtensor network starts with a bright tensor containing one or more output indices and ends before the next bright tensor. (b) Organizing the contraction of the $k$ tensor networks resulting from computing $k$ amplitudes into a tree, where each node of the tree corresponds to an output index and the edge after it corresponds to a specific choice of this index. A full path along the tree from left to right corresponds to contracting one tensor network and traversing the tree means to contract all the tensor networks. Generally, for computing a large number of uncorrelated amplitudes, the leftmost edge (the trunk) contains most of the tensors, the number of edges in a vertical layer grows exponentially in the central part (the branch) and stops growing in the tail (the twig).

Figure 2

(a) The red line with diamond shows the scaling of the theoretical complexity of our maTNC against the number of amplitudes $k$ for Sycamore, while the blue line shows the linear scaling of the saTNC as a reference. (b) The quantum speedup of Sycamore against our maTNC, defined as our classical runtime divided by the quantum runtime, as a function of $k$.

Figure 3

Histogram for the distribution of the probabilities of the $3\times {10}^6$ experimentally generated bitstrings from Sycamore [44], where the $x$ axis is log rescaled. The blue solid line denotes the corresponding theoretical prediction under the same cross-entropy benchmarking (XEB) fidelity as defined in Eq. (2).