論文の概要: A QUBO Formulation for Nowhere-Zero $k$-Flows
- arxiv url: http://arxiv.org/abs/2606.28687v1
- Date: Sat, 27 Jun 2026 01:59:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-30 18:07:15.644234
- Title: A QUBO Formulation for Nowhere-Zero $k$-Flows
- Title（参考訳）: Nowhere-Zero $k$-FlowsのQUBO式
- Abstract要約: 任意のゼロフローは、トゥッテの5$-フロー予想と関係がなく、グラフ理論において多くの文脈で現れる。
我々はQUBOハミルトニアンとしてゼロでないフローの符号化を行い、その構成の正しさを証明した。
- 参考スコア（独自算出の注目度）: 0.3908906925636173
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the encoding of graph problems as Quadratic Unconstrained Binary Optimization (QUBO) problems, which are solvable by either quantum or classical annealers. Yet, the class of problems encoded as QUBO problems has not previously included nowhere-zero flows. Nowhere-zero flows are related to Tutte's $5$-flow conjecture and appear in many contexts in graph theory. We provide an encoding of nowhere-zero flows as a QUBO Hamiltonian and prove the correctness of the construction. Our construction yields a Hamiltonian $H_{\mathrm{mod},k}$ whose ground state has zero energy if and only if the graph $G$ has a nowhere-zero $\mathbb Z_k$-flow. By Tutte's equivalence theorem, zero ground energy is equivalent to $\varphi(G)\le k$, and the zero-energy degeneracy is given by the flow polynomial $F(G;k)$. In particular, when the ground-state energy is zero, this is also the ground-state degeneracy. The construction uses one-hot variables to represent the edge flow residues modulo $k$ and auxiliary variables to represent the per-vertex modular quotient. We prove that the correctness of the construction is independent of the choice of orientation, root vertex, and positive penalty weights. We verify the construction on $59$ examples of graphs and values of $k$ that include both yes-instances and no-instances. We exhaustively sweep orientations and root choices on selected robustness instances and test a finite suite of positive penalty weights. The resulting Hamiltonian is implemented using the dimod.BinaryQuadraticModel class, which is compatible with the D-Wave Ocean SDK. Quantum-hardware runs and claims about potential speedup using these devices are left to follow-up work.
- Abstract（参考訳）: グラフ問題の符号化を量子アンネラと古典アンネラのどちらでも解ける擬似非制約バイナリ最適化(QUBO)問題とみなす。
しかし、QUBO問題として符号化された問題のクラスは、以前はゼロフローを含まないものではなかった。
任意のゼロフローは、トゥッテの5$-フロー予想と関係がなく、グラフ理論において多くの文脈で現れる。
我々はQUBOハミルトニアンとしてゼロでないフローの符号化を行い、その構成の正しさを証明した。
我々の構成は、基底状態がゼロエネルギーを持つハミルトニアン$H_{\mathrm{mod},k}$を、グラフ$G$がゼロゼロの$\mathbb Z_k$-フローを持つ場合に限る。
トゥッテの同値定理により、ゼロ基底エネルギーは$\varphi(G)\le k$と等価であり、ゼロエネルギー縮退はフロー多項式$F(G;k)$によって与えられる。
特に、基底状態エネルギーがゼロの場合、これは基底状態の縮退でもある。
この構成では、エッジフロー残余を modulo $k$ で表現するために1ホット変数を使用し、補助変数は頂点ごとのモジュラー商を表す。
建設の正しさは, 配向, 根頂点, 正のペナルティ重みの選択とは無関係であることを示す。
グラフの59ドルの例と$k$の値に、yes-instancesとno-instancesの両方を含む構成を検証します。
我々は、選択されたロバスト性インスタンスの向きと根の選択を徹底的に網羅し、正のペナルティ重みの有限組をテストする。
結果は、D-Wave Ocean SDKと互換性のあるdimod.BinaryQuadraticModelクラスを使って実装される。
量子ハードウェアが動作し、これらのデバイスを使用した潜在的なスピードアップに関する主張は、後続の作業に残されている。
関連論文リスト
- Zero-Energy Problems for Supersymmetric Hamiltonians on a Chain Are $\mathrm{QMA}_1$-Complete [2.4344882758650743]
相互作用を1次元鎖上に配置した超対称性量子系の正確なゼロモードについて検討する。
この構成は、還元されたNOインスタンスのすべての基底エネルギーに明示的な逆多項式の下界を与え、それをゼロから分離する。
論文 参考訳（メタデータ） (2026-08-29T15:32:39Z) - A Provable Oracle-Free Quantum Algorithm for Nonlinear Dynamics on Hybrid Oscillator-Qubit Processors [14.814423713691623]
そこで我々は,次数$L$の非線型常微分方程式に対して,演算次数$dotmathbfx=mathbff(mathbfx)$のハイブリッドqubit-qumodeアルゴリズムを開発した。
このアルゴリズムは状態密度を伝播し、その密度のピークとして小雑音の極限で軌道を返す。
論文 参考訳（メタデータ） (2026-07-30T17:10:47Z) - An Optimal Analysis of the Product Test [42.29010058743949]
製品テストは、純多部量子状態が特定のテンソル分解に完全に絡み合っているかどうかを決定する。
基本的なプロパティテストタスクであり、多くのアプリケーションがあるにもかかわらず、製品テストの正確な(最悪のケース)受け入れ確率曲線は、まだ完全には決定されていない。
複雑性理論の応用として,Harrow-Montanaro還元の1ショット音響パラメータを$mathsfQMA(k)$から$mathsfQMA(2)$に改善した。
論文 参考訳（メタデータ） (2026-07-23T16:17:44Z) - Quantum Brownian motion with non-Gaussian noises: Fluctuation-Dissipation Relation and nonlinear Langevin equation [0.0]
我々は1つの発振器を持つ量子ブラウン運動(QBM)モデルをシステムとみなす。
インフルエンサーアクション$S_IF$は、摂動展開を$$で計算する。
非ガウス雑音核は、対応する力のゼロでない3点相関関数をもたらす。
論文 参考訳（メタデータ） (2026-02-11T02:03:26Z) - Discrete symmetries in classical and quantum oscillators [51.56484100374058]
複素バーグマン・フォック・セガル表現において、量子ハミルトニアンの固有函数 $_n=zn$ を示す。
重ね合わせ $=sum_n c_n_n$ は、シュルディンガー方程式を解くための初期データの不完全な知識によってのみ生じる。
論文 参考訳（メタデータ） (2026-01-05T10:04:39Z) - On stability of k-local quantum phases of matter [0.4999814847776097]
一般量子低密度パリティチェック符号に対応するハミルトンのユークリッドに対するエネルギーギャップの安定性を解析する。
局所ハミルトニアンは広い零温度エントロピーを持つことができるので、熱力学の第3法則の意味を論じる。
論文 参考訳（メタデータ） (2024-05-29T18:00:20Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Small-time controllability for the nonlinear Schr\"odinger equation on
$\mathbb{R}^N$ via bilinear electromagnetic fields [55.2480439325792]
非線形シュラー・オーディンガー方程式(NLS)の磁場および電場の存在下での最小時間制御可能性問題に対処する。
詳細は、十分に大きな制御信号によって、所望の速度で(NLS)のダイナミクスを制御できる時期について調べる。
論文 参考訳（メタデータ） (2023-07-28T21:30:44Z) - Taming Dyson-Schwinger equations with null states [0.913755431537592]
場の量子論において、ダイソン=シュウィンガー方程式(ダイソン=シュウィンガーしき、英: Dyson-Schwinger equations)は、n$ポイントグリーンの関数を自己整合的に関連する無限の方程式の集合である。
主要な問題の1つは、無限系の有限個の切り離しが過小評価されていることである。
本稿では,ヌルブートストラップを考慮した別の経路を提案する。
論文 参考訳（メタデータ） (2023-03-20T10:04:43Z) - Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。
境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。
治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
論文 参考訳（メタデータ） (2022-08-12T15:05:07Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。