論文の概要: Not All SWAPs Have the Same Cost: A Case for Optimization-Aware Qubit Routing

• arxiv url: http://arxiv.org/abs/2205.10596v1
• Date: Sat, 21 May 2022 13:36:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-12 05:27:19.315486
• Title: Not All SWAPs Have the Same Cost: A Case for Optimization-Aware Qubit Routing
• Title（参考訳）: SWAPのコストが同じとは限らない:最適化対応のクビットルーティングの場合
• Authors: Ji Liu, Peiyi Li, Huiyang Zhou
• Abstract要約: NISQ量子コンピュータと比較的長期のスケーラブルな量子アーキテクチャは完全な接続を提供していない。 量子コンパイラは、回路をデバイスレイアウトと互換性を持たせるために、キュービットルーティングを実行する必要がある。 本稿では、上記の量子ビットルーティングが最適ではないことを観察し、その後のゲート最適化では、キュービットルーティングはテキスト化されないようにすべきである。
• 参考スコア（独自算出の注目度）: 15.018468499770242
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite rapid advances in quantum computing technologies, the qubit connectivity limitation remains to be a critical challenge. Both near-term NISQ quantum computers and relatively long-term scalable quantum architectures do not offer full connectivity. As a result, quantum circuits may not be directly executed on quantum hardware, and a quantum compiler needs to perform qubit routing to make the circuit compatible with the device layout. During the qubit routing step, the compiler inserts SWAP gates and performs circuit transformations. Given the connectivity topology of the target hardware, there are typically multiple qubit routing candidates. The state-of-the-art compilers use a cost function to evaluate the number of SWAP gates for different routes and then select the one with the minimum number of SWAP gates. After qubit routing, the quantum compiler performs gate optimizations upon the circuit with the newly inserted SWAP gates. In this paper, we observe that the aforementioned qubit routing is not optimal, and qubit routing should \textit{not} be independent on subsequent gate optimizations. We find that with the consideration of gate optimizations, not all of the SWAP gates have the same basis-gate cost. These insights lead to the development of our qubit routing algorithm, NASSC (Not All Swaps have the Same Cost). NASSC is the first algorithm that considers the subsequent optimizations during the routing step. Our optimization-aware qubit routing leads to better routing decisions and benefits subsequent optimizations. We also propose a new optimization-aware decomposition for the inserted SWAP gates. Our experiments show that the routing overhead compiled with our routing algorithm is reduced by up to $69.30\%$ ($21.30\%$ on average) in the number of CNOT gates and up to $43.50\%$ ($7.61\%$ on average) in the circuit depth compared with the state-of-the-art scheme, SABRE.
• Abstract（参考訳）: 量子コンピューティング技術の急速な進歩にもかかわらず、量子ビット接続制限は依然として重要な課題である。 NISQ量子コンピュータと比較的長期のスケーラブルな量子アーキテクチャの両方が完全な接続を提供していない。 その結果、量子回路は量子ハードウェア上で直接実行されることはなく、量子コンパイラはデバイスレイアウトと互換性を持たせるために量子ビットルーティングを実行する必要がある。 キュービットルーティングステップの間、コンパイラはSWAPゲートを挿入し、回路変換を行う。 ターゲットハードウェアの接続トポロジを考えると、一般的に複数のqubitルーティング候補が存在する。 最先端のコンパイラはコスト関数を使用して、異なるルートのSWAPゲートの数を評価し、最小数のSWAPゲートを選択する。 キュービットルーティング後、量子コンパイラは新たに挿入されたSWAPゲートで回路上でゲート最適化を行う。 本稿では,前述のqubitルーティングが最適ではないこと,およびqubitルーティングがその後のゲート最適化に依存しないことを観察する。 ゲート最適化を考えると、全てのスワップゲートが同じ基底ゲートコストを持つわけではないことが分かる。 これらの知見は、我々のキュービットルーティングアルゴリズムであるNASC(Not All Swaps have the Same Cost)の開発につながります。 NASSCはルーティングステップにおけるその後の最適化を検討する最初のアルゴリズムである。 我々の最適化対応キュービットルーティングは、より良いルーティング決定とその後の最適化の恩恵をもたらす。 また,挿入スワップゲートに対する新しい最適化・アウェア分解法を提案する。 私たちの実験では、ルーティングアルゴリズムでコンパイルされたルーティングのオーバーヘッドは、cnotゲート数で最大69.30\%$ (平均で21.30\%$)、回路深さで$43.50\%$ (平均で7.61\%$$) に減少することが示されています。

関連論文リスト

• LightSABRE: A Lightweight and Enhanced SABRE Algorithm [39.814077130655505]
  我々は,実行効率と回路品質の両方を向上するSABREアルゴリズムの大幅な拡張であるLightSABREを紹介する。 我々は,Qiskit 1.2.0のアルゴリズムのバージョンを,Qiskit 0.20.1の実装の約200倍の速度で実現した。
  論文  参考訳（メタデータ） (2024-09-12T19:19:59Z)
• SWAP-less Implementation of Quantum Algorithms [0.0]
  本稿では,接続性に制限のあるデバイスにアルゴリズムを実装するために,パリティ量子情報のフローを追跡するフォーマリズムを提案する。 我々は、エンタングゲートが量子状態を操作するだけでなく、量子情報の伝達にも活用できるという事実を活用している。
  論文  参考訳（メタデータ） (2024-08-20T14:51:00Z)
• Route-Forcing: Scalable Quantum Circuit Mapping for Scalable Quantum Computing Architectures [41.39072840772559]
  Route-Forcingは量子回路マッピングアルゴリズムで、平均スピードアップが3.7Times$であることを示している。 本稿では、最先端のスケーラブルな手法と比較して平均3.7倍の高速化を示す量子回路マッピングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-24T14:21:41Z)
• Improved Qubit Routing for QAOA Circuits [0.0]
  我々はQuantum Approximate Optimization Algorithm (QAOA)のための古典的な実行時間付きキュービットルーティングアルゴリズムを開発した。 提案手法では,QAOA回路とErd"os-Renyi問題グラフを最大$N leq 400$で定義する。
  論文  参考訳（メタデータ） (2023-12-26T10:26:10Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• Universal qudit gate synthesis for transmons [44.22241766275732]
  超伝導量子プロセッサを設計する。 本稿では,2量子共振共振ゲートを備えたユニバーサルゲートセットを提案する。 ノイズの多い量子ハードウェアのための$rm SU(16)$ゲートの合成を数値的に実証する。
  論文  参考訳（メタデータ） (2022-12-08T18:59:53Z)
• Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits [11.391158217994782]
  Duostraは、実際のハードウェアデバイスで大規模量子回路を実装するという課題に対処するために設計されている。 ダブルキュービットゲートの最適経路を効率よく決定し、SWAPゲートを挿入することで動作する。 合理的なランタイム内で、良質な結果が得られます。
  論文  参考訳（メタデータ） (2022-10-04T01:47:11Z)
• Purification and Entanglement Routing on Quantum Networks [55.41644538483948]
  不完全なチャネルフィリティと限られたメモリ記憶時間を備えた量子ネットワークは、ユーザ間の絡み合いを分散することができる。 本稿では,量子ネットワーク上の2ノード間で共有される絡み合いを最大化するための高速パスフィニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-23T19:00:01Z)
• Using Reinforcement Learning to Perform Qubit Routing in Quantum Compilers [0.0]
  深層Q-ラーニングパラダイムの修正版を用いたキュービットルーティング手法を提案する。 このシステムは、現在利用可能な最も先進的な量子コンパイラの2つから、キュービットルーティング手順を上回ります。
  論文  参考訳（メタデータ） (2020-07-31T10:57:24Z)
• 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)

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

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