論文の概要: Quantum 1-PCA with Pauli Measurements in Nearly Linear Time

• arxiv url: http://arxiv.org/abs/2610.06808v1
• Date: Mon, 05 Oct 2026 17:54:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 22:35:30.291452
• Title: Quantum 1-PCA with Pauli Measurements in Nearly Linear Time
• Title（参考訳）: パウリ測定によるほぼ直線時間での量子1-PCA
• Abstract要約: 量子1-PCAの問題を考える:未知の$n$-qubit混合状態のコピーを与えられた場合、その先行固有ベクトルの古典的な記述を復元する。 測定はすべて適応的に選択されず、単一キュービットのパウリベースで実行されます。 以上の結果から, 状態的不特定性の存在は多言語的要因まで, 同じ割合で維持されることが明らかとなった。
• 参考スコア（独自算出の注目度）: 6.084924068287969
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider the problem of quantum 1-PCA: given copies of an unknown $n$-qubit mixed state, recover a classical description of its leading eigenvector. Our goal is to do so using non-adaptive and single-qubit measurements. For an $n$-qubit state with top eigenvalue $λ$ and spectral gap at least $Δ> 0$, we give an algorithm that recovers the leading eigenvector to fidelity at least $1 - \varepsilon$ with high probability using $\tilde{O}\left( {2^n \cdot η^2} / {Δ^3 \varepsilon^3}\right)$ copies and $\tilde{O}((2^n/Δ\varepsilon) \cdot \operatorname{poly}(η/Δ\varepsilon))$ time, where $η= \max (1 - λ, \varepsilon)$. All of our measurements are non-adaptively chosen, and performed in single-qubit Pauli bases. When the spectral gap is constant and the desired accuracy is comparable to the noise level, i.e. $\varepsilon = Ω(η)$, our runtime and copy complexity become $\tilde{O} (2^n / \varepsilon)$. This generalizes the guarantees of Grewal et al. [arXiv:2601.04444], who achieved similar rates, but under the assumption $η= 0$, i.e., that the state was pure. Our results show that the same rates hold in the presence of state misspecification, up to polylogarithmic factors. From a technical perspective, our algorithm works by recursively constructing low-dimensional subspaces that approximately preserve the target eigenvector. To achieve nearly linear runtime dependence on the dimension of the Hilbert space, we develop a novel structured Pauli sampling scheme that enables fast batched computation of exponentially many projected Pauli matrices.
• Abstract（参考訳）: 量子1-PCAの問題を考える:未知の$n$-qubit混合状態のコピーを与えられた場合、その先行固有ベクトルの古典的な記述を復元する。 我々のゴールは、非適応的かつ単一キュービットの測定を使ってそれを行うことです。 最高固有値$λ$と少なくとも$Δ> 0$のスペクトルギャップを持つ$n$-qubit状態に対して、$\tilde{O}\left( {2^n \cdot η^2} / {Δ^3 \varepsilon^3}\right)$コピーと$\tilde{O}((2^n/Δ\varepsilon) \cdot \operatorname{poly}(η/Δ\varepsilon))$タイム($η= \max (1 - λ, \varepsilon)$$)を使って、先頭固有ベクトルを少なくとも1 - \varepsilon$に復元するアルゴリズムを与える。 測定はすべて適応的に選択されず、単一キュービットのパウリベースで実行されます。 スペクトルギャップが一定であり、所望の精度がノイズレベルに匹敵する場合、例えば$\varepsilon = Ω(η)$、我々のランタイムとコピーの複雑さは$\tilde{O} (2^n / \varepsilon)$となる。 これは、Grewal et al [arXiv:2601.04444] の保証を一般化するが、$η=0$という仮定の下では、状態は純粋である。 以上の結果から, 状態的不特定性の存在は多言語的要因まで, 同じ割合で維持されることが明らかとなった。 技術的観点から、我々のアルゴリズムはターゲット固有ベクトルをほぼ保存する低次元部分空間を再帰的に構築することで機能する。 ヒルベルト空間の次元にほぼ線形な実行時依存を実現するため、指数関数的に多くのパウリ行列の高速なバッチ計算を可能にする新しい構造付きパウリサンプリングスキームを開発した。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Fast Convex Optimization with Quantum Gradient Methods [2.5094874597551913]
  雑音関数評価オラクルを用いた量子(サブ)次次推定に基づく量子アルゴリズムについて検討する。 滑らかな条件と非滑らかな条件の両方において、ゼロ階凸最適化のための最初の次元非依存的な問合せ複雑性を示す。 半定値プログラミングと固有値最適化の接続を利用して、量子ミラー降下法を用いて、半定値プログラム、線形プログラム、ゼロサムゲームを解決するための新しい量子アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2025-03-21T17:58:12Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。 我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
  論文  参考訳（メタデータ） (2021-12-15T21:44:05Z)
• Rodeo Algorithm for Quantum Computing [0.0]
  量子ハミルトニアンの固有ベクトルを生成できる量子計算アルゴリズムを提案する。 固有状態生成の速度は、推定や断熱進化の速度よりも指数関数的に速い。
  論文  参考訳（メタデータ） (2020-09-09T04:12:54Z)

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

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