論文の概要: 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)
• Quantum Dissipative Search via Lindbladians [0.0]
  我々は、構造化されていない古典的な探索空間上の純粋に散逸した量子ランダムウォークを解析する。 ある種のジャンプ演算子は量子過程を古典的過程に複製させ、他方はオープン量子(OQRW)と古典的ランダムウォークの違いをもたらすことを示す。 また,従来観測されていた2次高速化も明らかにし,OQRWは古典的検索ほど効率的ではないことを示した。
  論文  参考訳（メタデータ） (2024-07-16T14:39:18Z)
• Tensor networks based quantum optimization algorithm [0.0]
  最適化において、よく知られた古典的アルゴリズムの1つは電力反復である。 我々はこの落とし穴を回避するために量子化を提案する。 我々の手法はインスタンス非依存となり、量子コンピューティングの枠組みの中でブラックボックス最適化に対処することができる。
  論文  参考訳（メタデータ） (2024-04-23T13:49:11Z)
• Quantum Bayesian Optimization [64.58749619145908]
  本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-09T03:10:42Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  変分量子アルゴリズム(VQA)は、特定の計算上の利点を得るために、短期量子マシンを利用する可能性がある。 現代のVQAは、巨大なデータを扱うために単独の量子プロセッサを使用するという伝統によって妨げられている、計算上のオーバーヘッドに悩まされている。 ここでは、この問題に対処するため、効率的な分散最適化手法であるQUDIOを考案する。
  論文  参考訳（メタデータ） (2021-06-24T08:18:42Z)
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions [4.2698418800007865]
  古典ハミルトニアンの分配関数を所定の温度で近似するための古典的および量子的アルゴリズムを提案する。 我々は,vStefankovivc,Vempala,Vigodaの古典的アルゴリズムを改良し,サンプルの複雑さを改善する。 我々はこの新しいアルゴリズムを量子化し、HarrowとWeiにより、この問題に対してこれまで最速の量子アルゴリズムを改善した。
  論文  参考訳（メタデータ） (2020-09-23T17:27:28Z)
• 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)

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

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