論文の概要: Beyond product state approximations for a quantum analogue of Max Cut
- arxiv url: http://arxiv.org/abs/2003.14394v1
- Date: Tue, 31 Mar 2020 17:41:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-27 07:32:28.633610
- Title: Beyond product state approximations for a quantum analogue of Max Cut
- Title（参考訳）: マックスカットの量子アナログに対する積状態近似を超えて
- Authors: Anurag Anshu, David Gosset, Karen Morenz
- Abstract要約: 目的が2局所ハミルトニアンの最大固有値を近似することを考える。
これまでの作業は、製品状態によるこの問題の近似性に光を当ててきた。
3 または 4 の正則グラフで定義される任意のインスタンスに対して、最高の積状態よりも大きいエネルギーを準備する効率的な計算可能な浅量子回路が存在することを示す。
- 参考スコア（独自算出の注目度）: 14.567067583556714
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a computational problem where the goal is to approximate the
maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg
interactions between qubits located at the vertices of a graph. Previous work
has shed light on this problem's approximability by product states. For any
instance of this problem the maximum energy attained by a product state is
lower bounded by the Max Cut of the graph and upper bounded by the standard
Goemans-Williamson semidefinite programming relaxation of it. Gharibian and
Parekh described an efficient classical approximation algorithm for this
problem which outputs a product state with energy at least 0.498 times the
maximum eigenvalue in the worst case, and observe that there exist instances
where the best product state has energy 1/2 of optimal. We investigate
approximation algorithms with performance exceeding this limitation which are
based on optimizing over tensor products of few-qubit states and shallow
quantum circuits. We provide an efficient classical algorithm which achieves an
approximation ratio of at least 0.53 in the worst case. We also show that for
any instance defined by a 3- or 4-regular graph, there is an efficiently
computable shallow quantum circuit that prepares a state with energy larger
than the best product state (larger even than its semidefinite programming
relaxation).
- Abstract（参考訳）: グラフの頂点に位置する量子ビット間のハイゼンベルク相互作用を記述する2局所ハミルトニアンの最大固有値を近似することを目的とする計算問題を考える。
これまでの作業は、製品状態によるこの問題の近似性に光を当ててきた。
この問題の任意の例において、積状態によって達成される最大エネルギーはグラフの最大カットによってより低く、標準のゴーマンス・ウィリアムソン半定値プログラミング緩和によって上限される。
gharibian と parekh は、最悪の場合において最大固有値の少なくとも 0.498 倍のエネルギーを持つ積状態を出力するこの問題の効率的な古典近似アルゴリズムを記述し、最高の積状態が最適エネルギー 1/2 を持つような例が存在することを観察する。
数量子状態と浅量子回路のテンソル積の最適化に基づく,この制限を超える性能を持つ近似アルゴリズムについて検討する。
最悪の場合、少なくとも 0.53 の近似比を達成する効率的な古典アルゴリズムを提供する。
また、3 または 4 の正則グラフで定義される任意のインスタンスに対して、最高の積状態(半定値プログラミング緩和よりも大きい)よりも大きいエネルギーの状態を準備する効率的な計算可能な浅量子回路が存在することを示す。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - An improved Quantum Max Cut approximation via matching [0.10878040851638002]
最近の研究の行は量子マックスカット(英語版)に焦点を当てており、そこでは与えられた反強磁性ハイゼンベルク・ハミルトンの高エネルギー状態を見つけるよう求められている。
一般的な入力に対して0.584の近似比を達成する量子マックスカットの古典的近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-08T00:36:32Z) - 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) - A Quantum Optimal Control Problem with State Constrained Preserving
Coherence [68.8204255655161]
非単体脱コヒーレンスチャネルを特徴とするマルコフ脱コヒーレンスを受ける3レベル$Lambda$型原子を考える。
我々は、デコヒーレンスレベルが予め定義された境界内にある状態制約で量子最適制御問題を定式化する。
論文 参考訳（メタデータ） (2022-03-24T21:31:34Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Optimizing Strongly Interacting Fermionic Hamiltonians [2.1756081703276]
物理学と量子化学の多くの基本的な問題は、ある種の反交換変数の低次を最適化することである。
特筆すべき例外は、最適化がいわゆる「ガウス状態」によって記述されるときであり、自由フェルミオン状態(free fermion state)とも呼ばれる。
我々は、$q=4$SYKモデルで最大固有値を上界化するための効率的な古典的証明アルゴリズムと、この最大固有値を下界化するための効率的な量子認証アルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-10-20T18:00:17Z) - Direct Optimal Control Approach to Laser-Driven Quantum Particle
Dynamics [77.34726150561087]
間接制御理論に対する頑健で柔軟な代替手段として, 直接最適制御を提案する。
この方法は、バイスタブルポテンシャルにおけるレーザー駆動のウェーブパレットダイナミクスの場合に説明される。
論文 参考訳（メタデータ） (2020-10-08T07:59:29Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳（メタデータ） (2020-09-23T08:33:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。