論文の概要: Improving Quantum Computation by Optimized Qubit Routing

• arxiv url: http://arxiv.org/abs/2206.01294v3
• Date: Tue, 31 Jan 2023 11:03:20 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-10 22:38:53.624351
• Title: Improving Quantum Computation by Optimized Qubit Routing
• Title（参考訳）: 最適化量子ビットルーティングによる量子計算の改善
• Authors: Friedrich Wagner, Andreas B\"armann, Frauke Liers, Markus Weissenb\"ack
• Abstract要約: スワップ挿入による量子ビットルーティングのための高品質な分解手法を提案する。 この最適化問題は、特定の量子ハードウェアに量子アルゴリズムをコンパイルする文脈で発生する。 本稿では,統合割当問題とトークンスワップ問題に対する数値計算結果について述べる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (arXiv:2106.06446), we formulate the allocation subproblem as a binary program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm. We present numerical results for the integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of gates and output circuit depth when compared to state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods.
• Abstract（参考訳）: 本研究では,スワップ挿入による量子ビットルーティングのための高品質な分解手法を提案する。 この最適化問題は、特定の量子ハードウェアに量子アルゴリズムをコンパイルする文脈で発生する。 このアプローチでは、ルーティング問題をアロケーションサブプロブレムとトークン交換問題のセットに分解する。 これにより、アロケーション部とトークンスワッピング部を別々に扱うことができます。 nannicini et al. (arxiv:2106.06446) の qubit ルーティングモデルから割り当て部分を抽出することで、割り当てサブプロブレムをバイナリプログラムとして定式化する。 そこで,本研究では,全体の経路問題目標の上限を低くしたコスト関数を採用する。 我々は新しい有効不等式によって線形緩和を強化する。 トークンスワッピング部では、正確に分岐とバウンドのアルゴリズムを開発する。 この文脈では、トークンスワップ問題における既知の下位境界を改善する。 さらに,既存の近似アルゴリズムを改良する。 本稿では,統合割当問題とトークン交換問題に対する数値計算結果を示す。 近似アルゴリズムの分解と利用により、達成された解は地球規模で最適ではないかもしれない。 しかし、解は高速に得られ、典型的には最適に近い。 さらに、最先端のヒューリスティックと比較すると、ゲート数と出力回路の深さが大幅に減少する。 これらの数値を減らすことは、近い将来のハードウェア上で量子アルゴリズムを実行するときノイズを最小化するのに不可欠である。 その結果、新しい分解アプローチを用いることで、品質が向上したコンパイルアルゴリズムが実現される。 実際、新しいルーティング手順でコンパイルして実際のハードウェアで実行すると、量子近似最適化アルゴリズムの実験結果は、標準的なルーティング手法と比較して、ソリューションの品質が著しく向上することを示している。

関連論文リスト

• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice [0.0]
  変分量子アルゴリズム、特に変分量子固有解器の変種は最適化(CO)問題に対処するために提案されている。 ベンチマークとしてMax-Cutを用いてCO問題を解く上で,このスケーリング結果がどのような意味を持つのかを数値的に検討する。
  論文  参考訳（メタデータ） (2024-08-06T09:57:34Z)
• A Fast and Adaptable Algorithm for Optimal Multi-Qubit Pathfinding in Quantum Circuit Compilation [0.0]
  この研究は、量子回路のコンパイルマッピング問題における臨界サブルーチンとして、マルチキュービットパスフィンディングに焦点を当てている。 本稿では,回路SWAPゲート深さに対して量子ハードウェア上で量子ビットを最適にナビゲートする二進整数線形計画法を用いてモデル化したアルゴリズムを提案する。 我々は、様々な量子ハードウェアレイアウトのアルゴリズムをベンチマークし、計算ランタイム、解SWAP深さ、累積SWAPゲート誤差率などの特性を評価した。
  論文  参考訳（メタデータ） (2024-05-29T05:59:15Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Size optimization of CNOT circuits on NISQ [13.391818915679796]
  ノイズの多い中間規模量子(NISQ)デバイス上でのCNOT回路の最適化について検討する。 我々はこのアルゴリズムをIBM20や他のNISQデバイス上で実装し、その結果は他の実験方法よりも優れている。
  論文  参考訳（メタデータ） (2022-10-11T06:44:04Z)
• Quantum Levenberg--Marquardt Algorithm for optimization in Bundle Adjustment [0.0]
  本稿では,正規方程式の線形系を解くための量子アルゴリズムを実装し,レバンス-マルカールトの最適化ステップを計算する。 提案した量子アルゴリズムは、点数に関して、この演算の複雑さを劇的に低減する。
  論文  参考訳（メタデータ） (2022-03-04T13:38:21Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Optimal qubit assignment and routing via integer programming [0.22940141855172028]
  論理量子回路を2ビット接続に制限のあるハードウェアにマッピングする問題を考察する。 我々はこの問題を2変数のネットワークフロー定式化を用いて整数線形プログラムとしてモデル化する。 本稿では,回路の忠実度,全深度,クロストークの尺度などのコスト関数について考察する。
  論文  参考訳（メタデータ） (2021-06-11T15:02:26Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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