論文の概要: A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation

• arxiv url: http://arxiv.org/abs/2603.21283v1
• Date: Sun, 22 Mar 2026 15:15:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-24 19:11:39.327404
• Title: A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation
• Title（参考訳）: 経路生成, コスト相, バリデーションによる旅行セールスパーソンツアーの量子符号化
• Abstract要約: 本稿では,ツアーの時間登録表現に基づくTSPの量子符号化について述べる。 本稿では,経路レジスタ上の一様経路生成,有効なツアーをマークするための可逆オラクル,総ツアーコストをエンコードする位相オラクルの3つの要素について述べる。
• 参考スコア（独自算出の注目度）: 45.88028371034407
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a compact quantum encoding of the Traveling Salesperson Problem (TSP) based on a time-register representation of tours. A candidate route is represented as a sequence of $n$ city labels over discrete time steps, with one fixed start city and the remaining cities encoded in binary registers. We describe three ingredients of the construction: uniform route generation over the route register, a reversible oracle for marking valid tours, and a phase oracle that encodes the total tour cost. The validity oracle distinguishes permutations of the non-start cities from invalid assignments, while the cost oracle accumulates the contribution of the start edge, intermediate transitions, and return edge into a tour-dependent phase. This yields a coherent superposition of candidate routes with feasibility and tour-length information embedded directly in the quantum state. The number of qubits required is $\Order{n\log_2(n)}$ and the circuit depth scales quadratically in $n$. The encoding is compatible with amplitude amplification or spectral filtering techniques such as the quantum singular value transform (QSVT) or Grover's algorithm. However, due to the exponentially small fraction of valid tours, the overall complexity remains exponential even when combined with amplitude amplification.
• Abstract（参考訳）: 本稿では,ツアーの時間登録表現に基づくTSPの量子符号化について述べる。 候補ルートは、個別の時間ステップで$n$の都市ラベルのシーケンスとして表現され、1つの固定開始都市と残りの都市がバイナリレジスタにエンコードされている。 本稿では,経路レジスタ上の一様経路生成,有効なツアーをマークするための可逆オラクル,総ツアーコストをエンコードする位相オラクルの3つの要素について述べる。 有効オラクルは、非起動都市の置換と不正な割り当てとを区別し、コストオラクルは、スタートエッジ、中間遷移、リターンエッジの寄与をツアー依存フェーズに蓄積する。 これにより、量子状態に直接埋め込まれた実現可能性とツアー長情報を備えた候補経路のコヒーレントな重ね合わせが得られる。 必要となる量子ビットの数は$\Order{n\log_2(n)}$で、回路深さは$n$で2次スケールする。 この符号化は、量子特異値変換(QSVT)やグローバーのアルゴリズムのような振幅増幅やスペクトルフィルタリング技術と互換性がある。 しかし、有効なツアーの指数的に少ないため、振幅増幅と組み合わせても全体的な複雑さは指数関数的のままである。

関連論文リスト

• The Gain-Engineered Transmon [68.89136228609398]
  標準的なトランスモン・リードアウト共振器回路において,ノイズバイアス量子ビットを導入し,実験的に実現する。 本システムは,ハードウェア効率のよい量子エラー検出と修正手法のための単純なビルディングブロックとして利用するための道を開く。
  論文  参考訳（メタデータ） (2026-08-26T17:00:42Z)
• Quantum Circuits for Quantum Spatial Search on $d$-Dimensional Lattices [2.2336243882030025]
  本稿では,$d$次元格子上の離散時間量子ウォークに基づく量子空間探索のための明示的な量子回路を提案する。 提案回路は2次元および3次元周期格子上の理論的ダイナミクスを再現する。
  論文  参考訳（メタデータ） (2026-07-21T14:51:25Z)
• Efficient Quantum Circuits for Coherent Conversion Between General First- and Second-Quantized Many-Body Representations [1.6089851562703383]
  逆の$Qdagger$を持つ明示的な$Q$を構築し、最初の量子化された状態をその固定された$N$の占有数形式にマッピングする。 変換は入力に対して対称性に依存しないが出力で完全に解決され、ボゾン、フェルミオン、パラ統計学のセクターに一様に適用される。
  論文  参考訳（メタデータ） (2026-06-23T18:00:04Z)
• Multi-Qubit Dyadic Phase Fixing for Fault-Tolerant Quantum Compilation [1.729914033210882]
  本稿では、位相キックバックを一般的な量子回路に拡張する汎用多ビット合成ツールであるDyadic Phase Fixing (DPF)を提案する。 DPFは数値的なユニタリ合成を用いて任意の入力回路から直角回転をグレード的に抽出する。 エンド・ツー・エンドのワークフローは、textttgridsynthと比較して最大70%T$-countを削減し、さまざまなベンチマークでRepeat-Until-Success合成と比較すると60%まで削減できる。
  論文  参考訳（メタデータ） (2026-06-03T20:07:30Z)
• Barriers to Universal Reasoning With Transformers (And How to Overcome Them) [46.59247939156339]
  CoT(Chain-of-Thought)は、トランスフォーマーの性能を実証的に改善し、理論的にはチューリング完全性への表現性を高めることが示されている。 我々は、Transformer長の一般化に関する最近の理論フレームワークを使用し、標準的な位置エンコーディングと有限アルファベットの下では、CoT を持つ変換器は$TC0$以上の問題を解くことができない。 我々は,シミュレーション実行時のCoTトレース長が一定まで線形であるチューリングマシンの時間一般化可能なシミュレーションを実現する。
  論文  参考訳（メタデータ） (2026-04-28T16:10:37Z)
• Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce $T$-count [1.6195650245658724]
  局所合成アプローチは、大きな回路をサブ構造に分解することで、一般に大きな回路をコンパイルするために用いられる。 我々は,回路等価性を保存するローカル編集セットを前提として,RLエージェントを用いて有効なシーケンスを識別する戦略であるtextscQ-PreSynを提案する。 実験結果は、最大25キュービットの回路上でのT$カウントを20%削減する。
  論文  参考訳（メタデータ） (2026-01-27T15:58:05Z)
• Quantum-Inspired Algorithms beyond Unitary Circuits: the Laplace Transform [0.0]
  量子インスパイアされたアルゴリズムは、古典的な最先端の手法よりも大幅にスピードアップできる。 離散ラプラス変換(非単項非周期変換)を計算するためのテンソル-ネットワークアプローチを導入する。 我々は最大$N=230$の入力データポイントと最大260$の出力データポイントのシミュレーションを実証し、ボンド次元が実行時と精度をどのように制御するかを定量化する。
  論文  参考訳（メタデータ） (2026-01-25T07:19:56Z)
• Accelerating Transpilation in Quantum Machine Learning with Haiqu's Rivet-transpiler [45.88028371034407]
  我々は、以前にトランスパイルされた回路を再利用してトランスパイラを高速化するリベットトランスパイラを開発した。 量子層学習において,600%のトランスパイル時間の改善を実証した。
  論文  参考訳（メタデータ） (2025-08-29T06:00:29Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Complexity for one-dimensional discrete time quantum walk circuits [0.0]
  1次元離散時間量子ウォーク(DTQW)から導かれる混合状態密度演算子の複雑性を計算する。 この複雑さは、混合状態の正準浄化から得られる2量子ビット量子回路を用いて計算される。
  論文  参考訳（メタデータ） (2023-07-25T12:25:03Z)
• Universal qudit gate synthesis for transmons [44.22241766275732]
  超伝導量子プロセッサを設計する。 本稿では,2量子共振共振ゲートを備えたユニバーサルゲートセットを提案する。 ノイズの多い量子ハードウェアのための$rm SU(16)$ゲートの合成を数値的に実証する。
  論文  参考訳（メタデータ） (2022-12-08T18:59:53Z)
• Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation [0.0]
  量子回路上でCNOTをルーティングするアルゴリズムPermRowColを提案する。 計算中に論理量子ビットを動的に再マップし、その結果、Steiner-Gauss や RowCol よりも出力 CNOT が少ない。
  論文  参考訳（メタデータ） (2022-05-02T08:20:13Z)
• Efficient multi-qubit subspace rotations via topological quantum walks [1.0486921990935787]
  選択された角度による部分空間の回転は、基本的な量子コンピューティングの演算である。 本稿では,位相量子ウォークを用いた高速かつ高忠実な計算手法を提案する。 この手順は、超伝導量子ビット、イオントラップ、リドベルク原子に星型接続で実装することができる。
  論文  参考訳（メタデータ） (2021-11-12T02:10:56Z)

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

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