論文の概要: Linear-time classical approximate optimization of cubic-lattice classical spin glasses
- arxiv url: http://arxiv.org/abs/2501.17267v4
- Date: Wed, 12 Feb 2025 23:33:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-14 13:44:34.587554
- Title: Linear-time classical approximate optimization of cubic-lattice classical spin glasses
- Title（参考訳）: 立方格子古典スピングラスの線形時間古典近似最適化
- Authors: Adil A. Gangat,
- Abstract要約: 短距離古典スピングラスは線形時間とテンソル-ネットワーク空間で概ね最適化可能であることを示す。
我々のアルゴリズムは大規模並列化に適しており、フォトニック行列乗算ハードウェアによる低消費電力で高速化された実装も可能である。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Computing low-energy configurations (i.e., approximate optimization) of classical spin glasses is of relevance to both condensed matter and combinatorial optimization. Recent theoretical work opens the possibility to make its time complexity with quantum annealing generically polynomial, and D-Wave experiments can now achieve approximate optimization of cubic-lattice classical Ising spin glasses with $\sim$$10^4$ spins. It is therefore timely to ask which short-range classical spin glasses are good candidates for demonstrating quantum advantage in the time complexity of heuristic approximate optimization. One intuition is to consider models with very rugged energy landscapes in configuration space. However, here we provide evidence that short-range classical spin glasses may be approximately optimized in linear time and space with a very simple deterministic tensor-network heuristic regardless of ruggedness. On the cubic lattice with up to 50$\times$50$\times$50 spins, we obtain energy errors of $\lesssim$3% for the $\pm J$ model used in recent D-Wave experiments, and $\lesssim$5% for much more rugged planted-solution instances. For cubic-lattice-Ising reductions of unweighted Max-Cut on random 3-regular graphs with up to 300 vertices, we find energy errors of $<$1% and approximation ratios of about 72-88%. A theoretical implication of our algorithm is that only quantum algorithms with sublinear time complexity may have time-complexity quantum advantage for heuristic approximate optimization of classical spin glasses that have decaying correlations. These results inform the search for quantum advantage and suggest an efficient classical method for generating warm starts for other spin-glass optimization algorithms. Our algorithm is amenable to massive parallelization and may also allow for low-power, accelerated implementations with photonic matrix-multiplication hardware.
- Abstract（参考訳）: 古典的スピングラスの低エネルギー構成(すなわち近似最適化)の計算は、凝縮物質と組合せ最適化の両方に関係している。
近年の理論的研究は、量子アニーリング一般多項式による時間複雑性の可能性を開放し、D-Wave実験は、$\sim$10^4$のスピンを持つ立方格子古典イジングスピングラスの近似的な最適化を達成できるようになった。
したがって、時間的近似最適化の時間的複雑さにおいて、どの短距離古典スピングラスが量子優位性を示す良い候補であるかを問うのがタイミングである。
直観の1つは、構成空間における非常に頑丈なエネルギー景観を持つモデルを考えることである。
しかし、ここでは、短距離古典スピングラスが、粗さに関係なく非常に単純な決定論的テンソルネットワークヒューリスティックで線形時間と空間で概ね最適化されていることを示す。
50$\times$50$\times$50スピンの立方体格子上では、最近のD-Wave実験で用いられる$\pm J$モデルに対して$\lesssim$3%のエネルギー誤差と、より頑丈な植民溶液の場合$\lesssim$5%のエネルギー誤差が得られる。
最大300頂点を持つランダムな3つの正則グラフ上の非重み付きMax-Cutの立方体格子イジング還元に対して、エネルギー誤差は$<1%、近似比は約72-88%である。
我々のアルゴリズムの理論的意味は、線形時間複雑性を持つ量子アルゴリズムだけが、崩壊相関を持つ古典的スピングラスのヒューリスティック近似最適化に時間複雑性を持つ可能性があるということである。
これらの結果は量子的優位性を探究し、他のスピングラス最適化アルゴリズムに対して、ウォームスタートを生成するための効率的な古典的手法を提案する。
我々のアルゴリズムは大規模並列化に適しており、フォトニック行列乗算ハードウェアによる低消費電力で高速化された実装も可能である。
関連論文リスト
- Exponentially Better Bounds for Quantum Optimization via Dynamical Simulation [0.5097809301149342]
我々は、勾配推定を必要としない連続的な最適化のために、いくつかの量子アルゴリズムを提供する。
我々は、最適化問題を物理系の力学にエンコードし、時間進化をコヒーレントにシミュレートする。
論文 参考訳（メタデータ） (2025-02-06T18:32:26Z) - Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs [0.8192907805418583]
重ヘックスグラフ上のイジングモデルは、経験的時間スケーリングにより古典的な計算硬度について検討する。
これらのイジングモデルの空間性のため、古典的アルゴリズムは大規模インスタンスに対しても効率的に最適解を見つけることができる。
論文 参考訳（メタデータ） (2024-12-20T05:09:30Z) - 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin
Models [8.463477025989542]
我々は、デジタルカウンタダイバティック量子最適化(DCQO)アルゴリズムを利用して、4つの局所相互作用までの$p$-spinモデルの最適解を求める。
変分法を用いてパラメータを最適化することにより,それぞれ100ドル,93%,83%のインスタンスに対して,単位精度2-スピン,3-スピン,4-スピンの問題を解く。
論文 参考訳（メタデータ） (2023-11-11T22:49:16Z) - A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。
一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
論文 参考訳（メタデータ） (2023-11-01T19:51:00Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。