English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the hardness of computing additive approximations to outputprobabilities of random quantum circuits. We consider three random circuitfamilies, namely, Haar random, $p=1$ QAOA, and random IQP circuits. Our resultsare as follows. For Haar random circuits with $m$ gates, we improve on priorresults by showing $\mathsf{coC_=P}$ hardness of average-case additiveapproximations to an imprecision of $2^{-O(m)}$. Efficient classical simulationof such problems would imply the collapse of the polynomial hierarchy. Forconstant depth circuits i.e., when $m=O(n)$, this linear scaling in theexponent is within a constant of the scaling required to show hardness ofsampling. Prior to our work, such a result was shown only for Boson Sampling inBouland et al (2021). We also use recent results in polynomial interpolation toshow $\mathsf{coC_=P}$ hardness under $\mathsf{BPP}$ reductions rather than$\mathsf{BPP}^{\mathsf{NP}}$ reductions. This improves the results of priorwork for Haar random circuits both in terms of the error scaling and the powerof reductions. Next, we consider random $p=1$ QAOA and IQP circuits and showthat in the average-case, it is $\mathsf{coC_=P}$ hard to approximate theoutput probability to within an additive error of $2^{-O(n)}$. For $p=1$ QAOAcircuits, this work constitutes the first average-case hardness result for theproblem of approximating output probabilities for random QAOA circuits, whichinclude Sherrington-Kirkpatrick and Erd\"{o}s-Renyi graphs. For IQP circuits, aconsequence of our results is that approximating the Ising partition functionwith imaginary couplings to an additive error of $2^{-O(n)}$ is hard even inthe average-case, which extends prior work on worst-case hardness ofmultiplicative approximation to Ising partition functions.

Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent