論文の概要: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
- arxiv url: http://arxiv.org/abs/2408.16244v4
- Date: Tue, 26 Nov 2024 15:22:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-27 13:31:44.373204
- Title: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
- Title（参考訳）: 量子シャドウトモグラフィによる効率的な後処理による量子アドバンテージ
- Authors: Yu Wang,
- Abstract要約: 計算量と記憶量の両方を削減できるquditシャドウトモグラフィーに基づく量子的アプローチを提案する。
(operatornametr(rho O)) は (textpoly(log d)) 計算で効率的に推定できる。
これらの進歩は、効率的な高次元データ解析とモデリングのための新しい道を開く。
- 参考スコア（独自算出の注目度）: 3.19428095493284
- License:
- Abstract: The computation of \(\operatorname{tr}(AB)\) is essential in quantum science and artificial intelligence, yet classical methods for \( d \)-dimensional matrices \( A \) and \( B \) require \( O(d^2) \) complexity, which becomes infeasible for exponentially large systems. We introduce a quantum approach based on qudit shadow tomography that reduces both computational and storage complexities to \( O(\text{poly}(\log d)) \) in specific cases. This method is applicable to quantum density matrices \( A \) and Hermitian matrices \( B \) with given \(\operatorname{tr}(B)\) and \(\operatorname{tr}(B^2)\) bounded by a constant (referred to as BN-observables). We prove that this method guarantees at least a quadratic speedup for any quantum state \(\rho\) and BN-observable \( O \) in the worst case, and an exponential speedup in the approximately average case. For any \( n \)-qubit stabilizer state \(\rho\) and arbitrary BN-observable \( O \), we show that \(\operatorname{tr}(\rho O)\) can be efficiently estimated with \(\text{poly}(n)\) computations. Moreover, our approach significantly reduces the post-processing complexity in shadow tomography using random Clifford measurements, and it is applicable to arbitrary dimensions \( d \). These advances open new avenues for efficient high-dimensional data analysis and modeling.
- Abstract（参考訳）: 量子科学や人工知能において、 \(\operatorname{tr}(AB)\) の計算は必須であるが、(d \)-次元行列 \(A \) と \(B \) の古典的手法では、指数関数的に大きな系では不可能となる \(O(d^2) \) の複雑性を必要とする。
我々は,quditシャドウトモグラフィーに基づく量子的アプローチを導入し,計算量と記憶量の両方の複雑さを,特定の場合において \(O(\text{poly}(\log d)) \) に還元する。
この方法は、与えられた \(\operatorname{tr}(B)\) と \(\operatorname{tr}(B^2)\) を定数で有界とする量子密度行列 \(A \) とエルミート行列 \(B \) に適用できる。
この方法では、最悪の場合、任意の量子状態 \(\rho\) と BN-観測可能な \(O \) に対して少なくとも二次的なスピードアップが保証され、ほぼ平均の場合、指数的なスピードアップが保証される。
任意の \(n \)-量子安定化状態 \(\rho\) と任意の BN-観測可能な \(O \) に対して、 \(\operatorname{tr}(\rho O)\) は \(\text{poly}(n)\) 計算で効率的に推定できることを示す。
さらに, ランダムクリフォード測定を用いて, シャドウトモグラフィにおける後処理の複雑さを著しく低減し, 任意の次元 \(d \) に適用できることを示す。
これらの進歩は、効率的な高次元データ解析とモデリングのための新しい道を開く。
関連論文リスト
- Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
本稿では,QUBO行列におけるテクステミシンメトリの概念を紹介する。
提案アルゴリズムは結合数と回路深さを最大45%削減することを示した。
論文 参考訳（メタデータ） (2024-12-18T12:05:18Z) - Contractive Unitary and Classical Shadow Tomography [8.406921897932131]
完全な量子状態トモグラフィーでは、システムサイズを指数関数的に測定する必要がある。
この研究は、ランダム-決定論的ハイブリダイゼーションプロトコルが完全なランダムな測定よりも効率的であることを示している。
論文 参考訳（メタデータ） (2024-11-28T18:59:12Z) - Resource-efficient algorithm for estimating the trace of quantum state powers [1.5133368155322298]
量子状態のトレースを$textTr(rhok)$, for $k$等量子状態と見積もるのは基本的な課題である。
我々は、$mathcalO(tilder)$ qubitsと$mathcalO(tilder)$ multi-qubit gatesのみを必要とするアルゴリズムを導入する。
我々はアルゴリズムを任意のオブザーバブルに対して$textTr(rhok)$と$textTr(rhok)$の推定にまで拡張する。
論文 参考訳（メタデータ） (2024-08-01T06:23:52Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳（メタデータ） (2023-10-17T17:55:32Z) - Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for
Multi-Block Bilevel Optimization [43.74656748515853]
非定常多重ブロック双レベル最適化問題には$mgg 1$低レベル問題があり、機械学習において重要な応用がある。
a)標準BO問題の最先端の複雑さを1ブロックに合わせること,(b)サンプルブロックごとのサンプルをサンプリングして並列高速化すること,(c)高次元ヘッセン行列推定器の逆計算を避けること,の3つの特性を実現することを目的とする。
論文 参考訳（メタデータ） (2023-05-30T04:10:11Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Faster Stochastic First-Order Method for Maximum-Likelihood Quantum
State Tomography [10.758021887982782]
量子状態トモグラフィーでは、サンプルサイズと寸法は量子ビットの数とともに指数関数的に増加する。
本稿では,バーグ様エントロピーを用いたミラー降下法を提案する。
我々の知る限りでは、これは現在、最大形量子状態トモグラフィーの高速で一階法である。
論文 参考訳（メタデータ） (2022-11-23T11:35:47Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。