論文の概要: Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry

• arxiv url: http://arxiv.org/abs/2606.13570v1
• Date: Thu, 11 Jun 2026 16:59:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-12 15:55:27.931306
• Title: Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
• Title（参考訳）: 有界度最大LINSATの近似可能性限界と復号量子干渉計への応用
• Authors: Maximilian J. Kramer, Carsten Schubert, Jens Eisert,
• Abstract要約: 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)$にハードネスを拡張する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For general max-k-XORSAT with $k \geq 3$, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless $\mathsf{P} = \mathsf{NP}$: approximating beyond the random-assignment value of $1/2$ is $\mathsf{NP}$-hard. The picture changes when each variable appears in at most $D$ constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order $1/\sqrt{D}$. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields $\mathbb{F}_q$, proving that it is $\mathsf{NP}$-hard to exceed $r/q + \mathcal{O}_{q,r}(1/\sqrt{D})$. These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on $(k,D)$-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic $1/\sqrt{D \log D}$ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the $1/\sqrt{D}$ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.
• Abstract（参考訳）: 一般の max-k-XORSAT with $k \geq 3$ に対して、$\mathsf{P} = \mathsf{NP}$: 1/2$ is $\mathsf{NP}$-hard のランダム割当値を超える近似がない限り、最悪のケースでランダムに推測するよりもはるかに良い多項式時間アルゴリズムは存在しない。 各変数が最大$D$制約で現れると、画像が変わる。 その有界な設定では、多項式時間アルゴリズムは1/\sqrt{D}$の加算量でランダムなベースラインを確実に打ち負かすことができる。 このスケーリングは最適であることが知られている: 一致する硬さの結果はTravisanによるもので、それに対応するアルゴリズム保証はBarakらによって確立された。 この接続を明示的にし、有界次数$D$ と任意の有限体 $\mathbb{F}_q$ を上の有界次数$E$k$-LINSAT$(q,r)$ に拡張し、$r/q + \mathcal{O}_{q,r}(1/\sqrt{D})$ を超えるように$\mathsf{NP}$-hard であることを証明する。 これらの結果は、復号量子干渉法(DQI)、QAOA、古典的ヒューリスティックス(英語版)を対象とする有界度インスタンスに対する複雑性理論のベンチマークを提供する。 したがって、有界次数インスタンス上の任意の量子優位性は定数プレファクタに限られる。 さらに、DQIと$(k,D)$-regularインスタンスのコンテキストにおいて、このプレファクタはデコーダの性質に敏感である: 古典的デコーダを持つDQIは、情報理論上の1/\sqrt{D \log D}$障壁に直面し、量子デコーダを持つDQIは1/\sqrt{D}$スケーリングと互換性がある。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  我々は、非時間アルゴリズムが任意の定数でランダム割当比$r/q$を超えることを、Hstadの定理から直接還元することで証明する。 この閾値は、デコードされた量子干渉法を規定する半円法則の$ell/mから0$制限と一致する。
  論文  参考訳（メタデータ） (2026-03-04T19:26:26Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• 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)

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

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