論文の概要: Optimized Qubit Routing for Commuting Gates via Integer Programming

• arxiv url: http://arxiv.org/abs/2507.12199v1
• Date: Wed, 16 Jul 2025 12:55:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-17 19:00:11.392053
• Title: Optimized Qubit Routing for Commuting Gates via Integer Programming
• Title（参考訳）: 整数プログラミングによるゲートの通信のための最適化されたビットルーティング
• Authors: Moritz Stargalla, Friedrich Wagner,
• Abstract要約: 本稿では,最適解を返すことが保証される整数計画法に基づく2段階分解手法を提案する。 いくつかの整数プログラミングモデルを開発し、関連するポリトープの線形記述を導出する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computers promise to outperform their classical counterparts at certain tasks. However, existing quantum devices are error-prone and restricted in size. Thus, effective compilation methods are crucial to exploit limited quantum resources. In this work, we address the problem of qubit routing for commuting gates, which arises, for example, during the compilation of the well-known Quantum Approximate Optimization Algorithm. We propose a two-step decomposition approach based on integer programming, which is guaranteed to return an optimal solution. To justify the use of integer programming, we prove NP-hardness of the underlying optimization problem. Furthermore, we derive asymptotic upper and lower bounds on the quality of a solution. We develop several integer programming models and derive linear descriptions of related polytopes, which generalize to applications beyond this work. Finally, we conduct a computational study showing that our approach outperforms existing heuristics in terms of quality and exact methods in terms of runtime.
• Abstract（参考訳）: 量子コンピュータは、あるタスクにおいて従来のコンピュータよりも優れたパフォーマンスを約束する。 しかし、既存の量子デバイスはエラーを起こしやすく、サイズが制限されている。 したがって、効率的なコンパイル手法は限られた量子資源を利用するのに不可欠である。 本稿では,例えば量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm)のコンパイル時に発生する,通勤ゲートのキュービットルーティングの問題に対処する。 本稿では,最適解を返すことが保証される整数計画法に基づく2段階分解手法を提案する。 整数プログラミングの使用を正当化するために、基礎となる最適化問題のNP完全性を証明する。 さらに, 溶液の品質に対する漸近的上層境界と下層境界を導出する。 いくつかの整数プログラミングモデルを開発し、関連するポリトープの線形記述を導出する。 最後に,本手法が既存のヒューリスティックスを,実行時の品質や正確な手法で上回っていることを示す計算的研究を行った。

関連論文リスト

• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  量子コンピュータは、最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 本稿では,量子SDPソルバの非漸近的リソース要求の解析を行う。
  論文  参考訳（メタデータ） (2025-02-21T12:54:05Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Dependency-Aware Compilation for Surface Code Quantum Architectures [7.543907169342984]
  表面符号を実装した量子コンピュータにおける量子回路のコンパイル問題について検討する。 我々はこの問題を新しいアルゴリズムで効率よく、ほぼ最適に解決する。 我々の評価は、我々のアプローチが現実的なワークロードをコンパイルするのに強力で柔軟であることを示している。
  論文  参考訳（メタデータ） (2023-11-29T19:36:19Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  本研究では,最適化のための量子および古典的手法の可能性を統合する。 線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。 実量子ハードウェアの計算結果を多数提示する。
  論文  参考訳（メタデータ） (2023-02-10T20:12:53Z)
• Approximate encoding of quantum states using shallow circuits [0.0]
  量子シミュレーションとアルゴリズムの一般的な要件は、2量子ゲートのシーケンスを通して複雑な状態を作成することである。 ここでは、限られた数のゲートを用いて、ターゲット状態の近似符号化を作成することを目的とする。 我々の研究は、局所ゲートを用いて目標状態を作成する普遍的な方法を提供し、既知の戦略よりも大幅に改善されたことを示す。
  論文  参考訳（メタデータ） (2022-06-30T18:00:04Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Improving Quantum Computation by Optimized Qubit Routing [0.0]
  スワップ挿入による量子ビットルーティングのための高品質な分解手法を提案する。 この最適化問題は、特定の量子ハードウェアに量子アルゴリズムをコンパイルする文脈で発生する。 本稿では,統合割当問題とトークンスワップ問題に対する数値計算結果について述べる。
  論文  参考訳（メタデータ） (2022-06-02T20:32:18Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。 私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。 実際の量子コンピュータを用いて得られた結果について述べる。
  論文  参考訳（メタデータ） (2022-01-25T05:59:24Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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