論文の概要: Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints
- arxiv url: http://arxiv.org/abs/2408.07774v1
- Date: Wed, 14 Aug 2024 19:04:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-16 15:48:53.091614
- Title: Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints
- Title（参考訳）: アダマール試験と近似振幅制約による量子メタヒューリスティックによる多項式最適化
- Authors: Iria W. Wang, Robin Brown, Taylor L. Patti, Anima Anandkumar, Marco Pavone, Susanne F. Yelin,
- Abstract要約: 最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
- 参考スコア（独自算出の注目度）: 76.53316706600717
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computation shows promise for addressing numerous classically intractable problems, such as optimization tasks. Many optimization problems are NP-hard, meaning that they scale exponentially with problem size and thus cannot be addressed at scale by traditional computing paradigms. The recently proposed quantum algorithm arXiv:2206.14999 addresses this challenge for some NP-hard problems, and is based on classical semidefinite programming (SDP). In this manuscript, we generalize the SDP-inspired quantum algorithm to sum-of-squares programming, which targets a broader problem set. Our proposed algorithm addresses degree-$k$ polynomial optimization problems with $N \leq 2^n$ variables (which are representative of many NP-hard problems) using $O(nk)$ qubits, $O(k)$ quantum measurements, and $O(\textrm{poly}(n))$ classical calculations. We apply the proposed algorithm to the prototypical Max-$k$SAT problem and compare its performance against classical sum-of-squares, state-of-the-art heuristic solvers, and random guessing. Simulations show that the performance of our algorithm surpasses that of classical sum-of-squares after rounding. Our results further demonstrate that our algorithm is suitable for large problems and approximates the best known classical heuristics, while also providing a more generalizable approach compared to problem-specific heuristics.
- Abstract（参考訳）: 量子計算は、最適化タスクのような古典的に難解な問題に対処することを約束している。
多くの最適化問題はNPハードであり、問題の大きさで指数関数的にスケールするので、従来の計算パラダイムでは対処できない。
最近提案された量子アルゴリズムarXiv:2206.14999は、いくつかのNPハード問題に対してこの問題に対処し、古典半定値プログラミング(SDP)に基づいている。
本稿では,SDPにインスパイアされた量子アルゴリズムを,より広範な問題集合を対象とする2乗プログラミングに一般化する。
提案アルゴリズムは、$O(nk)$ qubits、$O(k)$ 量子測定、$O(\textrm{poly}(n))$ 古典計算を用いて、$N \leq 2^n$変数(多くのNPハード問題を代表している)による多項式最適化問題に対処する。
提案アルゴリズムを試作したMax-$k$SAT問題に適用し、その性能を古典的な2乗和、最先端のヒューリスティックな解法、ランダムな推測と比較する。
シミュレーションにより, アルゴリズムの性能は, 丸め後の古典的な2乗和より優れていることが示された。
以上の結果から,本アルゴリズムは既知の古典的ヒューリスティックに近似し,問題固有のヒューリスティックに比較してより一般化可能なアプローチを提供する。
関連論文リスト
- Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。
本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
論文 参考訳（メタデータ） (2024-08-11T10:28:49Z) - Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。
深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
論文 参考訳（メタデータ） (2023-09-22T18:00:03Z) - Solving various NP-Hard problems using exponentially fewer qubits on a
Quantum Computer [0.0]
NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。
本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。
これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
論文 参考訳（メタデータ） (2023-01-17T16:03:33Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - 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) - Training variational quantum algorithms is NP-hard [0.7614628596146599]
古典最適化の問題はNPハードであることが示される。
対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。
論文 参考訳（メタデータ） (2021-01-18T19:00:01Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Warm-starting quantum optimization [6.832341432995627]
最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。
これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。
同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
論文 参考訳（メタデータ） (2020-09-21T18:00:09Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。