Parity vs. AC0 with simple quantum preprocessing
- URL: http://arxiv.org/abs/2311.13679v2
- Date: Wed, 29 Nov 2023 21:04:47 GMT
- Title: Parity vs. AC0 with simple quantum preprocessing
- Authors: Joseph Slote
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A recent line of work has shown the unconditional advantage of constant-depth
quantum computation, or $\mathsf{QNC^0}$, over $\mathsf{NC^0}$,
$\mathsf{AC^0}$, and related models of classical computation. Problems
exhibiting this advantage include search and sampling tasks related to the
parity function, and it is natural to ask whether $\mathsf{QNC^0}$ can be used
to help compute parity itself. We study $\mathsf{AC^0\circ QNC^0}$ -- a hybrid
circuit model where $\mathsf{AC^0}$ operates on measurement outcomes of a
$\mathsf{QNC^0}$ circuit, and conjecture $\mathsf{AC^0\circ QNC^0}$ cannot
achieve $\Omega(1)$ correlation with parity. As evidence for this conjecture,
we prove:
$\bullet$ When the $\mathsf{QNC^0}$ circuit is ancilla-free, this model
achieves only negligible correlation with parity.
$\bullet$ For the general (non-ancilla-free) case, we show via a connection
to nonlocal games that the conjecture holds for any class of postprocessing
functions that has approximate degree $o(n)$ and is closed under restrictions,
even when the $\mathsf{QNC^0}$ circuit is given arbitrary quantum advice. By
known results this confirms the conjecture for linear-size $\mathsf{AC^0}$
circuits.
$\bullet$ Towards a switching lemma for $\mathsf{AC^0\circ QNC^0}$, we study
the effect of quantum preprocessing on the decision tree complexity of Boolean
functions. We find that from this perspective, nonlocal channels are no better
than randomness: a Boolean function $f$ precomposed with an $n$-party nonlocal
channel is together equal to a randomized decision tree with worst-case depth
at most $\mathrm{DT}_\mathrm{depth}[f]$.
Our results suggest that while $\mathsf{QNC^0}$ is surprisingly powerful for
search and sampling tasks, that power is "locked away" in the global
correlations of its output, inaccessible to simple classical computation for
solving decision problems.
Related papers
- 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) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n.
We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
arXiv Detail & Related papers (2022-09-04T10:01:39Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
arXiv Detail & Related papers (2022-03-17T23:52:08Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals.
Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
arXiv Detail & Related papers (2021-08-19T16:16:48Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
We establish the first general connection between the design of quantum algorithms and circuit lower bounds.
Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
arXiv Detail & Related papers (2020-12-03T14:03:20Z) - Degree vs. Approximate Degree and Quantum Implications of Huang's
Sensitivity Theorem [4.549831511476248]
We show that for any total Boolean function $f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$: The degree of $f$ is at mosttrivial quadratic in the approximate degree of $f$.
We show that if $f$ is a non monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $mathrmQ(f)=Omega(n)$, which is also optimal.
arXiv Detail & Related papers (2020-10-23T19:21:28Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
For a quantum circuit $C$ on $n$ qubits and a sample $z in 0,1n$, the benchmark involves computing $|langle z|C|0n rangle|2$.
We show that for any $varepsilon ge frac1mathrmpoly(n)$, outputting a sample $z$ is the optimal 1-query for $|langle z|C|0nrangle|2$ on average.
arXiv Detail & Related papers (2020-08-20T01:04:32Z) - On the complexity of zero gap MIP* [0.11470070927586014]
We show that the class $mathsfMIP*$ is equal to $mathsfRE$.
In particular this shows that the complexity of approximating the quantum value of a non-local game $G$ is equivalent to the complexity of the Halting problem.
arXiv Detail & Related papers (2020-02-24T19:11:01Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.