論文の概要: Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

• arxiv url: http://arxiv.org/abs/2510.10056v3
• Date: Thu, 04 Dec 2025 12:40:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-25 16:54:51.381376
• Title: Quantum Alternating Direction Method of Multipliers for Semidefinite Programming
• Title（参考訳）: 半有限計画法における乗算器の量子交互方向法
• Authors: Hantao Nie, Dong An, Zaiwen Wen,
• Abstract要約: SDPに対する乗算器の量子交互方向法(QADMM)を提案する。 ブロック符号化近似と量子計測から生じる反復近似の誤差を許容する不正確なADMMフレームワークを開発した。 我々は、このスキームが強い双対性仮定の下でSDP問題の最適解に$$$収束することを証明した。
• 参考スコア（独自算出の注目度）: 9.11785675254736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an $ε$-optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs.
• Abstract（参考訳）: セミデフィニティプログラミング(SDP)は、広範囲のアプリケーションに対する基本的な凸最適化問題である。 しかし、線形システムの解法と固有値分解のコストが高いため、大規模インスタンスの解法は依然として計算的に困難である。 本稿では、近年の量子コンピューティングの進歩を基盤として、SDP用乗算器の量子交互方向法(QADMM)を提案する。 ブロックエンコーディング近似と量子計測から生じる繰り返しのエラーを許容する不正確なADMMフレームワークを開発した。 このロバストなスキームの中で、半定値の円錐制約に対処する多項式近作用素を設計し、量子特異値変換を適用して、最もコストのかかる投影更新を高速化する。 我々は、このスキームが強い双対性仮定の下で SDP 問題の$ε$-最適解に収束することを証明した。 QADMMアルゴリズムは,従来のADMMアルゴリズムや量子インテリアポイント法と比較して,次元のスケーリングが良好であることを示し,大規模SDPの解法の可能性を強調した。

関連論文リスト

• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  チュートリアルは変分量子回路とQUBO問題の概要から始まる。 次に、ハミルトンの定式化、ゲート分解、サンプル応用など、QAOAの詳細を探索する。 このチュートリアルはこれらの概念を高階ハミルトニアンに拡張し、関連する対称性と回路構成について議論する。
  論文  参考訳（メタデータ） (2025-11-23T09:54:20Z)
• Quantum-Efficient Reinforcement Learning Solutions for Last-Mile On-Demand Delivery [1.8262547855491453]
  時間Windowsを用いた大規模キャパシタイトピックアップ・デリバリ問題の解法を量子コンピューティングで検討する。 エンタングル層と変分層を有する新しい問題固有符号化量子回路を提案する。
  論文  参考訳（メタデータ） (2025-08-07T13:50:43Z)
• Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
  独立支配問題(IDP)は、様々な現実のシナリオにおいて実践的な意味を持つ。 IDPの既存の古典的アルゴリズムは計算の複雑さに悩まされている。 本稿では、IDPに対処するための量子近似最適化(QAOA)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-10-22T17:49:00Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。 アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
  論文  参考訳（メタデータ） (2022-11-22T18:54:48Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。 我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。 すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
  論文  参考訳（メタデータ） (2020-10-01T18:14:11Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers [3.04585143845864]
  本稿では,2次最適化問題に対する現行手法の適用性を高めるために,分解に基づくアプローチを提案する。 我々は、乗算器の交互方向法(ADMM)が、MBOを二項制約のない問題(量子アルゴリズムで解ける)に分割できることを示した。 提案手法の有効性は,Qiskit で実装された量子回路上での VQE と QAOA を用いたシミュレーションにより,いくつかの最適化問題に対して得られた数値結果によって示される。
  論文  参考訳（メタデータ） (2020-01-07T14:43:13Z)

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

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