論文の概要: Quantum k-SAT Related Hypergraph Problems

• arxiv url: http://arxiv.org/abs/2506.17066v1
• Date: Fri, 20 Jun 2025 15:12:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-07 02:47:44.249436
• Title: Quantum k-SAT Related Hypergraph Problems
• Title（参考訳）: 量子k-SAT関連ハイパーグラフ問題
• Authors: Simon-Luca Kremer, Dorian Rudolph, Sevag Gharibian,
• Abstract要約: 量子k-SAT問題は、k-SAT問題の量子である。 構造コアと半径を持つ量子k-SAT問題のグラフ理論による研究を行う。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum k-SAT problem is the quantum generalization of the k-SAT problem. It is the problem whether a given local Hamiltonian is frustration-free. Frustration-free means that the ground state of the k-local Hamiltonian minimizes the energy of every local interaction term simultaneously. This is a central question in quantum physics and a canonical QMA_1-complete problem. The Quantum k-SAT problem is not as well studied as the classical k-SAT problem in terms of special tractable cases, approximation algorithms and parameterized complexity. In this paper, we will give a graph-theoretic study of the Quantum k-SAT problem with the structures core and radius. These hypergraph structures are important to solve the Quantum k-SAT problem. We can solve a Quantum k-SAT instance in polynomial time if the derived hypergraph has a core of size n-m+a, where a is a constant, and the radius is at most logarithmic. If it exists, we can find a core of size n-m+a with the best possible radius in polynomial time, whereas finding a general minimum core with minimal radius is NP-hard.
• Abstract（参考訳）: 量子k-SAT問題は、k-SAT問題の量子一般化である。 与えられた局所ハミルトニアンがフラストレーションのないかどうかが問題である。 フラストレーションフリーとは、k-局所ハミルトニアン基底状態が全ての局所相互作用項のエネルギーを同時に最小化することを意味する。 これは量子物理学における中心的な問題であり、正準QMA_1完全問題である。 量子k-SAT問題は、特別な抽出可能なケース、近似アルゴリズム、パラメータ化複雑性の観点から、古典的なk-SAT問題ほどよく研究されていない。 本稿では、構造コアと半径を持つ量子k-SAT問題のグラフ理論による研究を行う。 これらのハイパーグラフ構造は量子k-SAT問題を解く上で重要である。 導出したハイパーグラフのコアが n-m+a であり、a が定数であり、半径が最大対数である場合、多項式時間で量子 k-SAT のインスタンスを解くことができる。 もし存在するなら、多項式時間内に最も可能な半径を持つ大きさ n-m+a のコアを見つけることができるが、最小半径の一般最小コアを見つけることはNPハードである。

関連論文リスト

• 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)
• Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields [0.0]
  IST-SAT(Iterative Symphonic Tunneling for Satisfiability Problem)と呼ばれる新しい反復量子アルゴリズムを導入する。 IST-SATは高周波振動横場を用いた量子スピンガラス最適化問題を解く。
  論文  参考訳（メタデータ） (2024-08-13T02:09:30Z)
• Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
  平均ケース複雑性理論に基づいて,$m=Omega(n2+delta+epsilon)$のとき,max-k-SSAT が平均計算アルゴリズムであることを示す。 また、平均ケース複雑性理論に基づいて$m=Omega(n2+delta+epsilon)$のとき、max-k-SSATが平均であることが証明される。
  論文  参考訳（メタデータ） (2024-03-05T15:03:47Z)
• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。 両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
  論文  参考訳（メタデータ） (2024-01-05T15:11:24Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。 この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
  論文  参考訳（メタデータ） (2023-06-07T12:19:22Z)
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs [1.2179548969182574]
  実験では、リドベルク原子を用いて(すなわち、満足度(3-SAT)の問題をプログラムし、解を求める)。
  論文  参考訳（メタデータ） (2023-02-28T07:49:10Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。 我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。 提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
  論文  参考訳（メタデータ） (2021-08-06T19:38:03Z)
• Quantum algorithm of a set of quantum 2-sat problem [0.0]
  本稿では,量子2-満足度(Q2SAT)問題に対する量子断熱アルゴリズムを提案する。 Q2SAT 問題に対して、ハイゼンベルク連鎖に類似したハミルトニアンを構成する。
  論文  参考訳（メタデータ） (2020-09-05T21:01:27Z)

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

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