論文の概要: 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)$の効率的な計算を可能にしている。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。