論文の概要: Linear Circuit Synthesis using Weighted Steiner Trees
- arxiv url: http://arxiv.org/abs/2408.04060v1
- Date: Wed, 7 Aug 2024 19:51:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-09 17:20:07.275769
- Title: Linear Circuit Synthesis using Weighted Steiner Trees
- Title(参考訳): 重み付きステイナツリーを用いた線形回路合成
- Authors: Nir Gavrielov, Alexander Ivrii, Shelly Garion,
- Abstract要約: CNOT回路は一般的な量子回路の共通構成ブロックである。
本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。
シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
- 参考スコア(独自算出の注目度): 45.11082946405984
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: CNOT circuits are a common building block of general quantum circuits. The problem of synthesizing and optimizing such circuits has received a lot of attention in the quantum computing literature. This problem is especially challenging for quantum devices with restricted connectivity, where two-qubit gates can only be placed between adjacent qubits. The state-of-the-art algorithms for optimizing the number of CNOT gates are heuristic algorithms that are based on Gaussian elimination and that use Steiner trees to connect between different subsets of qubits. In this article, we suggest considering weighted Steiner trees, and we present a simple low-cost heuristic to compute weights. The simulated evaluation shows that the suggested heuristic is almost always beneficial and reduces the number of CNOT gates by up to 10%.
- Abstract(参考訳): CNOT回路は一般的な量子回路の共通構成ブロックである。
このような回路の合成と最適化の問題は、量子コンピューティングの文献で注目されている。
この問題は、隣接する量子ビット間にのみ2量子ビットゲートを配置できるような、接続が制限された量子デバイスにとって特に困難である。
CNOTゲートの数を最適化する最先端のアルゴリズムはガウス除去に基づくヒューリスティックアルゴリズムであり、異なるキュービットのサブセット間の接続にSteiner木を用いる。
本稿では,重み付きSteiner木について検討し,重みを計算するための簡易な低コストヒューリスティックを提案する。
シミュレーションにより,提案したヒューリスティックがほぼ常に有用であることが示され,CNOTゲートの数が最大10%削減された。
関連論文リスト
- Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳(メタデータ) (2023-04-06T02:18:52Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳(メタデータ) (2022-09-08T17:55:30Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳(メタデータ) (2022-07-07T08:04:15Z) - Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum
Compilation [0.0]
量子回路上でCNOTをルーティングするアルゴリズムPermRowColを提案する。
計算中に論理量子ビットを動的に再マップし、その結果、Steiner-Gauss や RowCol よりも出力 CNOT が少ない。
論文 参考訳(メタデータ) (2022-05-02T08:20:13Z) - Approaching the theoretical limit in quantum gate decomposition [0.0]
本稿では,CNOT$ゲート数を持つ1量子および2量子ビットの量子ゲートを用いて,一般量子プログラムを分解する新しい数値計算手法を提案する。
本手法は, 既設計量子回路における単一量子ビット回転ゲートに関するパラメータの逐次最適化に基づく。
論文 参考訳(メタデータ) (2021-09-14T15:36:22Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。
我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。
提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
論文 参考訳(メタデータ) (2021-08-06T19:38:03Z) - Reducing the CNOT count for Clifford+T circuits on NISQ architectures [6.964575422457177]
物理量子ビットの接続性は、CNOTのような2量子演算を「連結」量子ビットに制限する制約の1つである。
本稿では,接続制約アーキテクチャ上でのClifford+T回路におけるCNOT数削減の問題について考察する。
我々は、アダマール門の位置で回路を「スライス」し、ステイナー木を用いて中間のCNOT,Tサブ回路を「構築」する。
論文 参考訳(メタデータ) (2020-11-24T16:35:05Z) - Efficient CNOT Synthesis for NISQ Devices [1.0152838128195467]
ノイズの多い中間スケール量子(NISQ)の時代、実際の量子デバイス上で量子アルゴリズムを実行することは、ユニークな課題に直面している。
この問題を解決するために,トークン還元法と呼ばれるCNOT合成法を提案する。
我々のアルゴリズムは、テストされた全ての量子アーキテクチャにおいて、最も広くアクセス可能なアルゴリズムよりも一貫して優れています。
論文 参考訳(メタデータ) (2020-11-12T15:13:32Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。