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

• arxiv url: http://arxiv.org/abs/2603.21283v2
• Date: Thu, 26 Mar 2026 10:04:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-27 13:32:29.869567
• Title: A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation Oracle
• Title（参考訳）: ルート生成, コストフェーズ, 妥当性のあるOracleによる旅行セールスパーソンツアーの量子符号化
• Authors: Alexander Johannes Stasik, Franz Georg Fuchs,
• 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)やグローバーのアルゴリズムのような振幅増幅やスペクトルフィルタリング技術と互換性がある。 しかし、有効なツアーの指数的に少ないため、振幅増幅と組み合わせても全体的な複雑さは指数関数的のままである。

関連論文リスト

• 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)
• 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)

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

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