論文の概要: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
- arxiv url: http://arxiv.org/abs/2408.16244v2
- Date: Wed, 6 Nov 2024 13:55:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-08 04:19:50.135666
- Title: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
- Title（参考訳）: 量子シャドウトモグラフィによる効率的な後処理による量子アドバンテージ
- Authors: Yu Wang,
- Abstract要約: 計算量と記憶量の両方を指数関数的に削減するために,qudit shadow tomographyフレームワークによる量子的アプローチを提案する。
ランダムなクリフォード測定によるシャドウトモグラフィーと比較すると,本手法は,測定後処理の計算複雑性を指数的に最悪のシナリオから一定に低減する。
- 参考スコア（独自算出の注目度）: 3.19428095493284
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The calculation of \(\text{tr}(AB)\) is essential in fields like quantum science and artificial intelligence, but the classical computational complexity is \( O(d^2) \) when \( A \) and \( B \) are \( d \)-dimensional matrices. Moreover, storing \( A \) and \( B \) requires \( O(d^2) \) memory, which poses additional challenges for exponential high-dimensional systems. We propose a quantum approach through a qudit shadow tomography framework to exponentially reduce both the computational and storage complexity to \( O(\text{poly}(\log d)) \) for a broad class of matrices \( A \) and for bounded-norm Hermitian matrices \( B \) with known \(\text{tr}(B)\). Compared to shadow tomography via random Clifford measurements, our method reduces the computational complexity of post-processing per measurement from an exponential worst-case scenario to a constant, and it is applicable across arbitrary dimensions \( d \). This advancement opens new pathways for efficient high-dimensional data analysis and complex system modeling.
- Abstract（参考訳）: 量子科学や人工知能などの分野において、 \(\text{tr}(AB)\) の計算は必須であるが、古典的な計算複雑性は \(A \) と \(B \) が \(d \)-次元行列であるときに \(O(d^2) \) である。
さらに、 \(A \) と \(B \) を格納するには \(O(d^2) \) メモリが必要であるため、指数関数的な高次元システムにはさらなる課題が生じる。
広義の行列のクラス \(A \) と有界ノルムエルミート行列 \(B \) に対して、計算と記憶の複雑さを指数関数的に \(O(\text{poly}(\log d)) \) に減らし、既知の \(\text{tr}(B)\ を持つ有界ノルムエルミート行列 \(B \) に対して量子的アプローチを提案する。
ランダムなクリフォード測定によるシャドウトモグラフィーと比較すると,本手法は,測定毎の計算処理の複雑さを指数最悪のシナリオから定数に減らし,任意の次元の \(d \) に適用可能である。
この進歩は、効率的な高次元データ解析と複雑なシステムモデリングのための新しい経路を開く。
関連論文リスト
- Estimating quantum amplitudes can be exponentially improved [11.282486674587236]
量子振幅の推定は、量子コンピューティングの基本的な課題である。
純状態を行列形式に変換することによって量子振幅を推定するための新しい枠組みを提案する。
我々のフレームワークは、それぞれ標準量子極限$epsilon-2$とハイゼンベルク極限$epsilon-1$を達成する。
論文 参考訳（メタデータ） (2024-08-25T04:35:53Z) - 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) - 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) - 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) - Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer [0.20999222360659603]
いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。
この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。
我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
論文 参考訳（メタデータ） (2023-01-10T23:12:05Z) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。