論文の概要: Quantum Speedup for the Maximum Cut Problem
- arxiv url: http://arxiv.org/abs/2305.16644v1
- Date: Fri, 26 May 2023 05:31:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-29 16:50:18.670325
- Title: Quantum Speedup for the Maximum Cut Problem
- Title（参考訳）: 最大カット問題に対する量子スピードアップ
- Authors: Weng-Long Chang, Renata Wong, Wen-Yu Chung, Yu-Hao Chen, Ju-Chin Chen,
Athanasios V. Vasilakos
- Abstract要約: 古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。
NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
- 参考スコア（独自算出の注目度）: 6.588073742048931
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Given an undirected, unweighted graph with $n$ vertices and $m$ edges, the
maximum cut problem is to find a partition of the $n$ vertices into disjoint
subsets $V_1$ and $V_2$ such that the number of edges between them is as large
as possible. Classically, it is an NP-complete problem, which has potential
applications ranging from circuit layout design, statistical physics, computer
vision, machine learning and network science to clustering. In this paper, we
propose a quantum algorithm to solve the maximum cut problem for any graph $G$
with a quadratic speedup over its classical counterparts, where the temporal
and spatial complexities are reduced to, respectively, $O(\sqrt{2^n/r})$ and
$O(m^2)$. With respect to oracle-related quantum algorithms for NP-complete
problems, we identify our algorithm as optimal. Furthermore, to justify the
feasibility of the proposed algorithm, we successfully solve a typical maximum
cut problem for a graph with three vertices and two edges by carrying out
experiments on IBM's quantum computer.
- Abstract（参考訳）: n$の頂点と$m$の辺を持つ非方向の非重み付きグラフが与えられたとき、最大のカット問題は、$n$の頂点の分割を、それらの間のエッジの数が可能な限り大きいような非連結部分集合に分割することである。
古典的にはNP完全問題であり、回路レイアウト設計、統計物理学、コンピュータビジョン、機械学習、ネットワーク科学、クラスタリングなど、潜在的な応用がある。
本稿では,従来のグラフに対して,時間的および空間的複雑さをそれぞれ$O(\sqrt{2^n/r})$と$O(m^2)$に減らした2次スピードアップを持つ任意のグラフに対して,最大カット問題を解く量子アルゴリズムを提案する。
NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
さらに,提案アルゴリズムの有効性を正当化するために,ibm の量子コンピュータ上で実験を行い,頂点が3つ,辺が2つあるグラフの最大カット問題を解くことに成功した。
関連論文リスト
- 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) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem [0.0]
ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。
本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
論文 参考訳（メタデータ） (2023-11-18T02:36:10Z) - Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem [2.107421958337625]
有限グラフ $(X,E)$ に対する逆問題を考える。
この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
論文 参考訳（メタデータ） (2023-06-08T14:48:48Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45: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) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Classical algorithms for Forrelation [2.624902795082451]
1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。
この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。
グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
論文 参考訳（メタデータ） (2021-02-13T17:25:41Z) - Decomposition algorithms for solving NP-hard problems on a quantum
annealer [0.0]
NPハード問題は、計算化学、生化学、コンピュータネットワークセキュリティに応用されている。
Adaabatic quantum annealers can search the optimum value of such NP-hard optimization problem, because the problem can be embedded on their hardware。
本稿ではNP-hardグラフ問題に対する分解アルゴリズムの一般的な枠組みについて検討する。
論文 参考訳（メタデータ） (2020-09-10T15:59:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。