論文の概要: 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シミュレーションのような量子アルゴリズムの研究を可能にする。
関連論文リスト
- HAIL: An Efficient Iterative Algorithm for Qubit Mapping via Layer-Weight Assignment and Search Space Reduction [7.698997402561804]
現在の量子デバイスは物理的量子ビットと限られた数の隣接する量子ビット間の相互作用しかサポートしていない。
回路を実行するには、キュービット間のマッピング関係を調整するためにSWAPゲートを挿入する必要がある。
本稿では,新たなSWAPゲートを最小化するための効率的な反復量子ビットマッピングアルゴリズムであるHAILを提案する。
論文 参考訳(メタデータ) (2025-02-11T13:21:33Z) - Quantum circuit synthesis with SQiSW [10.12389814746236]
iSWAPゲートの平方根としても知られるSQiSWゲートは、優れた実験性能のためにかなりの注目を集めている。
本研究では,8つのSQiSWゲートのみを用いたトフォリゲートの正確な合成手法を提案する。
論文 参考訳(メタデータ) (2024-12-19T13:17:43Z) - Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
CNOT回路は一般的な量子回路の共通構成ブロックである。
本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。
シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
論文 参考訳(メタデータ) (2024-08-07T19:51:22Z) - Route-Forcing: Scalable Quantum Circuit Mapping for Scalable Quantum Computing Architectures [41.39072840772559]
Route-Forcingは量子回路マッピングアルゴリズムで、平均スピードアップが3.7Times$であることを示している。
本稿では、最先端のスケーラブルな手法と比較して平均3.7倍の高速化を示す量子回路マッピングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-07-24T14:21:41Z) - 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) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。