論文の概要: Enhancing Quantum Algorithms for Quadratic Unconstrained Binary
Optimization via Integer Programming
- arxiv url: http://arxiv.org/abs/2302.05493v2
- Date: Thu, 25 May 2023 07:21:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 20:55:43.205064
- Title: Enhancing Quantum Algorithms for Quadratic Unconstrained Binary
Optimization via Integer Programming
- Title（参考訳）: 整数計画による2値最適化のための量子アルゴリズムの拡張
- Authors: Friedrich Wagner, Jonas N\"u{\ss}lein, Frauke Liers
- Abstract要約: 本研究では,最適化のための量子および古典的手法の可能性を統合する。
線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。
実量子ハードウェアの計算結果を多数提示する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: To date, research in quantum computation promises potential for outperforming
classical heuristics in combinatorial optimization. However, when aiming at
provable optimality, one has to rely on classical exact methods like integer
programming. State-of-the-art integer programming algorithms can compute strong
relaxation bounds even for hard instances, but 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 finding
high-quality solutions for hard problems can be done fast. Still, near-future
quantum hardware considerably limits the size of treatable problems. In this
work, we go one step into integrating the potentials of quantum and classical
techniques for combinatorial optimization. We propose a hybrid heuristic for
the weighted maximum-cut problem or, equivalently, for quadratic unconstrained
binary optimization. The heuristic employs a linear programming relaxation,
rendering it well-suited for integration into exact branch-and-cut algorithms.
For large instances, we reduce the problem size according to a linear
relaxation such that the reduced problem can be handled by quantum machines of
limited size. Moreover, we improve the applicability of QAOA, a parameterized
quantum algorithm, by deriving optimal parameters for special instances which
motivates a parameter estimate for arbitrary instances. We present numerous
computational results from real quantum hardware.
- Abstract（参考訳）: 今日まで、量子計算の研究は、組合せ最適化において古典的ヒューリスティックを上回る可能性を約束している。
しかし、証明可能な最適性を目指す場合、整数プログラミングのような古典的な正確な方法に頼る必要がある。
最先端の整数プログラミングアルゴリズムは、ハードインスタンスでも強い緩和境界を計算することができるが、最適な解を決定するために多くのサブプロームを列挙する必要がある。
量子コンピューティングのポテンシャルが実現すれば、特に難しい問題に対する高品質な解を見つけることは迅速にできると期待できる。
それでも、近い将来の量子ハードウェアは、処理可能な問題のサイズをかなり制限する。
本研究では、組合せ最適化のための量子および古典的手法のポテンシャルを統合するための一歩を踏み出す。
本研究では,重み付き最大カット問題に対するハイブリッドヒューリスティック,あるいは二次非拘束二元最適化について提案する。
ヒューリスティックは線形プログラミングの緩和を採用しており、正確な分岐・カットアルゴリズムへの統合に適している。
大規模な例では、縮小した問題を限られたサイズの量子マシンで処理できるように、線形緩和に従って問題のサイズを小さくする。
さらに,任意のインスタンスに対するパラメータ推定を動機付ける特殊インスタンスの最適パラメータを導出することにより,パラメータ化量子アルゴリズムであるqaoaの適用性を向上させる。
実量子ハードウェアの計算結果を多数提示する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。