論文の概要: Towards Implementable Quantum Divide and Conquer: A TSP Solver with Improved Exponential Base over Held-Karp

• arxiv url: http://arxiv.org/abs/2606.07322v1
• Date: Fri, 05 Jun 2026 14:39:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-08 14:33:29.786322
• Title: Towards Implementable Quantum Divide and Conquer: A TSP Solver with Improved Exponential Base over Held-Karp
• Title（参考訳）: 量子ディバイドとコンバータの実現に向けて:Held-Karp上での指数ベースを改良したTSPソルバ
• Authors: Xujun Bai, Yun Shang, Honghong Lin,
• Abstract要約: 古典的動的プログラミングと量子探索を組み合わせることで、旅行セールスマンの問題に対して達成可能な量子的優位性が得られることを示す。 我々の研究は、量子探索の量子スピードアップだけでなく、構造化された量子状態の準備からもたらされる。
• 参考スコア（独自算出の注目度）: 0.4014524824655106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The traveling salesman problem (TSP) is a significant classical NP-hard combinatorial optimization problem. In this work, we demonstrate that combining classical dynamic programming with quantum search can yield an achievable quantum advantage for TSP on the basis of excellent work by the authors of~\cite{ambainis2019quantum}. We design the quantum divide and conquer strategy to provide a parameterized spectrum for this combination. The hybrid algorithm proposed in~\cite{ambainis2019quantum} corresponds to a specific case in this spectrum, while the two extremes of the spectrum represent the purely classical Held-Karp and the purely quantum search algorithm, respectively. Within our parameterized spectrum, we prove that the optimal query complexity is $O^*(1.865666\ldots^n)$, achieved with the 4-subset scheme, while the counting in~\cite{ambainis2019quantum} overlooked half of the recursive branches. The correct query complexity of their algorithm is $O^*(2.225880\ldots^n)$ at their chosen parameter ($α\approx0.055362$), and cannot fall below $O^*(2^n)$ for any $α$ - meaning their $8$-subset scheme, correctly analyzed, never surpasses the classical Held-Karp bound. Furthermore, in previous studies on quantum advantages for NP-hard combinatorial optimization problems, researchers focused only on improvements in query complexity. Our work, however, points out that the quantum advantage stems not only from the quadratic speedup of quantum search but also from the structured quantum state preparation. We argue that structured state preparation is indispensable for realizing the oracle operator while maintaining the total time complexity of $O^*(1.865666\ldots^n)$. Therefore, we design an elegant method for preparing the set partition state, which makes our TSP solver practically executable.
• Abstract（参考訳）: 旅行セールスマン問題(TSP)は、古典的なNPハード組合せ最適化問題である。 本研究では,古典的動的プログラミングと量子探索を組み合わせることで,—\cite{ambainis2019quantum} の著者らによる優れた研究に基づいて,TSPの量子的優位性が得られることを示す。 我々は、この組み合わせのためのパラメータ化スペクトルを提供するために、量子分割と征服戦略を設計する。 The hybrid algorithm proposed in~\cite{ambainis2019quantum} is corresponding to a specific case in this spectrum, the two extremes of the spectrum represents the purely classical Held-Karp and the purely quantum search algorithm。 パラメータ化スペクトルにおいて、最適クエリ複雑性は 4-subset スキームで達成される$O^*(1.865666\ldots^n)$であり、~\cite{ambainis2019quantum} のカウントは再帰枝の半分を覆っていた。 アルゴリズムの正しいクエリ複雑性は、選択されたパラメータ(α\approx0.055362$)において$O^*(2.225880\ldots^n)$であり、任意の$α$に対して$O^*(2^n)$を下回ることができない。 さらに、NPハード組合せ最適化問題に対する量子的優位性に関する以前の研究では、研究者はクエリの複雑さの改善にのみ焦点を絞った。 しかしながら、我々の研究は、量子優位性は量子探索の二次的なスピードアップだけでなく、構造化された量子状態の準備からもたらされることを指摘している。 我々は、O^*(1.865666\ldots^n)$の総時間複雑性を維持しながら、オラクル演算子を実現するためには構造化状態の準備が不可欠であると主張している。 そこで我々は,設定された分割状態を作成するためのエレガントな手法を設計し,TSPソルバを現実的に実行可能にする。

関連論文リスト

• Optimal algorithmic complexity of inference in quantum kernel methods [0.815557531820863]
  量子カーネル法は、教師あり学習において量子優位性を達成するための主要な候補の一つである。 標準アプローチでは、各項をサンプリングによって独立に見積もっており、クエリの複雑さは$O(NlVertrVert2/varepsilon2)$である。 単一可観測体の期待値として全推論和を符号化したクエリ-最適組合せを提案する。 この結果から,クエリ最適化アルゴリズムと,ハードウェア能力による戦略選択の両立が期待できる。
  論文  参考訳（メタデータ） (2026-04-16T16:45:02Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。 一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
  論文  参考訳（メタデータ） (2023-11-01T19:51:00Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum algorithms for escaping from saddle points [7.191453718557392]
  本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。 我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。 また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
  論文  参考訳（メタデータ） (2020-07-20T16:42:53Z)

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

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