論文の概要: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
- arxiv url: http://arxiv.org/abs/2408.16244v1
- Date: Thu, 29 Aug 2024 03:56:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-30 15:05:40.510813
- Title: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
- Title(参考訳): 量子シャドウトモグラフィによる効率的な後処理による量子アドバンテージ
- Authors: Yu Wang,
- Abstract要約: 我々は、この計算を、広い行列のクラスに対して$O(textpoly(log d))$ timeで行うために、量子的優位性を活用することを検討する。
本稿では,Dense Dual Baseへのランダム射影計測を利用した任意の$d$次元システムに対するシャドウトモグラフィー手法を提案する。
このスキームは量子情報科学以上の大きな可能性を秘めている。
- 参考スコア(独自算出の注目度): 3.19428095493284
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Efficiently computing the trace of the product of exponential-scale matrices $A$ and $B$ presents a significant challenge in classical computation, particularly when $A$ is a $d$-dimensional positive Hermitian matrix with trace 1, and $B$ is a Hermitian matrix with a bounded norm. This computation traditionally requires $O(d^2)$ time complexity. We explore leveraging quantum advantage to perform this computation in $O(\text{poly}(\log d))$ time for a broad class of matrices $A$, offering potential applications in high-dimensional data analysis and complex systems. We propose a shadow tomography scheme for arbitrary $d$-dimensional systems that utilizes random projective measurements onto Dense Dual Bases for efficient sampling and post-processing. Unlike random Clifford or mutually unbiased bases (MUB) measurements, our method is experimentally feasible on optical platforms. It requires exponentially fewer computations to determine all coefficients of the randomly projected states, with a constant post-processing time per measurement, as opposed to the exponential worst-case scenario seen with random Clifford (MUB) measurements. For general dimensions $d$, the existence of $d+1$ MUBs in general dimensions is still an open question, and the processing of randomized Clifford measurements is not fully understood. While the applicability of matrix $A$ may be more limited compared to random Clifford measurements, our approach remains efficient in several cases, with average performance that is particularly efficient. For all $A$, the computational complexity is $O(d)$, and in the approximately average case, it is $O(\text{poly}(\log d))$. This scheme holds significant potential beyond quantum information science; it could be instrumental in fields such as artificial intelligence, enabling efficient computation of $\text{tr}(AB)$.
- Abstract(参考訳): 指数スケール行列の積のトレースを効率よく計算すると、$A$ と $B$ は古典計算において重要な問題を示し、特に$A$ がトレース 1 を持つ$d$-次元正のエルミート行列であり、$B$ が有界ノルムを持つエルミート行列である場合である。
この計算は伝統的に$O(d^2)$時間複雑さを必要とする。
O(\text{poly}(\log d))$ Time for a wide class of matrices $A$, offered potential application in high-dimensional data analysis and complex systems。
本稿では,Dense Dual Basesにランダムな射影計測を応用し,効率的なサンプリングと後処理を行う,任意の$d$次元システムのためのシャドウトモグラフィー手法を提案する。
ランダムなクリフォードや相互に偏りのないベース(MUB)測定とは異なり、本手法は光学プラットフォーム上で実験的に実現可能である。
ランダムなクリフォード(MUB)測定で見られる指数関数的な最悪のシナリオとは対照的に、ランダムに投影された状態の全ての係数を決定するために指数関数的に少ない計算を必要とする。
一般次元$d$の場合、一般次元における$d+1$ MUBsの存在は依然として未解決の問題であり、ランダム化されたクリフォード測定の処理は完全には理解されていない。
行列の$A$の適用性は、ランダムなクリフォードの測定よりも限定的であるが、我々のアプローチはいくつかのケースにおいて効率的であり、平均的性能は特に効率的である。
すべての$A$に対して、計算複雑性は$O(d)$であり、ほぼ平均の場合、$O(\text{poly}(\log d))$である。
このスキームは、量子情報科学以上の大きな可能性を秘めており、人工知能などの分野において、$\text{tr}(AB)$の効率的な計算を可能にしている。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。
大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
論文 参考訳(メタデータ) (2022-05-16T02:24:52Z) - Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time [54.65688986250061]
我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。
我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
論文 参考訳(メタデータ) (2022-02-09T15:26:03Z) - Computationally Efficient Approximations for Matrix-based Renyi's
Entropy [33.72108955447222]
最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。
そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。
我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
論文 参考訳(メタデータ) (2021-12-27T14:59:52Z) - Fast estimation of outcome probabilities for quantum circuits [0.0]
我々は、$n$ qubits上の普遍量子回路のシミュレーションのための2つの古典的アルゴリズムを提案する。
我々のアルゴリズムは、パラメータの異なる条件下で最高の処理を行うことで、お互いを補完する。
アルゴリズムのC+Python実装を提供し、ランダム回路を用いてそれらをベンチマークする。
論文 参考訳(メタデータ) (2021-01-28T19:00:04Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳(メタデータ) (2020-09-09T18:00:09Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳(メタデータ) (2020-06-15T21:55:34Z) - Faster classical Boson Sampling [0.15229257192293197]
平均ケースタイムの複雑さがより速く、$m$が$n$に比例するBoson Samplingのアルゴリズムを提案する。
この結果により、ボソンサンプリングによる量子計算の超越性を確立するために必要な問題サイズが増大する。
論文 参考訳(メタデータ) (2020-05-07T20:01:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。