論文の概要: NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization
- arxiv url: http://arxiv.org/abs/2305.14197v2
- Date: Thu, 19 Oct 2023 16:13:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-20 20:20:36.561785
- Title: NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization
- Title（参考訳）: 制約のない離散最適化のためのNISQ互換近似量子アルゴリズム
- Authors: M. R. Perelshtein, A. I. Pakhomchik, Ar. A. Melnikov, M. Podobrii, A.
Termanova, I. Kreidich, B. Nuriev, S. Iudin, C. W. Mansell, V. M. Vinokur
- Abstract要約: 本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum algorithms are getting extremely popular due to their potential to
significantly outperform classical algorithms. Yet, applying quantum algorithms
to optimization problems meets challenges related to the efficiency of quantum
algorithms training, the shape of their cost landscape, the accuracy of their
output, and their ability to scale to large-size problems. Here, we present an
approximate gradient-based quantum algorithm for hardware-efficient circuits
with amplitude encoding. We show how simple linear constraints can be directly
incorporated into the circuit without additional modification of the objective
function with penalty terms. We employ numerical simulations to test it on
MaxCut problems with complete weighted graphs with thousands of nodes and run
the algorithm on a superconducting quantum processor. We find that for
unconstrained MaxCut problems with more than 1000 nodes, the hybrid approach
combining our algorithm with a classical solver called CPLEX can find a better
solution than CPLEX alone. This demonstrates that hybrid optimization is one of
the leading use cases for modern quantum devices.
- Abstract（参考訳）: 量子アルゴリズムは古典的アルゴリズムを著しく上回る可能性があるため、非常に人気がある。
しかしながら、最適化問題に量子アルゴリズムを適用することは、量子アルゴリズムのトレーニングの効率、コスト環境の形状、アウトプットの精度、大規模問題へのスケール能力に関する課題を満たしている。
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
我々は,数千ノードの重み付きグラフを用いたmaxcut問題に対して数値シミュレーションを行い,超伝導量子プロセッサ上でアルゴリズムを実行する。
1000以上のノードを持つ制約のないMaxCut問題に対して、我々のアルゴリズムとCPLEXと呼ばれる古典的解法を組み合わせるハイブリッドアプローチは、CPLEX単独よりも優れた解を見つけることができる。
これはハイブリッド最適化が現代の量子デバイスの主要なユースケースの1つであることを証明している。
関連論文リスト
- 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) - Quantum Optimization for the Maximum Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
半定値アプローチに着想を得たハイブリッド量子古典アルゴリズムの性能について検討した。
何千もの問題インスタンスのランダムアンサンブルに対して平均99%のパフォーマンスを達成した。
実行時解析により、大規模問題における量子解法は、グロビと競合するが、他の問題には劣ることを示した。
論文 参考訳（メタデータ） (2024-04-26T17:59:22Z) - A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。
我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。
この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
論文 参考訳（メタデータ） (2023-06-10T23:28:13Z) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
本研究では,最適化のための量子および古典的手法の可能性を統合する。
線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。
実量子ハードウェアの計算結果を多数提示する。
論文 参考訳（メタデータ） (2023-02-10T20:12:53Z) - Solving various NP-Hard problems using exponentially fewer qubits on a
Quantum Computer [0.0]
NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。
本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。
これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
論文 参考訳（メタデータ） (2023-01-17T16:03:33Z) - 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) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation
Algorithm [7.581898299650999]
我々はQQRA(Quantum Qubit Rotation Algorithm)という単純なアルゴリズムを導入する。
最大カット問題の近似解は 1 に近い確率で得られる。
我々は、よく知られた量子近似最適化アルゴリズムと古典的なゲーマン・ウィリアムソンアルゴリズムと比較する。
論文 参考訳（メタデータ） (2021-10-15T11:19:48Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。