論文の概要: Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing
- arxiv url: http://arxiv.org/abs/2608.26894v1
- Date: Thu, 27 Aug 2026 09:48:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-28 16:30:58.336877
- Title: Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing
- Title（参考訳）: 固定翼車両ルーティングのためのアークベースQUBOモデルの補正接続性
- Abstract要約: 我々は、固定フリート、均質、無容量の車両ルーティングに対して、次数のみのアークハミルトニアンを再検討する。
局所的な罰則は2次サイクルのカバーのみを定義するため、接地状態は補給所から切り離された顧客サイクルを含む可能性がある。
我々は、全ての基底状態ルーティングが明示的なペナルティ仮定の下で接続され、コストが最適であることを証明した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing. Because its local penalties define only a cycle cover, ground states may contain customer cycles disconnected from the depot. We construct a polynomial-size quadratic unconstrained binary optimization (QUBO) repair using capped single-commodity flow and prove that every ground-state routing is connected and cost-optimal under explicit penalty assumptions. For $N-1$ customers and $K$ nonempty routes, the unreduced encoding uses exactly $|E|(1+\lceil\log_2(N-K+1)\rceil)$ logical problem qubits. A reversible compute--phase--uncompute realization evaluates the flow penalties in $O(N^2\log N+N\log^2N)$ logical gates on a complete graph with $O(\log N)$ reusable workspace and no product register. On complete loopless graphs, a depot-delimited single-sequence position encoding uses fewer problem qubits and fewer written terms when the flow-word length grows. Conversely, the flow model achieves a smaller structured logical-gate upper bound under a common reversible accounting model. Exact audits of the Hamiltonian and circuit implementation, combined with a $1{,}200$-matrix classical benchmark, verify the formulation and quantify the connectivity gap. Finally, a 32,000-shot Amazon Braket task on IQM Emerald characterizes depth-one termwise Ising circuits on a diagnostic $N = 4,\, K = 1$ counterexample instance. In the degree-only circuit, $78.05\%$ of selected $p=1$ shots realize the invalid disconnected ground state; the reduced 14-qubit flow-augmented circuit yields no fully feasible sample. These device results characterize mapped Hamiltonians and compilation rather than an asymptotic routing solution advantage.
- Abstract（参考訳）: 我々は、固定フリート、均質、無容量の車両ルーティングに対して、次数のみのアークハミルトニアンを再検討する。
局所的な罰則はサイクルカバーのみを定義するため、接地状態は補給所から切り離された顧客サイクルを含む可能性がある。
固定単商品フローを用いた多項式サイズの2次非拘束二元最適化 (QUBO) を構築, 明示的なペナルティ仮定の下で, 基底状態のルーティングが接続され, コストが最適であることを証明した。
N-1$の顧客と$K$の空でないルートの場合、非還元エンコーディングは正確に$|E|(1+\lceil\log_2(N-K+1)\rceil)$論理問題キュービットを使用する。
可逆的な計算位相非コンパクトな実現法は、$O(N^2\log N+N\log^2N)$論理ゲートが$O(\log N)$再利用可能なワークスペースを持ち、製品レジスタが存在しない完全グラフ上のフローペナルティを評価する。
完全ループレスグラフでは、depot-delimited single-sequence position encoding は、フローワード長が大きくなると、より少ない問題量子ビットと少ない記述項を使用する。
逆に、フローモデルは、共通の可逆的会計モデルの下で、より小さな構造化された論理ゲートの上界を達成する。
ハミルトンおよび回路実装の厳密な監査と1{,}200$-matrixの古典的ベンチマークを組み合わせることで、定式化を検証し、接続ギャップを定量化する。
最後に、IQM Emerald上の32,000ショットのAmazon Braketタスクは、診断用の$N = 4,\, K = 1$反例インスタンス上で、深さ1項のIsing回路を特徴付ける。
次数のみの回路では、選択された$p=1$ショットの78.05\%$は、無効な不連結な基底状態を実現する。
これらのデバイスは、漸近的なルーティングソリューションの利点ではなく、マッピングされたハミルトンとコンパイルを特徴付ける。
関連論文リスト
- Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians [4.914113120082008]
構成されたフェルミオンおよびスピンハミルトニアンのブロック符号化を単位クリフォード$+T$モデルで構築するコストについて検討する。
我々の主要な技術ツールは、アンシラ圧縮の定理である:$n$-qubit演算子を$a$クリーンアンシラで、少なくとも$s$T$ゲートで圧縮して、少なくとも$mina,n+2s$アンシラで使用することができる。
論文 参考訳（メタデータ） (2026-09-10T07:01:08Z) - A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Restrictions on non-Clifford fault tolerance and ruling out beyond-SQL quantum metrology [0.0]
既知のNo-go結果を取り巻く潜在的な経路は、物理信号が論理ゲートとして誘導される量子コードにセンサーを符号化することである。
小角$$の単一量子ビット回転は、低ウェイト正規化器測定から耐障害的に再構成できることが示される。
また、量子クラメロ-ラオ境界の仮定を回避し、一定の強度の信号整列ノイズがACまたはDCセンシングにおける計算よりも有利であることを示す。
論文 参考訳（メタデータ） (2026-07-29T18:01:14Z) - Compander-Aligned Query Geometry for Quantized Zeroth-Order Optimization [12.92201130466754]
CAQ-ZO は 1-grid-step Rademacher stencils $z pm r$ in $z = (x)$,map endpoints back through $-1$, update in $z$ となる。
提案理論は, グリッドの分散性を証明し, 終端を囲む推定器残差を分解し, 一般のオフグリッドクエリが2/2$残差チャネルを保持するステーション境界を与える一方で, CAQ-ZO はクエリ時間残差を正確にゼロにする。
論文 参考訳（メタデータ） (2026-05-11T14:55:20Z) - Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems [0.0]
逐次決定問題に対するコヒーレント量子ロールアウトには、ユニタリシミュレータが必要である。
枝依存の有効作用では、この写像は、絡み合った$N-bitマスク上のコヒーレントなランク選択である。
このプリミティブの最初の可逆・可逆的複雑性解析を行う。
論文 参考訳（メタデータ） (2026-04-28T00:46:37Z) - INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
本稿では,学習した補正を支配方程式に統合する間接ニューラルコレクタ(mathrmINC$)を提案する。
$mathrmINC$は、$t-1 + L$の順番でエラー増幅を減らし、$t$はタイムステップ、$L$はリプシッツ定数である。
大規模なベンチマークで$mathrmINC$をテストし、1Dカオスシステムから3D乱流まで、多くの異なる解法、神経バックボーン、テストケースをカバーした。
論文 参考訳（メタデータ） (2025-11-16T20:14:28Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Fast quantum circuit cutting with randomized measurements [0.0]
本稿では,単一デバイス上で利用可能な物理量子ビット数を超えて,量子計算のサイズを拡大する手法を提案する。
これは、大きな回路の出力状態を異なるデバイス間で分離可能な状態として表すために、無作為に計測・準備チャネルを挿入することで達成される。
論文 参考訳（メタデータ） (2022-07-29T15:13:04Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。
結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
論文 参考訳（メタデータ） (2021-10-08T08:22:05Z) - Exponential Error Suppression for Near-Term Quantum Devices [0.0]
NISQ時代には、最小のQECでさえ採用するために必要な複雑さと規模は禁じられている。
観測可能な天体の期待値を推定する重要な場合において、実効的な指数的抑制を達成できることが示される。
論文 参考訳（メタデータ） (2020-11-11T18:00:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。