論文の概要: Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
- arxiv url: http://arxiv.org/abs/2609.36464v1
- Date: Tue, 29 Sep 2026 01:24:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-30 21:28:47.08898
- Title: Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
- Title（参考訳）: 量子SATのための微細複合性境界としてのDegree Balance
- Abstract要約: 2つの軽度の仮定の下で指数関数的に高速な古典的および量子的アルゴリズムを示す。
アルゴリズムの正則性への依存は、ある意味では、ほぼ最適である。
我々の上と下の境界は、量子飽和性のための微細な複雑さの二分法を確立する。
- 参考スコア（独自算出の注目度）: 0.9449650062296824
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The local Hamiltonian problem is the canonical $\mathsf{QMA}$-complete problem, and $O(2^n)$ time classical algorithms and $O(2^{n/2})$ time quantum algorithms are known to solve the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs. In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints. We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but $O(\sqrt{n})$ qubits participate in only constantly many constraints, while the remaining $O(\sqrt{n})$ qubits each participate in $O(\sqrt{n})$ constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of $n^δ$, for any $δ>0$, our algorithm solves the problem in time $O(2^{(1- \varepsilon)n})$ for some $\varepsilon>0$. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.
- Abstract（参考訳）: 局所ハミルトン問題は、標準の$\mathsf{QMA}$完全問題であり、$O(2^n)$時古典アルゴリズムと$O(2^{n/2})$時量子アルゴリズムは、最悪の場合、この問題を解決するために知られている。
基底状態は一般に絡み合っており、古典的CSPの既知の戦略を直接適用することはできないため、この問題の幅広いクラスに対して、これらの残酷な力戦略をどのように改善するかは明らかではない。
本研究では,(1)ハミルトニアンがYESインスタンス上でフラストレーションフリーであること,(2)ほぼ正則であること,すなわち各キュービットがほぼ同じ数の制約で作用すること,という2つの軽微な仮定の下で,指数関数的に高速な古典的および量子的アルゴリズムを提示する。
我々は、(Q)SETH を仮定すると、量子 5-SAT は非自明な最悪のケースのスピードアップを認めないことを示すことによって、これらの上限を補完する。
我々の下限はさらに、アルゴリズムの正則性への依存が、ある意味でほぼ最適であることを示す。
具体的には、量子 5-SAT は (Q) SETH-ハードなままであり、例えば、$O(\sqrt{n})$ qubits 以外はすべて常に多くの制約にのみ参加し、残りの $O(\sqrt{n})$ qubits は$O(\sqrt{n})$ qubits がそれぞれ $O(\sqrt{n})$ の制約に参加している。
対照的に、この高次部分集合のサイズまたはその量子ビットの次数が任意の$δ>0$に対して$n^δ$の係数で減少すると、我々のアルゴリズムは、ある$\varepsilon>0$に対して$O(2^{(1- \varepsilon)n})$の時間で問題を解く。
上界と下界は共に、量子的充足性のための微細な複雑さの二分法を確立する。
関連論文リスト
- Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions [1.43494686131174]
1-varepsilon)n)$ for any $varepsilon>0$ for any $varepsilon>0$ under the Strong Exponential-Time hypothesis (SETH)。
我々は、任意の1/mathrmpoly(n)$相対誤差に対して$O(sqrt2n)$ timeで実行し、下位境界にマッチし、Bravyi、Chowdhury、Gossによる最先端アルゴリズムを改善する量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-02-16T01:11:55Z) - 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH [0.6015898117103068]
局所ハミルトン問題の計算複雑性と量子分割関数(QPF)の近似について検討する。
どちらの問題もQMAハードであることが知られており、$mathsfBQP neq mathsfQMA$ という広く信じられている仮定の下では、効率的な量子アルゴリズムの出口は存在しない。
量子アルゴリズムがLHまたは近似QPFを3局所ハミルトニアンに対しても$O(2n/2)$よりもかなり高速に解くことはできないことを証明している。
論文 参考訳（メタデータ） (2025-10-08T19:45:24Z) - 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) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Quantum Speedups for Bayesian Network Structure Learning [12.02309220445177]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(2nn2)$で実行され、20年で改善はない。
量子コンピューティングの最近の進歩に触発されて、ある定数$c$が2ドル以下であれば、時間$O(cn)$で量子アルゴリズムによって解けるかどうかを問う。
論文 参考訳（メタデータ） (2023-05-31T09:15:28Z) - 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) - 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) - Quantum algorithm of a set of quantum 2-sat problem [0.0]
本稿では,量子2-満足度(Q2SAT)問題に対する量子断熱アルゴリズムを提案する。
Q2SAT 問題に対して、ハイゼンベルク連鎖に類似したハミルトニアンを構成する。
論文 参考訳（メタデータ） (2020-09-05T21:01:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。