論文の概要: A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices

• arxiv url: http://arxiv.org/abs/2110.03400v1
• Date: Thu, 7 Oct 2021 12:42:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-12 05:50:09.779324
• Title: A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices
• Title（参考訳）: 雑音量子デバイスを用いた半定値計画のためのカットプレーン法
• Authors: Jakub Marecek and Albert Akhriev
• Abstract要約: 切削平面法を用いてSDPソルバの高速化に固有解器の量子スピードアップを利用する方法を示す。 我々は, RCP法が境界オラクルのノイズに対して非常に頑健であることを示し, ノイズの多い量子デバイスでもRCPが使用するのに適していることを示した。
• 参考スコア（独自算出の注目度）: 7.99536002595393
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There is an increasing interest in quantum algorithms for optimization problems. Within convex optimization, interior-point methods and other recently proposed quantum algorithms are non-trivial to implement on noisy quantum devices. Here, we discuss how to utilize an alternative approach to convex optimization, in general, and semidefinite programming (SDP), in particular. This approach is based on a randomized variant of the cutting-plane method. We show how to leverage quantum speed-up of an eigensolver in speeding up an SDP solver utilizing the cutting-plane method. For the first time, we demonstrate a practical implementation of a randomized variant of the cutting-plane method for semidefinite programming on instances from SDPLIB, a well-known benchmark. Furthermore, we show that the RCP method is very robust to noise in the boundary oracle, which may make RCP suitable for use even on noisy quantum devices.
• Abstract（参考訳）: 最適化問題に対する量子アルゴリズムへの関心が高まっている。 凸最適化では、内部点法やその他の最近提案された量子アルゴリズムはノイズの多い量子デバイスで実装するのは非自明である。 本稿では,特に半定義型プログラミング(sdp)において,凸最適化の代替手法をどのように利用するかについて議論する。 このアプローチは、切断平面法のランダムな変種に基づいている。 切削平面法を用いてSDPソルバの高速化に固有解器の量子スピードアップを利用する方法を示す。 本稿では,SDPLIB のインスタンス上での半定値プログラミングのための切削平面法をランダムに実装した実例を示す。 さらに, RCP法は境界オラクルのノイズに対して非常に頑健であり, ノイズの多い量子デバイスでもRCPが使用するのに適している可能性が示唆された。

関連論文リスト

• Surrogate optimization of variational quantum circuits [1.0546736060336612]
  変分量子固有解法は、多くの応用に影響を及ぼすことのできる短期的アルゴリズムとして評価される。 収束性を改善するアルゴリズムや手法を見つけることは、VQEの短期ハードウェアの能力を加速するために重要である。
  論文  参考訳（メタデータ） (2024-04-03T18:00:00Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。 USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
  論文  参考訳（メタデータ） (2023-12-19T02:27:22Z)
• Probabilistic tensor optimization of quantum circuits for the max-$k$-cut problem [0.0]
  本稿では,変分量子アルゴリズムにおけるパラメータ化回路の最適化手法を提案する。 本稿では,量子近似最適化アルゴリズム (QAOA) を最大$k$-cut問題に適用した例について述べる。
  論文  参考訳（メタデータ） (2023-10-16T12:56:22Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Bayesian Optimization for QAOA [0.0]
  量子回路を最適化するためのベイズ最適化手法を提案する。 提案手法により,量子回路の呼び出し回数を大幅に削減できることを示す。 提案手法は,ノイズの多い中間規模量子デバイス上でのQAOAのハイブリッド特性を活用するための,有望なフレームワークであることが示唆された。
  論文  参考訳（メタデータ） (2022-09-08T13:59:47Z)
• The Quantum Approximate Optimization Algorithm performance with low entanglement and high circuit depth [0.0]
  変分量子アルゴリズムは、現在の雑音量子コンピュータを使用する最も広範な方法の1つである。 最適化問題の解法における絡み合いの役割について検討する。 ここでは, 絡み合いが MaxCut と Exact Cover 3 問題において軽微な役割を担っていると結論づける。
  論文  参考訳（メタデータ） (2022-07-07T16:21:36Z)
• 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 algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。 プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
  論文  参考訳（メタデータ） (2021-11-30T12:21:41Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

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

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