論文の概要: A Resource-Efficient Variational Quantum Framework for the Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2605.00739v1
- Date: Fri, 01 May 2026 15:40:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-04 17:43:29.001672
- Title: A Resource-Efficient Variational Quantum Framework for the Traveling Salesman Problem
- Title（参考訳）: トラベリングセールスマン問題に対する資源効率の良い変分量子フレームワーク
- Authors: Yuefeng Lin, Chao Zheng, Cong Guo,
- Abstract要約: 本稿では,コンパクトなバイナリレジスタエンコーディングに基づく資源効率の変動量子フレームワークを提案する。
4、5、6都市の旅行セールスマン問題(TSP)の数値シミュレーションは、それぞれ100%、100%、95.5%の平均的な成功率を達成している。
- 参考スコア（独自算出の注目度）: 5.114988201269962
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、原始的な組合せ最適化問題であるが、その量子実装は標準のワンホット符号化のO(n^2)量子ビットオーバーヘッドによって制限される。
本稿では、コンパクトなバイナリレジスタエンコーディングに基づくリソース効率の変動量子フレームワーク、置換保存問題に着想を得たアンサッツ、相補的な分割・参照実行戦略を提案する。
コンパクトエンコーディングはデータキュービット要求をO(n log n)に減らし、パーティション・アンド・コンカの定式化は各ローカルハードウェアの実行に必要なキュービット数を最大サブシステムのサイズに減らした。
4、5、6都市のTSPインスタンスの数値シミュレーションは、それぞれ100%、100%、95.5%の平均的な成功率を達成している。
さらに,SpinQ Gemini Pro と SpinQ Triangulum II NMR 量子コンピュータ上の 5 都市 TSP インスタンスに対して,分量子近似の局所的な2量子ビット実装を評価する。
この結果から, 資源制約量子ハードウェア上での最小の組合せ最適化インスタンスの研究に, 従来のポストプロセッシングによる符号化と分割・コーダの実行をいかに小型化できるかが示唆された。
関連論文リスト
- EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
既存の技術は情報損失のコストで量子ビットの削減に依存しており、計算性能は劣化している。
等価保存量子ビット効率QAOAを提案し、性能を劣化させることなく必要なキュービット数を著しく削減する。
完全独立変数を持つ非制約問題を除いて,大規模最適化問題に広く適用可能であることを示す。
論文 参考訳（メタデータ） (2026-04-20T13:57:49Z) - A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
分散量子最適化のための構造認識フレームワークを提案する。
検索スペースが$N$の場合、我々のフレームワークはプロセッサやセパレータに依存した要素に対して$O(sqrtN)$クエリ複雑性を達成する。
構造を考慮した分解は、量子ネットワーク上でのスケーラブルな分散量子最適化に実践的な道をもたらすことを示す。
論文 参考訳（メタデータ） (2026-03-08T15:15:52Z) - An edge-based and subspace reduction encoding scheme to solve the traveling salesman problem in quantum computers [0.0]
本稿では,量子コンピュータ上でのトラベリングセールスマン問題(TSP)を解くための,エッジベースの新しい符号化手法を提案する。
実量子デバイスにおける実装において,解空間の次元をさらに小さくするために,部分空間縮小符号化を適用した。
論文 参考訳（メタデータ） (2025-12-19T07:14:31Z) - Solving larger Travelling Salesman Problem networks with a penalty-free Variational Quantum Algorithm [5.690622599243828]
トラベルセールスマン問題(TSP)はNPハード問題としてよく知られており、ラストマイル配送のような産業用ユースケースがある。
我々は、最大12箇所のネットワークのノイズフリーシミュレーションにおいて、ハイブリッドペナルティフリー回路モデルを用いて高品質な解を提案する。
論文 参考訳（メタデータ） (2025-12-06T18:21:21Z) - Route-Forcing: Scalable Quantum Circuit Mapping for Scalable Quantum Computing Architectures [41.39072840772559]
Route-Forcingは量子回路マッピングアルゴリズムで、平均スピードアップが3.7Times$であることを示している。
本稿では、最先端のスケーラブルな手法と比較して平均3.7倍の高速化を示す量子回路マッピングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-24T14:21:41Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - Mapping quantum circuits to modular architectures with QUBO [3.0148208709026005]
マルチコアアーキテクチャでは、アルゴリズムの実行時にコア間の通信量を最小化することが重要である。
問題と解をエンコードする擬似非制約バイナリ最適化手法を初めて提案する。
提案手法は有望な結果を示し,非常に高密度かつ並列化された回路で極めて良好に動作した。
論文 参考訳（メタデータ） (2023-05-11T09:45:47Z) - Wide Quantum Circuit Optimization with Topology Aware Synthesis [0.8469686352132708]
ユニタリ合成は、量子回路を制限的量子ビット位相にマッピングしながら最適なマルチキュービットゲート数を達成する最適化手法である。
我々は,emphBQSKitフレームワークで構築されたトポロジ対応合成ツールであるTopASを紹介した。
論文 参考訳（メタデータ） (2022-06-27T21:59:30Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Optimal Qubit Mapping with Simultaneous Gate Absorption [9.530683922512873]
コンパイルにおける重要なステップは、プログラム内の量子ビットを、与えられた量子コンピュータ上の物理量子ビットにマッピングすることである。
OLSQ-GAは、SWAPゲートを同時に吸収する鍵となる特徴を持つ最適量子ビットマッパーである。
OLSQ-GAは、他の最先端手法と比較して、深さを最大50.0%、SWAPカウントを100%削減する。
論文 参考訳（メタデータ） (2021-09-14T05:15:36Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。