論文の概要: Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction

• arxiv url: http://arxiv.org/abs/2610.14062v1
• Date: Wed, 07 Oct 2026 07:30:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 23:31:29.889898
• Title: Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction
• Title（参考訳）: トラベルセールスマン問題の閾値変動に対するグローバー探索:サーキットレベル構築
• Abstract要約: トラベリングセールスマン問題(TSP)は、最適化形式においてNP完全であり、決定問題としてNP完全である古典的な最適化問題である。 本稿では,有望な問題として定式化されたロバストなTSPと呼ばれるしきい値-フレクションの変種について検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem which is NP-hard in optimisation form and NP-complete as a decision problem. The standard question asks for the shortest tour that visits every city exactly once and returns to the origin. This paper studies a threshold-fraction variant, which we call the robust TSP, formulated as a promise problem: given a distance threshold $K$ and a promised fraction $p$, decide whether at least a fraction $p$ of all tours have total length at most $K$, or whether no such tour exists. We show that Grover's quantum search algorithm decides this problem using $O(1/\sqrt{p})$ oracle queries, independent of the number of cities $N$, with each query implemented by a quantum circuit of polynomial size in $N$. For any fixed robustness level $p$, the total runtime is therefore polynomial in $N$. Measured in oracle queries, the quantum algorithm offers a quadratic improvement in the dependence on $1/p$ over classical random sampling, which needs $Θ(1/p)$ samples; because each quantum query is costly, however, it is faster in total running time only when $p$ is very small (roughly below $N^{-4}$), where the number of queries is no longer constant. We describe the problem formulation, detail the oracle construction (edge-length loading, sequential quantum addition, and threshold comparison), and analyse the query complexity to achieve the required result.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、最適化形式においてNP完全であり、決定問題としてNP完全である古典的な組合せ最適化問題である。 通常の質問は、すべての都市を正確に1度訪問し、原点に戻る最も短いツアーを要求する。 距離しきい値が$K$と約束される分数$p$を与えられた場合、すべてのツアーの少なくとも1つの分数$p$が総長さが$K$であるかどうか、あるいはそのようなツアーが存在しないかどうかを決定する。 我々は,Grover の量子探索アルゴリズムがこの問題を$O(1/\sqrt{p})$ Oracle query を用いて決定することを示した。 任意の固定ロバストネスレベル$p$に対して、総ランタイムは$N$の多項式である。 オラクルクエリで測定された量子アルゴリズムは、古典的なランダムサンプリングよりも1/p$に対する依存度を2次的に改善する。これは、$1/p)$サンプルを必要とするが、それぞれの量子クエリはコストがかかるため、$p$が非常に小さい場合(主に$N^{-4}$未満)にのみ、実行時間が速い。 問題の定式化、オラクル構築(エッジ長ローディング、シーケンシャル量子加算、しきい値比較)を詳述し、必要な結果を得るためにクエリの複雑さを分析する。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• 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)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses [0.0]
  平均ケース複雑性理論に基づいて,$m=Omega(n2+delta+epsilon)$のとき,max-k-SSAT が平均計算アルゴリズムであることを示す。 また、平均ケース複雑性理論に基づいて$m=Omega(n2+delta+epsilon)$のとき、max-k-SSATが平均であることが証明される。
  論文  参考訳（メタデータ） (2024-03-05T15:03:47Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  我々は、$tildeO(sqrtnk+k2)$-timeアルゴリズムを提案し、$tildeO(sqrtnz)$クエリを使用します。 2つ目の貢献は、$tildeO(sqrtnz)$の最適時間複雑性を達成する量子アルゴリズムである。
  論文  参考訳（メタデータ） (2023-11-03T09:09:23Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

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

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