Fugu-MT 論文翻訳(概要): Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry

論文の概要: Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry

arxiv url: http://arxiv.org/abs/2603.04540v1
Date: Wed, 04 Mar 2026 19:26:26 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-06 22:06:10.944721
Title: Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry
Title（参考訳）: 最大LINSATのタイト不適合性と復号量子干渉計への応用
Abstract要約: 我々は、非時間アルゴリズムが任意の定数でランダム割当比$r/q$を超えることを、Hstadの定理から直接還元することで証明する。この閾値は、デコードされた量子干渉法を規定する半円法則の$ell/mから0$制限と一致する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We establish tight inapproximability bounds for max-LINSAT, the problem of maximizing the number of satisfied linear constraints over the finite field $\mathbb{F}_q$, where each constraint accepts $r$ values. Specifically, we prove by a direct reduction from Håstad's theorem that no polynomial-time algorithm can exceed the random-assignment ratio $r/q$ by any constant, assuming $\mathsf{P} \neq \mathsf{NP}$. This threshold coincides with the $\ell/m \to 0$ limit of the semicircle law governing decoded quantum interferometry (DQI), where $\ell$ is the decoding radius of the underlying code: as the decodable structure vanishes, DQI's approximation ratio degrades to exactly the worst-case bound established by our result. Together, these observations delineate the boundary between worst-case hardness and potential quantum advantage, showing that any algorithm surpassing $r/q$ must exploit algebraic structure specific to the instance.
Abstract（参考訳）: 有限体$\mathbb{F}_q$ 上の満足線形制約の数を最大化する問題であり、各制約が$r$ の値を受け入れる。具体的には、Håstad の定理から、任意の定数で任意の多項式時間アルゴリズムがランダム割当比 $r/q$ を超えないことを証明し、$\mathsf{P} \neq \mathsf{NP}$ を仮定する。この閾値は、デコードされた量子干渉法(DQI)を規定する半円法則の$\ell/m \to 0$制限と一致する。これらの観測は、最悪の場合の硬さと潜在的な量子的優位性の境界を明確にし、$r/q$を超えるアルゴリズムは、インスタンス固有の代数的構造を利用する必要があることを示した。

関連論文リスト

Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文参考訳（メタデータ） (2026-09-07T01:38:41Z)
A Lower Bound Framework for Quantum Functional Estimation [13.491187998442596]
我々は、$d$次元量子状態の関数を推定するための下界の証明のための統一的なフレームワークを開発する。このフレームワークは、Haar-randomのモーメントエンコーディングプロセスとモーメントマッチングと最適な近似を組み合わせる。
論文参考訳（メタデータ） (2026-08-03T17:59:11Z)
Boundary-Adapted PINNs for Elliptic Dirichlet Problems: $H^2(Ω)$ A Priori Error Bounds with Application to Mean Escape Time Computation [14.109379170744546]
境界強化物理情報ニューラルネットワーク(PINN)を用いた楕円ディリクレ境界値問題(BVP)について検討する。プリミティブエラーバウンダリを導出し、$$への依存を明確にします。我々の証明はまた、ReQU および tanh ネットワークの高階微分の仮説空間に対して、新しい VC-次元境界を与える。
論文参考訳（メタデータ） (2026-07-21T15:03:42Z)
Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry [0.0]
for general max-k-XORSAT with $k geq 3$, no-time algorithm can be significantly better than random guessing on worst-case instance。この接続を明示的にし、任意の有限体上の有界次数$D$および有界次数$E$k$-LINSAT$(q,r)$にハードネスを拡張する。
論文参考訳（メタデータ） (2026-06-11T16:59:12Z)
Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文参考訳（メタデータ） (2026-05-22T15:05:33Z)
Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文参考訳（メタデータ） (2026-04-09T16:38:14Z)
Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文参考訳（メタデータ） (2026-03-19T15:53:41Z)
Arbitrary Boundary Conditions and Constraints in Quantum Algorithms for Differential Equations via Penalty Projections [5.720812431258812]
複雑な境界条件は、自然と工学で生じる現象を正確に記述するために不可欠である。任意の境界条件で微分方程式を解くための効率的な量子アルゴリズムを設計する。
論文参考訳（メタデータ） (2025-06-26T20:14:32Z)
On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut [2.2776283699063664]
最大カット問題(Max-Cut)の1-varepsilon$と1-varepsilon1/2$から、任意の有限$ell_p$-normの下での$gamma$-Approximate Closest Vector Problemへの線形サイズの縮小を示す。有限 $ell_p$-norm における $o(sqrtlog nfrac1p)$- Approximate Closest Vector Problem に対する部分指数時間(古典的あるいは量子的)アルゴリズムは、状態よりも高速であることを示す。
論文参考訳（メタデータ） (2024-11-06T18:58:17Z)
Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文参考訳（メタデータ） (2023-02-03T03:19:14Z)
Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文参考訳（メタデータ） (2022-06-30T03:15:23Z)
A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文参考訳（メタデータ） (2022-02-23T16:10:23Z)
Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文参考訳（メタデータ） (2022-02-23T02:39:04Z)
A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文参考訳（メタデータ） (2022-01-31T22:19:49Z)
Calculable lower bounds on the efficiency of universal sets of quantum gates [0.0]
現在利用可能な量子コンピュータ、いわゆるNoisy Intermediate-Scale Quantum (NISQ) は、比較的少ない量子ビットと適度なゲートフィデリティによって特徴づけられる。本稿では、$mathrmgap_r(mathcalS)$ 上の下界を導出し、その結果、$d$次元量子ゲートの普遍集合の効率について述べる。
論文参考訳（メタデータ） (2022-01-27T19:38:13Z)
Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-20T04:29:18Z)
Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
論文参考訳（メタデータ） (2020-05-18T16:55:08Z)

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