論文の概要: Quantum learning algorithms imply circuit lower bounds
- arxiv url: http://arxiv.org/abs/2012.01920v1
- Date: Thu, 3 Dec 2020 14:03:20 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-23 14:36:59.923171
- Title: Quantum learning algorithms imply circuit lower bounds
- Title（参考訳）: 量子学習アルゴリズムは下限を巡回する
- Authors: Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira,
Aarthi Sundaram
- Abstract要約: 量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
- 参考スコア（独自算出の注目度）: 7.970954821067043
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We establish the first general connection between the design of quantum
algorithms and circuit lower bounds. Specifically, let $\mathfrak{C}$ be a
class of polynomial-size concepts, and suppose that $\mathfrak{C}$ can be
PAC-learned with membership queries under the uniform distribution with error
$1/2 - \gamma$ by a time $T$ quantum algorithm. We prove that if $\gamma^2
\cdot T \ll 2^n/n$, then $\mathsf{BQE} \nsubseteq \mathfrak{C}$, where
$\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$ is an exponential-time analogue of
$\mathsf{BQP}$. This result is optimal in both $\gamma$ and $T$, since it is
not hard to learn any class $\mathfrak{C}$ of functions in (classical) time $T
= 2^n$ (with no error), or in quantum time $T = \mathsf{poly}(n)$ with error at
most $1/2 - \Omega(2^{-n/2})$ via Fourier sampling. In other words, even a
marginal improvement on these generic learning algorithms would lead to major
consequences in complexity theory.
Our proof builds on several works in learning theory, pseudorandomness, and
computational complexity, and crucially, on a connection between non-trivial
classical learning algorithms and circuit lower bounds established by Oliveira
and Santhanam (CCC 2017). Extending their approach to quantum learning
algorithms turns out to create significant challenges. To achieve that, we show
among other results how pseudorandom generators imply learning-to-lower-bound
connections in a generic fashion, construct the first conditional pseudorandom
generator secure against uniform quantum computations, and extend the local
list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP
2010) to quantum circuits via a delicate analysis. We believe that these
contributions are of independent interest and might find other applications.
- Abstract（参考訳）: 量子アルゴリズムの設計と回路下界との間の最初の一般的な接続を確立する。
具体的には、$\mathfrak{C}$ を多項式サイズの概念のクラスとし、$\mathfrak{C}$ を誤差 $1/2 - \gamma$ の均一分布の下でメンバシップクエリで PAC を学習できると仮定する。
もし$\gamma^2 \cdot t \ll 2^n/n$なら、$\mathsf{bqe} \nsubseteq \mathfrak{c}$、ただし$\mathsf{bqe} = \mathsf{bqtime}[2^{o(n)}]$は$\mathsf{bqp}$の指数時間類似である。
この結果は、クラス$\mathfrak{C}$を(古典的な)時間$T = 2^n$(誤りのない)あるいは量子時間$T = \mathsf{poly}(n)$を最大1/2 - \Omega(2^{-n/2})$でフーリエサンプリングすることによって学習することが難しいため、$\gamma$と$T$の両方で最適である。
言い換えれば、これらの一般的な学習アルゴリズムに対する限界的な改善でさえ、複雑性理論において大きな結果をもたらすだろう。
本証明は,学習理論,擬似ランダム性,計算複雑性に関するいくつかの研究と,oliveira と santhanam (ccc 2017) によって確立された非自明な古典的学習アルゴリズムと回路下限との関係を基礎としている。
量子学習アルゴリズムへのアプローチを拡張することで、大きな課題が生まれる。
そこで本研究では, 擬似乱数生成器が汎用的な方法で学習・下界接続を示唆し, 均一な量子計算に対して確保された最初の条件付き擬似乱数生成器を構築し, 微妙な解析によりImpagliazzo, Jaiswal, Kabanets, Wigderson (SICOMP 2010) の局所的リスト復号アルゴリズムを拡張した。
これらの貢献は独立した関心事であり、他の応用を見出すかもしれないと信じています。
関連論文リスト
- Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。
この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
論文 参考訳（メタデータ） (2024-11-04T19:40:01Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Quantum Speedups for Bayesian Network Structure Learning [0.0]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。
近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。
我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-05-31T09:15:28Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $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-クエリであることを示す。
論文 参考訳（メタデータ） (2020-08-20T01:04:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。