論文の概要: The Complexity of Quantum Circuit Mapping with Fixed Parameters

• arxiv url: http://arxiv.org/abs/2207.08438v1
• Date: Mon, 18 Jul 2022 08:44:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-04 15:58:04.242560
• Title: The Complexity of Quantum Circuit Mapping with Fixed Parameters
• Title（参考訳）: 固定パラメータを用いた量子回路マッピングの複雑さ
• Authors: Pengcheng Zhu, Shenggen Zheng, Lihua Wei, Xueyun Cheng, Zhijin Guan, Shiguang Feng
• Abstract要約: NISQデバイスに実装する前に、量子回路を前処理しなければならない。 量子回路マッピングは、回路をNISQデバイスのアーキテクチャ制約に準拠した等価な回路に変換する。 我々は、QCMの正確なアルゴリズムを示し、NISQデバイスのアーキテクチャが修正された場合、そのアルゴリズムが時間内に実行されることを示す。
• 参考スコア（独自算出の注目度）: 4.716951747614208
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A quantum circuit must be preprocessed before implementing on NISQ devices due to the connectivity constraint. Quantum circuit mapping (QCM) transforms the circuit into an equivalent one that is compliant with the NISQ device's architecture constraint by adding SWAP gates. The QCM problem asks the minimal number of auxiliary SWAP gates, and is NP-complete. The complexity of QCM with fixed parameters is studied in the paper. We give an exact algorithm for QCM, and show that the algorithm runs in polynomial time if the NISQ device's architecture is fixed. If the number of qubits of the quantum circuit is fixed, we show that the QCM problem is NL-complete by a reduction from the undirected shortest path problem. Moreover, the fixed-parameter complexity of QCM is W[1]-hard when parameterized by the number of qubits of the quantum circuit. We prove the result by a reduction from the clique problem. If taking the depth of the quantum circuits and the coupling graphs as parameters, we show that the QCM problem is still NP-complete over shallow quantum circuits, and planar, bipartite and degree bounded coupling graphs.
• Abstract（参考訳）: 接続制約のため、NISQデバイスに実装する前に量子回路を前処理しなければならない。 量子回路マッピング(QCM)は、SWAPゲートを追加することで、NISQデバイスのアーキテクチャ制約に準拠する等価な回路に変換する。 QCM問題は、補助的なSWAPゲートの最小数を求め、NP完全である。 固定パラメータを持つqcmの複雑性について検討した。 qcmの正確なアルゴリズムを与え、nisqデバイスのアーキテクチャが固定された場合、アルゴリズムが多項式時間で実行されることを示す。 量子回路の量子ビット数が固定された場合、QCM問題は最短経路問題からの還元によりNL完全であることが示される。 さらに、量子回路の量子ビット数によってパラメータ化される場合、QCMの固定パラメータ複雑性はW[1]ハードとなる。 我々は、クライク問題からの削減によって結果を証明する。 量子回路と結合グラフの深さをパラメータとして考えると、qcm問題はまだ浅い量子回路上でnp完全であり、平面、双部、次数有界結合グラフであることを示す。

関連論文リスト

• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  超伝導プロセッサのための強化学習型量子コンパイラを開発した。 短絡の新規・ハードウェア対応回路の発見能力を示す。 本研究は,効率的な量子コンパイルのためのハードウェアによるソフトウェア設計を実証する。
  論文  参考訳（メタデータ） (2024-06-18T01:49:48Z)
• ISAAQ: Ising Machine Assisted Quantum Compiler [3.8137985834223502]
  我々はIsingマシンで量子ビットルーティングを行うためのISing mAchine Assisted Quantum compiler (ISAAQ)を提案する。 ISAAQは、以前のコンパイル結果を使って自分自身を更新することで、コンパイルコストを正確に見積もる。 ISAAQは、物理的に少ないCNOTゲートを持つ可換論理制御NOT(CNOT)ゲートを実装するコスト削減手法を利用する。
  論文  参考訳（メタデータ） (2023-03-06T01:47:10Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。 我々はQiskitでIQuCSを実装し、集中的な実験を行う。 その結果、量子ビットの消費を最大66.2%削減できることが示されている。
  論文  参考訳（メタデータ） (2022-09-22T21:54:28Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。 我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。 提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
  論文  参考訳（メタデータ） (2021-08-06T19:38:03Z)
• A Quantum Dot Plot Generation Algorithm for Pairwise Sequence Alignment [0.0]
  量子ペアワイズシーケンスアライメント(QPSA)アルゴリズムは、データアライメントタスクにおいて指数的なスピードアップを提供する。 これは、量子重ね合わせに整列する古典的なデータを効率的に符号化するというオープンな問題に依存している。 我々は、量子ドットプロット(QDP)と呼ばれる、このオラクルの代替的で明示的な構成を提供する。 我々はQDPの運用上の複雑さを、Q#とQiskitのソフトウェアフレームワークが生成する量子マシン命令の分析を通じて評価する。
  論文  参考訳（メタデータ） (2021-07-23T16:48:29Z)
• Variational Quantum Eigensolver with Reduced Circuit Complexity [3.1158760235626946]
  電子構造計算におけるVQEにおける量子回路の複雑性を低減するための新しい手法を提案する。 我々のアルゴリズムは、ClusterVQEと呼ばれ、初期量子ビット空間を、個々の量子回路にさらに分散したサブスペース(キュービットクラスタ)に分割する。 この新しいアルゴリズムは同時に量子ビット数と回路深度を減少させ、NISQデバイス上での量子化学シミュレーションの潜在的なリーダーとなる。
  論文  参考訳（メタデータ） (2021-06-14T17:23:46Z)
• Automatically Differentiable Quantum Circuit for Many-qubit State Preparation [1.5662820454886202]
  任意の量子数量子ビット状態を効率的に準備するための自動微分可能な量子回路(ADQC)アプローチを提案する。 この回路は、進化した状態と目標状態との間の距離を最小化するためにバック伝搬を用いて潜在ゲートを更新することで最適化される。 我々の研究は、機械学習手法と組み合わせることで、多量子ビットシステムにおける量子回路の「インテリジェントな構成」に光を当てている。
  論文  参考訳（メタデータ） (2021-04-30T12:22:26Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
  本稿では量子回路マッピングQXXとその機械学習バージョンQXX-MLPを紹介する。 後者は、レイアウトされた回路の深さが小さくなるように最適なQXXパラメータ値を自動的に推論する。 近似を用いてレイアウト法を学習可能な経験的証拠を提示する。
  論文  参考訳（メタデータ） (2020-07-29T05:26:19Z)
• Supervised Learning Using a Dressed Quantum Network with "Super Compressed Encoding": Algorithm and Quantum-Hardware-Based Implementation [7.599675376503671]
  ノイズのある中間量子(NISQ)デバイス上での変分量子機械学習(QML)アルゴリズムの実装には、必要となるキュービット数とマルチキュービットゲートに関連するノイズに関連する問題がある。 本稿では,これらの問題に対処するための量子ネットワークを用いた変分QMLアルゴリズムを提案する。 他の多くのQMLアルゴリズムとは異なり、我々の量子回路は単一量子ビットゲートのみで構成されており、ノイズに対して堅牢である。
  論文  参考訳（メタデータ） (2020-07-20T16:29:32Z)

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

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