論文の概要: Classical algorithms for Forrelation
- arxiv url: http://arxiv.org/abs/2102.06963v2
- Date: Sun, 31 Oct 2021 16:26:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-11 06:08:08.929339
- Title: Classical algorithms for Forrelation
- Title（参考訳）: Forrelationのための古典的アルゴリズム
- Authors: Sergey Bravyi, David Gosset, Daniel Grier, and Luke Schaeffer
- Abstract要約: 1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。
この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。
グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
- 参考スコア（独自算出の注目度）: 2.624902795082451
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the forrelation problem: given a pair of $n$-bit Boolean functions
$f$ and $g$, estimate the correlation between $f$ and the Fourier transform of
$g$. This problem is known to provide the largest possible quantum speedup in
terms of its query complexity and achieves the landmark oracle separation
between the complexity class BQP and the Polynomial Hierarchy. Our first result
is a classical algorithm for the forrelation problem which has runtime
$O(n2^{n/2})$. This is a nearly quadratic improvement over the best previously
known algorithm. Secondly, we show that quantum query algorithm that makes $t$
queries to an $n$-bit oracle can be simulated by classical query algorithm
making only $O(2^{n(1-1/2t)})$ queries. This fixes a gap in the literature
arising from a recently discovered critical error in a previous proof; it
matches recently established lower bounds (up to $poly(n,t))$ factors) and thus
characterizes the maximal separation in query complexity between quantum and
classical algorithms. Finally, we introduce a graph-based forrelation problem
where $n$ binary variables live at vertices of some fixed graph and the
functions $f,g$ are products of terms describing interactions between
nearest-neighbor variables. We show that the graph-based forrelation problem
can be solved on a classical computer in time $O(n)$ for any bipartite graph,
any planar graph, or, more generally, any graph which can be partitioned into
two subgraphs of constant treewidth. The graph-based forrelation is simply
related to the variational energy achieved by the Quantum Approximate
Optimization Algorithm (QAOA) with two entangling layers and Ising-type cost
functions. By exploiting the connection between QAOA and the graph-based
forrelation we were able to simulate the recently proposed Recursive QAOA with
two entangling layers and $225$ qubits on a laptop computer.
- Abstract（参考訳）: 1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。
この問題は、クエリの複雑さの観点から最大の量子スピードアップを提供し、複雑性クラス BQP とポリノミアル階層の間のランドマークなオラクル分離を実現することが知られている。
最初の結果は、実行時$o(n2^{n/2})$を持つforrelation問題の古典的なアルゴリズムです。
これは、最もよく知られたアルゴリズムに対するほぼ二乗的な改善である。
次に、n$bit oracleに$t$クエリを作る量子クエリアルゴリズムは、$o(2^{n(1-1/2t)})$クエリしか生成しない古典的なクエリアルゴリズムによってシミュレートできることを示す。
これは、先述の証明で最近発見された臨界誤差から生じる文献のギャップを解消し、最近確立された下界($poly(n,t))$ factor)と一致し、量子アルゴリズムと古典アルゴリズムの間のクエリ複雑性の最大分離を特徴付ける。
最後に、n$バイナリ変数が固定グラフの頂点に存在し、関数$f,g$が最寄り-neighbor変数間の相互作用を記述する用語の積であるグラフベースのforrelation問題を導入する。
グラフに基づく回帰問題は、任意の二部グラフ、任意の平面グラフ、あるいはより一般的には、定数木幅の2つの部分グラフに分割できるグラフに対して、古典的なコンピュータ上で時間$O(n)$で解けることを示す。
グラフに基づくforrelationは、2つの絡み合う層とイジング型コスト関数を持つ量子近似最適化アルゴリズム(qaoa)によって達成された変動エネルギーと単純に関係している。
qaoaとグラフベースの相関の関係を利用することで、最近提案された再帰的なqaoaを、2つの絡み合う層とラップトップコンピュータ上の225ドルのキュービットでシミュレートすることができた。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳（メタデータ） (2023-06-23T01:28:24Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。