論文の概要: Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid
Memory
- arxiv url: http://arxiv.org/abs/2303.00209v1
- Date: Wed, 1 Mar 2023 03:22:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-02 16:12:11.990180
- Title: Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid
Memory
- Title（参考訳）: 古典量子ハイブリッドメモリを用いた学習のためのメモリサンプル下限
- Authors: Qipeng Liu, Ran Raz, Wei Zhan
- Abstract要約: 古典的メモリと量子メモリの両方を持つ量子アルゴリズムは、古典的メモリの$Omega(n2)$ビットか、量子メモリの$Omega(n)$ビットか、指数的なサンプル数を必要とする。
この結果から,量子メモリの少ない場合,これらの問題を効率的に学習するために必要な古典的メモリのサイズが大幅に減少する可能性が示唆された。
- 参考スコア（独自算出の注目度）: 9.615949949517901
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for
parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical
memory or an exponential number (in~$n$) of random samples. A line of recent
works continued that research direction and showed that for a large collection
of classical learning tasks, either super-linear classical memory size or
super-polynomially many samples are needed. However, these results do not
capture all physical computational models, remarkably, quantum computers and
the use of quantum memory. It leaves the possibility that a small piece of
quantum memory could significantly reduce the need for classical memory or
samples and thus completely change the nature of the classical learning task.
In this work, we prove that any quantum algorithm with both, classical memory
and quantum memory, for parity learning on $n$ bits, requires either
$\Omega(n^2)$ bits of classical memory or $\Omega(n)$ bits of quantum memory or
an exponential number of samples. In other words, the memory-sample lower bound
for parity learning remains qualitatively the same, even if the learning
algorithm can use, in addition to the classical memory, a quantum memory of
size $c n$ (for some constant $c>0$).
Our results refute the possibility that a small amount of quantum memory
significantly reduces the size of classical memory needed for efficient
learning on these problems. Our results also imply improved security of several
existing cryptographical protocols in the bounded-storage model (protocols that
are based on parity learning on $n$ bits), proving that security holds even in
the presence of a quantum adversary with at most $c n^2$ bits of classical
memory and $c n$ bits of quantum memory (for some constant $c>0$).
- Abstract（参考訳）: Raz (J. ACM と FOCS 16) の研究では、$n$ビットでパリティ学習を行うアルゴリズムは古典記憶の$\Omega(n^2)$ビットか、ランダムサンプルの指数数 (in~$n$) を必要とすることが証明された。
最近の一連の研究は研究の方向性を続け、多くの古典的学習課題において、超線形の古典的メモリサイズまたは超ポリノミカルな多くのサンプルが必要であることを示した。
しかし、これらの結果は全ての物理計算モデル、驚くべきことに量子コンピュータと量子メモリの使用を捉えていない。
これは、小さな量子メモリが古典的メモリやサンプルの必要性を大幅に減少させ、古典的学習タスクの性質を完全に変える可能性を残している。
この研究で、古典的メモリと量子メモリの両方を持つ量子アルゴリズムが、$n$ビットでパリティ学習するためには、古典的メモリの$\Omega(n^2)$ビットか、量子メモリの$\Omega(n)$ビットか、指数的なサンプル数を必要とすることを証明した。
言い換えれば、パリティ学習のためのメモリサンプルの下限は、たとえ学習アルゴリズムが古典的なメモリに加えて、$c n$(一定の$c>0$)の量子メモリを使うことができるとしても、定性的に同じである。
その結果,量子メモリの少なさは,これらの問題の効率的な学習に必要な古典記憶量を大幅に削減する可能性が示唆された。
我々はまた、有界記憶モデル($n$ビットのパリティ学習に基づくプロトコール)における既存の暗号プロトコルのセキュリティを改善し、古典メモリの最大$c n^2$ビットと量子メモリの$c n$ビット(一定の$c>0$)の量子敵が存在する場合でもセキュリティは維持可能であることを証明した。
関連論文リスト
- Exponential learning advantages with conjugate states and minimal
quantum memory [0.0]
将来量子コンピュータで利用可能な新しい学習リソースについて検討する。
特定のシャドウトモグラフィータスクでは、$rho otimes rhoast$ のコピーのみの測定は $rhootimes K$ の測定よりも指数関数的に強力である。
この利点は、量子シミュレーションの改善、量子センサーからの学習、新しい物理現象の発見に応用できるかもしれない。
論文 参考訳（メタデータ） (2024-03-06T05:04:45Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Cumulative Memory Lower Bounds for Randomized and Quantum Computation [1.52292571922932]
累積記憶は時間空間の複雑さの尺度である。
逐次古典計算と量子回路の両方において、累積メモリの複雑さに関する最初の下位境界を証明した。
論文 参考訳（メタデータ） (2023-01-13T17:57:02Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Memory Compression with Quantum Random-Access Gates [0.0]
量子ランダムアクセスゲートを備えた量子アルゴリズムに対して、類似した結果を示す。
空間非効率であるがスパースな量子データ構造を構築することはしばしば可能である。
論文 参考訳（メタデータ） (2022-03-10T19:27:53Z) - Exponential separations between learning with and without quantum memory [17.763817187554096]
量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。
多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。
このトレードオフは、幅広い学習問題に固有のものであることを示す。
論文 参考訳（メタデータ） (2021-11-10T19:03:49Z) - Kanerva++: extending The Kanerva Machine with differentiable, locally
block allocated latent memory [75.65949969000596]
エピソディックメモリとセマンティックメモリは、人間のメモリモデルの重要なコンポーネントです。
我々は、エピソードメモリとセマンティックメモリのギャップを埋める新しい原理ベイズメモリ割り当てスキームを開発しました。
この割り当て方式がメモリ条件画像生成の性能を向上させることを実証する。
論文 参考訳（メタデータ） (2021-02-20T18:40:40Z) - Quantum advantage for computations with limited space [6.327095331866255]
我々は、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算を考える。
我々は、量子回路による3ドル、4ドル、5ドル、6ドルという計算を、カスタム2量子ゲートを利用して実験的に実証した。
論文 参考訳（メタデータ） (2020-08-14T17:31:12Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。