论文标题
量子至高无上的tsirelson不平等
The Quantum Supremacy Tsirelson Inequality
论文作者
论文摘要
在噪声随机量子电路上验证近期量子至上实验的领先建议是线性跨透镜基准测试。对于$ n $ Qubits上的量子电路$ c $和样本$ z \ in \ {0,1 \}^n $，基准涉及计算$ | \ langle z | c | c | 0^n \ rangle |^2 $，即，从$ c $ c $上的$ c $上的$ c $上的$ c $上的$ z $上的可能性。在强烈的猜想中，关于估算量子电路输出概率的经典硬度，没有给定的多项式经典算法可以输出一个字符串$ z $，因此$ | \ langle z | c | c | c | c | c | 0^n \ rangle |^2 $大于$ \ frac {1}} $ gunn and and anon and anon和aarons and（aarons and anon），另一方面，对于一个随机量子电路$ c $，从$ c $ Achieves $ | \ langle z | c | 0^n \ rangle |^2 \ langle |^2 \ oft \ frac {2} {2^n} $取样$ z $。 与量子非局部相关性的Tsirelson不等式类似，我们问：多项式时量子算法可以比$ \ frac {2} {2} {2^n} $好得多？我们在查询（或黑匣子）模型中研究此问题，其中量子算法可以访问$ c $。我们表明，对于任何$ \ varepsilon \ ge \ frac {1} {\ mathrm {poly}（n）} $，输出样本$ z $，以便$ | \ langle z | c | c | c | c | c | c | c | c | c | c | c | c | c | c | c | c | c | c | c | c | 0^n \ rangle |^rangle |^ge \ ge \ ge \ ge \ frac frac {2 + \ varepsilon} $Ω\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 Haar随机$ n $ qubit State。我们还表明，当来自随机布尔函数的傅立叶分布中的$ c $样品时，从$ c $采样的幼稚算法是最佳的1 Query算法，用于最大化$ | \ langle z | c | c | 0^n \ rangle | rangle |^2 $。
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 $Ω\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.
