論文の概要: On the approximability of random-hypergraph MAX-3-XORSAT problems with
quantum algorithms
- arxiv url: http://arxiv.org/abs/2312.06104v1
- Date: Mon, 11 Dec 2023 04:15:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-12 17:06:00.374007
- Title: On the approximability of random-hypergraph MAX-3-XORSAT problems with
quantum algorithms
- Title（参考訳）: 量子アルゴリズムを用いたランダムハイパーグラフMAX-3-XORSAT問題の近似性について
- Authors: Eliot Kapit, Brandon A. Barton, Sean Feeney, George Grattan, Pratik
Patnaik, Jacob Sagal, Lincoln D. Carr, and Vadim Oganesyan
- Abstract要約: ハミルトン時間進化に基づく量子アルゴリズムにおける近似硬さの直感的なメカニズムはよく理解されていない。
これらの問題に支障を来さない新しいスペクトル畳み込み最適化法を提案する。
エネルギーを$E = N_unsat-N_sat$と定義すれば、スペクトル的に折り畳まれた量子最適化はエネルギー$E leq Aを持つ状態を返す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Constraint satisfaction problems are an important area of computer science.
Many of these problems are in the complexity class NP which is exponentially
hard for all known methods, both for worst cases and often typical.
Fundamentally, the lack of any guided local minimum escape method ensures the
hardness of both exact and approximate optimization classically, but the
intuitive mechanism for approximation hardness in quantum algorithms based on
Hamiltonian time evolution is poorly understood. We explore this question using
the prototypically hard MAX-3-XORSAT problem class. We conclude that the
mechanisms for quantum exact and approximation hardness are fundamentally
distinct. We qualitatively identify why traditional methods such as quantum
adiabatic optimization are not good approximation algorithms. We propose a new
spectral folding optimization method that does not suffer from these issues and
study it analytically and numerically. We consider random rank-3 hypergraphs
including extremal planted solution instances, where the ground state satisfies
an anomalously high fraction of constraints compared to truly random problems.
We show that, if we define the energy to be $E = N_{unsat}-N_{sat}$, then
spectrally folded quantum optimization will return states with energy $E \leq A
E_{GS}$ (where $E_{GS}$ is the ground state energy) in polynomial time, where
conservatively, $A \simeq 0.6$. We thoroughly benchmark variations of
spectrally folded quantum optimization for random classically
approximation-hard (planted solution) instances in simulation, and find
performance consistent with this prediction. We do not claim that this
approximation guarantee holds for all possible hypergraphs, though our
algorithm's mechanism can likely generalize widely. These results suggest that
quantum computers are more powerful for approximate optimization than had been
previously assumed.
- Abstract（参考訳）: 制約満足度問題はコンピュータ科学の重要な分野である。
これらの問題の多くは、最悪の場合と典型的には、すべての既知の方法において指数関数的に難しい複雑性クラスNPにある。
基本的には、誘導された局所的最小脱出法の欠如は、厳密な最適化と近似的最適化の両方のハードネスを古典的に保証するが、ハミルトニアン時間発展に基づく量子アルゴリズムの近似ハードネスの直感的なメカニズムはあまり理解されていない。
我々は,max-3-xorsat問題クラスを用いてこの問題を考察する。
量子完全性と近似硬さのメカニズムは基本的に異なると結論づける。
量子断熱最適化のような従来の手法が良い近似アルゴリズムでない理由を定性的に同定する。
これらの問題に支障を来さない新しいスペクトル折り畳み最適化法を提案し,解析的および数値的に検討する。
基底状態が真のランダム問題と比較して異常な割合の制約を満たすような,極端に植栽された解インスタンスを含むランダムランク3ハイパーグラフを考える。
エネルギーを$E = N_{unsat}-N_{sat}$と定義すると、スペクトル的に折り畳まれた量子最適化はエネルギー$E \leq A E_{GS}$(ここでは$E_{GS}$は基底状態エネルギー)を多項式時間で返し、保守的に$A \simeq 0.6$となる。
シミュレーションにおけるランダム近似ハード(プラントド・ソリューション)インスタンスに対するスペクトル折り畳み量子最適化のパラメータ変動を徹底的にベンチマークし、この予測と一致した性能を求める。
我々は、この近似保証がすべての可能なハイパーグラフに対して成り立つとは主張しないが、アルゴリズムのメカニズムは広く一般化することができる。
これらの結果は、量子コンピュータが以前想定されていたよりも近似最適化に強力であることを示唆している。
関連論文リスト
- 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) - A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。
一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
論文 参考訳（メタデータ） (2023-11-01T19:51:00Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - The Quantum Approximate Optimization Algorithm performance with low
entanglement and high circuit depth [0.0]
変分量子アルゴリズムは、現在の雑音量子コンピュータを使用する最も広範な方法の1つである。
最適化問題の解法における絡み合いの役割について検討する。
ここでは, 絡み合いが MaxCut と Exact Cover 3 問題において軽微な役割を担っていると結論づける。
論文 参考訳（メタデータ） (2022-07-07T16:21:36Z) - 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) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。
本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。
これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
論文 参考訳（メタデータ） (2022-03-09T19:00:00Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian
Problems [3.553493344868414]
k-局所ハミルトン問題は古典的制約満足問題(k-CSP)の一般化である
極大絡み合いのインスタンスである厳密な二次インスタンスに対しては、古典的な 0.764 時間 0.764 近似を提供する。
これらは近似するのが最も難しい例であると推測する。
我々の研究は、最近開発されたCSPの古典近似解析技術を採用しており、量子情報科学者と古典計算機科学者の両方にアクセスできることを意図している。
論文 参考訳（メタデータ） (2020-12-22T20:41:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。