論文の概要: Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations
- arxiv url: http://arxiv.org/abs/2604.04570v1
- Date: Mon, 06 Apr 2026 10:08:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-07 15:49:19.165541
- Title: Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations
- Title（参考訳）: カラー変色による最適量子車両ルーティング
- Authors: Chinonso Onah, Kristel Michielsen,
- Abstract要約: 静電容量化車両ルーティング問題に対するグローバル配置色置換符号化を定式化する。
この表現は、共通の置換構造の上に$K$カラー層として配置された$n2K$バイナリ決定変数を使用する。
- 参考スコア（独自算出の注目度）: 0.2578242050187029
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the $K$ vehicles selects a disjoint partial permutation, and the sum of these $K$ color layers forms a full $n\times n$ permutation matrix that assigns every customer to exactly one visit position. This representation uses $n^2K$ binary decision variables arranged as $K$ color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class, requiring no explicit load register and hence no extra logical qubits beyond the routing variables. In contrast, many prior quantum encodings introduce an explicit capacity or load representation with additional qubits. Our construction is designed to exploit the Constraint-Enhanced QAOA framework together with its encoded-manifold analyses. Building on a requirements-based view of quantum utility in CVRP, we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. On a standard benchmark suite, our end-to-end pipeline recovers the independently verified optima. The feasibility oracle may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.
- Abstract（参考訳）: 静電容量化車両ルーティング問題に対するグローバル配置色置換符号化を定式化する。
それぞれの$K$車両は不整合部分置換を選択し、これらの$K$カラーレイヤーの合計は完全な$n\times n$置換行列を形成し、すべての顧客を正確に1つの訪問位置に割り当てる。
この表現は、共通の置換構造上の$K$カラー層として配置された$n^2K$のバイナリ決定変数を使用し、一方、車両の容量は各カラークラスのエントリの重み付け和によって強制されるため、明示的な負荷レジスタは不要であり、従って、ルーティング変数以外の論理量子ビットは不要である。
対照的に、多くの先行量子符号化は、追加の量子ビットを持つ明示的なキャパシティやロード表現を導入している。
コンストラット強化QAOAフレームワークと符号化多様体解析を併用して構築した。
我々は,CVRPにおける量子ユーティリティの要求に基づくビューを構築し,車両ラベルの論理量子コストと明示的な容量制約といった,短期的ボトルネックの1つを直接対象とするルーティング最適化の定式化を開発する。
提案手法は,量子ビット効率に加えてアルゴリズム性能も高いことを示す。
標準ベンチマークスイートでは、エンドツーエンドパイプラインが独立に検証されたオプティマを復元します。
実現可能性オラクルは、量子および量子に着想を得たルーティングパイプラインに対する再利用可能な多項式時間復号および証明プリミティブとして、独立した関心を持つこともある。
関連論文リスト
- Model selection in hybrid quantum neural networks with applications to quantum transformer architectures [0.3848364262836075]
量子,古典,ハイブリッドトランスフォーマーアーキテクチャを評価するためのフレームワークを開発する。
Simplicity Bias(texttSB$)とExpressivity(texttEXP$)について、さまざまなモデルを比較するリーンメトリクスを紹介します。
我々は、$texttQBET$によって、有望なモデルバリアントの効率的な事前スクリーニングが可能になることを示す。
論文 参考訳（メタデータ） (2026-03-23T09:43:04Z) - A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation Oracle [45.88028371034407]
本稿では,ツアーの時間登録表現に基づくTSPの量子符号化について述べる。
本稿では,経路レジスタ上の一様経路生成,有効なツアーをマークするための可逆オラクル,総ツアーコストをエンコードする位相オラクルの3つの要素について述べる。
論文 参考訳（メタデータ） (2026-03-22T15:15:28Z) - A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
分散量子最適化のための構造認識フレームワークを提案する。
検索スペースが$N$の場合、我々のフレームワークはプロセッサやセパレータに依存した要素に対して$O(sqrtN)$クエリ複雑性を達成する。
構造を考慮した分解は、量子ネットワーク上でのスケーラブルな分散量子最適化に実践的な道をもたらすことを示す。
論文 参考訳（メタデータ） (2026-03-08T15:15:52Z) - Resource-Scalable Fully Quantum Metropolis-Hastings for Integer Linear Programming [0.0]
我々はメトロポリス線形プログラミングのための完全量子化メトロポリス・ハスティングスアルゴリズムを提案する。
各ウォークステップは、一貫性のある候補の動きを準備する一元的な更新である。
本手法は,完全量子制約プログラミングのためのコヒーレントなリソース特性を持つベースラインを提供する。
論文 参考訳（メタデータ） (2026-02-11T19:01:45Z) - Extractors: QLDPC Architectures for Efficient Pauli-Based Computation [39.98920557126034]
本稿では,任意のQLDPCメモリをPauliベースの計算に適した計算ブロックに拡張できる新しいプリミティブを提案する。
特に、メモリ上でサポートされている任意の論理パウリ演算子は、1つの論理サイクルでフォールトトレラントに測定できる。
我々のアーキテクチャは並列論理的測定により普遍的な量子回路を実装できる。
論文 参考訳（メタデータ） (2025-03-13T14:07:40Z) - Non-Iterative Disentangled Unitary Coupled-Cluster based on Lie-algebraic structure [0.0]
量子化学変分量子ソルバ(VQE)計算の実行には、固定されたユニタリ結合クラスター(UCC)アンス"アゼが魅力的である。
固定および非整合型ユニタリカップリング・クラスタコンパクトアンサッツである$k$-NI-DUCCを導入する。
論文 参考訳（メタデータ） (2024-08-26T14:19:53Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - QUANTIFY: A framework for resource analysis and design verification of
quantum circuits [69.43216268165402]
QUINTIFYは、量子回路の定量的解析のためのオープンソースのフレームワークである。
Google Cirqをベースにしており、Clifford+T回路を念頭に開発されている。
ベンチマークのため、QUINTIFYは量子メモリと量子演算回路を含む。
論文 参考訳（メタデータ） (2020-07-21T15:36:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。