論文の概要: A Classical Quadratic Speedup for Planted $k$XOR
- arxiv url: http://arxiv.org/abs/2508.09422v1
- Date: Wed, 13 Aug 2025 01:45:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-15 13:42:23.661305
- Title: A Classical Quadratic Speedup for Planted $k$XOR
- Title（参考訳）: プランティング$k$XORの古典的擬似高速化
- Authors: Meghal Gupta, William He, Ryan O'Donnell, Noah G. Singer,
- Abstract要約: Schmidhuberらによる最近の研究は、既知の全ての古典的アルゴリズムよりも4倍高速に動作する、雑音の多い$k$XOR問題の量子アルゴリズムを示した。
我々は,大定数$k$の場合において,前者よりも2次的に高速な新しい古典的アルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 1.593690982728631
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A recent work of Schmidhuber et al (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted $k$XOR problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant $k$. Thus for such $k$, the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.
- Abstract（参考訳）: Schmidhuber et al (QIP, SODA, & Phys. X 2025) の最近の研究は、既知のすべての古典的アルゴリズムよりも四進的に高速に動作する、雑音の多いプランニングされた$k$XOR問題の量子アルゴリズムを示した。
そこで本研究では,大定数$k$の場合,従来よりも2次的に高速な古典的アルゴリズムを設計する。
したがって、そのような$k$の場合、Schmidhuber et al の量子スピードアップは(空間上の優位性は保たれるが)2次にしかならない。
我々のアルゴリズムは半ランダムの場合でも機能し、サブ線形時間アルゴリズム(本質的には誕生日パラドックス)と多項式反集中のツールを組み合わせる。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳（メタデータ） (2023-11-17T20:38:38Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。
我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。
我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
論文 参考訳（メタデータ） (2023-04-27T14:02:54Z) - Recovering the original simplicity: succinct and deterministic quantum
algorithm for the welded tree problem [0.0]
この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。
最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-17T16:03:50Z) - 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.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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。