論文の概要: 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 18:34:55.493916
• Title: Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography
• Title（参考訳）: 量子シャドウトモグラフィによる効率的な後処理による量子アドバンテージ
• Authors: Yu Wang,
• Abstract要約: 内部積(演算子名(AB))は量子科学と人工知能に根ざしている。 計算複雑性を著しく低減し,古典的シャドウトモグラフィに基づく量子的アプローチを導入する。 本研究は,高次元データ解析と処理を含むタスクにおいて,スケーラブルな量子アドバンテージを実現するために,実用的でモジュール型の量子サブルーチンを構築した。
• 参考スコア（独自算出の注目度）: 3.19428095493284
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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$よりも指数関数的に小さい。 本研究は,高次元データ解析と処理を含むタスクにおいて,スケーラブルな量子アドバンテージを実現するために,実用的でモジュール型の量子サブルーチンを構築した。

関連論文リスト

• Quantum oracles for the finite element method [45.200826131319815]
  本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。 本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
  論文  参考訳（メタデータ） (2025-04-28T14:28:31Z)
• 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)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• 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)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。 我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
  論文  参考訳（メタデータ） (2023-03-03T18:23:20Z)
• 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)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Classical shadows of fermions with particle number symmetry [0.0]
  我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。 ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
  論文  参考訳（メタデータ） (2022-08-18T17:11:12Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• 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)
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation [0.0]
  ノイズの多い中間スケールの量子計算は、スパース量子コンピューティングチップ上の対数深度量子回路と見なすことができる。 このようなノイズの多い中間スケール量子計算を効率よく検証する手法を提案する。
  論文  参考訳（メタデータ） (2021-09-30T08:56:30Z)
• Improved quantum data analysis [1.8416014644193066]
  我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。 また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
  論文  参考訳（メタデータ） (2020-11-22T01:22:37Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。