論文の概要: 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ソルバは多項式誤差依存か、実現可能性の低い精度を持つ。
関連論文リスト
- 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 [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - End-to-end resource analysis for quantum interior point methods and
portfolio optimization [92.13478140615481]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳(メタデータ) (2022-11-22T18:54:48Z) - Quantum Sparse Coding [5.130440339897477]
我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。
量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。
我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
論文 参考訳(メタデータ) (2022-09-08T13:00:30Z) - 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 [5.37133760455631]
半定値プログラム(SDP)は、操作研究、最適化、量子情報科学などにおける凸最適化問題である。
本稿では,SDPを近似的に解くための変分量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-12-16T13:10:48Z) - Robust Interior Point Method for Quantum Key Distribution Rate
Computation [5.43684033059546]
我々は、鍵レート計算問題に対する凸非線形半定値計画(SDP)の安定な再構成を導出する。
本稿では,従来の難解な問題を解くとともに,スピードと精度を劇的に向上させる実験結果について報告する。
論文 参考訳(メタデータ) (2021-04-08T15:49:37Z) - Direct Optimal Control Approach to Laser-Driven Quantum Particle
Dynamics [77.34726150561087]
間接制御理論に対する頑健で柔軟な代替手段として, 直接最適制御を提案する。
この方法は、バイスタブルポテンシャルにおけるレーザー駆動のウェーブパレットダイナミクスの場合に説明される。
論文 参考訳(メタデータ) (2020-10-08T07:59:29Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。