論文の概要: QSlack: A slack-variable approach for variational quantum semi-definite
programming
- arxiv url: http://arxiv.org/abs/2312.03830v1
- Date: Wed, 6 Dec 2023 19:00:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 17:00:57.624254
- Title: QSlack: A slack-variable approach for variational quantum semi-definite
programming
- Title（参考訳）: qslack: 変分量子半定義型プログラミングのためのslack可変アプローチ
- Authors: Jingxuan Chen, Hanna Westerheim, Zo\"e Holmes, Ivy Luo, Theshani
Nuradha, Dhrumil Patel, Soorya Rethinasamy, Kathie Wang, Mark M. Wilde
- Abstract要約: 量子コンピュータは、最もよく知られた古典的アルゴリズムのスピードアップを提供することができる。
半定値および線形プログラムを含む最適化問題の解法を示す。
これらの問題に対する予備問題と双対問題の両方の実装が、基礎的真理に近づいていることが示される。
- 参考スコア（独自算出の注目度）: 5.0579795245991495
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving optimization problems is a key task for which quantum computers could
possibly provide a speedup over the best known classical algorithms. Particular
classes of optimization problems including semi-definite programming (SDP) and
linear programming (LP) have wide applicability in many domains of computer
science, engineering, mathematics, and physics. Here we focus on semi-definite
and linear programs for which the dimensions of the variables involved are
exponentially large, so that standard classical SDP and LP solvers are not
helpful for such large-scale problems. We propose the QSlack and CSlack methods
for estimating their optimal values, respectively, which work by 1) introducing
slack variables to transform inequality constraints to equality constraints, 2)
transforming a constrained optimization to an unconstrained one via the penalty
method, and 3) replacing the optimizations over all possible non-negative
variables by optimizations over parameterized quantum states and parameterized
probability distributions. Under the assumption that the SDP and LP inputs are
efficiently measurable observables, it follows that all terms in the resulting
objective functions are efficiently estimable by either a quantum computer in
the SDP case or a quantum or probabilistic computer in the LP case.
Furthermore, by making use of SDP and LP duality theory, we prove that these
methods provide a theoretical guarantee that, if one could find global optima
of the objective functions, then the resulting values sandwich the true optimal
values from both above and below. Finally, we showcase the QSlack and CSlack
methods on a variety of example optimization problems and discuss details of
our implementation, as well as the resulting performance. We find that our
implementations of both the primal and dual for these problems approach the
ground truth, typically achieving errors of order $10^{-2}$.
- Abstract（参考訳）: 最適化問題の解決は、量子コンピュータが既知の古典的アルゴリズムを高速化する上で重要な課題である。
半定値プログラミング(SDP)や線形プログラミング(LP)を含む最適化問題のクラスは、計算機科学、工学、数学、物理学の多くの領域で広く適用可能である。
ここでは,変数の次元が指数関数的に大きい半定値線形プログラムに着目し,従来のSDPとLPソルバはそのような大規模問題に役に立たない。
我々は,それぞれの最適値を推定するためのqslackとcslackの手法を提案する。
1)不等式制約を等式制約に変換するためのslack変数の導入。
2)制約付き最適化をペナルティ法による制約なし最適化に変換すること、及び
3)すべての可能な非負変数に対する最適化を、パラメータ化された量子状態とパラメータ化された確率分布の最適化に置き換える。
SDP と LP の入力が効率的に測定可能であると仮定すると、結果の目的関数の全ての項は、SDP の場合の量子コンピュータまたは LP の場合の量子または確率コンピュータによって効率的に推定可能である。
さらに, sdp と lp の双対性理論を用いることにより, これらの手法が, 目的関数の大域的オプティマを見いだせるならば, 結果値が上と下の両方から真の最適値を挟むという理論的保証を与えることを証明した。
最後に、様々なサンプル最適化問題に関するqslackとcslackメソッドを紹介し、実装の詳細と結果のパフォーマンスについて論じる。
これらの問題に対する原始問題と双対問題の両方の実装は、基礎的真理に近づき、典型的には10^{-2}$という命令の誤りをもたらす。
関連論文リスト
- BO4IO: A Bayesian optimization approach to inverse optimization with uncertainty quantification [5.031974232392534]
この研究はデータ駆動逆最適化(IO)に対処する。
目的は最適化モデルにおける未知のパラメータを、最適あるいは準最適と仮定できる観測された決定から推定することである。
論文 参考訳（メタデータ） (2024-05-28T06:52:17Z) - Two-Stage ML-Guided Decision Rules for Sequential Decision Making under Uncertainty [55.06411438416805]
SDMU (Sequential Decision Making Under Uncertainty) は、エネルギー、金融、サプライチェーンといった多くの領域において、ユビキタスである。
いくつかのSDMUは、自然にマルチステージ問題(MSP)としてモデル化されているが、結果として得られる最適化は、計算の観点からは明らかに困難である。
本稿では,2段階の一般決定規則(TS-GDR)を導入し,線形関数を超えて政策空間を一般化する手法を提案する。
TS-GDRの有効性は、TS-LDR(Two-Stage Deep Decision Rules)と呼ばれるディープリカレントニューラルネットワークを用いたインスタンス化によって実証される。
論文 参考訳（メタデータ） (2024-05-23T18:19:47Z) - Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳（メタデータ） (2024-02-16T16:35:18Z) - Improving Performance in Combinatorial Optimization Problems with
Inequality Constraints: An Evaluation of the Unbalanced Penalization Method
on D-Wave Advantage [0.0]
非バランスなペナル化と呼ばれる新しい手法が、スラック変数の使用を避けるために提案されている。
本研究は、旅行セールスマン問題(TSP)に対するD-Wave Advantage上の実量子ハードウェアを用いた不均衡ペナル化法をテストする。
その結果、不均衡なペナル化法はスラック変数を用いた解よりも優れていた。
論文 参考訳（メタデータ） (2023-05-30T05:40:50Z) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
本研究では,最適化のための量子および古典的手法の可能性を統合する。
線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。
実量子ハードウェアの計算結果を多数提示する。
論文 参考訳（メタデータ） (2023-02-10T20:12:53Z) - A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM
Framework [14.531920189937495]
本稿では,半定値プログラミング(SDP)を高精度に解くために,凸最適化の基本的な問題について検討する。
我々は、その出力の最適性と実現可能性の両方において高精度な量子二階法を提案する。
論文 参考訳（メタデータ） (2022-07-22T15:51:02Z) - 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) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。