論文の概要: Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints
- arxiv url: http://arxiv.org/abs/2206.14999v3
- Date: Sun, 9 Jul 2023 03:51:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 22:45:22.122983
- Title: Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints
- Title（参考訳）: アダマール試験と近似振幅制約を用いた量子ゲーマン-ウィリアムソンアルゴリズム
- Authors: Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F. Yelin
- Abstract要約: 本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,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. One such
semidefinite program is the Goemans-Williamson algorithm, a popular integer
relaxation technique. We introduce a variational quantum algorithm for the
Goemans-Williamson algorithm that uses only $n{+}1$ qubits, a constant number
of circuit preparations, and $\text{poly}(n)$ expectation values in order to
approximately solve semidefinite programs with up to $N=2^n$ variables and $M
\sim O(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 a polynomial number of Pauli string amplitude constraints.
We demonstrate the effectiveness of our protocol by devising an efficient
quantum implementation of the Goemans-Williamson algorithm for various NP-hard
problems, including MaxCut. Our method exceeds the performance of analogous
classical methods on a diverse subset of well-studied MaxCut problems from the
GSet library.
- Abstract（参考訳）: 半有限プログラムは、難しい組合せ問題を近似するなど、幅広い応用の最適化手法である。
そのような半定義のプログラムの1つは、一般的な整数緩和法であるゴーマンス・ウィリアムソンアルゴリズムである。
我々は、最大$N=2^n$変数と$M \sim O(N)$制約を持つ半定値プログラムを近似的に解くために、n{+}1$ qubits, a constant number of circuit prepareds, $\text{poly}(n)$ expectation値のみを使用するGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを導入する。
効率的な最適化は、目的行列を補助量子ビット上で適切にパラメータ化されたユニタリ条件として符号化することで達成される。
アダマールテストにより、指数的に多くの期待値を推定するのではなく、1つの期待値のみを推定することで、目的関数を最適化することができる。
同様に、半定値プログラミングの制約は、パウリ弦振幅制約の多項式数を課すとともに、第2アダマールテストを実装することで効果的に実施できることを示す。
我々は,Guemans-Williamson アルゴリズムの効率的な量子実装を MaxCut を含む様々なNPハード問題に対して考案し,提案プロトコルの有効性を実証する。
本手法は,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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。