The Quantum Supremacy Tsirelson Inequality
- URL: http://arxiv.org/abs/2008.08721v4
- Date: Wed, 8 Sep 2021 22:29:01 GMT
- Title: The Quantum Supremacy Tsirelson Inequality
- Authors: William Kretschmer
- Abstract summary: For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$.
We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
- Score: 0.22843885788439797
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A leading proposal for verifying near-term quantum supremacy experiments on
noisy random quantum circuits is linear cross-entropy benchmarking. For a
quantum circuit $C$ on $n$ qubits and a sample $z \in \{0,1\}^n$, the benchmark
involves computing $|\langle z|C|0^n \rangle|^2$, i.e. the probability of
measuring $z$ from the output distribution of $C$ on the all zeros input. Under
a strong conjecture about the classical hardness of estimating output
probabilities of quantum circuits, no polynomial-time classical algorithm given
$C$ can output a string $z$ such that $|\langle z|C|0^n\rangle|^2$ is
substantially larger than $\frac{1}{2^n}$ (Aaronson and Gunn, 2019). On the
other hand, for a random quantum circuit $C$, sampling $z$ from the output
distribution of $C$ achieves $|\langle z|C|0^n\rangle|^2 \approx \frac{2}{2^n}$
on average (Arute et al., 2019).
In analogy with the Tsirelson inequality from quantum nonlocal correlations,
we ask: can a polynomial-time quantum algorithm do substantially better than
$\frac{2}{2^n}$? We study this question in the query (or black box) model,
where the quantum algorithm is given oracle access to $C$. We show that, for
any $\varepsilon \ge \frac{1}{\mathrm{poly}(n)}$, outputting a sample $z$ such
that $|\langle z|C|0^n\rangle|^2 \ge \frac{2 + \varepsilon}{2^n}$ on average
requires at least $\Omega\left(\frac{2^{n/4}}{\mathrm{poly}(n)}\right)$ queries
to $C$, but not more than $O\left(2^{n/3}\right)$ queries to $C$, if $C$ is
either a Haar-random $n$-qubit unitary, or a canonical state preparation oracle
for a Haar-random $n$-qubit state. We also show that when $C$ samples from the
Fourier distribution of a random Boolean function, the naive algorithm that
samples from $C$ is the optimal 1-query algorithm for maximizing $|\langle
z|C|0^n\rangle|^2$ on average.
Related papers
- Quantum (Inspired) $D^2$-sampling with Applications [0.138120109831448]
We show a quantum implementation of $k$-means++ that runs in time $tildeO(zeta2 k2)$.
It can be shown through a robust approximation analysis of $k$-means++ that the quantum version preserves its $O(logk)$ approximation guarantee.
This results in a fast quantum-inspired classical implementation of $k$-means++, which we call QI-$k$-means++, with a running time $O(Nd) + tildeO(zeta
arXiv Detail & Related papers (2024-05-22T05:13:28Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.
Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.
Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
arXiv Detail & Related papers (2023-08-16T06:46:37Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions.
We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$.
We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
arXiv Detail & Related papers (2023-04-25T15:32:37Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy.
For small enough $epsilon$, we show an improved algorithm with sample complexity.
arXiv Detail & Related papers (2020-06-06T13:34:41Z) - Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
Google's noisy quantum simulation of a 53 qubit circuit $C$ achieved a fidelity value of $(2.24pm0.21)times10-3$.
Our results can be considered as an evidence that fooling the linear XEB test might be easier than achieving a full simulation of quantum circuit.
arXiv Detail & Related papers (2020-05-05T18:01:48Z) - Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
We show that a quantum algorithm can be solved by making $2O(k)$ queries to the inputs.
For any constant $varepsilon>0$, this gives a $O(1)$ vs. $N2/3-varepsilon$ separation.
arXiv Detail & Related papers (2019-12-29T01:42:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.