Fugu-MT 論文翻訳(概要): A Classical Quadratic Speedup for Planted $k$XOR

論文の概要: 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)
Quartic quantum speedups for planted inference [44.820711784498]
そこで本研究では,植物ノイズの量子アルゴリズムについて述べる。我々の研究は、いくつかの構造は超4次量子攻撃の影響を受けやすいことを示唆している。
論文参考訳（メタデータ） (2024-06-27T17:54:28Z)
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)
Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
時間複雑性を持つ整数乗算の量子アルゴリズムをO(sqrtnlog2 n)$で提案する。 Harveyアルゴリズムとは異なり、我々のアルゴリズムは極大数にのみ適用できるという制限はない。また、古典的乗法アルゴリズムの歴史と発展を概観し、量子資源がこの根本的な問題に対してどのように新たな視点と可能性を提供できるかを探求する動機付けとなる。
論文参考訳（メタデータ） (2023-06-14T12:40:54Z)
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)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文参考訳（メタデータ） (2022-05-26T20:32:36Z)
Hybrid Quantum-Classical Search Algorithms [0.0]
古典計算は,探索問題自体が解けない限り,量子計算を補助できないことを示す。我々はこの結果を、不安定な成功確率を持つアルゴリズムに一般化する。
論文参考訳（メタデータ） (2022-02-23T11:43:17Z)
Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文参考訳（メタデータ） (2021-06-01T19:51:55Z)
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding [4.5686700995634055]
最短ベクトル問題(SVP)に対する証明可能な古典量子アルゴリズムの新しいアルゴリズムを提案する。 SVPの新しいアルゴリズムは、時間複雑性とメモリ要求の間のスムーズなトレードオフを提供する。 20.950n+o(n)$で動作し、20.5n+o(n)$クラシックメモリとポリ(n)量子ビットを必要とするSVPの量子アルゴリズム。
論文参考訳（メタデータ） (2020-02-19T01:38:34Z)

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