Sampling of globally depolarized random quantum circuit

Abstract

The recent paper [F. Arute et al. Nature {\bf 574}, 505 (2019)] considered exact classical sampling of the output probability distribution of the globally depolarized random quantum circuit. In this paper, we show three results. First, we consider the case when the fidelity $F$ is constant. We show that if the distribution is classically sampled in polynomial time within a constant multiplicative error, then $\mathrm{BQP}\subseteq \mathrm{SBP}$, which means that BQP is in the second level of the polynomial-time hierarchy. We next show that for any $F\le 1/2$, the distribution is classically trivially sampled by the uniform distribution within the multiplicative error $F{2}^{n+2}$, where $n$ is the number of qubits. We finally show that for any $F$, the distribution is classically trivially sampled by the uniform distribution within the additive error $2F$. These last two results show that if we consider realistic cases, both $F\sim 2^{-m}$ and $m\gg n$, or at least $F\sim 2^{-m}$, where $m$ is the number of gates, quantum supremacy does not exist for approximate sampling even with the exponentially-small errors. We also argue that if $F\sim 2^{-m}$ and $m\gg n$, the standard approach will not work to show quantum supremacy even for exact sampling.

arXiv comment9 pages, no figure

References in corpus (7)

• On the Power of One Bit of Quantum Information
• Average-case complexity versus approximate simulation of commuting quantum computations
• On the hardness of classically simulating the one clean qubit model
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Power of one non-clean qubit
• Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count

Cited by in corpus (1)

• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity