論文の概要: Dimension Independent and Computationally Efficient Shadow Tomography
- arxiv url: http://arxiv.org/abs/2411.01420v1
- Date: Sun, 03 Nov 2024 03:07:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 14:38:32.432080
- Title: Dimension Independent and Computationally Efficient Shadow Tomography
- Title（参考訳）: 次元独立・計算効率の良いシャドウトモグラフィー
- Authors: Pulkit Sinha,
- Abstract要約: シャドウトモグラフィーアルゴリズムは$n=Theta(sqrtmlog m/epsilon2)$サンプルを使用し、$m$の測定と追加エラー$epsilon$について説明する。
これは、ナイーブなアプローチを改善する、これまで知られていたすべてのアルゴリズムとは対照的である。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: We describe a new shadow tomography algorithm that uses $n=\Theta(\sqrt{m}\log m/\epsilon^2)$ samples, for $m$ measurements and additive error $\epsilon$, which is independent of the dimension of the quantum state being learned. This stands in contrast to all previously known algorithms that improve upon the naive approach. The sample complexity also has optimal dependence on $\epsilon$. Additionally, this algorithm is efficient in various aspects, including quantum memory usage (possibly even $O(1)$), gate complexity, classical computation, and robustness to qubit measurement noise. It can also be implemented as a read-once quantum circuit with low quantum memory usage, i.e., it will hold only one copy of $\rho$ in memory, and discard it before asking for a new one, with the additional memory needed being $O(m\log n)$. Our approach builds on the idea of using noisy measurements, but instead of focusing on gentleness in trace distance, we focus on the \textit{gentleness in shadows}, i.e., we show that the noisy measurements do not significantly perturb the expected values.
- Abstract（参考訳）: 量子状態の次元に依存しない$m$の測定および加算誤差$\epsilon$に対して、$n=\Theta(\sqrt{m}\log m/\epsilon^2)$サンプルを使用する新しいシャドウトモグラフィーアルゴリズムを記述する。
これは、ナイーブなアプローチを改善する、これまで知られていたすべてのアルゴリズムとは対照的である。
サンプルの複雑さは$\epsilon$にも最適に依存する。
さらに、このアルゴリズムは量子メモリ使用量(おそらく$O(1)$)、ゲート複雑性、古典計算、量子ビット計測ノイズに対する堅牢性など、様々な面で効率的である。
また、量子メモリ使用量の少ないリードオンス量子回路として実装することもでき、例えば、$\rho$を1コピーだけメモリに保持し、新しいメモリを要求する前に捨てることができ、追加メモリは$O(m\log n)$である。
提案手法はノイズ測定の考え方に基づいているが,トレース距離の優しさに焦点をあてるのではなく,<textit{gentleness in shadows},すなわち,ノイズ測定が期待値を大きく乱すことはないことを示す。
関連論文リスト
- Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
同一の$k$密度行列のパワーのトレースを推定することは、多くのアプリケーションにとって重要なサブルーチンである。
The Newton-Girard method, we developed a algorithm that only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates。
論文 参考訳（メタデータ） (2024-08-01T06:23:52Z) - Weak Schur sampling with logarithmic quantum memory [0.0]
弱いシュアサンプリングのための新しいアルゴリズムを提案する。
我々のアルゴリズムは、既約表現をインデックスするヤングラベルと対称群の多重度ラベルの両方を効率的に決定する。
論文 参考訳（メタデータ） (2023-09-21T10:02:46Z) - 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) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
量子状態に対するシャドウトモグラフィーは、量子システムの特性を予測するためのサンプル効率の良いアプローチを提供する。
我々は,この問題を高い確率で解決するオンラインシャドウトモグラフィー手法を開発した。
論文 参考訳（メタデータ） (2022-09-07T09:08:58Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Exponential separations between learning with and without quantum memory [17.763817187554096]
量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。
多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。
このトレードオフは、幅広い学習問題に固有のものであることを示す。
論文 参考訳（メタデータ） (2021-11-10T19:03:49Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。