論文の概要: Enhancing Quantum Algorithms for Maximum Cut via Integer Programming
- arxiv url: http://arxiv.org/abs/2302.05493v1
- Date: Fri, 10 Feb 2023 20:12:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 20:04:00.093329
- Title: Enhancing Quantum Algorithms for Maximum Cut via Integer Programming
- Title（参考訳）: 整数プログラミングによる最大カットのための量子アルゴリズムの強化
- Authors: Friedrich Wagner, Jonas N\"u{\ss}lein, Frauke Liers
- Abstract要約: 整数最適化のための量子および古典的手法のポテンシャルを統合するための一歩を踏み出した。
重み付きグラフ上での最大カット問題に対する量子古典ハイブリッドアルゴリズムを提案する。
最大100ノードの物理により動機付けられたインスタンスに対して,実量子ハードウェアによる多数の計算結果を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: To date, quantum computation promises potential for future speed-ups in
combinatorial optimization, when compared to classical integer programming
algorithms that -- next to determining relaxations -- typically also include
some clever enumerative part. Integer programming methods can efficiently
compute strong bounds even for large instances however, may have to enumerate a
large number of subproblems for determining an optimum solution. If the
potential of quantum computing realizes, it can be expected that in particular
searching large solution spaces can be done fast. However, near-future quantum
hardware considerably limits the size of treatable problems and is also prone
to noise. In this work, we go one step into integrating the potentials of
quantum and classical techniques for integer optimization. We propose a
quantum-classical hybrid algorithm for the maximum cut problem on weighted
graphs. The algorithm relies on a classical linear programming relaxation based
on odd-cycle inequalities. For instances that are too large to be solved on
available quantum machines, we reduce the problem size according to the
solution of the linear programming relaxation. The reduced problem can be
solved by quantum computers of limited size. Returned solutions are extended to
feasible solutions of the original instance. Moreover, we improve the
applicability of QAOA, a well-known parameterized quantum algorithm by deriving
optimal parameters for special instances of the weighted maximum cut problem
which motivates a parameter estimate for arbitrary instances. We present
numerous computational results from real quantum hardware for instances
motivated by physics with up to 100 nodes which exceeds the available quantum
hardware capacities. Although all instances can be solved easily by classical
computers, they provide a proof-of-principle for the proposed method.
- Abstract（参考訳）: これまで量子計算は、リラクゼーションの決定の隣にある古典的な整数プログラミングアルゴリズムと比較して、組合せ最適化における将来の高速化の可能性も約束している。
整数型プログラミング法では,大規模インスタンスにおいても強い境界を効率的に計算することができるが,最適な解を決定するためには,多数のサブプロブレムを列挙する必要がある。
量子コンピューティングのポテンシャルが実現すれば、特に大きな解空間の探索が高速に行えることが期待できる。
しかし、近未来の量子ハードウェアは処理可能な問題のサイズをかなり制限し、ノイズも生じやすい。
本研究では、整数最適化のための量子および古典的手法のポテンシャルを統合するための一歩を踏み出す。
重み付きグラフの最大カット問題に対する量子古典ハイブリッドアルゴリズムを提案する。
このアルゴリズムは、奇サイクル不等式に基づく古典的な線形プログラミング緩和に依存する。
利用可能な量子マシンで解くには大きすぎるインスタンスに対しては、線形プログラミング緩和の解に従って問題のサイズを小さくする。
削減された問題は限られたサイズの量子コンピュータで解くことができる。
返却された解は元のインスタンスの可能な解に拡張される。
さらに、任意のインスタンスに対するパラメータ推定を動機付ける重み付き最大カット問題の特殊インスタンスに対する最適パラメータを導出することにより、よく知られたパラメータ化量子アルゴリズムであるQAOAの適用性を向上させる。
利用可能な量子ハードウェア容量を超える最大100ノードの物理により動機づけられたインスタンスに対して、実量子ハードウェアによる多数の計算結果を示す。
全てのインスタンスは古典的コンピュータによって容易に解くことができるが、それらは提案手法の原理証明を提供する。
関連論文リスト
- 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) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
論文 参考訳（メタデータ） (2023-05-23T16:17:57Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
量子ゼノダイナミクスを用いて、不等式を含む複数の任意の制約で最適化問題を解く手法を提案する。
量子最適化のダイナミクスは、フォールトトレラントな量子コンピュータ上の制約内部分空間に効率的に制限できることを示す。
論文 参考訳（メタデータ） (2022-09-29T18:00:40Z) - 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) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Solving Quadratic Unconstrained Binary Optimization with
divide-and-conquer and quantum algorithms [0.0]
分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。
この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
論文 参考訳（メタデータ） (2021-01-19T19:00:40Z) - 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) - Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial
Optimization [0.14755786263360526]
最小限のフォールトトレラント量子コンピュータで試すのに、最適化のための量子アルゴリズムが最も実用的であるかを探る。
この結果から,2次高速化のみを実現する量子最適化が,古典的アルゴリズムよりも有利であるという考えが否定される。
論文 参考訳（メタデータ） (2020-07-14T22:54:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。