論文の概要: Algorithmic Theory of Qubit Routing
- arxiv url: http://arxiv.org/abs/2305.02059v1
- Date: Wed, 3 May 2023 12:02:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-04 15:04:51.111816
- Title: Algorithmic Theory of Qubit Routing
- Title（参考訳）: 量子ビットルーティングのアルゴリズム理論
- Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi,
Yoshio Okamoto
- Abstract要約: 本稿では,理論計算機科学の観点から,量子ビットルーティング問題について考察する。
量子ビットルーティング問題はNPハードであることを証明する。
各キュービットが少なくとも1つの2キュービットゲートに関与している場合、最小化時間アルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 4.316090167342715
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The qubit routing problem, also known as the swap minimization problem, is a
(classical) combinatorial optimization problem that arises in the design of
compilers of quantum programs. We study the qubit routing problem from the
viewpoint of theoretical computer science, while most of the existing studies
investigated the practical aspects. We concentrate on the linear nearest
neighbor (LNN) architectures of quantum computers, in which the graph topology
is a path. Our results are three-fold. (1) We prove that the qubit routing
problem is NP-hard. (2) We give a fixed-parameter algorithm when the number of
two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when
each qubit is involved in at most one two-qubit gate.
- Abstract（参考訳）: 量子ビットルーティング問題(qubit routing problem)またはスワップ最小化問題(swap minimization problem)は、量子プログラムのコンパイラの設計において生じる(古典的な)組合せ最適化問題である。
理論計算機科学の立場から量子経路問題を研究する一方,既存の研究の多くは実用的側面を考察している。
我々は、グラフトポロジが経路である量子コンピュータの線形近接アーキテクチャ(LNN)に集中する。
私たちの結果は3倍です。
1) 量子ビットルーティング問題はNPハードであることを証明する。
2) 2量子ゲートの数がパラメータである場合,固定パラメータアルゴリズムを提案する。
(3) 各キュービットが少なくとも1つの2量子ビットゲートに関与している場合に多項式時間アルゴリズムを与える。
関連論文リスト
- Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
トラベルセールスマン問題(TSP)はNP-ハード組合せ最適化問題として人気がある。
本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。
我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
論文 参考訳（メタデータ） (2024-07-24T12:06:37Z) - Full Characterization of the Depth Overhead for Quantum Circuit
Compilation with Arbitrary Qubit Connectivity Constraint [6.799314463590596]
量子コンピュータのいくつかの物理的実装では、2量子ビット演算は特定の量子ビットのペアにのみ適用できる。
本稿では、基礎となる制約グラフのルーティング数によって、深さオーバーヘッドを完全に特徴づける。
論文 参考訳（メタデータ） (2024-02-04T08:29:41Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - 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) - Improving Quantum Computation by Optimized Qubit Routing [0.0]
スワップ挿入による量子ビットルーティングのための高品質な分解手法を提案する。
この最適化問題は、特定の量子ハードウェアに量子アルゴリズムをコンパイルする文脈で発生する。
本稿では,統合割当問題とトークンスワップ問題に対する数値計算結果について述べる。
論文 参考訳（メタデータ） (2022-06-02T20:32:18Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。
この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。
GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
論文 参考訳（メタデータ） (2022-04-18T21:45:13Z) - Locality-aware Qubit Routing for the Grid Architecture [1.4459640831465588]
本稿では,グラフ理論に基づく局所性を考慮した量子ビットルーティングアルゴリズムを提案する。
我々のアルゴリズムはグリッドとある種の"グリッドのような"アーキテクチャのために設計されている。
論文 参考訳（メタデータ） (2022-03-21T20:46:39Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - Optimal qubit assignment and routing via integer programming [0.22940141855172028]
論理量子回路を2ビット接続に制限のあるハードウェアにマッピングする問題を考察する。
我々はこの問題を2変数のネットワークフロー定式化を用いて整数線形プログラムとしてモデル化する。
本稿では,回路の忠実度,全深度,クロストークの尺度などのコスト関数について考察する。
論文 参考訳（メタデータ） (2021-06-11T15:02:26Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。