論文の概要: Quantum Heuristic Separation of Comb Inequalities for the Travelling Salesman Problem

• arxiv url: http://arxiv.org/abs/2610.33188v1
• Date: Fri, 23 Oct 2026 18:30:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-29 19:31:33.189931
• Title: Quantum Heuristic Separation of Comb Inequalities for the Travelling Salesman Problem
• Title（参考訳）: 旅行セールスマン問題におけるコム不平等の量子ヒューリスティック分離
• Abstract要約: 我々は,Combの不等式に対する量子分離アルゴリズムを提案する。 本稿では,データレジスタのハミング重みを補助レジスタの1ホット形式でコヒーレントに符号化する回路を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Comb inequalities are essential cutting planes for the travelling salesman problem, yet their separation remains computationally challenging. We propose a quantum heuristic separation algorithm for this family of inequalities. The algorithm uses a procedure that prepares a uniform superposition of all combs with a fixed number of teeth using polynomially many gates and qubits. As part of this procedure, we present a circuit that coherently encodes the Hamming weight of a data register in one-hot form in an auxiliary register. The separation algorithm then searches for violated inequalities using the Grover-Mixer Quantum Alternating Operator Ansatz. Its running time is polynomial under prescribed polynomial budgets for the number of QAOA rounds, parameter optimization steps and samples gathered, although we provide no evidence that such budgets suffice to find a violated comb with constant probability when one exists. We provide an explicit circuit construction for the mixer unitary, the full problem Hamiltonian and a resource analysis.
• Abstract（参考訳）: コンブの不等式は、旅行セールスマン問題にとって必須の切断面であるが、その分離は計算的に困難である。 この不等式の族に対する量子ヒューリスティック分離アルゴリズムを提案する。 このアルゴリズムは、多項式的に多くのゲートとキュービットを使用して、固定数の歯ですべてのコームの均一な重ね合わせを作成する手順を使用する。 この処理の一環として、補助レジスタにおいてデータレジスタのハミング重みを1ホット形式でコヒーレントに符号化する回路を提案する。 分離アルゴリズムはGrover-Mixer Quantum Alternating Operator Ansatzを用いて不正な不等式を探索する。 実行時間は、QAOAラウンド数、パラメータ最適化ステップ、サンプル収集数に対する所定の多項式予算の下での多項式である。 我々は、ミキサーユニタリに対する明示的な回路構成、ハミルトニアン問題と資源分析を提供する。

関連論文リスト

• Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
  我々は,バッテッチとエーデンベンツの以前の研究に基づいて,旅行販売問題のための国家準備ルーチンを構築した。 イテレーションでは、数回のイテレーションだけで妥当な近似比を達成することを目指しています。
  論文  参考訳（メタデータ） (2026-02-09T09:21:04Z)
• A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization [39.146761527401424]
  この研究は、測定駆動量子SATソルバの厳密な最悪の実行時解析を示す。 この量子アルゴリズムはGrover型法にのみ依存せず,有望な数値性能を示す。 また,複数のタスクを満足するインスタンスに対しても,効率的に解を見つける新しい読み出しルーチンを開発した。
  論文  参考訳（メタデータ） (2025-11-12T19:00:13Z)
• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• Runtime-coherence trade-offs for hybrid SAT-solvers [1.087459729391301]
  総ランタイムとコヒーレンスタイムの間には,単純なトレードオフ関係が存在する,と我々は主張する。 最適トレードオフを伴うハイブリッドアルゴリズムの実装において,さらなる柔軟性を示唆する数値シミュレーションを提案する。
  論文  参考訳（メタデータ） (2024-04-23T17:11:39Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
  従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。 確率分布が均一な量子ビットアンサンブルの量子推定処理を計算すれば、よりクワッドラティックなスピードアップがもたらされることを示す。 例として、正則および準正則なクォービット状態集合の推理を計算する。
  論文  参考訳（メタデータ） (2021-12-03T01:24:57Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。 我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。 我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
  論文  参考訳（メタデータ） (2020-12-03T07:12:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。