02244nas a2200133 4500008004100000245006000041210006000101260001500161520182800176100002802004700002002032700002102052856003702073 2019 eng d00aQuantum hardness of learning shallow classical circuits0 aQuantum hardness of learning shallow classical circuits c03/07/20193 a

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.

1 aArunachalam, Srinivasan1 aGrilo, Alex, B.1 aSundaram, Aarthi uhttps://arxiv.org/abs/1903.0284001529nas a2200109 4500008004100000245005800041210005700099520118800156100002101344700001701365856003701382 2018 eng d00aMathematical methods for resource-based type theories0 aMathematical methods for resourcebased type theories3 a

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'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.

1 aSundaram, Aarthi1 aLackey, Brad uhttps://arxiv.org/abs/1812.0872601662nas a2200145 4500008004100000245008400041210006900125520118800194100002101382700001901403700001801422700002101440700001801461856003701479 2018 eng d00aQuantum generalizations of the polynomial hierarchy with applications to QMA(2)0 aQuantum generalizations of the polynomial hierarchy with applica3 a

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'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.

1 aGharibian, Sevag1 aSantha, Miklos1 aSikora, Jamie1 aSundaram, Aarthi1 aYirka, Justin uhttps://arxiv.org/abs/1805.11139