論文の概要: Fast Numerical Solver of Ising Optimization Problems via Pruning and Domain Selection
- arxiv url: http://arxiv.org/abs/2312.05837v2
- Date: Tue, 3 Sep 2024 14:59:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-04 21:52:48.831992
- Title: Fast Numerical Solver of Ising Optimization Problems via Pruning and Domain Selection
- Title(参考訳): プルーニングとドメイン選択によるイジング最適化問題の高速数値解法
- Authors: Langyu Li, Daoyi Dong, Yu Pan,
- Abstract要約: 本稿では,Ising最適化問題に対する高速かつ効率的な解法を提案する。
我々の解法は古典的解法よりも桁違いに高速で、量子インスパイアされたアニールよりも少なくとも2倍高速である。
- 参考スコア(独自算出の注目度): 4.460518115427853
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum annealers, coherent Ising machines and digital Ising machines for solving quantum-inspired optimization problems have been developing rapidly due to their near-term applications. The numerical solvers of the digital Ising machines are based on traditional computing devices. In this work, we propose a fast and efficient solver for the Ising optimization problems. The algorithm consists of a pruning method that exploits the graph information of the Ising model to reduce the computational complexity, and a domain selection method which introduces significant acceleration by relaxing the discrete feasible domain into a continuous one to incorporate the efficient gradient descent method. The experiment results show that our solver can be an order of magnitude faster than the classical solver, and at least two times faster than the quantum-inspired annealers including the simulated quantum annealing on the benchmark problems. With more relaxed requirements on hardware and lower cost than quantum annealing, the proposed solver has the potential for near-term application in solving challenging optimization problems as well as serving as a benchmark for evaluating the advantage of quantum devices.
- Abstract(参考訳): 量子アンニア、コヒーレントイジングマシン、および量子に着想を得た最適化問題を解決するデジタルイジングマシンは、その短期的応用により急速に発展してきた。
デジタルイジングマシンの数値解法は、従来の計算装置に基づいている。
本研究では,Ising最適化問題に対する高速かつ効率的な解法を提案する。
本アルゴリズムは、Isingモデルのグラフ情報を利用して計算複雑性を低減させるプルーニング法と、離散可能な領域を連続的な領域に緩和して大きな加速をもたらす領域選択法とから構成される。
実験の結果, 従来の解法よりも桁違いに高速であり, ベンチマーク問題に対する量子アニールを含む量子インスピレーションアニールよりも少なくとも2倍高速であることがわかった。
ハードウェアに対する要求が緩和され、量子アニールよりも低コストになるため、提案した解法は、挑戦的な最適化問題の解決における短期的応用の可能性と、量子デバイスの利点を評価するためのベンチマークとして機能する。
関連論文リスト
- Sparks of Quantum Advantage and Rapid Retraining in Machine Learning [0.0]
我々はAdiabatic quantum computer を利用してKolmogorov-Arnold Networks を最適化する。
トレーニングサンプルの数とは無関係に、固定サイズのソリューションスペースを作成します。
私たちのアプローチは、古典よりも速いトレーニング時間を通じて、量子的優位性を生み出します。
論文 参考訳(メタデータ) (2024-07-22T19:55:44Z) - Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut
Problems with QAOA [1.5047640669285467]
量子近似最適化アルゴリズム(QAOA)は、近似を用いて最適化問題を解くために用いられる一般的な量子アルゴリズムの1つである。
しかし、仮想量子コンピュータ上でのQAOAの実行は、最適化問題を解くのに遅いシミュレーション速度に悩まされている。
本稿では,QAOAの量子演算を数学的に最適化し,QCSを高速化する手法を提案する。
論文 参考訳(メタデータ) (2023-12-05T06:08:57Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
線形最適化問題を解くために、非現実的な量子内点法を開発した。
また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
論文 参考訳(メタデータ) (2022-05-02T21:30:56Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳(メタデータ) (2022-01-06T21:02:30Z) - 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) - Integer Programming from Quantum Annealing and Open Quantum Systems [0.8049701904919515]
我々は,古典的なNPハード問題である整数線形プログラミング問題を量子アニール上で解くアルゴリズムを開発した。
このアルゴリズムはランダムな推測よりも優れているが、小さな問題に限られている。
論文 参考訳(メタデータ) (2020-09-24T22:18:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。