論文の概要: Qubit Mapping and Routing via MaxSAT

• arxiv url: http://arxiv.org/abs/2208.13679v1
• Date: Mon, 29 Aug 2022 15:39:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-28 14:44:41.992123
• Title: Qubit Mapping and Routing via MaxSAT
• Title（参考訳）: 量子マッピングとMaxSAT経由のルーティング
• Authors: Abtin Molavi, Amanda Xu, Martin Diges, Lauren Pick, Swamit Tannu, Aws Albarghouthi
• Abstract要約: 短期量子コンピューティングにおける重要な問題は、量子ビット間の接続が限られている物理デバイスに論理回路を配置することである。 QMRを可能な限り最適に解いて追加ノイズの量を減らすことが重要であり、量子的に無駄になる可能性がある。 本稿では,最大満足度(MAXSAT)の低減によるQMR問題の最適解法を提案する。
• 参考スコア（独自算出の注目度）: 6.711547274386115
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Near-term quantum computers will operate in a noisy environment, without error correction. A critical problem for near-term quantum computing is laying out a logical circuit onto a physical device with limited connectivity between qubits. This is known as the qubit mapping and routing (QMR) problem, an intractable combinatorial problem. It is important to solve QMR as optimally as possible to reduce the amount of added noise, which may render a quantum computation useless. In this paper, we present a novel approach for optimally solving the QMR problem via a reduction to maximum satisfiability (MAXSAT). Additionally, we present two novel relaxation ideas that shrink the size of the MAXSAT constraints by exploiting the structure of a quantum circuit. Our thorough empirical evaluation demonstrates (1) the scalability of our approach compared to state-of-the-art optimal QMR techniques (solves more than 3x benchmarks with 40x speedup), (2) the significant cost reduction compared to state-of-the-art heuristic approaches (an average of ~5x swap reduction), and (3) the power of our proposed constraint relaxations.
• Abstract（参考訳）: 短期量子コンピュータは、誤り訂正なしでノイズの多い環境で動作します。 短期量子コンピューティングにおける重要な問題は、キュービット間の接続が制限された物理デバイス上に論理回路を配置することである。 これはQMR問題(qubit mapping and routing)と呼ばれ、難解な組合せ問題である。 QMRを可能な限り最適に解いて追加ノイズの量を減らすことが重要であり、量子計算は役に立たない可能性がある。 本稿では,最大満足度(MAXSAT)の低減によるQMR問題の最適解法を提案する。 さらに、量子回路の構造を利用してMAXSAT制約のサイズを小さくする2つの新しい緩和アイデアを提案する。 以上の結果から,1)最先端のQMR技術(40倍高速化による3倍以上のベンチマーク)と比較して,アプローチのスケーラビリティ,2)最先端のヒューリスティックアプローチ(平均5倍スワップ縮小)に対する大幅なコスト削減,3)提案した制約緩和のパワーが示された。

関連論文リスト

• Second order cone relaxations for quantum Max Cut [3.237380113935023]
  量子マックスカット(Quantum Max Cut、QMC)は、量子多体物理学と計算機科学に関連するQMA完全問題である。 我々はQMCに対して2次円錐緩和を与えるが、これは相互に一貫した3量子化密度行列の集合を最適化する。 我々の緩和は数百の量子ビットを持つ系で解決可能であり、大規模量子スピン系の基底状態エネルギー上の下界と上界を計算的に効率的に計算する方法を舗装する。
  論文  参考訳（メタデータ） (2024-11-06T18:54:26Z)
• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  本稿では,デバイス間通信コストを大幅に削減する量子回路の構築手法を提案する。 そこで本研究では,従来のQDCA手法の約3倍の大きさのトラクタブル回路を構築できることを示す。
  論文  参考訳（メタデータ） (2024-05-01T20:49:50Z)
• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  本稿では,2つの分解法,すなわちグラフ縮小と回路切断の精巧な組み合わせを提案する。 この結果から,現在の量子技術の制約内での最適化問題に対するアルゴリズムの性能に関する知見が得られた。
  論文  参考訳（メタデータ） (2024-04-08T14:19:25Z)
• Toward Consistent High-fidelity Quantum Learning on Unstable Devices via Efficient In-situ Calibration [5.0854551390284]
  近未来の雑音型中間スケール量子(NISQ)時代には、高ノイズは量子コンピューティングの忠実度を著しく低下させる。 本稿では,量子パルスに基づく新しい雑音適応フレームワークQuPADを提案する。 実験により、8-10キュービットのQuPADの量子デバイス上でのランタイムは15分未満であり、パラメータシフトアプローチよりも最大270倍高速であることが示された。
  論文  参考訳（メタデータ） (2023-09-12T15:39:06Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness [2.854196251981274]
  本研究では,MILP(Mixed-Integer Linear Programming)の2つの分解法について検討した。 我々は、元の問題をより小さなサブプロブレムに分割することに集中し、量子古典的ハードウェアのアプローチを組み合わせて反復的に解決する。 実験の結果,従来の量子アニール法やゲートベース量子コンピュータと比較して最大90%の量子ビットを削減できることがわかった。
  論文  参考訳（メタデータ） (2023-04-30T13:10:56Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。 量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
  論文  参考訳（メタデータ） (2021-03-12T20:58:41Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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