Quantum algorithms and approximating polynomials for composed functions with shared inputs

Mark Bun1, Robin Kothari2, and Justin Thaler3

1Boston University
2Microsoft Quantum
3Georgetown University

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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 $\tilde{O}(\sqrt{Q(f) \cdot n})$ quantum queries. This improves on the bound of $O(Q(f) \cdot \sqrt{n})$ 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 $\tilde{O}(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 \circ \oplus$ circuits of depth $d+1$ require size $\tilde{\Omega}(n^{1/(1- 2^{-d})}) \geq \omega(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).

► BibTeX data

► References

[1] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. Candidate weak pseudorandom functions in AC$^0 \circ \mathsf{MOD}_2$. In Proceedings of the 5th conference on Innovations in theoretical computer science, ITCS ’14, pages 251–260, 2014.

[2] Miklos Ajtai and Michael Ben-Or. A theorem on probabilistic constant depth computations. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC '84, pages 471–474, 1984.

[3] Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang. Any AND-OR formula of size $N$ can be evaluated in time $N^{1/​2 + o(1)}$ on a quantum computer. SIAM Journal on Computing, 39(6):2513–2530, 2010.

[4] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997.

[5] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001.

[6] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5):493–505, 1998.

[7] Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In 40th Annual Symposium on Foundations of Computer Science, pages 358–368, 1999.

[8] Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan. On the power of statistical zero knowledge. In 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 708–719, 2017.

[9] Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21–43, 2002.

[10] Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 297–310, 2018.

[11] Mark Bun, Robin Kothari, and Justin Thaler. Quantum algorithms and approximating polynomials for composed functions with shared inputs. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 662–678, 2019.

[12] Paul Beame and Widad Machmouchi. The quantum query complexity of AC$^0$. Quantum Information & Computation, 12(7-8):670–676, 2012.

[13] Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf. Robust polynomials and quantum algorithms. Theory of Computing Systems, 40(4):379–395, 2007.

[14] Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, AC$^0$ functions, and spectral norms. SIAM Journal on Computing, 21(1):33–42, 1992.

[15] Mark Bun and Justin Thaler. A nearly optimal lower bound on the approximate degree of AC$^0$. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 1–12, 2017.

[16] Mark Bun and Justin Thaler. Guest column: Approximate degree in classical and quantum computing. SIGACT News, 51(4):48–72, January 2021.

[17] Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo. Discrete-query quantum algorithm for NAND trees. Theory of Computing, 5:119–123, 2009.

[18] Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC0 $\circ$ MOD2 lower bounds for the Boolean inner product. In LIPIcs-Leibniz International Proceedings in Informatics, volume 55. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.

[19] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In International Workshop on Parameterized and Exact Computation, pages 75–85, 2009.

[20] Andrew M. Childs, Shelby Kimmel, and Robin Kothari. The quantum query complexity of read-many formulas. In 20th Annual European Symposium on Algorithms (ESA 2012), pages 337–348, 2012.

[21] Shiva Chaudhuri and Jaikumar Radhakrishnan. Deterministic restrictions in circuit complexity. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, STOC ’96, pages 30–36, 1996.

[22] Gil Cohen and Igor Shinkar. The complexity of DNF of parities. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 47–58, 2016.

[23] Ning Ding, Yanli Ren, and Dawu Gu. PAC learning depth-3 AC$^0$ circuits of bounded top fanin. In Proceedings of the 28th International Conference on Algorithmic Learning Theory, volume 76 of Proceedings of Machine Learning Research, pages 667–680, 2017. URL: http:/​/​proceedings.mlr.press/​v76/​ding17a.html.

[24] Michael Ezra and Ron D. Rothblum. Small circuits imply efficient Arthur-Merlin protocols. Technical Report TR21-127, Electronic Colloquium on Computational Complexity (ECCC), 2021. URL: https:/​/​eccc.weizmann.ac.il/​report/​2021/​127/​.

[25] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4(1):169–190, 2008.

[26] Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O'Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer. Real analysis in computer science: A collection of open problems, 2014. URL: https:/​/​simons.berkeley.edu/​sites/​default/​files/​openprobsmerged.pdf.

[27] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 212–219, 1996.

[28] Peter Høyer, Troy Lee, and Robert Špalek. Negative weights make adversaries stronger. In Proceedings of the 39th Symposium on Theory of Computing (STOC 2007), pages 526–535, 2007.

[29] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6):1777–1805, 2008.

[30] Adam Klivans, Pravesh Kothari, and Igor C. Oliveira. Constructing hard functions using learning algorithms. In IEEE Conference on Computational Complexity (CCC 2013), pages 86–97, 2013.

[31] Michal Koucký, Clemens Lautemann, Sebastian Poloczek, and Denis Therien. Circuit lower bounds via Ehrenfeucht-Fraisse games. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), pages 190–201, 07 2006.

[32] Swastik Kopparty. AC0 lower bounds and pseudorandomness. Lecture notes of ``Topics in Complexity Theory and Pseudorandomness (Spring 2013)'' at Rutgers University. http:/​/​sites.math.rutgers.edu/​ sk1233/​courses/​topics-S13/​lec4.pdf (Retrieved July 12, 2018), 2013.

[33] Michal Koucký. Circuit complexity of regular languages. Theory of Computing Systems, 45(4):865–879, 2009.

[34] Adam R. Klivans and Rocco A. Servedio. Learning DNF in time $2^{{\tilde O}(n^{1/​3})}$. Journal of Computer and System Sciences, 68(2):303–318, 2004.

[35] Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2-3):115–141, 1994.

[36] Wee Sun Lee, Peter L. Bartlett, and Robert C. Williamson. On efficient agnostic learning of linear combinations of basis functions. In Proceedings of the eighth annual conference on Computational learning theory, pages 369–376, 1995.

[37] Troy Lee. Slides for the paper ``improved quantum query algorithms for triangle finding and associativity testing'' by T. Lee, F. Magniez, M. Santha. Available at http:/​/​research.cs.rutgers.edu/​ troyjlee/​troy_triangle.pdf (Retrieved July 11, 2018), 2012.

[38] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263–399, 2009.

[39] Noam Nisan. Shortest formula for an $n$-term monotone CNF. Theoretical Computer Science Stack Exchange, 2011. https:/​/​cstheory.stackexchange.com/​q/​7087 (version: 2011-06-23).

[40] Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301–313, 1994.

[41] Igor C. Carboni Oliveira and Rahul Santhanam. Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:49, 2017.

[42] Alexander A Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987.

[43] Ben Reichardt. Reflections for quantum query algorithms. In SODA '11: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, pages 560–569, 2011.

[44] Alexander A. Razborov and Alexander A. Sherstov. The sign-rank of AC$^0$. SIAM Journal on Computing, 39(5):1833–1855, 2010.

[45] Prabhakar Ragde and Avi Wigderson. Linear-size constant-depth polylog-threshold circuits. Information Processing Letters, 39(3):143–146, 1991.

[46] Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing, 40(6):1969–2000, 2011.

[47] Alexander A. Sherstov. Strong direct product theorems for quantum communication and query complexity. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC 2011), pages 41–50, 2011.

[48] Alexander A. Sherstov. The intersection of two halfspaces has high threshold degree. SIAM Journal on Computing, 42(6):2329–2374, 2013.

[49] Alexander A. Sherstov. Making polynomials robust to noise. Theory of Computing, 9:593–615, 2013.

[50] Alexander A. Sherstov. The power of asymmetry in constant-depth circuits. In IEEE 56th Annual Symposium on Foundations of Computer Science, pages 431–450, 2015.

[51] Alexander A. Sherstov. Algorithmic polynomials. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), 2018.

[52] Rahul Santhanam and Srikanth Srinivasan. On the limits of sparsification. In International Colloquium on Automata, Languages, and Programming, pages 774–785. Springer, 2012.

[53] Rocco A. Servedio and Li-Yang Tan. What Circuit Classes Can Be Learned with Non-Trivial Savings? In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:21, 2017.

[54] Rocco A Servedio and Emanuele Viola. On a special case of rigidity. Technical Report TR12-144, Electronic Colloquium on Computational Complexity (ECCC), 2012. URL: https:/​/​eccc.weizmann.ac.il/​report/​2012/​144/​.

[55] Avishay Tal. The bipartite formula complexity of inner-product is quadratic. Technical Report TR16-181, Electronic Colloquium on Computational Complexity (ECCC), 2016. URL: https:/​/​eccc.weizmann.ac.il/​report/​2016/​181/​.

[56] Avishay Tal. Formula lower bounds via the quantum method. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 1256–1268, 2017.

[57] Avishay Tal. Personal communication, 2018.

[58] Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, Nov 1984.

Cited by

[1] Scott Aaronson, Daniel Grier, and Luke Schaeffer, "A Quantum Query Complexity Trichotomy for Regular Languages", arXiv:1812.04219.

[2] Kamil Khadiev and Liliya Safina, "Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs", arXiv:1804.09950.

The above citations are from SAO/NASA ADS (last updated successfully 2021-10-27 17:48:05). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2021-10-27 17:48:02).