論文の概要: Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs
- arxiv url: http://arxiv.org/abs/2412.15572v1
- Date: Fri, 20 Dec 2024 05:09:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-23 16:22:53.368235
- Title: Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs
- Title（参考訳）: 2次元ヘビーヘックスグラフを用いたランダムアイシングモデルの古典的組合せ最適化
- Authors: Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz,
- Abstract要約: 重ヘックスグラフ上のイジングモデルは、経験的時間スケーリングにより古典的な計算硬度について検討する。
これらのイジングモデルの空間性のため、古典的アルゴリズムは大規模インスタンスに対しても効率的に最適解を見つけることができる。
- 参考スコア（独自算出の注目度）: 0.8192907805418583
- License:
- Abstract: Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA). In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the Time-to-Solution metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. $100,000$ variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time Time-to-Solution scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA: Quantum Approximate Optimization Algorithm)のような量子アルゴリズムの能力を探索するために、短期的な量子コンピューティングハードウェアの制限によって動機付けられた、現在の量子アルゴリズムとほとんどあるいは全くオーバーヘッドのないノイズの多いハードウェアによって対処できる組合せ最適化問題を用いる。
本研究では,計算時間スケーリングの定量化による古典的計算困難度について,近距離量子コンピューティングハードウェアが定義した組合せ最適化問題であるIsingモデルについて検討した。
具体的には、最適化ソフトウェアであるGurobiが最適な変数割り当てを見つけるのに要する時間と、最適な変数割り当て(基底状態)を見つけるのに、古典的ヒューリスティック・シミュレート・アニールを用いた時間と解法の測定を行う。
これらのイジングモデルの空間性のため、古典的アルゴリズムは大規模インスタンス(例えば10,000ドルの変数)に対しても効率的に最適解を見つけることができる。
幾何的局所立方体項を持つIsingモデルと非局所立方体項を持つIsingモデルは、グロビを用いて正確に解くと平均2次スケールまたは2次スケールを示し、Isingモデルは擬似アニールを用いてサンプリングすると指数時間から解までのスケーリングの証拠を示す。
これらの発見は、量子コンピューティングが古典コンピューティングよりも実用的な優位性を持つために、より複雑な、より密接な最適化問題を開発し、テストする必要があることを示唆している。
我々の結果は、異なる古典的アルゴリズムが指数関数的に異なる実行時間を持つことで、量子コンピューティングと古典的コンピューティングの比較において最も重要な実用的古典的技法の同定を可能にする別の例である。
関連論文リスト
- 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) - A quantum advantage over classical for local max cut [48.02822142773719]
量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。
結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
論文 参考訳（メタデータ） (2023-04-17T16:42:05Z) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
本研究では,最適化のための量子および古典的手法の可能性を統合する。
線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。
実量子ハードウェアの計算結果を多数提示する。
論文 参考訳（メタデータ） (2023-02-10T20:12:53Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Adapting Quantum Approximation Optimization Algorithm (QAOA) for Unit
Commitment [2.8060379263058794]
ユニットコミットと呼ばれる電力系統最適化問題に対して,ハイブリッド量子古典アルゴリズムを定式化し,適用する。
提案アルゴリズムは、量子近似最適化アルゴリズム(QAOA)を古典最小値で拡張し、混合二元最適化をサポートする。
提案手法は,400個の発電ユニット未満のシミュレーション単位コミットに対して,古典的解法が有効であることを示す。
論文 参考訳（メタデータ） (2021-10-25T03:37:34Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Accelerating variational quantum algorithms with multiple quantum
processors [78.36566711543476]
変分量子アルゴリズム(VQA)は、特定の計算上の利点を得るために、短期量子マシンを利用する可能性がある。
現代のVQAは、巨大なデータを扱うために単独の量子プロセッサを使用するという伝統によって妨げられている、計算上のオーバーヘッドに悩まされている。
ここでは、この問題に対処するため、効率的な分散最適化手法であるQUDIOを考案する。
論文 参考訳（メタデータ） (2021-06-24T08:18:42Z) - Training variational quantum algorithms is NP-hard [0.7614628596146599]
古典最適化の問題はNPハードであることが示される。
対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。
論文 参考訳（メタデータ） (2021-01-18T19:00:01Z) - GEO: Enhancing Combinatorial Optimization with Classical and Quantum
Generative Models [62.997667081978825]
我々は、生成モデルとして知られる機械学習モデルを活用する新しいフレームワークを導入し、最適化問題を解決する。
我々は、テンソルネットワークマシンに依存するGEOの量子インスパイアされたバージョンに注力する。
関数呼び出し数に対する固定予算が与えられた場合、その目標が最小限の最小値を求める場合、その優れた性能を示す。
論文 参考訳（メタデータ） (2021-01-15T18:18:38Z) - Warm-starting quantum optimization [6.832341432995627]
最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。
これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。
同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
論文 参考訳（メタデータ） (2020-09-21T18:00:09Z) - Quantum vs. classical algorithms for solving the heat equation [0.04297070083645048]
量子コンピュータは、おそらく指数関数的に偏微分方程式を解くために古典的よりも優れていると予測されている。
ここでは、矩形領域における熱方程式である原始型PDEを考察し、それを解くための10の古典的および量子的アルゴリズムの複雑さを詳細に比較する。
論文 参考訳（メタデータ） (2020-04-14T13:57:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。