論文の概要: The Quantum Supremacy Tsirelson Inequality
- arxiv url: http://arxiv.org/abs/2008.08721v4
- Date: Wed, 8 Sep 2021 22:29:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 12:31:21.559056
- Title: The Quantum Supremacy Tsirelson Inequality
- Title（参考訳）: 量子超越性チレルソン不等式
- Authors: William Kretschmer
- Abstract要約: 量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。
任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: ノイズのあるランダム量子回路における短期量子超越実験を検証するための主要な提案は線形クロスエントロピーベンチマークである。
量子回路 $C$ on $n$ qubits とサンプル $z \in \{0,1\}^n$ の場合、このベンチマークは計算に$|\langle z|C|0^n \rangle|^2$、すなわち全てのゼロ入力の出力分布から$C$を測定する確率を含む。
量子回路の出力確率を推定する古典的困難さに関する強い予想の下で、$C$の多項式時間古典的アルゴリズムは、$|\langle z|C|0^n\rangle|^2$ が$\frac{1}{2^n}$ (Aaronson and Gunn, 2019) よりもかなり大きいような文字列 $z$ を出力できない。
一方、ランダム量子回路$c$の場合、$c$の出力分布から$z$をサンプリングすると、平均で$|\langle z|c|0^n\rangle|^2 \approx \frac{2}{2^n}$となる(arute et al., 2019)。
量子非局所相関によるツィレルソンの不等式と類似して、多項式時間量子アルゴリズムは$\frac{2}{2^n}$よりもかなり良いことができるのか?
我々は、この質問をクエリ(またはブラックボックス)モデルで研究し、量子アルゴリズムに$C$へのオラクルアクセスが与えられる。
任意の$\varepsilon \ge \frac{1}{\mathrm{poly}(n)}$に対して、サンプル$z$を出力すると、$|\langle z|C|0^n\rangle|^2 \ge \frac{2 + \varepsilon}{2^n}$が平均すると、少なくとも$\Omega\left(\frac{2^{n/4}}{\mathrm{poly}(n)}\right)$C$へのクエリは$C$より大きいが$O\left(2^{n/3}\right)$クエリは$C$になる。
また、ランダムブール関数のフーリエ分布からの$c$ サンプルの場合、$c$ からサンプルを得るナイーブアルゴリズムは、平均で$|\langle z|c|0^n\rangle|^2$ を最大化する最適な 1-クエリアルゴリズムである。
関連論文リスト
- Quantum (Inspired) $D^2$-sampling with Applications [0.138120109831448]
我々は、$k$-means++の量子実装を示し、その時間は$tildeO(zeta2 k2)$で実行される。
これは、量子バージョンが$O(logk)$近似を保証する$k$-means++の堅牢な近似解析によって示される。
これはQI-$k$-means++と呼ばれ、実行時間は$O(Nd) + tildeO(zeta)である。
論文 参考訳（メタデータ） (2024-05-22T05:13:28Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
Googleの53量子ビット回路のノイズ量子シミュレーションでは、C$は2.24pm0.21)times10-3$の忠実度値を得た。
この結果は,線形XEBテストの不正化が,量子回路の完全なシミュレーションを実現するよりも容易であることを示す証拠とみなすことができる。
論文 参考訳（メタデータ） (2020-05-05T18:01:48Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
論文 参考訳（メタデータ） (2019-12-29T01:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。