論文の概要: An Exact Branch and Bound Algorithm for the generalized Qubit Mapping Problem

• arxiv url: http://arxiv.org/abs/2508.21718v1
• Date: Fri, 29 Aug 2025 15:35:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-01 19:45:11.097873
• Title: An Exact Branch and Bound Algorithm for the generalized Qubit Mapping Problem
• Title（参考訳）: 一般化されたビットマッピング問題に対する排他的分岐と境界アルゴリズム
• Authors: Bjørnar Luteberget, Kjell Fredrik Pettersen, Giorgio Sartor, Franz G. Fuchs, Dominik Leib, Tobias Seidel, Raoul Heese,
• Abstract要約: 量子回路は通常、一組の仮想量子ビット上のゲートの(順序付けられた)シーケンスで表される。 Qubit Mapping Problem (QMP) はNPハードであることが知られている。 一般化されたQMPに対するフレキシブル分岐およびバウンドアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Quantum circuits are typically represented by a (ordered) sequence of gates over a set of virtual qubits. During compilation, the virtual qubits of the gates are assigned to the physical qubits of the underlying quantum hardware, a step often referred to as the qubit assignment problem. To ensure that the resulting circuit respects hardware connectivity constraints, additional SWAP gates are inserted as needed, which is known as the qubit routing problem. Together, they are called the Qubit Mapping Problem (QMP), which is known to be NP-hard. A very common way to deal with the complexity of the QMP is to partition the sequence of gates into a sequence of gate groups (or layers). However, this imposes a couple of important restrictions: (1) SWAP gates can only be added between pairs of consecutive groups, and (2) all the gates belonging to a certain group have to be executed (in parallel) in the same time slot. The first one prevents gates to be re-arranged optimally, while the second one imposes a time discretization that practically ignores gate execution time. While this clearly reduces the size of the feasible space, little is still known about how much is actually lost by imposing a fixed layering when looking at the minimization of either the number of SWAPs or the makespan of the compiled circuit. In this paper, we present a flexible branch and bound algorithm for a generalized version of the QMP that either considers or ignores the gate layering and the gate execution time. The algorithm can find find proven optimal solutions for all variations of the QMP, but also offers a great platform for different heuristic algorithms. We present results on several benchmark sets of small quantum circuits, and we show how ignoring the layering can significantly improve some key performance indicators of the compiled circuit.
• Abstract（参考訳）: 量子回路は通常、一組の仮想量子ビット上のゲートの(順序付けられた)シーケンスで表される。 コンパイル中、ゲートの仮想量子ビットは、基礎となる量子ハードウェアの物理量子ビットに割り当てられる。 結果の回路がハードウェア接続制約を遵守することを保証するため、追加のSWAPゲートを必要に応じて挿入し、キュービットルーティング問題(qubit routing problem)と呼ばれる。 共にQubit Mapping Problem (QMP) と呼ばれ、NP-hardとして知られている。 QMPの複雑さに対処する非常に一般的な方法は、ゲートの列をゲート群(または層)の列に分割することである。 しかし、これはいくつかの重要な制限を課している: (1) SWAPゲートは連続したグループのペア間でのみ追加することができ、(2) あるグループに属するすべてのゲートは、同じタイムスロットで(並行して)実行されなければならない。 第1は、ゲートが最適に配置されるのを防止し、第2は、ゲート実行時間を実質的に無視する時間離散化を課す。 これにより、実現可能な空間のサイズは明らかに縮小されるが、SWAPの数の最小化やコンパイルされた回路のメースパンの最小化を見る際に、固定層を配置することで、実際にどれだけの損失が生じるかは、いまだに分かっていない。 本稿では,ゲート層やゲート実行時間を考慮または無視する汎用バージョンのQMPに対して,フレキシブル分岐およびバウンドアルゴリズムを提案する。 このアルゴリズムは、QMPのすべてのバリエーションに対して証明された最適解を見つけることができるが、異なるヒューリスティックアルゴリズムのための優れたプラットフォームを提供する。 そこで本研究では,いくつかの小量子回路のベンチマークセットに対して,階層化を無視することで,コンパイルされた回路の重要な性能指標が大幅に向上することを示す。

関連論文リスト

• Accelerating Transpilation in Quantum Machine Learning with Haiqu's Rivet-transpiler [45.88028371034407]
  我々は、以前にトランスパイルされた回路を再利用してトランスパイラを高速化するリベットトランスパイラを開発した。 量子層学習において,600%のトランスパイル時間の改善を実証した。
  論文  参考訳（メタデータ） (2025-08-29T06:00:29Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [44.99833362998488]
  我々は、イオントラップハードウェアに存在するGlobal Molmer-Sorensenゲートのようなグローバルな相互作用を用いて量子回路を最適化し、合成する。 このアルゴリズムはZX計算に基づいており、係留ゲートをGlobal MolmerSorensenゲートにグループ化する特別な回路抽出ルーチンを使用する。 我々は,このアルゴリズムを様々な回路でベンチマークし,最新ハードウェアによる性能向上の方法を示す。
  論文  参考訳（メタデータ） (2025-07-28T10:25:31Z)
• An Efficient Iterative Algorithm for Qubit Mapping via Layer-Weight Assignment and Search Space Reduction [7.698997402561804]
  現在の量子デバイスは物理的に隣接する量子ビット間の相互作用のみをサポートし、これらのデバイス上で量子回路が直接実行されるのを防ぐ。 SWAP ゲートの追加を最小化するために,効率的な反復量子ビットマッピングアルゴリズム HAIL を提案する。 HAIL-3は、最先端のアルゴリズムと比較して、$mathcalB_23$に挿入される追加ゲート数を20.62%削減することを示す。
  論文  参考訳（メタデータ） (2025-02-11T13:21:33Z)
• Efficient compilation of quantum circuits using multi-qubit gates [0.0]
  本稿では,Ising型,長距離,マルチキュービット・エンタングリングゲートのシーケンスに一般回路分解を実装したコンパイル方式を提案する。 我々は,2量子ゲートを用いた従来の実現法と比較して,量子ボリュームの対数関係を20%$から25%$に改善することを示した。
  論文  参考訳（メタデータ） (2025-01-28T19:08:13Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  量子格子ボルツマン法(QLBM)における非圧縮性ナビエ-ストークス方程式の多重回路アルゴリズムを提案する。 提案法は2次元蓋駆動キャビティフローに対して検証および実証を行った。
  論文  参考訳（メタデータ） (2024-01-20T15:32:01Z)
• One Gate Scheme to Rule Them All: Introducing a Complex Yet Reduced Instruction Set for Quantum Computing [8.478982715648547]
  $XX+YY$結合を持つキュービットのスキームは、単一キュービットゲートまでの任意の2キュービットゲートを実現する。 一般的な$n$-qubitゲート合成、量子ボリューム、キュービットルーティングなど、様々な応用において顕著な改善が見られた。
  論文  参考訳（メタデータ） (2023-12-09T19:30:31Z)
• Software mitigation of coherent two-qubit gate errors [55.878249096379804]
  2量子ゲートは量子コンピューティングの重要な構成要素である。 しかし、量子ビット間の不要な相互作用(いわゆる寄生ゲート)は、量子アプリケーションの性能を低下させる。 寄生性2ビットゲート誤差を軽減するための2つのソフトウェア手法を提案する。
  論文  参考訳（メタデータ） (2021-11-08T17:37:27Z)
• Quantum Compiling by Deep Reinforcement Learning [30.189226681406392]
  回路量子コンピュータのアーキテクチャは、高レベルな量子アルゴリズムを量子ゲートの低レベルな回路にコンパイルするための層を必要とする。 量子コンパイルの一般的な問題は、量子計算を記述する任意のユニタリ変換を、普遍的な量子ゲートの有限基底から選択された要素の列として近似することである。 我々は,探索時間と搾取時間とのトレードオフが著しく異なる,より深い強化学習手法を代替戦略として活用する。
  論文  参考訳（メタデータ） (2021-05-31T15:32:15Z)
• 2D Qubit Placement of Quantum Circuits using LONGPATH [1.6631602844999722]
  任意の量子回路におけるSWAPゲートの数を最適化する2つのアルゴリズムが提案されている。 提案手法は1Dおよび2D NTCアーキテクチャにおけるSWAPゲート数を大幅に削減する。
  論文  参考訳（メタデータ） (2020-07-14T04:09:52Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)

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

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