論文の概要: Accelerating Classical and Quantum Tensor PCA

• arxiv url: http://arxiv.org/abs/2602.10366v1
• Date: Tue, 10 Feb 2026 23:35:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-12 21:44:01.339195
• Title: Accelerating Classical and Quantum Tensor PCA
• Title（参考訳）: 古典的および量子的テンソルPCAの加速
• Authors: Matthew B. Hastings,
• Abstract要約: 我々は、古典的アルゴリズムと量子的アルゴリズムの両方を加速させる方法を示し、同じクォート的分離を維持する。 これらのスピードアップは、リカバリではなく、検出のためにのみ証明するが、我々のアルゴリズムはリカバリも達成できるという強い妥当性の議論を与える。
• 参考スコア（独自算出の注目度）: 0.40611352512781873
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Spectral methods are a leading approach for tensor PCA with a ``spiked" Gaussian tensor. The methods use the spectrum of a linear operator in a vector space with exponentially high dimension and in Ref. 1 it was shown that quantum algorithms could then lead to an exponential space saving as well as a quartic speedup over classical. Here we show how to accelerate both classical and quantum algorithms quadratically, while maintaining the same quartic separation between them. That is, our classical algorithm here is quadratically faster than the original classical algorithm, while the quantum algorithm is eigth-power faster than the original classical algorithm. We then give a further modification of the quantum algorithm, increasing its speedup over the modified classical algorithm to the sixth power. We only prove these speedups for detection, rather than recovery, but we give a strong plausibility argument that our algorithm achieves recovery also. Note added: After this paper was prepared, A. Schmidhuber pointed out to me Ref. 3. This improves the best existing bounds on the spectral norm of a certain random operator. Because the norm of this operator enters into the runtime, with this improvement on the norm, we no longer have a provable polynomial speedup. Our results are phrased in terms of certain properties of the spectrum of this operator (not merely the largest eigenvalue but also the density of states). So, if these properties still hold, the speedup still holds. Rather than modify the paper, I have left it unchanged but added a section at the end discussing the needed property of density of states and considering for which problems (there are several problems for which this kind of quartic quantum speedup has been used and the techniques here will likely be applicable to several of them) the property is likely to hold.
• Abstract（参考訳）: スペクトル法は '`spiked' ガウステンソルを持つテンソルPCAの先導的アプローチである。 これらの手法は指数的に高次元のベクトル空間における線型作用素のスペクトルを用いており、Ref. 1では量子アルゴリズムが指数空間の節約と古典上のクォート的なスピードアップに繋がることを示した。 ここでは、古典的アルゴリズムと量子的アルゴリズムの両方を2次的に加速する方法を示す。 つまり、我々の古典的アルゴリズムは元の古典的アルゴリズムより2倍速く、一方量子的アルゴリズムは元の古典的アルゴリズムより1桁高速である。 次に、量子アルゴリズムをさらに改良し、修正された古典的アルゴリズムを6番目のパワーに高速化する。 これらのスピードアップは、リカバリではなく、検出のためにのみ証明するが、我々のアルゴリズムはリカバリも達成できるという強い妥当性の議論を与える。 注記: この論文が準備された後、A. Schmidhuber氏はRef.3を指摘した。 これにより、あるランダム作用素のスペクトルノルム上の最良の既存の境界が改善される。 この作用素のノルムがランタイムに入るので、このノルムの改善により、もはや証明可能な多項式のスピードアップは得られなくなる。 我々の結果は、この作用素のスペクトルの特定の性質(最大の固有値だけでなく状態の密度も含む)で表現される。 したがって、これらの特性が保留されている場合、スピードアップは保留される。 論文を変更せずに、最後に、状態の密度の必要な性質を議論する部分を追加し、どの問題(この種のクォート量子スピードアップが使われているか、ここでのテクニックはいくつかの問題に適用される可能性が高い)を考えると、その性質は保持される可能性が高い。

関連論文リスト

• Quartic quantum speedups for community detection [84.14713515477784]
  我々は,準量子スピードアップを実現するハイパーグラフコミュニティ検出のための量子アルゴリズムを開発した。 提案アルゴリズムは,従来検討されていた PCA や $p$XORSAT といった問題を超えて拡張した Kikuchi 法に基づいている。
  論文  参考訳（メタデータ） (2025-10-09T17:35:17Z)
• Tensor networks based quantum optimization algorithm [0.0]
  最適化において、よく知られた古典的アルゴリズムの1つは電力反復である。 我々はこの落とし穴を回避するために量子化を提案する。 我々の手法はインスタンス非依存となり、量子コンピューティングの枠組みの中でブラックボックス最適化に対処することができる。
  論文  参考訳（メタデータ） (2024-04-23T13:49:11Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer [0.157286095422595]
  いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。 この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。 我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
  論文  参考訳（メタデータ） (2023-01-10T23:12:05Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• 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)

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

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