Fugu-MT 論文翻訳(概要): A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization

論文の概要: A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization

arxiv url: http://arxiv.org/abs/2105.03528v2
Date: Fri, 17 Jan 2025 06:08:17 GMT
ステータス: 翻訳完了
システム内更新日: 2025-01-20 13:57:38.933956
Title: A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
Title（参考訳）: 組合せ最適化のための量子アルゴリズムのベンチマーク研究
Authors: Krishanu Sankar, Artur Scherer, Satoshi Kako, Sam Reifenstein, Navid Ghadermarzy, Willem B. Krayenhoff, Yoshitaka Inui, Edwin Ng, Tatsuhiro Onodera, Pooya Ronagh, Yoshihisa Yamamoto,
Abstract要約: 評価フィードバックコヒーレントIsing Machine(MFB-CIM)、離散断熱量子計算(DAQC)、量子最小探索(DH-QMF)のためのD"urr-Hoyerアルゴリズムの3つの量子アルゴリズムの性能スケーリングについて検討する。各アルゴリズムに対して、ランダムに生成されたエッジ重みを持つ重み付きグラフインスタンスを1ドルで1ドルから1ドルで、ランダムに生成されたSherrington-Kirkpatrick(SK)スピングラスインスタンスをランダムに生成する。
参考スコア（独自算出の注目度）: 0.0
License:
Abstract: We study the performance scaling of three quantum algorithms for combinatorial optimization: measurement-feedback coherent Ising machines (MFB-CIM), discrete adiabatic quantum computation (DAQC), and the D\"urr-Hoyer algorithm for quantum minimum finding (DH-QMF) that is based on Grover's search. We use MaxCut problems as a reference for comparison, and time-to-solution (TTS) as a practical measure of performance for these optimization algorithms. For each algorithm, we analyze its performance in solving two types of MaxCut problems: weighted graph instances with randomly generated edge weights attaining 21 equidistant values from $-1$ to $1$; and randomly generated Sherrington-Kirkpatrick (SK) spin glass instances. We empirically find a significant performance advantage for the studied MFB-CIM in comparison to the other two algorithms. We empirically observe a sub-exponential scaling for the median TTS for the MFB-CIM, in comparison to the almost exponential scaling for DAQC and the proven $\widetilde{O}\left(\sqrt{2^n}\right)$ scaling for DH-QMF. We conclude that the MFB-CIM outperforms DAQC and DH-QMF in solving MaxCut problems.
Abstract（参考訳）: 本稿では,測度フィードバックコヒーレントIsing Machine(MFB-CIM),離散断熱量子計算(DAQC),およびGroverの探索に基づく量子最小探索(DH-QMF)のためのD\"urr-Hoyerアルゴリズムの3種類の量子アルゴリズムの性能スケーリングについて検討する。比較のための基準としてMaxCut問題を使用し、これらの最適化アルゴリズムの性能の実用的な尺度としてTTS(Time-to-solution)を用いる。各アルゴリズムに対して、ランダムに生成されたエッジ重みを持つ重み付きグラフインスタンスを1ドルで1ドルから1ドルで、ランダムに生成されたSherrington-Kirkpatrick(SK)スピングラスインスタンスをランダムに生成する。実験により,他の2つのアルゴリズムと比較して,MFB-CIMの有意な性能上の優位性を実証的に見出した。 MFB-CIMの中央値TSのサブ指数スケーリングを、DAQCのほぼ指数スケーリングと証明された$\widetilde{O}\left(\sqrt{2^n}\right)$スケーリングと比較して実証的に観察する。 MFB-CIM は MaxCut 問題の解法において DAQC と DH-QMF より優れていた。

関連論文リスト

A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
論文参考訳（メタデータ） (2025-01-02T05:06:16Z)
Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
論文参考訳（メタデータ） (2024-10-30T08:41:29Z)
Quantum and classical correlations in shrinking algorithms for optimization [0.0]
最適化問題(COP)の解法として量子コンピューティングを用いる。本研究では,再帰的に縮小することでCOPを解くアルゴリズムを拡張し,解析する。量子近似最適化アルゴリズム(QAOA)と古典線形計画法(LP)と半定値計画法(SDP)の相関性を備えたアルゴリズムの性能を比較した。
論文参考訳（メタデータ） (2024-04-26T08:29:04Z)
Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文参考訳（メタデータ） (2023-10-18T10:29:58Z)
Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
論文参考訳（メタデータ） (2023-10-01T03:57:13Z)
QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem [6.783232060611114]
より大規模なMax-Cut問題を解決するためにQAOA回路を設計するためのフレームワークを提案する。古典アルゴリズムとQAOAの近似比を仮定して理論的に近似を保証する。われわれのフレームワークは平均で18ドルと0.950ドルしか消費しない。
論文参考訳（メタデータ） (2023-07-28T02:06:42Z)
Quantum Approximate Optimization Algorithm with Cat Qubits [0.0]
猫の量子ビットを用いたQAOAを用いてMaxCut問題の解法を数値シミュレーションする。猫の量子ビットを用いたQAOAの実行は、2レベルシステムに符号化された量子ビットに対して、MaxCutのランダムなインスタンスに対する近似比を増大させることを示す。
論文参考訳（メタデータ） (2023-05-09T15:44:52Z)
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)
Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文参考訳（メタデータ） (2021-11-30T12:21:41Z)
Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。両レベル最適化のための2つの新しいアルゴリズムを提案する。両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文参考訳（メタデータ） (2021-06-08T21:05:30Z)
Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文参考訳（メタデータ） (2021-06-08T15:54:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。