論文の概要: The PRODSAT phase of random quantum satisfiability
- arxiv url: http://arxiv.org/abs/2404.18447v1
- Date: Mon, 29 Apr 2024 06:10:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-30 14:36:46.029544
- Title: The PRODSAT phase of random quantum satisfiability
- Title(参考訳): ランダム量子充足可能性のProDSAT相
- Authors: Joon Lee, Nicolas Macris, Jean Bernoulli Ravelomanana, Perrine Vantalon,
- Abstract要約: k$-QSAT問題は、有名な$k$-SAT制約満足度問題の量子アナログである。
ゼロエネルギーの積状態が高い確率で存在することは、基礎因子グラフが節被覆二量体構成を持つ場合に限る。
- 参考スコア(独自算出の注目度): 7.5465062534540515
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The $k$-QSAT problem is a quantum analog of the famous $k$-SAT constraint satisfaction problem. We must determine the zero energy ground states of a Hamiltonian of $N$ qubits consisting of a sum of $M$ random $k$-local rank-one projectors. It is known that product states of zero energy exist with high probability if and only if the underlying factor graph has a clause-covering dimer configuration. This means that the threshold of the PRODSAT phase is a purely geometric quantity equal to the dimer covering threshold. We revisit and fully prove this result through a combination of complex analysis and algebraic methods based on Buchberger's algorithm for complex polynomial equations with random coefficients. We also discuss numerical experiments investigating the presence of entanglement in the PRODSAT phase in the sense that product states do not span the whole zero energy ground state space.
- Abstract(参考訳): k$-QSAT問題は、有名な$k$-SAT制約満足度問題の量子アナログである。
我々は、M$ランダム$k$ローカライズワンプロジェクターの和からなる$N$ qubitsのハミルトニアンのゼロエネルギー基底状態を決定する必要がある。
ゼロエネルギーの積状態が高い確率で存在することは、基礎因子グラフが節被覆二量体構成を持つ場合に限る。
これは、PRDSAT相のしきい値は、ダイマー被覆しきい値に等しい純粋に幾何学的な量であることを意味する。
複素係数を持つ複素多項式方程式に対するブーベルガーのアルゴリズムに基づく複素解析と代数的手法の組み合わせにより、この結果を再検討し、完全に証明する。
また、生成物状態がゼロエネルギー基底状態空間全体にまたがらないという意味で、ProdSAT相における絡み合いの存在を研究する数値実験についても論じる。
関連論文リスト
- On the Computational Complexity of Schrödinger Operators [6.1436827446807705]
実空間におけるシュル「オーディンガー作用素 $H = -Delta + V$ に関する計算問題について検討する。
i) シュル・オーディンガー作用素が生成する力学をシミュレートすると、普遍量子計算、すなわち、BQP-ハードであり、(ii) シュル・オーディンガー作用素の基底エネルギーを推定することは、符号問題のない局所ハミルトン多様体のエネルギーを推定するのと同じくらい難しいことを証明する。
一般ボソニックハミルトニアンの基底エネルギー問題は知られているので、この結果は特に興味深い。
論文 参考訳(メタデータ) (2024-11-07T19:39:52Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。
d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文 参考訳(メタデータ) (2023-12-16T12:44:36Z) - A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。
この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
論文 参考訳(メタデータ) (2023-06-07T12:19:22Z) - Testing quantum satisfiability [0.04297070083645048]
量子k-SATはランダムな時間で解けることを示す。
まず、量子 k-SAT の充足可能なインスタンスに対して、一定数の量子ビット上のほとんどの部分プロブレムは積状態によって満足できることを示す。
次に、積状態によって満足できない量子 k-SAT のインスタンスの場合、ほとんどのサブプロブレムは積状態によって満足できないことを示す。
論文 参考訳(メタデータ) (2023-01-25T17:02:46Z) - The Parameterized Complexity of Quantum Verification [7.7155343772895275]
量子回路の整合性の問題に対して,非クリフォードゲート数で指数関数的にスケーリングすることで問題を解くアルゴリズムが存在することを示す。
我々は、サーキット適合性のインスタンスの$T$-countと$W$-stateの$$$-countに新しい下位境界を導出する。
論文 参考訳(メタデータ) (2022-02-16T14:53:42Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳(メタデータ) (2021-11-09T18:49:48Z) - K-sparse Pure State Tomography with Phase Estimation [1.2183405753834557]
純状態の再構成のための量子状態トモグラフィ(QST)は、キュービット数で資源と測定を指数的に増加させる必要がある。
特定の測定セットにおける$n$bitsの異なる計算基底状態の重ね合わせからなる純状態のQST再構成を示す。
論文 参考訳(メタデータ) (2021-11-08T09:43:12Z) - Annihilating Entanglement Between Cones [77.34726150561087]
ローレンツ錐体は、ある種の強いレジリエンス特性を満たす対称基底を持つ唯一の円錐体であることを示す。
我々の証明はローレンツ・コーンの対称性を利用しており、エンタングルメント蒸留のプロトコルに類似した2つの構造を適用している。
論文 参考訳(メタデータ) (2021-10-22T15:02:39Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳(メタデータ) (2020-02-25T19:18:36Z) - Approximate unitary $t$-designs by short random quantum circuits using
nearest-neighbor and long-range gates [0.0]
ply(t)cdot n1/D$-depth local random quantum circuits with two qudit Near-ighbor gates are almost $t$-designs in various measures。
また,異なるモデルを用いた深度O(log(n)loglog(n)において,反濃縮が可能であることを証明した。
論文 参考訳(メタデータ) (2018-09-18T22:28:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。