論文の概要: On the approximability of random-hypergraph MAX-3-XORSAT problems with
quantum algorithms
- arxiv url: http://arxiv.org/abs/2312.06104v2
- Date: Tue, 23 Jan 2024 04:33:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-24 18:43:27.086177
- 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$となる。
シミュレーションにおけるランダム近似ハード(プラントド・ソリューション)インスタンスに対するスペクトル折り畳み量子最適化のパラメータ変動を徹底的にベンチマークし、この予測と一致した性能を求める。
我々は、この近似保証がすべての可能なハイパーグラフに対して成り立つとは主張しないが、アルゴリズムのメカニズムは広く一般化することができる。
これらの結果は、量子コンピュータが以前想定されていたよりも近似最適化に強力であることを示唆している。
関連論文リスト
- When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳(メタデータ) (2023-12-18T18:29:01Z) - A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。
一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
論文 参考訳(メタデータ) (2023-11-01T19:51:00Z) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳(メタデータ) (2022-03-11T17:19:26Z) - Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。
本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。
これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
論文 参考訳(メタデータ) (2022-03-09T19:00:00Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - 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) - Training variational quantum algorithms is NP-hard [0.7614628596146599]
古典最適化の問題はNPハードであることが示される。
対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。
論文 参考訳(メタデータ) (2021-01-18T19:00:01Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳(メタデータ) (2020-12-11T08:28:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。