論文の概要: Distributed Quantum Advantage for Local Problems
- arxiv url: http://arxiv.org/abs/2411.03240v1
- Date: Tue, 05 Nov 2024 16:38:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-06 14:58:14.140713
- Title: Distributed Quantum Advantage for Local Problems
- Title（参考訳）: 局所問題に対する分散量子アドバンテージ
- Authors: Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren,
- Abstract要約: 分散コンピューティングの古典的ランダム化LOCALモデルと,その量子的モデルとの超コンスタントな分離を示す。
本稿では,局所的制約のみを用いて定義した反復GHZ問題を提案する。
- 参考スコア（独自算出の注目度）: 3.1024627815534593
- License:
- Abstract: We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree $\Delta$, any classical (deterministic or randomized) LOCAL model algorithm will require $\Omega(\Delta)$ rounds to solve the iterated GHZ problem, while the problem can be solved in $1$ round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires $\Omega(\Delta)$ rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.
- Abstract（参考訳）: 本稿では,分散コンピューティングの古典的ランダム化LOCALモデルと,その量子的モデルとの超コンスタントな分離を示す最初の局所問題を示す。
以前の研究では、このような分離は本質的にグローバルな定義を持つ人工グラフ問題 [Le Gall et al 2019] でのみ知られていた。
本稿では,局所的制約のみを用いて定義した反復GHZ問題を提案する。
形式的には、局所チェック可能なラベリング問題(Naor and Stockmeyer 1995)のファミリーであり、特に、定ラウンド分散アルゴリズムで解を検証できる。
最大次数$\Delta$のグラフでは、古典的(決定論的またはランダム化)なLOCALモデルアルゴリズムは繰り返しGHZ問題を解決するために$\Omega(\Delta)$ラウンドを必要とするが、量子LOCALでは1ドルで解ける。
我々はこのラウンド除去手法を用いて、古典アルゴリズムの繰り返しGHZ問題に$\Omega(\Delta)$ラウンドが必要であることを証明している。
これは、円の除去が実際に2つのモデルを分離できることを示す最初の研究であり、また、円の除去が量子LOCALの下位境界を証明するために使用できないことも示している。
本手法は, 繰り返しGHZ問題の範囲を超えて, 最大マッチング(FOCS 2019, PODC 2020)の事前結果を体系的に再現することができる。
関連論文リスト
- Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
パラメタライズド量子ゲートのツリー配置を導入し、1ラウンド$i$HVAを用いて任意のツリーグラフを正確に解けるようにする。
我々のアンサッツは、最大24ノードと$D leq 5$のグラフに対して、MaxCutを正確に解く。
論文 参考訳（メタデータ） (2024-08-17T03:34:17Z) - 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) - Online Locality Meets Distributed Quantum Computing [2.3821076274208552]
分散コンピューティングの古典的なLOCALモデルの拡張について、3行の研究が最近行われた。
局所チェック可能なラベリング問題(LCL)に対するこれらのモデルの機能と制限に関する新しい結果が証明された。
我々の研究は、分散環境での利点の限界を示唆しており、より厳密な境界を示すための新たな障壁も示しています。
論文 参考訳（メタデータ） (2024-03-04T10:03:54Z) - A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical
Initialization [107.07093621337084]
正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。
1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。
有名な座標降下法に基づく新しいN-Cut解法を提案する。
論文 参考訳（メタデータ） (2023-11-26T07:11:58Z) - Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
Algorithm [77.53604156112144]
我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。
非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
論文 参考訳（メタデータ） (2023-10-19T13:57:38Z) - Local to Global: A Distributed Quantum Approximate Optimization
Algorithm for Pseudo-Boolean Optimization Problems [7.723735038335632]
量子近似最適化アルゴリズム(QAOA)は、量子超越性を実証するための有望な候補と考えられている。
量子ビットの可用性が制限され、コヒーレンス時間制限がQAOAに挑戦し、大規模な擬ブール問題を解く。
本稿では,これを単純化したIsingモデルに変換することで,一般の擬似ブール問題を解く分散QAOAを提案する。
論文 参考訳（メタデータ） (2023-10-08T08:07:11Z) - No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
分散アルゴリズムを用いた$c$-coloring $chi$-chromatic graphの難易度を,ほぼ完全に評価する。
これらの問題は、分散量子の優位性を認めないことを示している。
論文 参考訳（メタデータ） (2023-07-18T17:17:27Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳（メタデータ） (2020-09-23T08:33:18Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。