論文の概要: A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates

• arxiv url: http://arxiv.org/abs/2212.05666v2
• Date: Sun, 30 Jul 2023 10:22:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-02 00:06:46.308313
• Title: A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates
• Title（参考訳）: 通勤ゲートのSWAPゲート挿入における初期写像問題に対するSATアプローチ
• Authors: Atsushi Matsuo, Shigeru Yamashita, Daniel J. Egger
• Abstract要約: ほとんどの量子回路は、量子ビット接続が制限された量子ハードウェア上で動作するためにSWAPゲート挿入を必要とする。 スワップ戦略に対する優れた初期マッピングは、必要なスワップゲートの数を減らす。 本稿では,通信ゲートをハードウェアにトランスパイルした回路に対して,SATを用いた優れた初期写像を求める手法を提案する。
• 参考スコア（独自算出の注目度）: 0.8057006406834467
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.
• Abstract（参考訳）: ほとんどの量子回路は、量子ハードウェア上で量子ビット接続に制限のあるSWAPゲート挿入を必要とする。 2ビットゲートを交換するブロックに対する有望なSWAPゲート挿入方法は、結合マップ上で同時に実行可能なSWAPゲートの層を適用した所定のスワップ戦略である。 スワップ戦略に対する優れた初期マッピングは、必要なスワップゲートの数を減らす。 しかし、量子近似最適化アルゴリズム(QAOA)やイジン・ハミルトニアンのトロッター化シミュレーションのように、回路が通勤ゲートで構成されている場合でも、よい初期写像を見つけることは難しい問題である。 そこで本研究では,スワップ戦略を応用したコンミューティングゲートをハードウェアにトランスパイアした回路の初期マッピングをsatで求める手法を提案する。 この手法は500ノードのランダムな3正則グラフに対するゲート数を65%削減する。 さらに,SATの定式化とクラスタリングアルゴリズムを組み合わせたヒューリスティックな手法を提案する。 このアプローチは、1000ノードのランダムな3正則グラフの自明な初期マッピングとランダムな初期マッピングの両方と比較して、スワップ層数を25%削減する。 良い初期写像は、数百の量子ビットを持つノイズの多い量子ハードウェア上で、スパース問題に適用されたQAOAやIsing Hamiltonianシミュレーションのような量子アルゴリズムの研究を可能にする。

関連論文リスト

• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT回路は一般的な量子回路の共通構成ブロックである。 本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。 シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
  論文  参考訳（メタデータ） (2024-08-07T19:51:22Z)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  CFD問題を解決するための現在の量子アルゴリズムは、単一の量子回路と、場合によっては格子ベースの方法を用いる。 量子格子ボルツマン法(QLBM)を用いた新しい多重回路アルゴリズムを提案する。 この問題は2次元ナビエ・ストークス方程式の流動関数-渦性定式化として鋳造され、2次元蓋駆動キャビティフローで検証および試験された。
  論文  参考訳（メタデータ） (2024-01-20T15:32:01Z)
• Tackling the Qubit Mapping Problem with Permutation-Aware Synthesis [9.885057869188087]
  本稿では,新しい階層型量子ビットマッピングとルーティングアルゴリズムを提案する。 第2段階の置換認識合成(PAS)では、各ブロックを最適化し、分離して合成する。 第3段階では、置換対応マッピング(PAM)アルゴリズムが第2段階の情報に基づいてブロックをターゲットデバイスにマッピングする。
  論文  参考訳（メタデータ） (2023-05-04T15:39:54Z)
• High-fidelity parallel entangling gates on a neutral atom quantum computer [41.74498230885008]
  最大60個の原子に99.5%の忠実度を持つ2量子エンタングリングゲートの実現を報告した。 これらの進歩は、量子アルゴリズム、誤り訂正回路、デジタルシミュレーションの大規模実装の基礎となった。
  論文  参考訳（メタデータ） (2023-04-11T18:00:04Z)
• Wide Quantum Circuit Optimization with Topology Aware Synthesis [0.8469686352132708]
  ユニタリ合成は、量子回路を制限的量子ビット位相にマッピングしながら最適なマルチキュービットゲート数を達成する最適化手法である。 我々は,emphBQSKitフレームワークで構築されたトポロジ対応合成ツールであるTopASを紹介した。
  論文  参考訳（メタデータ） (2022-06-27T21:59:30Z)
• Efficient variational synthesis of quantum circuits with coherent multi-start optimization [1.3108652488669734]
  我々は、CNOTゲートと任意の1量子ビット(1q)ゲートからなるゲート集合に合成する問題を考察する。 私たちが提案する重要なアイデアは、IDゲートとCNOTゲートの間を補間できるパラメタライズされた2量子ビット(2q)位相ゲートを使用することである。 このアーキテクチャの一貫性のある最適化と1qゲートは、実際驚くほどうまく機能しているようだ。
  論文  参考訳（メタデータ） (2022-05-02T18:00:03Z)
• Software mitigation of coherent two-qubit gate errors [55.878249096379804]
  2量子ゲートは量子コンピューティングの重要な構成要素である。 しかし、量子ビット間の不要な相互作用(いわゆる寄生ゲート)は、量子アプリケーションの性能を低下させる。 寄生性2ビットゲート誤差を軽減するための2つのソフトウェア手法を提案する。
  論文  参考訳（メタデータ） (2021-11-08T17:37:27Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。 量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。 提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
  論文  参考訳（メタデータ） (2021-06-06T13:15:25Z)
• 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)
• Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search [5.980663391414905]
  論理量子回路をNISQ(Noisy Intermediate-Scale Quantum)デバイスにマッピングすることは難しい問題である。 本稿では,NISQ デバイスアーキテクチャグラフと入力論理回路によって誘導されるグラフとの類似性を考慮した初期写像を選択することで,効率的な手法を提案する。 提案した回路変換アルゴリズムは、論理回路に追加するために必要な補助的な2ビットゲートの数を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-04-15T15:07:49Z)

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

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