論文の概要: An improved Quantum Max Cut approximation via matching
- arxiv url: http://arxiv.org/abs/2401.03616v1
- Date: Mon, 8 Jan 2024 00:36:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-09 18:03:39.000659
- Title: An improved Quantum Max Cut approximation via matching
- Title（参考訳）: マッチングによる量子最大カット近似の改良
- Authors: Eunou Lee
- Abstract要約: 最近の研究の行は量子マックスカット(英語版)に焦点を当てており、そこでは与えられた反強磁性ハイゼンベルク・ハミルトンの高エネルギー状態を見つけるよう求められている。
本稿では、一般的な入力に対して0.584の近似比、三角形のない入力に対して0.595の近似比を達成する量子マックスカットの古典的近似アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finding a high (or low) energy state of a given quantum Hamiltonian is a
potential area to gain a provable and practical quantum advantage. A line of
recent studies focuses on Quantum Max Cut, where one is asked to find a high
energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work,
we present a classical approximation algorithm for Quantum Max Cut that
achieves an approximation ratio of 0.584 given a generic input, and a ratio of
0.595 given a triangle-free input, outperforming the previous best algorithms
of Lee \cite{Lee22} (0.562, generic input) and King \cite{King22} (0.582,
triangle-free input). The algorithm is based on finding the maximum weighted
matching of an input graph and outputs a product of at most 2-qubit states,
which is simpler than the fully entangled output states of the previous best
algorithms.
- Abstract（参考訳）: 与えられた量子ハミルトニアンの高(または低)エネルギー状態を見つけることは、証明可能かつ実用的な量子優位を得る可能性領域である。
最近の一連の研究は量子マックス切断に焦点を当てており、そこでは与えられた反強磁性ハイゼンベルクハミルトニアンの高エネルギー状態を求める。
本研究では,一般的な入力に対して0.584の近似比と0.595の三角形のない入力を与える量子マックスカットの古典近似アルゴリズムを提案し,Lie \cite{Lee22} (0.562,ジェネリック入力)とKing \cite{King22} (0.582,三角形なし入力)のアルゴリズムよりも優れた精度で性能を向上した。
このアルゴリズムは、入力グラフの最大重み付きマッチングを見つけ、以前の最良のアルゴリズムの完全な絡み合った出力状態よりも単純な、最大2量子ビット状態の積を出力する。
関連論文リスト
- A quantum advantage over classical for local max cut [48.02822142773719]
量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。
結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
論文 参考訳（メタデータ） (2023-04-17T16:42:05Z) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。
本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。
位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
論文 参考訳（メタデータ） (2023-02-07T10:57:36Z) - An Improved Approximation Algorithm for Quantum Max-Cut [0.0]
我々は、SDP緩和を絡み合った量子状態に丸めることによって動作するQuantum Max-Cutの近似アルゴリズムを提案する。
EPRハミルトニアンに対しては、全てのグラフに対して近似比1/sqrt2$の近似アルゴリズムを与える。
論文 参考訳（メタデータ） (2022-09-06T15:45:04Z) - 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) - An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians
with Positive Terms [3.553493344868414]
積状態を用いた量子マックスカット(QMC)問題の最大エネルギーの近似性について検討する。
半定値プログラミング緩和を用いた古典的な0.498近似はQMCで知られている。
非条件最適QMCに対して古典的1/2近似を与える。
論文 参考訳（メタデータ） (2022-06-16T17:44:52Z) - Quantum mean states are nicer than you think: fast algorithms to compute
states maximizing average fidelity [1.9336815376402714]
量子状態の任意の有限アンサンブル上での平均忠実度を最大化するという開問題を解く。
まず、最適値が最大平均忠実度である半定値プログラムを構築し、次に最適な状態に収束する不動点アルゴリズムを導出する。
我々はまた、アンサンブルの全ての状態が通勤するときに正確である最大平均忠実度に対して計算し易い準最適状態と上下境界の表現を導出する。
論文 参考訳（メタデータ） (2022-06-16T13:52:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳（メタデータ） (2020-09-23T08:33:18Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Beyond product state approximations for a quantum analogue of Max Cut [14.567067583556714]
目的が2局所ハミルトニアンの最大固有値を近似することを考える。
これまでの作業は、製品状態によるこの問題の近似性に光を当ててきた。
3 または 4 の正則グラフで定義される任意のインスタンスに対して、最高の積状態よりも大きいエネルギーを準備する効率的な計算可能な浅量子回路が存在することを示す。
論文 参考訳（メタデータ） (2020-03-31T17:41:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。