@article {2386, title = {Quantum hardness of learning shallow classical circuits}, year = {2019}, month = {03/07/2019}, abstract = {

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1) Hardness of learning AC0 and TC0 under the uniform distribution. Our first result concerns the concept class TC0 (resp. AC0), the class of constant-depth and polynomial-sized circuits with unbounded fan-in majority gates (resp. AND, OR, NOT gates). We show that if there exists no quantum polynomial-time (resp. sub-exponential time) algorithm to solve the Learning with Errors (LWE) problem, then there exists no polynomial-time quantum learning algorithm for TC0 (resp. AC0) under the uniform distribution (even with access to quantum membership queries). The main technique in this result uses explicit pseudo-random generators that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2) Hardness of learning TC02 in the PAC setting. Our second result shows that if there exists no quantum polynomial time algorithm for the LWE problem, then there exists no polynomial time quantum PAC learning algorithm for the class TC02, i.e., depth-2 TC0 circuits. The main technique in this result is to establish a connection between the quantum security of public-key cryptosystems and the learnability of a concept class that consists of decryption functions of the cryptosystem. This gives a strong conditional negative answer to one of the \"Ten Semi-Grand Challenges for Quantum Computing Theory\" raised by Aaronson [Aar05], who asked if AC0 and TC0 can be PAC-learned in quantum polynomial time.

}, url = {https://arxiv.org/abs/1903.02840}, author = {Srinivasan Arunachalam and Alex B. Grilo and Aarthi Sundaram} } @article {2330, title = {Mathematical methods for resource-based type theories}, year = {2018}, abstract = {

With the wide range of quantum programming languages on offer now, efficient program verification and type checking for these languages presents a challenge -- especially when classical debugging techniques may affect the states in a quantum program. In this work, we make progress towards a program verification approach using the formalism of operational quantum mechanics and resource theories. We present a logical framework that captures two mathematical approaches to resource theory based on monoids (algebraic) and monoidal categories (categorical). We develop the syntax of this framework as an intuitionistic sequent calculus, and prove soundness and completeness of an algebraic and categorical semantics that recover these approaches. We also provide a cut-elimination theorem, normal form, and analogue of Lambek\&$\#$39;s lifting theorem for polynomial systems over the logics. Using these approaches along with the Curry-Howard-Lambek correspondence for programs, proofs and categories, this work lays the mathematical groundwork for a type checker for some resource theory based frameworks, with the possibility of extending it other quantum programming languages.

}, url = {https://arxiv.org/abs/1812.08726}, author = {Aarthi Sundaram and Brad Lackey} } @article {2261, title = {Quantum generalizations of the polynomial hierarchy with applications to QMA(2)}, journal = {Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, year = {2018}, abstract = {

The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH does not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, QCPH, uses classical proofs, and the second, QPH, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda\&$\#$39;s theorem. For the latter, we place its third level, QΣ3, into NEXP {using the Ellipsoid Method for efficiently solving semidefinite programs}. These results yield two implications for QMA(2), the variant of Quantum Merlin-Arthur (QMA) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs \"equivalent\"), then QMA(2) is in the Counting Hierarchy (specifically, in PPPPP). Second, unless QMA(2)=QΣ3 (i.e., alternating quantifiers do not help in the presence of \"unentanglement\"), QMA(2) is strictly contained in NEXP.

}, doi = {https://doi.org/10.4230/LIPIcs.MFCS.2018.58}, url = {https://arxiv.org/abs/1805.11139}, author = {Sevag Gharibian and Miklos Santha and Jamie Sikora and Aarthi Sundaram and Justin Yirka} }