論文の概要: Parallel Token Swapping for Qubit Routing
- arxiv url: http://arxiv.org/abs/2411.18581v1
- Date: Wed, 27 Nov 2024 18:26:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-28 15:25:05.848106
- Title: Parallel Token Swapping for Qubit Routing
- Title（参考訳）: ビットルーティングのための並列トークンスワッピング
- Authors: Ishan Bansal, Oktay Günlük, Richard Shapley,
- Abstract要約: 現代の量子コンピュータでよく見られるグラフトポロジ上の並列トークンスワップ問題に対する最初の定数係数近似アルゴリズムを提供する。
また、量子ビットルーティング問題に対する再構成を設計する際に有用であることが示されている自然下界のいわゆる伸張係数についても検討した。
- 参考スコア（独自算出の注目度）: 2.280359339174839
- License:
- Abstract: In this paper we study a combinatorial reconfiguration problem that involves finding an optimal sequence of swaps to move an initial configuration of tokens that are placed on the vertices of a graph to a final desired one. This problem arises as a crucial step in reducing the depth of a quantum circuit when compiling a quantum algorithm. We provide the first known constant factor approximation algorithms for the parallel token swapping problem on graph topologies that are commonly found in modern quantum computers, including cycle graphs, subdivided star graphs, and grid graphs. We also study the so-called stretch factor of a natural lower bound to the problem, which has been shown to be useful when designing heuristics for the qubit routing problem. Finally, we study the colored version of this reconfiguration problem where some tokens share the same color and are considered indistinguishable.
- Abstract（参考訳）: 本稿では,グラフの頂点に置かれるトークンの初期構成を,最終的な所望のものに移動させるために,スワップの最適シーケンスを見つけることを伴う組合せ再構成問題について検討する。
この問題は、量子アルゴリズムをコンパイルする際の量子回路の深さを減らすための重要なステップとして生じる。
我々は、現代の量子コンピュータでよく見られるグラフトポロジ上の並列トークンスワップ問題に対して、サイクルグラフ、分割されたスターグラフ、グリッドグラフに対する最初の定数係数近似アルゴリズムを提供する。
また、量子ビットルーティング問題に対するヒューリスティックスの設計において有用であることが示されている自然下界のいわゆる伸張係数についても検討した。
最後に、いくつかのトークンが同じ色を共有しており、区別できないと考えられる、この再構成問題のカラーバージョンについて検討する。
関連論文リスト
- The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
グラフ同型問題のノイズバージョンは、エッジの大部分を保存する2つのグラフのノード間のマッチングを見つけることを目的としている。
この論文は、この問題の基本的な情報理論的限界を理解すること、および、基礎となるデータのアライメントを回復できるアルゴリズムを設計および分析することに焦点を当てている。
論文 参考訳（メタデータ） (2024-04-18T15:31:13Z) - Full Characterization of the Depth Overhead for Quantum Circuit
Compilation with Arbitrary Qubit Connectivity Constraint [6.799314463590596]
量子コンピュータのいくつかの物理的実装では、2量子ビット演算は特定の量子ビットのペアにのみ適用できる。
本稿では、基礎となる制約グラフのルーティング数によって、深さオーバーヘッドを完全に特徴づける。
論文 参考訳（メタデータ） (2024-02-04T08:29:41Z) - Discrete Graph Auto-Encoder [52.50288418639075]
離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。
まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。
2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
論文 参考訳（メタデータ） (2023-06-13T12:40:39Z) - Algorithmic Theory of Qubit Routing [4.316090167342715]
本稿では,理論計算機科学の観点から,量子ビットルーティング問題について考察する。
量子ビットルーティング問題はNPハードであることを証明する。
各キュービットが少なくとも1つの2キュービットゲートに関与している場合、最小化時間アルゴリズムを与える。
論文 参考訳（メタデータ） (2023-05-03T12:02:40Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Parallelization techniques for quantum simulation of fermionic systems [0.0]
フェルミオン作用素を量子ビット作用素にマッピングすることは、量子コンピュータ上でフェルミオン系をシミュレートするための重要なステップである。
このような写像の選択が量子プロセッサの量子ビット接続とどのように相互作用するかを検討する。
論文 参考訳（メタデータ） (2022-07-25T18:41:59Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳（メタデータ） (2022-07-13T18:12:36Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。
この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。
GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
論文 参考訳（メタデータ） (2022-04-18T21:45:13Z) - From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。
本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。
今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
論文 参考訳（メタデータ） (2022-02-19T02:56:47Z) - Quantum Optimization for the Graph Coloring Problem with Space-Efficient
Embedding [0.0]
グラフ彩色問題に対する空間効率のよい量子最適化アルゴリズムを提案する。
我々の回路は標準的アプローチよりも深い。
現在利用可能な代替品を探索するために、量子アニール上でランダムなグラフ色付けの研究を行う。
論文 参考訳（メタデータ） (2020-09-15T18:34:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。