論文の概要: Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit

• arxiv url: http://arxiv.org/abs/2510.06925v1
• Date: Wed, 08 Oct 2025 12:05:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.472777
• Title: Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit
• Title（参考訳）: 量子スパース回復と量子直交マッチング
• Authors: Armando Bellante, Stefano Vanerio, Stefano Zanero,
• Abstract要約: 我々は古典的OMPグリードアルゴリズムの最初の量子アナログである量子直交整合法(QOMP)を紹介する。 標準的な相互整合性と条件の整合性の下で、QOMPはスパース時間で$K$スパース状態の正確なサポートを確実に回復する。 我々はQRAMモデルでQOMPを解析し、古典的なOMP実装よりも高速化する。
• 参考スコア（独自算出の注目度）: 2.1745861377927507
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given coherent quantum access to a state and a dictionary of vectors, the goal is to reconstruct the state up to $\ell_2$ error using as few vectors as possible. We first show that the general recovery problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids iteration-to-iteration error accumulation. Under standard mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a $K$-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in $\ell_2$ norm, achieving query complexity $\widetilde{O}(\sqrt{N}/\epsilon)$ in favorable regimes and reducing tomography to estimating only $K$ coefficients instead of $N$ amplitudes. In particular, for pure-state tomography with $m=O(N)$ dictionary vectors and sparsity $K=\widetilde{O}(1)$ on a well-conditioned subdictionary, this circumvents the $\widetilde{\Omega}(N/\epsilon)$ lower bound that holds in the dense, orthonormal-dictionary setting, without contradiction, by leveraging sparsity together with non-orthogonality. Beyond tomography, we analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary of $m$ vectors in $O(m/\epsilon)$ queries, improving over both deterministic and quantum-inspired classical methods.
• Abstract（参考訳）: 非直交的でオーバーコンプリートな辞書における量子スパース回復の研究:状態へのコヒーレントな量子アクセスとベクトルの辞書が与えられた場合、その目的は極小ベクトルを用いて最大$\ell_2$エラーを再構築することである。 まず、一般的なリカバリ問題はNPハードであることが示され、完全汎用性において効率的な正確なアルゴリズムを除外する。 これを解決するために、古典的なOMPグリードアルゴリズムの最初の量子アナログであるQuantum Orthogonal Matching Pursuit (QOMP)を導入する。 QOMPは、内部積の推定、最大探索、ブロック符号化されたプロジェクションのための量子サブルーチンと、イテレーションからイテレーションまでのエラーの蓄積を避けるエラーリセット設計を組み合わせている。 標準的な相互整合性と条件の整合性仮定の下で、QOMPは多項式時間で$K$スパース状態の正確なサポートを確実に回復する。 アプリケーションとして、$\ell_2$ノルムの非直交辞書によるスパース量子トモグラフィーのための最初のフレームワークを提供し、クエリ複雑性を達成し、$\widetilde{O}(\sqrt{N}/\epsilon)$を好適なレジームで提供し、トモグラフィーを減らし、$N$振幅の代わりに$K$係数のみを推定する。 特に、$m=O(N)$ 辞書ベクトルとスパーシティ $K=\widetilde{O}(1)$ 条件のよい部分ディクショナリーにおいて、これは高密度で正規直交的なディクショナリー設定にある$\widetilde{\Omega}(N/\epsilon)$ 下界を、矛盾なく回避し、非直交性とともにスパーシティを活用することによって回避する。 トモグラフィー以外にも、QRAMモデルでQOMPを分析し、古典的なOMP実装よりも多項式スピードアップが得られ、量子アルゴリズムにより$O(m/\epsilon)$クエリにおける$m$ベクトルの辞書の相互不整合を推定し、決定論的および量子的に着想を得た古典的手法よりも改善する。

関連論文リスト

• A probabilistic quantum algorithm for Lyapunov equations and matrix inversion [0.0]
  リアプノフ方程式の解に比例した混合状態を生成する確率論的量子アルゴリズムを提案する。 各ステップでアルゴリズムは現在の状態を返すか、全く正の正の地図をトレースしないか、あるいは偏りのあるコインフリップとアンシラ測定の結果に応じて再起動する。 最も一般的な形式で、アルゴリズムは行列値の重み付き和と積分を近似した混合状態を生成する。
  論文  参考訳（メタデータ） (2025-08-06T17:52:06Z)
• Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla [18.660349597156266]
  量子特異値変換(Quantum Singular Value Transformation, QSVT)は,最もよく知られた量子アルゴリズムをカプセル化する統一フレームワークである。 その結果,量子アルゴリズムの新しいフレームワークが確立され,ハードウェアのオーバヘッドが大幅に低減され,ほぼ最適性能が維持された。
  論文  参考訳（メタデータ） (2025-04-03T08:24:15Z)
• Purest Quantum State Identification [14.22473588576799]
  我々は、量子計算と通信の精度を向上させるために使用できる、最も純粋な量子状態同定を導入する。 非コヒーレントな戦略に対しては、エラー確率$expleft(-Omegaleft(fracN H_1log(K) 2nfracright)$を達成し、量子特性学習を根本的に改善する最初の適応アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2025-02-20T07:42:16Z)
• Low-depth quantum symmetrization [1.5566524830295307]
  一般対称性問題に対する最初の効率的な量子アルゴリズムを提案する。 我々のアルゴリズムは、第一量子化におけるボゾン量子系の効率的なシミュレーションを可能にする。 また、第2量子状態から第1量子状態に変換するために、$tildeO(log3 n)$-depth量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-06T16:00:46Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。 Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。 評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
  論文  参考訳（メタデータ） (2024-04-30T23:55:03Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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