論文の概要: Solving MaxCut with Quantum Imaginary Time Evolution
- arxiv url: http://arxiv.org/abs/2201.12221v1
- Date: Fri, 28 Jan 2022 16:24:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 16:02:22.845164
- Title: Solving MaxCut with Quantum Imaginary Time Evolution
- Title（参考訳）: 量子イマジナリー時間進化によるMaxCutの解法
- Authors: Rizwanul Alam, George Siopsis, Rebekah Herrman, James Ostrowski,
Phillip Lotshaw, Travis Humble
- Abstract要約: 量子想像時間進化(QITE)に基づくMaxCut問題の解法を提案する。
10ステップの後に、平均解は最大MaxCut解の100%、99%、98%、97%であることが示される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a method to solve the MaxCut problem efficiently based on
quantum imaginary time evolution (QITE). We employ a linear Ansatz for unitary
updates and an initial state that involve no entanglement. We apply the method
to graphs with number of vertices |V| = 4,6,8,10, and show that after ten QITE
steps, the average solution is 100%, 99%, 98%, 97%, respectively, of the
maximum MaxCut solution. By employing an imaginary-time-dependent Hamiltonian
interpolating between a given graph and a subgraph with two edges excised, we
show that the modified algorithm has a 100% performance converging to the
maximum solution of the MaxCut problem for all graphs up to eight vertices as
well as about 100 random samples of ten-vertex graphs. This improved method has
an overhead which is polynomial in the number of vertices.
- Abstract（参考訳）: 量子イマジナリー時間発展(qite)に基づくマックスカット問題を効率的に解く手法を提案する。
ユニタリ更新には線形Ansatzを使用し、絡み合いを伴わない初期状態とする。
この手法を頂点数 |V| = 4,6,8,10 のグラフに適用し、平均解が最大MaxCut 解の 100%, 99%, 98%, 97% となることを示す。
与えられたグラフと2つのエッジを持つグラフを補間する仮想時間依存ハミルトニアン補間を用いることで、修正アルゴリズムは最大8頂点のグラフと約100個の10頂点グラフのランダムサンプルに対して最大解に100%の精度で収束することを示した。
この改良された手法は頂点数の多項式であるオーバーヘッドを持つ。
関連論文リスト
- Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
パラメタライズド量子ゲートのツリー配置を導入し、1ラウンド$i$HVAを用いて任意のツリーグラフを正確に解けるようにする。
我々のアンサッツは、最大24ノードと$D leq 5$のグラフに対して、MaxCutを正確に解く。
論文 参考訳（メタデータ） (2024-08-17T03:34:17Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Combinatorial optimization with quantum imaginary time evolution [2.048226951354646]
線形アンザッツは、幅広いPUBO問題に対して良い結果をもたらすことを示す。
我々は,Low Autocorrelation Binary Sequences (LABS) と重み付きMaxCut最適化問題の数値結果を得た。
論文 参考訳（メタデータ） (2023-12-27T18:18:12Z) - Graph decomposition techniques for solving combinatorial optimization
problems with variational quantum algorithms [1.2622634782102324]
我々はQAOA入力問題グラフをより小さな問題に分解するアルゴリズムを開発し、削減グラフ上でQAOAを用いてMaxCutを解く。
量子量子コンピュータH1-1上で1層QAOA回路を動作させることにより、10個の100頂点グラフに対する最適解を測定することができる。
論文 参考訳（メタデータ） (2023-06-01T09:44:17Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Online Correlation Clustering for Dynamic Complete Signed Graphs [9.13755431537592]
動的完備グラフに対する相関クラスタリングの問題点を考察する。
相関クラスタリングのための [CALM+21] におけるオンライン近似アルゴリズムを用いる。
これは、グラフ編集操作の完全なセットを可能にする、動的グラフのための最初のオンラインアルゴリズムである。
論文 参考訳（メタデータ） (2022-11-13T19:36:38Z) - 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) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
論文 参考訳（メタデータ） (2021-12-30T20:31:46Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。