Fugu-MT 論文翻訳(概要): Quantum advantage through the magic pentagram problem

論文の概要: Quantum advantage through the magic pentagram problem

arxiv url: http://arxiv.org/abs/2209.15188v1
Date: Fri, 30 Sep 2022 02:29:28 GMT
ステータス: 処理完了
システム内更新日: 2023-01-24 07:52:53.555253
Title: Quantum advantage through the magic pentagram problem
Title（参考訳）: マジックペンタグラム問題による量子優位性
Authors: Haesol Han, Jeonghyeon Shin, Minjin Choi, Byung Chan Kim, Soojoon Lee
Abstract要約: この問題は$mathbfQNC0$の回路で解けるが、$mathbfNC0$の回路では解けない。
参考スコア（独自算出の注目度）: 3.1161346038764526
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Through the two specific problems, the 2D hidden linear function problem and the 1D magic square problem, Bravyi et al. have recently shown that there exists a separation between $\mathbf{QNC^0}$ and $\mathbf{NC^0}$, where $\mathbf{QNC^0}$ and $\mathbf{NC^0}$ are the classes of polynomial-size and constant-depth quantum and classical circuits with bounded fan-in gates, respectively. In this paper, we present another problem with the same property, the magic pentagram problem based on the magic pentagram game, which is a nonlocal game. In other words, we show that the problem can be solved with certainty by a $\mathbf{QNC^0}$ circuit but not by any $\mathbf{NC^0}$ circuits.
Abstract（参考訳）: 2d隠れ線形関数問題(英語版)と1dマジック正方問題(英語版)であるbravyiらは最近、$\mathbf{qnc^0}$と$\mathbf{nc^0}$と$\mathbf{qnc^0}$と$\mathbf{nc^0}$の分離が存在することを示した。本稿では,非ローカルゲームであるマジックペンタグラムゲームに基づくマジックペンタグラム問題という,同じ性質の別の問題を提案する。言い換えると、問題は$\mathbf{qnc^0}$回路によって確実に解くことができるが、$\mathbf{nc^0}$回路では解くことができない。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文参考訳（メタデータ） (2024-08-29T09:40:55Z)
Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文参考訳（メタデータ） (2024-02-06T15:39:09Z)
Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文参考訳（メタデータ） (2023-11-22T20:27:05Z)
On the Pauli Spectrum of QAC0 [2.3436632098950456]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。我々は新しい回路の低境界と学習結果を応用として得る。
論文参考訳（メタデータ） (2023-11-16T07:25:06Z)
A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-08-28T18:12:54Z)
Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文参考訳（メタデータ） (2022-07-28T17:50:53Z)
The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
論文参考訳（メタデータ） (2021-06-06T14:19:43Z)
Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文参考訳（メタデータ） (2021-03-10T07:33:03Z)
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
2つの問題の量子クエリ複雑性について検討する。グリッドのエッジのいくつかが欠落している場合、グリッドグラフ上の2次元の接続問題を考える。平衡括弧」問題をグリッドに埋め込むことで、有向2Dグリッドに対して$Omega(n1.5-epsilon)$、無向2Dグリッドに対して$Omega(n2-epsilon)$の低い境界を示す。
論文参考訳（メタデータ） (2020-07-06T09:51:41Z)
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文参考訳（メタデータ） (2019-06-02T03:03:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。