Bounds on the QAC$^0$ Complexity of Approximating Parity
- URL: http://arxiv.org/abs/2008.07470v3
- Date: Mon, 30 Nov 2020 10:19:07 GMT
- Title: Bounds on the QAC$^0$ Complexity of Approximating Parity
- Authors: Gregory Rosenthal
- Abstract summary: We prove that QAC circuits of sublogarithmic depth can approximate parity regardless of size.
QAC circuits require at least $Omega(n/d)$ multi-qubit gates to achieve a $1/2 + exp(-o(n/d))$ approximation of parity.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of
arbitrary arity. QAC$^0$ circuits are QAC circuits of constant depth, and are
quantum analogues of AC$^0$ circuits. We prove the following:
$\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ QAC
circuit of size $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))$ that
approximates the $n$-qubit parity function to within error $\varepsilon$ on
worst-case quantum inputs. Previously it was unknown whether QAC circuits of
sublogarithmic depth could approximate parity regardless of size.
$\bullet$ We introduce a class of "mostly classical" QAC circuits, including
a major component of our circuit from the above upper bound, and prove a tight
lower bound on the size of low-depth, mostly classical QAC circuits that
approximate this component.
$\bullet$ Arbitrary depth-$d$ QAC circuits require at least $\Omega(n/d)$
multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity.
When $d = \Theta(\log n)$ this nearly matches an easy $O(n)$ size upper bound
for computing parity exactly.
$\bullet$ QAC circuits with at most two layers of multi-qubit gates cannot
achieve a $1/2 + \exp(-o(n))$ approximation of parity, even non-cleanly.
Previously it was known only that such circuits could not cleanly compute
parity exactly for sufficiently large $n$.
The proofs use a new normal form for quantum circuits which may be of
independent interest, and are based on reductions to the problem of
constructing certain generalizations of the cat state which we name "nekomata"
after an analogous cat y\=okai.
Related papers
- A shortcut to an optimal quantum linear system solver [55.2480439325792]
We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques.
If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel.
Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
arXiv Detail & Related papers (2024-06-17T20:54:11Z) - The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
One of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically.
We prove new separations between classical and quantum constant-depth circuits.
In the infinite-size gateset case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
arXiv Detail & Related papers (2024-04-28T07:44:27Z) - 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) - Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
Kitaev's quantum double model based on a finite group $G$.
We describe quantum circuits for (a) preparation of the ground state, (b) creation of anyon pairs separated by an arbitrary distance, and (c) non-destructive topological charge measurement.
arXiv Detail & Related papers (2022-05-04T08:10:36Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and
Energy [0.0]
We prove that any threshold circuit $C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $log (rk(M_C)) le ed.
For other models of neural networks such as a discretized ReLE circuits and decretized sigmoid circuits, we prove that a similar inequality also holds for a discretized circuit $C$.
arXiv Detail & Related papers (2021-07-01T05:37:53Z) - Unitarization Through Approximate Basis [0.0]
Unitarization is the problem of taking $k$ input circuits that produce quantum states from the all $0$ state.
We find an approximate basis in time for the following parameters.
arXiv Detail & Related papers (2021-04-01T22:11:05Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard.
We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
arXiv Detail & Related papers (2021-02-03T09:20:32Z) - Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
We introduce a quantum circuit mapping, QXX, and its machine learning version, QXX-MLP.
The latter infers automatically the optimal QXX parameter values such that the layed out circuit has a reduced depth.
We present empiric evidence for the feasibility of learning the layout method using approximation.
arXiv Detail & Related papers (2020-07-29T05:26:19Z)
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.