# On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking

@article{Aaronson2020OnTC, title={On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking}, author={Scott Aaronson and Sam Gunn}, journal={ArXiv}, year={2020}, volume={abs/1910.12085} }

Recently, Google announced the first demonstration of quantum computational supremacy with a programmable superconducting processor. Their demonstration is based on collecting samples from the output distribution of a noisy random quantum circuit, then applying a statistical test to those samples called Linear Cross-Entropy Benchmarking (Linear XEB). This raises a theoretical question: how hard is it for a classical computer to spoof the results of the Linear XEB test? In this short note, we… Expand

#### Topics from this paper

#### Paper Mentions

#### 22 Citations

Classical Simulation of Quantum Supremacy Circuits

- Computer Science, Physics
- 2020

It is shown that achieving quantum supremacy may require a period of continuing quantum hardware developments without an unequivocal first demonstration, and an orders-of-magnitude reduction in classical simulation time is indicated. Expand

Non-Randomness of Google's Quantum Supremacy Benchmark

- Physics
- 2021

The first achievement of quantum supremacy has been claimed recently by Google for the random quantum circuit benchmark with 53 superconducting qubits. Here, we analyze the randomness of Google’s… Expand

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits

- Physics, Computer Science
- ITCS
- 2021

A classical randomized algorithm is given that for a given circuit $C$ of depth $d$ with Haar random 2-qubit gates achieves in expectation a fidelity value of $\Omega(\tfrac{n}{L} \cdot 15^{-d})$ in running time $\textsf{poly}(n,2^L)$. Expand

Classical Coding Approaches to Quantum Applications

- Computer Science, Physics
- ArXiv
- 2020

This dissertation investigates a recently proposed quantum algorithm for this task, and shows that the algorithm is optimal for each bit and it appears to achieve optimal performance when deciding the full transmitted message, and proposes an efficient algorithm that can translate a given logical Clifford operation on a stabilizer code into all physical Clifford circuits that realize that operation. Expand

Efficient verification of anticoncentrated quantum states

- Physics
- npj Quantum Information
- 2021

I present a method for estimating the fidelity F ( μ , τ ) between a preparable quantum state μ and a classically specified pure target state $$\tau =\left|\tau \right\rangle \left\langle \tau… Expand

A game of quantum advantage: linking verification and simulation

- Computer Science, Physics
- 2020

A formalism is presented that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee, and establishes three results, including that exponential resources may be unavoidable for even the most basic verification tasks in the setting of random quantum circuits. Expand

Comment on the Quantum Supremacy Claim by Google

- Physics
- 2021

Quantum computation promises to execute certain computational tasks on time scales much faster than any known algorithm on an existing classical computer, for example calculating the prime factors of… Expand

Depth-efficient proofs of quantumness

- Physics
- 2021

A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the quantum advantage of an untrusted prover. That is, a quantum prover can… Expand

Theory of Quantum System Certification

- Computer Science, Physics
- 2020

This tutorial explains prominent protocols for certifying the physical layer of quantum devices described by quantum states and processes, and provides an introduction to powerful mathematical methods, widely used in quantum information theory, in order to derive theoretical guarantees for the protocols. Expand

Efficient approximation of experimental Gaussian boson sampling

- Physics
- 2021

Two recent landmark experiments have performed Gaussian boson sampling (GBS) with a nonprogrammable linear interferometer and threshold detectors on up to 144 output modes (see Refs. 1 and 2). Here… Expand

#### References

SHOWING 1-10 OF 17 REFERENCES

Complexity-Theoretic Foundations of Quantum Supremacy Experiments

- Computer Science, Physics
- Computational Complexity Conference
- 2016

General theoretical foundations are laid for how to use special-purpose quantum computers with 40--50 high-quality qubits to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible. Expand

On the complexity and verification of quantum random circuit sampling

- Physics
- 2019

A critical milestone on the path to useful quantum computers is the demonstration of a quantum computation that is prohibitively hard for classical computers—a task referred to as quantum supremacy.… Expand

Quantum Supremacy and the Complexity of Random Circuit Sampling

- Physics, Computer Science
- ITCS
- 2019

This paper shows complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy, and shows that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Expand

Characterizing quantum supremacy in near-term devices

- Physics, Mathematics
- 2016

A critical question for quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of… Expand

Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

- Physics, Mathematics
- Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- 2010

We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is… Expand

The computational complexity of linear optics

- Computer Science, Physics
- STOC '11
- 2011

A model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode is defined, giving new evidence that quantum computers cannot be efficiently simulated by classical computers. Expand

Quantum supremacy using a programmable superconducting processor

- Medicine, Computer Science
- Nature
- 2019

Quantum supremacy is demonstrated using a programmable superconducting processor known as Sycamore, taking approximately 200 seconds to sample one instance of a quantum circuit a million times, which would take a state-of-the-art supercomputer around ten thousand years to compute. Expand

Average-case complexity versus approximate simulation of commuting quantum computations

- Physics, Computer Science
- Physical review letters
- 2016

It is shown that, if either of two plausible average-case hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. Expand

Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates

- Physics, Mathematics
- 2018

We prove that $poly(t) \cdot n^{1/D}$-depth local random quantum circuits with two qudit nearest-neighbor gates on a $D$-dimensional lattice with n qudits are approximate $t$-designs in various… Expand

Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits

- Computer Science, Physics
- 2019

This analysis shows that Sycamore circuits with 53 and 54 qubits can be simulated with high fidelity to arbitrary depth in a matter of days, outputting all the amplitudes on the Summit supercomputer at Oak Ridge National Laboratories. Expand