論文の概要: Complexity of Fermionic 2-SAT

• arxiv url: http://arxiv.org/abs/2412.06383v2
• Date: Tue, 10 Dec 2024 13:09:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-11 14:36:41.993563
• Title: Complexity of Fermionic 2-SAT
• Title（参考訳）: フェルミオン2-SATの複雑さ
• Authors: Maarten Stroeks, Barbara M. Terhal,
• Abstract要約: 我々はフェルミオンの満足度問題であるフェルミオン$k$-SATを導入する。 この問題は、古典的に$k=2$で効率的に解けることを証明している。 また、与えられた粒子数に対するフェルミオン2-SATの満足な割り当てが存在するかどうかがNP完全であることを示す。
• 参考スコア（独自算出の注目度）: 0.7980273012483661
• License:
• Abstract: We introduce the fermionic satisfiability problem, Fermionic $k$-SAT: this is the problem of deciding whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on $n$ fermionic modes, where each fermionic projector involves at most $k$ fermionic modes. We prove that this problem can be solved efficiently classically for $k=2$. In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA$_1$-hard.
• Abstract（参考訳）: これはフェルミオン型、パリティ保存型プロジェクターの集合のヌル空間にフェルミオン状態が存在するかどうかを決定する問題であり、フェルミオン型プロジェクターは各フェルミオン型プロジェクターが少なくとも$k$フェルミオン型を含む。 この問題は、古典的に$k=2$で効率的に解けることを証明している。 さらに、与えられた固定粒子数パリティで満足な代入が存在するかどうかを決定することは、フェルミオン2-SATに対して、古典的な2-SAT問題に与えられたハミング重みパリティの解があるかどうかを問う量子フェルミオン拡張(英語版)においても、効率よく行うことができることを示す。 また、与えられた粒子数に対するフェルミオン2-SATの満足な割り当てが存在するかどうかがNP完全であることを示す。 これに対し、フェルミオン9-SAT は QMA$_1$-hard であることを示す。

関連論文リスト

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• The PRODSAT phase of random quantum satisfiability [7.5465062534540515]
  k$-QSAT問題は、有名な$k$-SAT制約満足度問題の量子アナログである。 ゼロエネルギーの積状態が高い確率で存在することは、基礎因子グラフが節被覆二量体構成を持つ場合に限る。
  論文  参考訳（メタデータ） (2024-04-29T06:10:45Z)
• A Simple and Efficient Joint Measurement Strategy for Estimating Fermionic Observables and Hamiltonians [0.0]
  量子化学と相関するフェルミオン系に関係のあるフェルミオン可観測物とハミルトンを簡易に推定する手法を提案する。 提案手法は,N$モードフェルミオン系におけるマヨラナ作用素の任意の積のノイズバージョンを共同測定する手法の実装に基づいている。
  論文  参考訳（メタデータ） (2024-02-29T15:04:34Z)
• Fermionic Hamiltonians without trivial low-energy states [12.961180148172197]
  低エネルギー自明な状態(NLTS)を持たない局所フェルミオンハミルトニアンを構成する。 キュービットの場合とは対照的に、有限深度$textitfermionic$量子回路を介して自明な状態を定義する。 我々は、クラス量子PCPのフェルミオンアナログを定義し、量子ビットバージョンとの関係を議論する。
  論文  参考訳（メタデータ） (2023-07-25T18:00:02Z)
• Quantum Monte Carlo for Gauge Fields and Matter without the Fermion Determinant [0.0]
  強相互作用性フェルミオン系のモンテカルロシミュレーションはフェルミオン符号問題に悩まされている。 我々は,行列式を含まないモデル群におけるフェルミオン符号問題の解法として,メロンクラスタアルゴリズムに着目した。
  論文  参考訳（メタデータ） (2023-05-15T18:00:08Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。 本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。 位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
  論文  参考訳（メタデータ） (2023-02-07T10:57:36Z)
• $O(N^2)$ Universal Antisymmetry in Fermionic Neural Networks [107.86545461433616]
  我々は、置換同変アーキテクチャを提案し、その上で行列式 Slater を適用して反対称性を誘導する。 FermiNetは、単一の行列式を持つ普遍近似能力があることが証明されている。 これは実装が容易であり、計算コストを$O(N2)$に下げることができる。
  論文  参考訳（メタデータ） (2022-05-26T07:44:54Z)
• Fermionic approach to variational quantum simulation of Kitaev spin models [50.92854230325576]
  キタエフスピンモデルは、自由フェルミオンへの写像を通じて、あるパラメータ状態において正確に解けることで知られている。 古典的なシミュレーションを用いて、このフェルミオン表現を利用する新しい変分アンザッツを探索する。 また、量子コンピュータ上での非アベリアオンをシミュレートするための結果の意味についてもコメントする。
  論文  参考訳（メタデータ） (2022-04-11T18:00:01Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  ローレンツ錐体は、ある種の強いレジリエンス特性を満たす対称基底を持つ唯一の円錐体であることを示す。 我々の証明はローレンツ・コーンの対称性を利用しており、エンタングルメント蒸留のプロトコルに類似した2つの構造を適用している。
  論文  参考訳（メタデータ） (2021-10-22T15:02:39Z)

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

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