論文の概要: Exponential separations between learning with and without quantum memory
- arxiv url: http://arxiv.org/abs/2111.05881v1
- Date: Wed, 10 Nov 2021 19:03:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-12 15:28:10.700465
- Title: Exponential separations between learning with and without quantum memory
- Title（参考訳）: 量子記憶の有無による学習の指数的分離
- Authors: Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
- Abstract要約: 量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。
多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。
このトレードオフは、幅広い学習問題に固有のものであることを示す。
- 参考スコア（独自算出の注目度）: 17.763817187554096
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the power of quantum memory for learning properties of quantum
systems and dynamics, which is of great importance in physics and chemistry.
Many state-of-the-art learning algorithms require access to an additional
external quantum memory. While such a quantum memory is not required a priori,
in many cases, algorithms that do not utilize quantum memory require much more
data than those which do. We show that this trade-off is inherent in a wide
range of learning problems. Our results include the following:
(1) We show that to perform shadow tomography on an $n$-qubit state rho with
$M$ observables, any algorithm without quantum memory requires $\Omega(\min(M,
2^n))$ samples of rho in the worst case. Up to logarithmic factors, this
matches the upper bound of [HKP20] and completely resolves an open question in
[Aar18, AR19].
(2) We establish exponential separations between algorithms with and without
quantum memory for purity testing, distinguishing scrambling and depolarizing
evolutions, as well as uncovering symmetry in physical dynamics. Our
separations improve and generalize prior work of [ACQ21] by allowing for a
broader class of algorithms without quantum memory.
(3) We give the first tradeoff between quantum memory and sample complexity.
We prove that to estimate absolute values of all $n$-qubit Pauli observables,
algorithms with $k < n$ qubits of quantum memory require at least
$\Omega(2^{(n-k)/3})$ samples, but there is an algorithm using $n$-qubit
quantum memory which only requires $O(n)$ samples.
The separations we show are sufficiently large and could already be evident,
for instance, with tens of qubits. This provides a concrete path towards
demonstrating real-world advantage for learning algorithms with quantum memory.
- Abstract（参考訳）: 量子記憶のパワーを量子系と力学の学習特性に応用し、物理学や化学において非常に重要である。
多くの最先端学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。
このような量子メモリは先入観を必要としないが、多くの場合、量子メモリを使わないアルゴリズムはそれよりもはるかに多くのデータを必要とする。
このトレードオフは、幅広い学習問題に固有のものであることを示す。
1) 量子ビット状態 rho に対して $m$ 可観測値を持つシャドウトモグラフィーを行うには, 量子メモリを持たないアルゴリズムでは, 最悪の場合には $\omega(\min(m, 2^n))$ の rho サンプルが必要となる。
対数的因子によると、これは[HKP20]の上界と一致し、[Aar18, AR19]の開問題を完全に解決する。
2) 物理力学の対称性を明らかにするとともに, 純粋性試験のための量子メモリと非量子メモリとの指数関数的分離を確立した。
我々の分離は[acq21]の以前の作業を改善し、一般化し、量子メモリなしでより広い種類のアルゴリズムを可能にする。
(3) 量子メモリとサンプルの複雑性のトレードオフについて述べる。
すべての$n$-qubit Pauliオブザーバブルの絶対値を推定するために、$k < n$ qubitsの量子メモリを持つアルゴリズムは少なくとも$\Omega(2^{(n-k)/3})$サンプルを必要とするが、$n$-qubitの量子メモリを用いるアルゴリズムは$O(n)$サンプルのみを必要とする。
私たちが示している分離は十分に大きく、例えば数十量子ビットで既に明らかである可能性がある。
これは量子メモリを用いた学習アルゴリズムの現実的な優位性を示すための具体的な道筋を提供する。
関連論文リスト
- A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
量子系の固有エネルギースペクトルを効率的に計算するための新しい量子XZ24アルゴリズムを提案する。
既存の量子法と比較して、新しいアルゴリズムは測定コストが著しく低いという点で際立っている。
我々は,新しいアルゴリズムが量子システムシミュレーションに大きな進歩をもたらすことを期待し,量子コンピューティングや量子情報処理において有望な応用を提供する。
論文 参考訳（メタデータ） (2024-06-01T04:31:43Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Fundamental causal bounds of quantum random access memories [13.19534468575575]
因果性に基づく高速量子メモリの本質的境界について検討する。
QRAMは1次元で$mathcalO(107)$論理量子ビット、様々な2次元アーキテクチャで$mathcalO(1015)$から$mathcalO(1020)$、そして3次元で$mathcalO(1024)$に対応可能であることを示す。
論文 参考訳（メタデータ） (2023-07-25T12:40:48Z) - Quantivine: A Visualization Approach for Large-scale Quantum Circuit
Representation and Analysis [31.203764035373677]
我々は量子回路の探索と理解のための対話型システムQuantivineを開発した。
一連の新しい回路視覚化は、キュービットの証明、並列性、絡み合いなどのコンテキストの詳細を明らかにするように設計されている。
Quantivineの有効性は、最大100キュービットの量子回路の2つの利用シナリオを通して示される。
論文 参考訳（メタデータ） (2023-07-18T04:51:28Z) - Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid
Memory [9.615949949517901]
古典的メモリと量子メモリの両方を持つ量子アルゴリズムは、古典的メモリの$Omega(n2)$ビットか、量子メモリの$Omega(n)$ビットか、指数的なサンプル数を必要とする。
この結果から,量子メモリの少ない場合,これらの問題を効率的に学習するために必要な古典的メモリのサイズが大幅に減少する可能性が示唆された。
論文 参考訳（メタデータ） (2023-03-01T03:22:26Z) - $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
量子データアクセスマシン(QDAM)と呼ばれる効率的な量子データアクセスプロセスを導入する。
我々は,実効量子誤り訂正符号内の論理量子ビットからなるフォールトトレラント量子計算(FTQC)の観点から,我々のアルゴリズムのランタイムを解析する。
論文 参考訳（メタデータ） (2022-11-08T01:36:02Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。
我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
論文 参考訳（メタデータ） (2022-01-27T13:16:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。