論文の概要: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
- arxiv url: http://arxiv.org/abs/2408.16244v5
- Date: Tue, 08 Apr 2025 20:25:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-10 13:04:12.091372
- Title: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
- Title（参考訳）: 量子シャドウトモグラフィによる効率的な後処理による量子アドバンテージ
- Authors: Yu Wang,
- Abstract要約: 内部積(演算子名(AB))は量子科学と人工知能に根ざしている。
計算複雑性を著しく低減し,古典的シャドウトモグラフィに基づく量子的アプローチを導入する。
本研究は,高次元データ解析と処理を含むタスクにおいて,スケーラブルな量子アドバンテージを実現するために,実用的でモジュール型の量子サブルーチンを構築した。
- 参考スコア（独自算出の注目度）: 3.19428095493284
- License:
- Abstract: Computing inner products of the form \( \operatorname{tr}(AB) \), where \( A \) is a \( d \)-dimensional density matrix (with \( \operatorname{tr}(A) = 1 \), \( A \geq 0 \)) and \( B \) is a bounded-norm observable (Hermitian with \( \operatorname{tr}(B^2) \le O(\mathrm{poly}(\log d)) \) and \( \operatorname{tr}(B) \) known), is fundamental across quantum science and artificial intelligence. Classically, both computing and storing such inner products require $O(d^2)$ resources, which rapidly becomes prohibitive as $d$ grows exponentially. In this work, we introduce a quantum approach based on qudit classical shadow tomography, significantly reducing computational complexity from $O(d^2)$ down to $O(\mathrm{poly}(\log d))$ in typical cases and at least to $O(d~ \text{poly}(\log d))$ in the worst case. Specifically, for \(n\)-qubit systems (with $n$ being the number of qubit and \(d = 2^n\)), our method guarantees efficient estimation of \(\operatorname{tr}(\rho O)\) for any known stabilizer state \(\rho\) and arbitrary bounded-norm observable \(O\), using polynomial computational resources. Crucially, it ensures constant-time classical post-processing per measurement and supports qubit and qudit platforms. Moreover, classical storage complexity of $A$ reduces from $O(d^2)$ to $O(m \log d)$, where the sample complexity $m$ is typically exponentially smaller than $d^2$. Our results establish a practical and modular quantum subroutine, enabling scalable quantum advantages in tasks involving high-dimensional data analysis and processing.
- Abstract（参考訳）: 形式 \( \operatorname{tr}(AB) \) の内積を計算する: \( A \) は \( d \) 次元密度行列( \( \operatorname{tr}(A) = 1 \), \( A \geq 0 \) と \( B \) は有界ノルム観測可能(エルミート的)であり、 \( \operatorname{tr}(B^2) \le O(\mathrm{poly}(\log d) \) と \( \operatorname{tr}(B) \) は、量子科学と人工知能において基本的なものである。
古典的には、そのような内部積の計算と保存には$O(d^2)$リソースが必要であり、$d$が指数関数的に成長するにつれて急速に禁止される。
本研究では,qudit 古典的シャドウトモグラフィに基づく量子アプローチを導入し,計算複雑性を$O(d^2)$から$O(\mathrm{poly}(\log d))$,少なくとも最悪の場合は$O(d~ \text{poly}(\log d))$に著しく低減する。
具体的には、ある既知安定化状態 \(\rho\) および任意の有界ノルム観測可能な \(O\) に対して、多項式計算資源を用いて、(n$ を qubit と \(d = 2^n\) の数を$n$ とすると、この方法では \(\operatorname{tr}(\rho O)\) の効率的な推定が保証される。
重要なことは、測定単位の定時古典的な後処理を保証し、qubitとquditプラットフォームをサポートする。
さらに、古典的なストレージの複雑さは$O(d^2)$から$O(m \log d)$に減少し、サンプルの複雑さの$m$は通常$d^2$よりも指数関数的に小さい。
本研究は,高次元データ解析と処理を含むタスクにおいて,スケーラブルな量子アドバンテージを実現するために,実用的でモジュール型の量子サブルーチンを構築した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。