論文の概要: Improved Quantum Random Self-Reduction for Linear Problems

• arxiv url: http://arxiv.org/abs/2609.39823v1
• Date: Wed, 30 Sep 2026 14:26:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.888052
• Title: Improved Quantum Random Self-Reduction for Linear Problems
• Title（参考訳）: 線形問題に対する量子ランダム自己還元の改良
• Abstract要約: 有限体上の線形問題に対する量子ランダム自己還元について検討する。 特に、$T=widetildeO(n)$の場合には、$widetildeO(n4/3)$の時間で、$widetildeO(n3/2+T)$のAsadi、Golovnev、Gur、Shinkar、Subramanian(SODA 2024)の還元を改善する。
• 参考スコア（独自算出の注目度）: 1.7587442088965224
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study quantum random self-reductions for linear problems over finite fields. Let $M\in\mathbb{F}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an oracle that agrees with the linear map $x\mapsto Mx$ on an $\varepsilon$-fraction of inputs $x\sim\mathbb{F}^n$. Given coherent access to $\mathcal{O}$ and coherent entry access to $M$, we give a uniform quantum reduction that computes $Mx$ on any prescribed input $x$ with probability at least $2/3$ in time $\widetilde{O}(nT^{1/3})$, for $n\le T\le n^{3/2}$ and constant field size and $\varepsilon$, where $T$ is the cost of one coherent query to $\mathcal{O}$. In particular, when $T=\widetilde{O}(n)$, the reduction runs in time $\widetilde{O}(n^{4/3})$, improving the $\widetilde{O}(n^{3/2}+T)$ reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024). Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.
• Abstract（参考訳）: 有限体上の線形問題に対する量子ランダム自己還元について検討する。 M\in\mathbb{F}^{n\times n}$を任意の行列とし、$\mathcal{O}$を、入力の$x\sim\mathbb{F}^n$上の線型写像 $x\mapsto Mx$と一致するオラクルとする。 M$へのコヒーレントなエントリアクセスと、$M$へのコヒーレントなエントリアクセスを与えられた場合、$Mx$は、少なくとも2/3$の確率で$$\widetilde{O}(nT^{1/3})$, for $n\le T\le n^{3/2}$と定数フィールドサイズと$\varepsilon$に対して$Mx$を計算し、$T$は$\mathcal{O}$へのコヒーレントなクエリのコストである。 特に、$T=\widetilde{O}(n)$の場合、この還元は時間$\widetilde{O}(n^{4/3})$で行われ、$\widetilde{O}(n^{3/2}+T)$Asadi, Golovnev, Gur, Shinkar, Subramanian (SODA 2024) が減少する。 我々の減算は加法コンビネータによって保証されるボゴリューボフ-ルッツァ部分空間を用いるが、この部分空間を明示的に学習することは避け、これは前回の減算で計算的に高価であった。特に、直交補空間の基底を回復しない。主な技術的ステップは、入力をスパーピースに分解し、振幅増幅に基づく量子探索によってボゴリューボフ-ルッツァ部分空間の外側にあるベクトルを見つけることである。 これにより、平均ケースのオラクルを問合せするコストと、行列ベクトル積を検証するコストとの調整可能なトレードオフが得られる。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$を符号、空間性、正方性制限なしで証明する。 純粋な$varepsilon$-DP行列力学クラスでは、最適化された最大誤差と平均二乗誤差の両方が$(varepsilon-2log3(n+1))$である。
  論文  参考訳（メタデータ） (2026-07-30T14:41:34Z)
• Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors [3.9657575162895196]
  我々は、隠蔽部分空間埋め込みの最適次元と空間性に関するネルソンとニュイエンの予想(FOCS 2013)の証明を与える。 任意の $ngeq d$ および $epsilongeq d-O(1)$ に対して、任意の $AinmathbbRntimes d に対して $tilde O(d/epsilon2)times n$ matrix $Pi$ with $tilde O(log(d)/epsilon)$ non-zeros per column が存在する。
  論文  参考訳（メタデータ） (2025-08-19T19:45:52Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Partially Unitary Learning [0.0]
  ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。 この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-16T17:13:55Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)

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

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