Demonstrating quantum advantage requires experimental implementation of a computational task that is hard to achieve using state-of-the-art classical systems. One approach is to perform sampling from a probability distribution associated with a class of highly entangled many-body wavefunctions. It has been suggested that this approach can be certified with the Linear Cross-Entropy Benchmark (XEB). We critically examine this notion. First, in a "benign" setting where an honest implementation of noisy quantum circuits is assumed, we characterize the conditions under which the XEB approximates the fidelity. Second, in an "adversarial" setting where all possible classical algorithms are considered for comparison, we show that achieving relatively high XEB values does not imply faithful simulation of quantum dynamics. We present an efficient classical algorithm that, with 1 GPU within 2s, yields high XEB values, namely 2-12% of those obtained in experiments. By identifying and exploiting several vulnerabilities of the XEB, we achieve high XEB values without full simulation of quantum circuits. Remarkably, our algorithm features better scaling with the system size than noisy quantum devices for commonly studied random circuit ensembles. To quantitatively explain the success of our algorithm and the limitations of the XEB, we use a theoretical framework in which the average XEB and fidelity are mapped to statistical models. We illustrate the relation between the XEB and the fidelity for quantum circuits in various architectures, with different gate choices, and in the presence of noise. Our results show that XEB's utility as a proxy for fidelity hinges on several conditions, which must be checked in the benign setting but cannot be assumed in the adversarial setting. Thus, the XEB alone has limited utility as a benchmark for quantum advantage. We discuss ways to overcome these limitations.
翻译:显示量子优势需要实验性地执行计算任务, 而计算任务很难使用最先进的古典系统。 一种方法是从与高度纠缠的多个身体波子相联的类别相关的概率分布中进行取样。 有人建议, 这种方法可以由线性跨 Entropy 基准( XEB 基准) (XEB) 来验证。 我们严格检查了这个概念。 首先, 在“ 基度” 环境中, 假设音量电路是诚实的, 我们描述XEB 选择接近准确性的条件。 其次, 在“ 对抗性” 设置中, 所有可能的经典算法都考虑进行比较, 我们表明, 相对较高的 XEB 值值值并不意味着对量性进行忠实的模拟。 我们展示了一个高效的经典算法, 1 GUP 在2 中, 产生高的 XEB 值, 也就是在实验中获得的2- 12%。 我们通过识别和利用XEB 的几种脆弱性电路路, 我们实现了高X 值的精确性, 但是, 我们的算算的数值比比比比比 只能用来解释我们测测算中的 XIEB 。 我们的直值和直径值结构中, 我们的测算的测算的成功度框架的测算。