Quantum algorithms and approximating polynomials for composed functions with shared inputs

DOI10.1137/1.9781611975482.42MaRDI QIDQ5236223zbMATH OpenOpenAlexFDO

Authors Mark Bun, Robin Kothari, Justin Thaler

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.02254

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be an $m$-bit Boolean function and consider an $n$-bit function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give an algorithm for evaluating $F$ using $ildeO(sqrtQ(f)cdotn)$ quantum queries. This improves on the bound of $O(Q(f)cdotsqrtn)$ that follows by treating each conjunction independently, and our bound is tight for worst-case choices of $f$. Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of $f$. By recursively applying our composition theorems, we obtain a nearly optimal $ildeO(n^{1-2^{-d}})$ upper bound on the quantum query complexity and approximate degree of linear-size depth-$d$ AC${}^0$ circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC${}^0$ circuits. As an additional consequence, we show that AC${}^{0}circoplus$ circuits of depth $d+1$ require size $ildeOmega(n^{1/(1-2^{-d})})geqomega(n^{1+2^{-d}})$ to compute the Inner Product function even on average. The previous best size lower bound was $Omega(n^{1+4^{-(d+1)}})$ and only held in the worst case (Cheraghchi et al., JCSS 2018).

Recommendations

• Improved bounds on quantum learning algorithms
• The quantum query complexity of read-many formulas
• The quantum query complexity of \(\mathrm{AC}^0\)
• The quantum query complexity of learning multilinear polynomials
• SOFSEM 2005: Theory and Practice of Computer Science

Cited in

(10)

• Polynomial approximation of quantum Lipschitz functions
• scientific article; zbMATH DE number 5320307 (Why is no real title available?)
• scientific article; zbMATH DE number 6820205 (Why is no real title available?)
• Quantum hardness of learning shallow classical circuits
• Algorithmic Polynomials
• A polynomial quantum algorithm for approximating the Jones polynomial
• Unconditionally secure computation against low-complexity leakage
• Correction to: ``Unconditionally secure computation against low-complexity leakage
• Parity vs. \(\text{AC}^0\) with simple quantum preprocessing
• On zeros of exponential polynomials and quantum algorithms

This page was built for publication: Quantum algorithms and approximating polynomials for composed functions with shared inputs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236223)