論文の概要: A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework

• arxiv url: http://arxiv.org/abs/2207.11154v1
• Date: Fri, 22 Jul 2022 15:51:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-04 02:54:57.238306
• Title: A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework
• Title（参考訳）: ロバストIPMフレームワークを用いた半定値プログラミングのための高速量子アルゴリズム
• Authors: Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, Ruizhe Zhang
• Abstract要約: 本稿では,半定値プログラミング(SDP)を高精度に解くために,凸最適化の基本的な問題について検討する。 我々は、その出力の最適性と実現可能性の両方において高精度な量子二階法を提案する。
• 参考スコア（独自算出の注目度）: 14.531920189937495
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies a fundamental problem in convex optimization, which is to solve semidefinite programming (SDP) with high accuracy. This paper follows from existing robust SDP-based interior point method analysis due to [Huang, Jiang, Song, Tao and Zhang, FOCS 2022]. While, the previous work only provides an efficient implementation in the classical setting. This work provides a novel quantum implementation. We give a quantum second-order algorithm with high-accuracy in both the optimality and the feasibility of its output, and its running time depending on $\log(1/\epsilon)$ on well-conditioned instances. Due to the limitation of quantum itself or first-order method, all the existing quantum SDP solvers either have polynomial error dependence or low-accuracy in the feasibility.
• Abstract（参考訳）: 本稿では,半定値プログラミング(SDP)を高精度に解くために,凸最適化の基本問題について検討する。 本稿では,[Huang, Jiang, Song, Tao and Zhang, FOCS 2022] による既存の頑健なSDPに基づく内部点法解析から従う。 一方、以前の作業は古典的な設定で効率的な実装を提供するだけである。 この研究は、新しい量子実装を提供する。 最適性と出力の実現可能性の両方において高い正確性を持つ量子二階アルゴリズムを与え、よく条件付けられたインスタンスに対して$\log(1/\epsilon)$ に依存する実行時間を与える。 量子そのものや一階法の制限のため、既存の量子SDPソルバは多項式誤差依存か、実現可能性の低い精度を持つ。

関連論文リスト

• Application of Langevin Dynamics to Advance the Quantum Natural Gradient Optimization Algorithm [47.47843839099175]
  近年,変分量子回路の最適化のためのQNGアルゴリズムが提案されている。 本研究では、この離散時間解が一般化形式を与えることを示すために、QNG力を持つランゲヴィン方程式を用いる。
  論文  参考訳（メタデータ） (2024-09-03T15:21:16Z)
• 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)
• Quantum Realization of the Finite Element Method [0.0]
  本稿では,二階線形楕円偏微分方程式を$d$線形有限要素で離散化するための量子アルゴリズムを提案する。 この構成において重要なステップはBPXプリコンディショナーであり、線形系を十分によく調和されたものに変換する。 我々は、任意の固定次元に対して、我々の量子アルゴリズムが与えられた寛容に対する解の適切な機能を計算することができることを示す構成的証明を提供する。
  論文  参考訳（メタデータ） (2024-03-28T15:44:20Z)
• Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm [0.0]
  2段階プログラミングは不確実性の下での意思決定における問題定式化である。 この研究は量子アルゴリズムを用いて、期待値関数をスピードアップで推定する。
  論文  参考訳（メタデータ） (2024-02-23T00:07:34Z)
• QSlack: A slack-variable approach for variational quantum semi-definite programming [5.0579795245991495]
  量子コンピュータは、最もよく知られた古典的アルゴリズムのスピードアップを提供することができる。 半定値および線形プログラムを含む最適化問題の解法を示す。 これらの問題に対する予備問題と双対問題の両方の実装が、基礎的真理に近づいていることが示される。
  論文  参考訳（メタデータ） (2023-12-06T19:00:01Z)
• On adaptive low-depth quantum algorithms for robust multiple-phase estimation [11.678822620192438]
  We present robust multiple-phase estimation (RMPE) algorithm with Heisenberg-limited scaling。 これらのアルゴリズムは、初期のフォールトトレラント量子コンピュータに特に適している。
  論文  参考訳（メタデータ） (2023-03-14T17:38:01Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。 アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
  論文  参考訳（メタデータ） (2022-11-22T18:54:48Z)
• 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)
• Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
  半定値プログラム(SDP)は、操作研究、最適化、量子情報科学などにおける凸最適化問題である。 本稿では,SDPを近似的に解くための変分量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-16T13:10:48Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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