Fugu-MT 論文翻訳(概要): Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative

論文の概要: Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative

arxiv url: http://arxiv.org/abs/2105.03528v1
Date: Fri, 7 May 2021 22:35:02 GMT
ステータス: 処理完了
システム内更新日: 2023-04-01 05:17:40.522031
Title: Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative
Title（参考訳）: 組合せ最適化のための量子アルゴリズムのベンチマーク研究:ユニタリ対散逸
Authors: Krishanu Sankar, Artur Scherer, Satoshi Kako, Sam Reifenstein, Navid Ghadermarzy, Willem B. Krayenhoff, Yoshitaka Inui, Edwin Ng, Tatsuhiro Onodera, Pooya Ronagh, and Yoshihisa Yamamoto
Abstract要約: 最適化のための3つの量子アルゴリズムの性能スケーリングについて検討する。 MFB-CIM、離散断熱量子計算(DAQC)、量子最小探索(DH-QMF)のためのD"urr-Hoyerアルゴリズム
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
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 our reference for comparison, and time-to-solution (TTS) as a practical measure of performance for these optimization algorithms. We empirically observe a $\Theta(2^{\sqrt{n}})$ scaling for the median TTS for MFB-CIM, in comparison to the exponential scaling with the exponent $n$ for DAQC and the provable $\widetilde{\mathcal O}\left(\sqrt{2^n}\right)$ scaling for DH-QMF. We conclude that these scaling complexities result in a dramatic performance advantage for MFB-CIM in comparison to the other two algorithms for solving MaxCut problems.
Abstract（参考訳）: 本稿では,測度フィードバックコヒーレントIsing Machine(MFB-CIM),離散断熱量子計算(DAQC),およびGroverの探索に基づく量子最小探索(DH-QMF)のためのD\"urr-Hoyerアルゴリズムの3種類の量子アルゴリズムの性能スケーリングについて検討する。比較対象としてmaxcut問題、最適化アルゴリズムの性能評価にtime-to-solution(tts)を用いた。 MFB-CIM の中央値 TTS に対する $\Theta(2^{\sqrt{n}})$ のスケーリングを、DAQC の指数 $n$ と provable $\widetilde{\mathcal O}\left(\sqrt{2^n}\right)$ DH-QMF の指数スケーリングと比較して実証的に観察する。これらのスケーリングの複雑さは、MFB-CIMの他の2つのアルゴリズムと比較して劇的な性能上の優位性をもたらすと結論付けている。

関連論文リスト

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)
The role of quantum and classical correlations in shrinking algorithms for optimization [0.0]
最適化問題(COP)における縮小アルゴリズムの性能について検討する。量子近似最適化アルゴリズム (QAOA) と古典線形計画法 (LP) と半定値計画法 (SDP) の相関によるアルゴリズムの性能の比較を行った。その結果、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)
Quantum Approximate Optimization Algorithm with Cat Qubits [0.0]
猫の量子ビットを用いたQAOAを用いてMaxCut問題の解法を数値シミュレーションする。猫の量子ビットを用いたQAOAの実行は、2レベルシステムに符号化された量子ビットに対して、MaxCutのランダムなインスタンスに対する近似比を増大させることを示す。
論文参考訳（メタデータ） (2023-05-09T15:44:52Z)
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)
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)
Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
半定値プログラム(SDP)は、操作研究、最適化、量子情報科学などにおける凸最適化問題である。本稿では,SDPを近似的に解くための変分量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-12-16T13:10:48Z)
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)

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

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