Related papers: Quantum advantage through the magic pentagram problem

Quantum advantage through the magic pentagram problem

URL: http://arxiv.org/abs/2209.15188v1
Date: Fri, 30 Sep 2022 02:29:28 GMT
Title: Quantum advantage through the magic pentagram problem
Authors: Haesol Han, Jeonghyeon Shin, Minjin Choi, Byung Chan Kim, Soojoon Lee
Abstract summary: We show that the problem can be solved with certainty by a $mathbfQNC0$ circuit but not by any $mathbfNC0$ circuits.
Score: 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.

Related papers

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
arXiv Detail & Related papers (2024-10-26T06:21:42Z)
Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
We study classes of constant-depth circuits with bounds that compute restricted threshold functions. For large enough values of $mathsfbPTFC0[k]$, $mathsfbPTFC0[k] contains $mathsfTC0[k].
arXiv Detail & Related papers (2024-08-29T09:40:55Z)
Provably learning a multi-head attention layer [55.2904547651831]
Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
arXiv Detail & Related papers (2024-02-06T15:39:09Z)
Parity vs. AC0 with simple quantum preprocessing [0.0]
We study a hybrid circuit model where $mathsfAC0$ operates on measurement outcomes of a $mathsfQNC0$ circuit. We find that while $mathsfQNC0$ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output.
arXiv Detail & Related papers (2023-11-22T20:27:05Z)
On the Pauli Spectrum of QAC0 [2.3436632098950456]
We conjecture that the Pauli spectrum of $mathsfQAC0$ satisfies low-degree concentration. We obtain new circuit lower bounds and learning results as applications.
arXiv Detail & Related papers (2023-11-16T07:25:06Z)
A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
arXiv Detail & Related papers (2023-08-28T18:12:54Z)
Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
We study the complexity of PAC learning halfspaces in the presence of Massart noise. We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
arXiv Detail & Related papers (2022-07-28T17:50:53Z)
The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
We show that there are no better-than-brute-force algorithms for the problem. We also show the impossibility of better-than-brute-force algorithms when the prediction error is measured.
arXiv Detail & Related papers (2021-06-06T14:19:43Z)
Linear Bandits on Uniformly Convex Sets [88.3673525964507]
Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
arXiv Detail & Related papers (2021-03-10T07:33:03Z)
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
We study the quantum query complexity of two problems. We consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of $Omega(n1.5-epsilon)$ for the directed 2D grid and $Omega(n2-epsilon)$ for the undirected 2D grid.
arXiv Detail & Related papers (2020-07-06T09:51:41Z)
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
We consider non-con minimax problems, $min_mathbfx max_mathhidoty f(mathbfdoty)$ efficiently.
arXiv Detail & Related papers (2019-06-02T03:03:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.