論文の概要: A quantum-classical performance separation in nonconvex optimization
- arxiv url: http://arxiv.org/abs/2311.00811v1
- Date: Wed, 1 Nov 2023 19:51:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-03 15:40:26.524660
- Title: A quantum-classical performance separation in nonconvex optimization
- Title(参考訳): 非凸最適化における量子古典的性能分離
- Authors: Jiaqi Leng, Yufan Zheng, Xiaodi Wu
- Abstract要約: 我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。
一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
- 参考スコア(独自算出の注目度): 7.427989325451079
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we identify a family of nonconvex continuous optimization
instances, each $d$-dimensional instance with $2^d$ local minima, to
demonstrate a quantum-classical performance separation. Specifically, we prove
that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et
al., arXiv:2303.01471] is able to solve any $d$-dimensional instance from this
family using $\widetilde{\mathcal{O}}(d^3)$ quantum queries to the function
value and $\widetilde{\mathcal{O}}(d^4)$ additional 1-qubit and 2-qubit
elementary quantum gates. On the other side, a comprehensive empirical study
suggests that representative state-of-the-art classical optimization
algorithms/solvers (including Gurobi) would require a super-polynomial time to
solve such optimization instances.
- Abstract(参考訳): 本稿では、量子古典的性能分離を示すために、各$d$-dimensionalインスタンスと2^d$ローカルミニマの非凸連続最適化インスタンスの族を同定する。
具体的には、最近提案された量子ハミルトン Descent (QHD) アルゴリズム [Leng et al., arXiv:2303.01471] が、関数値への$\widetilde{\mathcal{O}}(d^3)$量子クエリと$\widetilde{\mathcal{O}}(d^4)$追加の1-qubitおよび2-qubit基本量子ゲートを用いて、このファミリーから$d$次元の任意のインスタンスを解くことができることを証明している。
一方、総合的な実証研究により、従来の最適化アルゴリズム/解法(グロビを含む)はそのような最適化を解くのに超多項式時間を必要とすることが示唆されている。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with
quantum algorithms [0.0]
ハミルトン時間進化に基づく量子アルゴリズムにおける近似硬さの直感的なメカニズムはよく理解されていない。
これらの問題に支障を来さない新しいスペクトル畳み込み最適化法を提案する。
エネルギーを$E = N_unsat-N_sat$と定義すれば、スペクトル的に折り畳まれた量子最適化はエネルギー$E leq Aを持つ状態を返す。
論文 参考訳(メタデータ) (2023-12-11T04:15:55Z) - Generalized Quantum Signal Processing [0.6768558752130311]
本稿では、一般的なSU(2)回転を信号処理演算子として用いた一般化量子信号処理手法を提案する。
我々のアプローチは、達成可能な変換の族に対するすべての実用的な制限を持ち上げ、残りの唯一の条件は、$|P|leq 1$である。
P$しか知られていない場合、我々は1分以内で識別できる効率的なGPU最適化を提供し、それに対応する$Q$は107$である。
論文 参考訳(メタデータ) (2023-08-03T01:51:52Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Quantum Lower Bounds for Finding Stationary Points of Nonconvex
Functions [8.495749905129278]
非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。
最初の設定について、Omegabig(frac-1+ppp)$。
第二設定については、おめがの()$。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
論文 参考訳(メタデータ) (2022-12-07T19:02:36Z) - 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) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Quantum algorithms for approximate function loading [0.0]
我々は,Grover-RudolphアルゴリズムにインスパイアされたNISQ時代の量子状態生成法を2つ導入した。
上述の滑らかさ条件を超えて関数をロードできる変分アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-11-15T17:36:13Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳(メタデータ) (2021-08-03T17:49:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。