論文の概要: 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}$回路では解くことができない。
関連論文リスト
- 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.5602836891933074]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々はこの予想を、少なくとも$nO(1/d)$補助量子ビットを持つ深さ-d$,-size $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) - Irreducible magic sets for $n$-qubit systems [0.0]
観測可能なマジックセットは、$nge 2$ qubitsのシステムに対して量子状態に依存しない利点をキャプチャする。
オープンな疑問は、正方形やペンタグラムに還元できないマジックセットが存在するかどうかである。
正方形や五角形に還元できないマジックセットを識別するには、n=3,4,5$、または6$ qubitsが必要である。
論文 参考訳(メタデータ) (2022-02-26T13:35:18Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。