論文の概要: Quantum Semidefinite Programming with the Hadamard Test and Approximate Amplitude Constraints

• arxiv url: http://arxiv.org/abs/2206.14999v2
• Date: Wed, 13 Jul 2022 05:38:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-07 04:49:59.533988
• Title: Quantum Semidefinite Programming with the Hadamard Test and Approximate Amplitude Constraints
• Title（参考訳）: ハダマール検定と近似振幅制約を用いた半定義型量子プログラミング
• Authors: Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F. Yelin
• Abstract要約: 半定値プログラムに対して最大$N=2n$変数と$M=2n$制約を持つ変分量子アルゴリズムを導入する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 本稿では,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
• 参考スコア（独自算出の注目度）: 62.72309460291971
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Semidefinite programs are optimization methods with a wide array of applications, such as approximating difficult combinatorial problems. We introduce a variational quantum algorithm for semidefinite programs that uses only $n$ qubits, a constant number of circuit preparations, and $O(n^2)$ expectation values in order to solve semidefinite programs with up to $N=2^n$ variables and $M=2^n$ constraints. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to optimize the objective function by estimating only a single expectation value of the ancilla qubit, rather than separately estimating exponentially many expectation values. Similarly, we illustrate that the semidefinite programming constraints can be effectively enforced by implementing a second Hadamard Test, as well as imposing $\sim n^2/2$ Pauli string amplitude constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm, which is a useful approximation for various NP-hard problems, such as MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems from the GSet library.
• Abstract（参考訳）: 半有限プログラムは、難しい組合せ問題を近似するなど、幅広い応用の最適化手法である。 n=2^n$変数と$m=2^n$制約を持つ半定値プログラムを解くために、n$ qubits、一定の回路準備数、および$o(n^2)$期待値のみを使用する半定値プログラムのための変分量子アルゴリズムを導入する。 効率的な最適化は、目的行列を補助量子ビット上で適切にパラメータ化されたユニタリ条件として符号化することで達成される。 アダマールテストにより、指数的に多くの期待値を推定するのではなく、1つの期待値のみを推定することで、目的関数を最適化することができる。 同様に、半定値プログラミングの制約は、2番目のアダマールテストを実装することで効果的に実施でき、さらに$\sim n^2/2$ Pauli文字列の制約を課す。 我々は,maxcut のような様々なnp-ハード問題に対して有用な近似である goemans-williamson アルゴリズムの効率的な量子実装を考案し,プロトコルの有効性を実証する。 本手法は,GSetライブラリから得られた多種多様なMaxCut問題に対する類似の古典的手法の性能を上回る。

関連論文リスト

• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。 目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
  論文  参考訳（メタデータ） (2023-05-23T16:17:57Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  本研究では,最適化のための量子および古典的手法の可能性を統合する。 線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。 実量子ハードウェアの計算結果を多数提示する。
  論文  参考訳（メタデータ） (2023-02-10T20:12:53Z)
• 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)
• Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
  半定値プログラム(SDP)は、操作研究、最適化、量子情報科学などにおける凸最適化問題である。 本稿では,SDPを近似的に解くための変分量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-16T13:10:48Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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