The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts) Sagnik Chatterjee Abstract This paper surveys various results in the field of Quantum Learning theory, specifically focusing on learning quantum-encoded classical concepts in the Probably Approximately Correct (PAC) framework. The cornerstone of this work is the emphasis on query, sample, and time complexity separations between classical and quantum learning that emerge under learning with query access to different labeling oracles. This paper aims to consolidate all known results in the area under the above umbrella and underscore the limits of our understanding by leaving the reader with 23 open problems. DNF Disjunctive Normal Form CNF Conjunctive Normal Form PAC Probably Approximately Correct RCN Random Classification Noise HSP Hidden Subgroup Problem LWE Learning with Errors LPN Learning Parity with Noise NCP Nearest Codeword Problem SVP Shortest Vector Problem DLP Discrete Logarithm Problem NISQ Noisy Intermediate-Scale Quantum RAM Random Access Memory QRAM Quantum Random Access Memory QQRAM Quantum Random Access for Quantum Memory CQRAM Quantum Random Access for Classical Memory QFT Quantum Fourier Transform MQ Membership Query EX Example Query REX Random Noise Example Query AEX Agnostic Example Query QEX Quantum Example Query QREX Quantum RCN Example Query QAEX Quantum Agnostic Example Query QGL Quantum Goldreich Levin keywords quantum computing, PAC learning, survey, time and sample complexity 1 Introduction Ever since computer scientists co-opted the notion of computational devices leveraging quantum mechanical principles 51 ; 52 ; 38 , the overarching goal in the quantum computing community has been to demonstrate speedups in computational tasks over their classical counterparts. This came to a head when the seminal results of Grover 56 and Shor 88 opened the proverbial floodgates for research into computational speedups in various areas of traditional computer science, previously thought to have reached their computational barriers. Learning theory 96 ; 95 ; 97 ; 94 is the study of how algorithms can generalize from data. This subfield of theoretical computer science is closely connected to fields like cryptography, coding theory, and circuit complexity, which makes it an extremely interesting area of research. The close of the twentieth century was marked with a series of results on classical impossibility barriers to efficient learning , 1 1 1 The notion of learnability and efficient learnability will be formally introduced later on. even for extremely simple concept classes such as Boolean functions. It was at this critical juncture that 28 spearheaded the development of the subfield of quantum learning theory by circumventing known classical barriers for learning DNF formulas by using quantum query algorithms . This survey aims to capture a vast portion of the literature on quantum learning theory, subject to a few constraints . 1.1 Structure and Organisation In Section 2 we establish basic notation, and provide an overview of Quantum Computing and Computational Learning Theory, followed an introduction of the PAC-learning framework in Section 2.4 , focusing on the notions of sample complexity (learnability) and time complexity (efficient learnability). We introduce various query models and discuss separations between them in Section 3 . Of particular importance are Sections 3.2 and 3.3 , where we highlight separations between sampling and membership queries in the classical and quantum settings, respectively, and propose a new generalized measure of separation between sampling and membership queries in the quantum case. In Section 4 , we survey sample complexity separations between classical and quantum PAC learning algorithms. Our discussions move beyond sample complexity separations in the traditional setup considered by previous surveys such as 8 ; 5 , and cover newer research directions that consider separations w.r.t. generalized oracles, separations in the multi-class setting, and separations under white-box access. In Section 5 , we survey computational separations between classical and quantum learning algorithms. We formally introduce the notion of the Hidden Subgroup Problem induced concept classes, and demonstrate that existing separations follow as from separations in this general concept class. We then interpret the seemingly magical quantum learning speedups for LWE ( LWE ) and LPN ( LPN ) as a consequence of learning under powerful new oracle models. We conclude the survey with the latest developments in separations and impossibility results on learning classical Boolean concept classes such as halfspaces, decision trees, juntas, DNFs, and shallow circuits. What this survey is not about As noted in the abstract, the main goal of this paper is to survey the sample and time complexity-theoretic separations between classical and quantum learning algorithms in the context of learning classical concept classes , specifically when restricted to the PAC learning framework. This work can be thought of as an extension to an earlier survey from 2017 by 8 , both in terms of giving an overview of new quantum learning results in the last decade and emphasizing the underlying philosophy of learning separations stemming from learning under labeling query oracles. We detail the scope of the survey upfront, before moving on to the main subject matter at hand. This survey does not touch on many important subareas of quantum learning theory, specifically under different learning models. We highlight two such categories below: 1. Quantum learning for quantum objects. This sub-field of quantum learning theory aligns with Feynman’s original vision of using quantum computers to figure out quantum phenomena. Examples include learning arbitrary quantum states, quantum channels, and quantum processes. We refer the reader to other surveys 43 ; 5 for a more comprehensive treatment of this area of quantum learning. 2. Quantum learning under different learning frameworks such as quantum statistical learning, quantum exact learning, etc. We refer the reader to the following manuscript by 82 for an introduction to quantum statistical learning, and the following resources 8 ; 7 for more details on quantum exact learning. 2 Background and Preliminaries 2.1 Basic Notation We represent the logarithm to base 2 by \log . For n\in\mathbb{N} , any positive polynomial function in n is denoted by \operatorname{poly}\left(n\right) . A multivariate polynomial over n -variables is denoted as \operatorname{poly}\left(x_{1},x_{2},\ldots,x_{n}\right) . For n\in\mathbb{N} , we denote by [n] the set \{1,\ldots,n\} . The finite field of order 2 is denoted by \mathbb{F}_{2}=\{-1,+1\} or \mathbb{Z}_{2}=\{0,1\} , and \mathbb{F}^{n}_{2} (resp. \mathbb{Z}^{n}_{2} ) denotes an n -dimensional vector space over \mathbb{F}_{2} (resp. \mathbb{Z}_{2} ). A string x\in\mathbb{F}^{n}_{2} is an n -dimensional vector in \mathbb{F}^{n}_{2} , where x_{i} denotes the i -th bit of x . A Boolean literal is a bit x_{i} or its negation \overline{x}_{i} . For a string x\in\mathbb{F}^{n}_{2} , the string \overline{x}\in\mathbb{F}^{n}_{2} is the string given by \overline{x}_{i}=1\oplus x_{i} , where \oplus is the bit-wise sum operation. For a,b\in\mathbb{F}^{n}_{2} (or \mathbb{Z}^{n}_{2} ), any bit-wise binary operation \odot results in a string (a\odot b)\in\mathbb{F}^{n}_{2} (or \mathbb{Z}^{n}_{2} respectively). The bit-wise AND, OR, and XOR operations are denoted as a\land b , a\lor b , and a\oplus b , respectively. The Hamming weight of x\in\mathbb{F}^{n}_{2} is denoted by \absolutevalue{x} . The indicator random variable for an event E is denoted by \mathbb{I}_{E} . The uniform distribution over a set \mathcal{S} is denoted by \mathcal{U}\left(\mathcal{S}\right) . The support of a distribution \mathfrak{D} over the Boolean hypercube \mathbb{F}^{n}_{2} is denoted as \operatorname{supp}\left(\mathfrak{D}\right)=\{z\in\mathbb{F}^{n}_{2}\;|\;\mathfrak{D}(z)\neq 0\} . x\sim\mathfrak{D} denotes a string sampled from a probability distribution \mathfrak{D} , i.e. \operatorname{Pr}(\mathbf{X}=x)=\mathfrak{D}(x) . Similarly, x\sim\mathcal{S}\iff x\sim\mathcal{U}(\mathcal{S}) , where \mathcal{S}\subseteq[n] . We denote by \underset{\mathfrak{D}}{\mathbb{E}}\,\left[\,\mathbf{X}\,\right] the expectation of the random variable \mathbf{X} with respect to the distribution \mathfrak{D} , and by \mathbb{E}\,\left[\,\mathbf{X}\,\right] the expectation of \mathbf{X} with respect to the uniform distribution. When dealing with inner product spaces, we will sometimes denote \underset{\mathfrak{D}}{\mathbb{E}}\,\left[\,\mathbb{X}\,\right] as \left\langle\mathfrak{D},\mathbb{X}\right\rangle . A function f:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2}^{m} is known as a Boolean function . Recall that the finite field of order 2 is denoted by \mathbb{F}_{2}=\{-1,+1\} or \mathbb{Z}_{2}=\{0,1\} , and \mathbb{F}^{n}_{2} (resp. \mathbb{Z}^{n}_{2} ) denotes an n -dimensional vector space over \mathbb{F}_{2} (resp. \mathbb{Z}_{2} ). For this survey, we are concerned with decision problems, i.e., binary-valued functions, and therefore mostly consider Boolean functions of the form f:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2} , unless explicitly stated otherwise. We refer the reader to Section 8 for more details on the representation of Boolean functions. 2.2 Basics of Quantum Computing A density matrix \rho corresponding to a n -qubit quantum state is a n\times n positive semi-definite (PSD) matrix with trace 1 : \rho=\sum_{i\in[n]}p_{i}\ket{\psi_i}\bra{\psi_i} , where \{\ket{\psi_i}\}_{i\in[n]} are pure states and \{p_{i}\}_{i\in[n]} form a probability distribution. Density matrices corresponding to pure states have rank 1 , i.e., \rho=\ket{\psi}\bra{\psi} . Definition 2.1 (Trace Distance) . The trace distance between two quantum states \rho and \sigma is denoted by D(\rho,\sigma)=\frac{1}{2}\norm{\rho-\sigma}_{1}. When \rho and \sigma correspond to pure states \ket{\phi} and \ket{\psi} the trace distance is expressed as D(\ket{\phi},\ket{\psi})=\sqrt{1-{\absolutevalue{\bra{\phi}\ket{\psi}}}^{2}}. Fact 2.1 (Distinguishing quantum states) . Suppose an algorithm is tasked with distinguishing between two mixed states \rho_{0} and \rho_{1} . If the algorithm is given \rho_{b} , where b is picked uniformly at random from \{0,1\} , then the best success probability of distinguishing between \rho_{0} and \rho_{1} is \frac{1}{2}+\frac{1}{2}D(\rho_{0},\rho_{1})=\frac{1}{2}+\frac{1}{2}\sqrt{1-{\absolutevalue{\bra{\rho_0}\ket{\rho_1}}}^{2}} . Given a Boolean function f , a quantum circuit computes f with error \varepsilon>0 , if \forall x\in\mathbb{F}^{n}_{2} , the quantum circuit Q can compute f(x) with probability at least 1-\varepsilon . 2 2 2 By compute, we mean that the outcome of the measurement in the ancilla is f(x) . The bounded error query complexity of computing f is the smallest number of calls to any oracle O_{x} s.t. Q computes f w.p. \geq 1-\varepsilon . The bounded error time complexity also takes into account the time taken to implement the unitaries V_{1},\ldots,V_{k} . The complexity class {\mathsf{BQP}} is the class of decision problems efficiently solvable by a quantum computer and is defined as the class of languages L\subseteq\{0,1\}^{*} that are decidable, with a bounded error probability of at most \nicefrac{{1}}{{3}} by a poly-time uniform family of quantum circuits \{Q_{n}\}_{n} . Remark 2.1 . Throughout this survey, when we say that a quantum algorithm exists that performs a certain task, we mean that there is a uniform family of quantum query circuits that performs said task. We refer the reader to Section 7 for more discussions on quantum algorithms. 2.3 Overview of Computational Learning Theory Let \mathcal{X}_{n}\subseteq\mathbb{F}^{n}_{2} be a set of n -bit instances (or strings), and \mathcal{Y} be the set of labels. For n\in\mathbb{N} , we denote by \mathcal{C}=\cup_{n>0}\mathcal{C}_{n} , where \mathcal{C}_{n}=\{c_{n}\;|\;c_{n}:\mathcal{X}_{n}\mapsto\mathcal{Y}\} , a class of functions that maps instances to labels, known as the concept class . Similarly, a hypothesis class \mathcal{H}=\cup_{n>0}\mathcal{H}_{n} , where \mathcal{H}_{n}=\{h_{n}\;|\;h_{n}:\mathcal{X}_{n}\mapsto\mathcal{Y}\} , is also a class of functions that maps instances to labels. When it is obvious from the context, we drop the subscript n from the definitions. For most of this survey, we assume that the label set is binary. Therefore, the concepts and the hypotheses discussed above are Boolean functions. Since multiple classes of Boolean circuits can compute the same Boolean function (see Section 8 for a detailed discussion), the choice of representation of the concept or hypothesis becomes important for computational tasks. We assume that the representation of any concept class or hypothesis class is fixed . Remark 2.2 . For this survey, the choice of the underlying representation is the concept class \mathcal{C} / hypothesis class \mathcal{H} under consideration, and its corresponding size, denoted by \operatorname{size}\left(\mathcal{C}\right) and \operatorname{size}\left(\mathcal{H}\right) respectively, is the maximal cost of the representation of \mathcal{C} and \mathcal{H} respectively. A learning algorithm (or learner) A is a randomized map from a set of instances \mathcal{S} , 3 3 3 The set \mathcal{S} is referred to as the training set for A . sampled (i.i.d.) according to an unknown distribution \mathfrak{D} and labeled by an unknown target concept c\in\mathcal{C} to a hypothesis function h\in\mathcal{H} . 4 4 4 We assume here that both the hypothesis class \mathcal{H} and the concept class \mathcal{C} are known, but the specific target concept c is unknown. Since the label set is binary, most of the algorithms discussed in this survey perform binary classification . We note here that the learner A can be either a classical randomized algorithm or a quantum algorithm. Throughout most of this survey, we focus on one metric to quantify the performance of the output hypotheses, namely, the error of a hypothesis. The notion of error semantically captures the number of mistakes made by the hypothesis h with respect to the concept c in different forms. Definition 2.2 (Error) . The error of a hypothesis h\in\mathcal{H}:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2} with respect to an unknown concept c\in\mathcal{C}:\mathbb{F}^{n}_{2}\mapsto\{-1,+1\} and an unknown underlying distribution \mathfrak{D} is defined as: \operatorname{err}_{\mathfrak{D},c}\left(h\right):=\underset{x\sim\mathfrak{D}}{\mathbb{E}}\,\left[\,\mathbb{I}_{\left(h(x)\neq c(x)\right)}\,\right]=\operatorname{Pr}_{x\sim\mathfrak{D}}\left[h(x)\neq c(x)\right]. (1) The optimal error of a hypothesis class \mathcal{H} with respect to an unknown concept c\in\mathcal{C} with respect to to an underlying distribution \mathfrak{D} is defined as \operatorname{opterr}_{\mathfrak{D},c}\left(\mathcal{H}\right):=\min_{h\in\mathcal{H}}\operatorname{err}_{\mathfrak{D},c}\left(h\right). Remark 2.3 . A hypothesis with \operatorname{err}\left(h\right)=0 is called the ideal hypothesis . 2.4 The PAC-learning framework In this section, we quantify the performance of the learning algorithm A using the PAC ( PAC ) learning model, introduced by 94 . Definition 2.3 ( (\varepsilon,\delta) -PAC learnability) . A learning algorithm A (\varepsilon,\delta) -PAC learns an unknown concept class \mathcal{C} over n -bit instances using hypothesis class \mathcal{H}_{A} , if for every distribution \mathfrak{D} over \mathcal{X} , and every target concept c\in\mathcal{C} , there exists a function m_{0}:(0,1)^{2}\mapsto\mathbb{N} , such that for every \varepsilon,\delta\in[0,1] , A takes as input a training set \mathcal{S} consisting of m>m_{0}(\varepsilon,\delta) sampled i.i.d. according to \mathfrak{D} and labeled by c and outputs h\in\mathcal{H}_{A} s.t. \operatorname{Pr}\left[\operatorname{err}_{\mathfrak{D},c}\left(h\right)\leq\varepsilon\right]\geq 1-\delta. (2) The probability in Eq. 2 is over the choice of the training set \mathcal{S} and any internal randomization of the learner A . We also note that in Definition 2.3 , there is an implicit assumption of realizability , i.e., with probability 1 over \mathcal{S} , there exists h_{\mathrm{opt}}\in\mathcal{H} s.t. \operatorname{err}_{\mathfrak{D},c}\left(h_{\mathrm{opt}}\right)=0 . 2.4.1 Sample Complexity and Learnability In Definition 2.3 , m is the sample complexity of the learner A for learning \mathcal{C} . If m=\operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right) , then the concert class \mathcal{C} is said to be PAC-learnable by A using the hypothesis class \mathcal{H}_{A} . A concept class \mathcal{C} is learnable or PAC-learnable using \mathcal{H}_{A} if there exists some \varepsilon,\delta,m_{0} for which Eq. 2 holds. Remark 2.4 . Definition 2.3 follows 87 , where the notion of sample complexity is decoupled from the definition of PAC learning. This is done in order to drive home the distinction between learnability and efficient learnability. In other standard textbooks and sources, it is common to find m=\operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right) directly in Definition 2.3 itself. 2.4.2 Time Complexity and Efficient Learnability If A (\varepsilon,\delta) -PAC learns \mathcal{C} in polynomial time, i.e., in time \mathrm{poly}{\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right)} , then we say that the concept class \mathcal{C} is efficiently PAC learnable (or simply, efficiently learnable ) by A using the hypothesis class \mathcal{H}_{A} . For efficient learners, \operatorname{size}\left(\mathcal{H}_{A}\right)=\operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{C}\right)\right). We note here that not all learnable concept classes with respect to a learner A are efficiently learnable with respect to A . Remark 2.5 . All Boolean functions are efficiently PAC learnable if the representation scheme of the underlying concept class is extremely expressive/ verbose, for example, the concept class is described using truth tables. The interesting case is when the underlying concept is represented using Boolean functions, which are believed to have limited expressivity, such as Decision trees, since extremely simple Boolean circuits can compute them. We refer the reader to Section 9.1 for more discussions on hypothesis classes associated with learning algorithms. While there are many possible ways to classify PAC learning algorithms, in this survey, we focus on the sample complexity and time complexity of PAC learners (specifically the separation between classical and quantum PAC learners) under various noise models, and with respect to various oracle queries. Remark 2.6 . One broad classification umbrella not included in this survey deals with the representation and accuracy of the output hypothesis produced by the learner. We refer the reader to Section 9.2 for a brief discussion on the above taxonomy. 3 Query Complexity Separations 3.1 PAC Learning with queries The learning algorithm A in Definition 2.3 (\varepsilon,\delta) - PAC learns \mathcal{C} with respect to random examples (provided in the form of the training set \mathcal{S} ). Alternatively, we can also assume that the learner A can make black-box queries, i.e., the learner has access to an oracle \mathcal{O} . Learning with respect to queries is primarily used to study generalizations or restrictions of PAC learning setups under various forms of labeling noise. For a more detailed discussion on label noise in the PAC framework, the reader is referred to Section 9.4 . In this generalized model, we redefine the notion of PAC learning as follows: Definition 3.1 ( PAC learning with Oracle access) . A learner A (\varepsilon,\delta) - PAC learns concept class \mathcal{C} over n -bit instances, with query access to oracle \mathcal{O} , using hypothesis class \mathcal{H}_{A} , if for every \varepsilon,\delta\in(0,1) , for every distribution \mathfrak{D} over \mathcal{X} , and every target concept c\in\mathcal{C} , A takes as input a training set \mathcal{S} consisting of m=\operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right) sampled i.i.d. according to \mathfrak{D} and labeled by c , and makes at most m queries to \mathcal{O} and outputs h s.t. the error of h is at most \varepsilon with probability at least 1-\delta . 3.1.1 PAC learning with Sampling Oracles Sampling oracles are also known as example query oracles. 3.1.2 Classical Example Query Oracles The EX ( EX ) Oracle: Querying the classical random example oracle \operatorname{EX}\left(\mathfrak{D},c\right) generates labeled examples of the form (x,c(x)) where x\sim\mathfrak{D} . Using the EX oracle, we can redefine the sample complexity and time complexity of PAC learning concept c\in\mathcal{C} using A in terms of the number of queries A makes to \operatorname{EX}\left(\mathfrak{D},c\right) as follows. Definition 3.2 ( \left(\varepsilon,\delta\right) -PAC learning with access to \mathrm{EX} oracle) . A learner A (\varepsilon,\delta) - PAC learns concept class \mathcal{C} over n -bit instances, with query access to \operatorname{EX}\left(\mathfrak{D},c\right) , using hypothesis class \mathcal{H}_{A} , if for every \varepsilon,\delta\in(0,1) , for every distribution \mathfrak{D} over \mathcal{X} , and every target concept c\in\mathcal{C} , A makes at most m=\operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right) queries to \operatorname{EX}\left(\mathfrak{D},c\right) and outputs h s.t. \operatorname{Pr}\left[\operatorname{err}_{\mathfrak{D},c}\left(h\right)\leq\varepsilon\right]\geq 1-\delta . The REX ( REX ) Oracle: Querying an \operatorname{REX}^{\eta}\left(\mathfrak{D},c\right) oracle generates labeled examples of the form \{(x_{i},y^{\prime}_{i})\}_{i\in[m]} , where y^{\prime}_{i}=\overline{y_{i}} w.p. \eta and y^{\prime}_{i}=y_{i} w.p. 1-\eta . Hence, PAC learning in the RCN ( RCN ) setting can be thought of as the learner A making queries to an REX oracle. The AEX ( AEX ) Oracle: Similar to the RCN setting, PAC learning in the agnostic setting can be thought of as the learner A making queries to an AEX oracle, where invoking an \operatorname{AEX}\left(\mathfrak{D}\right) oracle generates samples (x,y)\sim\mathfrak{D} according to some unknown joint distribution \mathfrak{D} over \mathcal{X}\times\mathcal{Y} . The notion of learnability in the agnostic case is defined as follows 66 . Definition 3.3 ( \beta -optimal (\varepsilon,\delta) -agnostic PAC learning) . A learner A \beta -optimally (\varepsilon,\delta) -agnostic PAC learns a benchmark concept class \mathcal{C} over n -bit instances, with query access to \operatorname{AEX}\left(\mathfrak{D}\right) , using hypothesis class \mathcal{H}_{A} , if for every \varepsilon,\delta\in(0,1) , for some \beta\in[0,\nicefrac{{1}}{{2}}) , for every distribution \mathfrak{D} over \mathcal{X}\times\mathcal{Y} , A makes at most m=\operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right) queries to \operatorname{AEX}\left(\mathfrak{D}\right) and outputs h s.t. \operatorname{Pr}\left[\operatorname{err}_{\mathfrak{D}}\left(h\right)\leq\operatorname{opterr}_{\mathfrak{D}}\left(\mathcal{C}\right)+\beta+\varepsilon\right]\geq 1-\delta for some \beta\in\left[0,\nicefrac{{1}}{{2}}\right) . Learnability (and efficient learnability) in Definition 3.3 implies that the number of queries made by A to \operatorname{AEX}\left(\mathfrak{D}\right) (time taken by A to output h , respectively) is polynomially bounded, similar to Definition 3.2 . In Definition 3.3 , if there exists a concept c\in\mathcal{C} s.t. \operatorname{err}_{\mathfrak{D}}\left(c\right):=\operatorname{Pr}_{(x,y)\sim\mathfrak{D}}\left[c(x)\neq y\right]=0, then \operatorname{opterr}_{\mathfrak{D}}\left(\mathcal{C}\right)=\beta , then we are almost back in the noiseless PAC learning setting. Observation 3.1 . The concept class \mathcal{C} serves as a benchmark for the learner A in the agnostic setting. If we choose a very bad benchmark concept class, i.e., \operatorname{opterr}_{\mathfrak{D}}\left(\mathcal{C}\right)>\nicefrac{{1}}{{2}} , then the best agnostic learner will produce a hypothesis with accuracy less than \nicefrac{{1}}{{2}} . Observation 3.2 . In learning under classical sampling oracles, the Learner A obtains copies of a convex combination, where the weights are Probability Masses. \sum_{x\in\mathcal{X}}\mathfrak{D}_{x}\;\;{(x,c(x))},\;\;\sum_{x\in\mathcal{X}}\mathfrak{D}_{x}=1,\;\;\mathfrak{D}:\mathcal{X}\xrightarrow{}[0,1].\;\text{(Noiseless setting.)} \sum_{(x,y)\in\mathcal{X}\times\mathcal{Y}}\mathfrak{D}_{x,y}\;\;{(x,y)},\;\;\sum_{(x,y)\in\mathcal{X}\times\mathcal{Y}}\mathfrak{D}_{x,y}=1,\;\;\mathfrak{D}:\mathcal{X}\times\mathcal{Y}\xrightarrow{}[0,1].\;\text{(Agnostic setting.)} 3.1.3 Quantum Example Query Oracles The QEX ( QEX ) Oracle: 28 generalized the notion of Definition 3.2 ( \left(\varepsilon,\delta\right) -PAC learning with access to \mathrm{EX} oracle) . to the quantum setting by introducing the QEX oracle (parameterized as \operatorname{QEX}\left(\mathfrak{D},c\right) ), and defining quantum PAC learning with access to a QEX oracle as follows. \operatorname{QEX}\left(\mathfrak{D},c\right):\ket{0,0}\mapsto\sum_{x\in\mathbb{F}^{n}_{2}}\sqrt{\mathfrak{D}(x)}\ket{x,c(x)}. (3) The QREX ( QREX ) Oracle: We can define a quantum example oracle that captures the RCN setting as follows. \operatorname{QREX}^{p}\left(\mathfrak{D},c\right):\ket{0,0}\mapsto\sum_{x\in\mathbb{F}^{n}_{2}}\sqrt{(1-p)\cdot\mathfrak{D}(x)}\ket{x,f(x)}+\sum_{x\in\mathbb{F}^{n}_{2}}\sqrt{p\cdot\mathfrak{D}(x)}\ket{x,\overline{f(x)}}. (4) Definition 3.4 (Quantum PAC learning with QEX (resp. QREX) oracle) . A quantum algorithm A (\varepsilon,\delta) -quantum PAC learns concept class \mathcal{C} over n -bit instances, with query access to \operatorname{QEX}\left(\mathfrak{D},c\right) (resp. \operatorname{QREX}^{p}\left(\mathfrak{D},c\right) ), using hypothesis class \mathcal{H}_{A} , if for every \varepsilon,\delta\in(0,1) , for every distribution \mathfrak{D} over \mathcal{X} , and every target concept c\in\mathcal{C} , A makes at most m=\operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right) queries to \operatorname{QEX}\left(\mathfrak{D},c\right) (resp. \operatorname{QREX}^{p}\left(\mathfrak{D},c\right) ) and outputs h s.t. \operatorname{Pr}\left[\operatorname{err}_{\mathfrak{D},c}\left(h\right)\leq\varepsilon\right]\geq 1-\delta . The QAEX ( QAEX ) Oracle: 8 generalized the AEX ( AEX ) oracle and the notion of Definition 3.3 ( \beta -optimal (\varepsilon,\delta) -agnostic PAC learning) . to the quantum setting as follows: \operatorname{QAEX}\left(\mathfrak{D}\right):\ket{0,0}\mapsto\sum_{(x,y)\in\mathbb{F}^{n+1}_{2}}\sqrt{\mathfrak{D}(x,y)}\ket{x,y}. (5) Definition 3.5 (Quantum agnostic PAC learning with QAEX oracle) . A quantum learner A \beta -optimally (\varepsilon,\delta) -PAC learns a benchmark concept class \mathcal{C} over n -bit instances, with query access to \operatorname{QAEX}\left(\mathfrak{D}\right) , using hypothesis class \mathcal{H}_{A} , if for every \varepsilon,\delta\in(0,1) , for some \beta\in[0,\nicefrac{{1}}{{2}}) , for every distribution \mathfrak{D} over \mathcal{X}\times\mathcal{Y} , A makes at most m=\operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right) queries to \operatorname{QAEX}\left(\mathfrak{D}\right) and outputs h s.t. \operatorname{Pr}\left[\operatorname{err}_{\mathfrak{D}}\left(h\right)\leq\operatorname{opterr}_{\mathfrak{D}}\left(\mathcal{C}\right)+\beta+\varepsilon\right]\geq 1-\delta for some \beta\in\left[0,\nicefrac{{1}}{{2}}\right) . Observation 3.3 . If the learner is classical but the query oracles are quantum, the only recourse left to the learner is to measure the state in Eqs. 3 , 5 and 4 to obtain one labeled sample. Therefore, the \operatorname{EX}\left(\mathfrak{D},c\right) and \operatorname{QEX}\left(\mathfrak{D},c\right) oracles (and their noisy versions, respectively) are equivalent to a classical learning algorithm. Remark 3.1 . In Definitions 3.4 and 3.5 , when we say that the quantum learner outputs a hypothesis, we mean that the quantum learner performs a POVM measurement such that each outcome of the measurement is associated with a hypothesis. Remark 3.2 . The concepts of learnability and efficient learnability in the quantum PAC setting are similar to those in the classical setting. The notions of complexity that we care about in the quantum PAC setting are, once again, the sample (and/or query) complexity and the time complexity of the learner. Remark 3.3 . We use A^{\mathcal{O}} to denote that learner A makes queries to oracle \mathcal{O} . Observation 3.4 . In learning under quantum sampling oracles, the Learner A obtains copies of a linear combination, where the weights are Probability Amplitudes. \sum_{x\in\mathcal{X}}\sqrt{\mathfrak{D}_{x}}\;\;{(x,c(x))},\;\;\sum_{x\in\mathcal{X}}\mathfrak{D}_{x}=1,\;\;\mathfrak{D}:\mathcal{X}\xrightarrow{}[0,1].\;\text{(Noiseless setting.)} \sum_{(x,y)\in\mathcal{X}\times\mathcal{Y}}\sqrt{\mathfrak{D}_{x,y}}\;\;{(x,y)},\;\;\sum_{(x,y)\in\mathcal{X}\times\mathcal{Y}}\mathfrak{D}_{x,y}=1,\;\;\mathfrak{D}:\mathcal{X}\times\mathcal{Y}\xrightarrow{}[0,1].\;\text{(Agnostic setting.)} Remark 3.4 . Recently, 10 introduced a stronger model of quantum agnostic learning under which they obtained state-of-the-art learnability results similar to the ones described in Section 5 . In their model, 10 consider that a benchmark quantum phase state that encodes information about the target concept class. The input 3.1.4 PAC learning with Membership Query Oracles One of the most important oracles for PAC learning is the Membership Query oracle \operatorname{MEM}_{c} . Querying the \operatorname{MEM}_{c} oracle with an instance x\in\mathbb{F}^{n}_{2} returns the instance’s label c(x) directly. As we can see, the MQ ( MQ ) oracle allows us to make very powerful out-of-distribution queries. 3.2 Power of Classical Membership Queries Learning with the membership queries is an active model of learning, where the learner can choose to query information about any instance-label pair it wishes, compared to the passive learning models in which the learner can only obtain instance-label pairs that are sampled according to an unknown distribution. We state two results below that give some intuition into the relative strength between the two query models of learning. 27 proved the following result. Lemma 3.1 (Learnability of Boolean functions) . Any n -bit Boolean function is PAC learnable with Membership queries in polynomial time in n and its DNF ( DNF ) size or its decision tree size. Recall that Definition 3.2 ( \left(\varepsilon,\delta\right) -PAC learning with access to \mathrm{EX} oracle) . is nothing but vanilla PAC learning, reformulated using query access to EX oracle. Hence, Lemma 3.1 immediately implies a possible learning separation between PAC learning with EX queries and MQ queries for DNF , which is not known to be PAC learnable with EX queries. The following proposition, which follows from similar arguments by 9 ; 6 , gives an unconditional (albeit polynomial) separation between MQ oracles and EX oracles. Proposition 3.2 ( MQ vs EX oracles) . Suppose a (publicly known) set of instances \mathcal{S} is the largest set shattered by a binary concept class \mathcal{C} , and let \mathfrak{D}:\mathcal{S}\mapsto[0,1] be a distribution that puts most of its weight on a particular instance as follows: \mathfrak{D}(x)=\begin{cases}1-3\varepsilon&\;\;,x=x^{\prime},\varepsilon=\nicefrac{{1}}{{\operatorname{poly}\left(\absolutevalue{\ccS}\right)}}\\ \frac{3\varepsilon}{\absolutevalue{\ccS}},&\;\;,x\in\mathcal{S}\setminus\{x^{\prime}\}.\end{cases} Then, any (\varepsilon,\delta) PAC learner for c with respect to \mathfrak{D} making queries to a \operatorname{MEM}_{c} oracle has polynomially smaller query complexity than a learner making queries to an \operatorname{EX}\left(\mathfrak{D},c\right) oracle. Proof. Learning with respect to MQ oracle: Since \mathcal{C} has VC-dim \absolutevalue{\ccS} , there exists a concept c\in\mathcal{C} , s.t. c(x^{\prime})=0 , and assigns some labeling in 2^{\absolutevalue{\ccS}-1} to other elements of the instance space. Let A be a PAC learner for c with respect to \mathfrak{D} that makes at most Q_{\text{\acs{MQ} }} queries to an \operatorname{MEM}_{c} oracle. A requires Q={\operatorname{O}\left(\frac{2}{3}\absolutevalue{\ccS}\right)} queries to PAC learn c with respect to \mathfrak{D} , since we need to learn the labels of at most \frac{2}{3}\absolutevalue{\ccS} instances to \varepsilon -approximate c . Learning with respect to EX oracle: From Lemma 12 of 9 , we obtain that Q_{\text{\acs{EX}}}=\operatorname{poly}\left(\absolutevalue{\ccS}\right) queries, straightforwardly. This is polynomially larger than the MQ case. ∎ Both Lemmas 3.1 and 3.2 show why active learning with MQ oracles is more powerful than relying on sampling queries for learning. In the next section, we show that there also exists a notion of separation between quantum active queries and quantum sampling queries. Despite the advantages, there have been criticisms of MQ oracles, outlined in Section 9.3 . 3.3 Power of Quantum Membership Query Oracles The quantum MQ oracle \mathrm{QMEM}(f):\ket{x}\mapsto\ket{x}\ket{f(x)} is simply a function oracle (see Fig. 1 ), and ubiquitous in designing quantum algorithms such as Algorithm 1 . We now introduce a nomenclature for biased quantum membership query oracles. Definition 3.6 ( \varepsilon -Biased oracles) . A quantum example query oracle \mathcal{O}^{\varepsilon}_{f} corresponding to a Boolean function f is called an \varepsilon -biased for some 0<\varepsilon<\frac{1}{2} , when \mathcal{O}^{\varepsilon}_{f}:\ket{0}^{\otimes n}\ket{0}\mapsto\sum_{x\in\mathbb{F}^{n}_{2}}\alpha\ket{x}\ket{f(x)}+\sqrt{1-\alpha^{2}}\ket{x}\ket{\overline{f(x)}},\;\;\;\alpha>\frac{1}{2}+\varepsilon. QREX oracles is an \varepsilon -biased oracle. Recall that an unbiased oracle is an \varepsilon -biased oracle with \alpha=1 . 63 proved the following lemma: Lemma 3.3 (Simulatability of Unbiased Oracles by \varepsilon -Biased Oracles) . For any {\operatorname{O}\left(T\right)} query quantum algorithm that solves a problem with high probability with query access to an unbiased oracle, there exists an {\operatorname{O}\left(\frac{T}{\varepsilon}\right)} query quantum algorithm that solves the same problem with high probability with query access to an \varepsilon -biased oracle. The notion of Definition 3.6 ( \varepsilon -Biased oracles) . was later generalized by 31 , who introduced the following oracle model. Definition 3.7 (Strongly Biased oracles) . A quantum example query oracle \mathcal{O}^{\varepsilon_{x}}_{f} corresponding to a Boolean function f is called a strongly biased for some 0<\varepsilon_{x}<\frac{1}{2},\forall x\in\mathbb{F}^{n}_{2} , when \mathcal{O}^{\varepsilon_{x}}_{f}:\ket{0}^{\otimes n}\ket{0}\mapsto\sum_{x\in\mathbb{F}^{n}_{2}}\alpha_{x}\ket{x}\ket{f(x)}+\sqrt{1-\alpha_{x}^{2}}\ket{x}\ket{\overline{f(x)}},\;\;\;\alpha_{x}>\frac{1}{2}+\varepsilon_{x},\forall x\in\mathbb{F}^{n}_{2}. Note that learning under the sampling oracle QAEX is a stronger model of learning than learning under a strongly biased oracle. To concretely demonstrate that there exists a separation between sampling and active queries even in the quantum setting, we first reprove a result of 28 showing that QEX oracles cannot exactly simulate \mathrm{QMEM} oracles w.r.t. the uniform distribution. First, we start by defining the notion of exact simulatability and then extending this to the notion of approximate simulatability. Then, we generalize the result of 28 to show that QEX oracles cannot even approximately simulate \mathrm{QMEM} oracles w.r.t. the uniform distribution. Definition 3.8 (Exact Simulatibility of \mathrm{QMEM} ) . A class of quantum (resp. classical) example oracles \mathcal{O} can exactly simulate \mathrm{QMEM} (resp. MQ ) for a Boolean concept class \mathcal{F} w.r.t. a distribution \mathcal{D} , if there exists a {\mathsf{BQP}} (resp. {\mathsf{BPP}} ) algorithm A s.t. for all f\in\mathcal{F} and all x\in\mathbb{F}^{n}_{2} , running A with access to \mathcal{O}\left(\mathfrak{D},f\right) on x can produce f(x) . Theorem 3.4 (Exact Simulatibility via QEX 28 ) . QEX cannot exactly simulate \mathrm{QMEM} w.r.t. \mathcal{U}\left(\mathbb{F}^{n}_{2}\right) . Proof. Consider two Boolean functions f and g that differ only in a single string x^{\prime}\in\mathbb{F}^{n}_{2} , e.g., let f(x)=0 for all x\in\mathbb{F}^{n}_{2} , and g(x)=\begin{cases}1\;\;,x=x^{\prime},\\ 0\;\;,\text{otherwise}.\end{cases} Consider a Boolean function h with the promise that it is either f or g . Suppose a quantum learner A makes Q queries to a QEX oracle \operatorname{QEX}\left(\mathcal{U},h\right) and wants to figure out which oracle it is querying. This task is the same as trying to discriminate between the following pair of states: \ket{\psi_f}={\left(\sum_{x\in\mathbb{F}^{n}_{2}}\sqrt{\mathcal{U}(x)}\ket{x,f(x)}\right)}^{\otimes Q}\;\;\;,\;\;\;\ket{\psi_g}={\left(\sum_{x\in\mathbb{F}^{n}_{2}}\sqrt{\mathcal{U}(x)}\ket{x,g(x)}\right)}^{\otimes Q}. (6) From Fact 2.1 , we know that the best success probability of distinguishing between \ket{\psi_f} and \ket{\psi_g} is \frac{1}{2}+\frac{1}{2}D\left(\ket{\psi_f},\ket{\psi_g}\right) . If this probability is greater than 1-\delta for any \delta\in(0,\nicefrac{{1}}{{2}}) , then \innerproduct{\psi_f}{\psi_g}\leq 2\sqrt{\delta\cdot(1-\delta)} . Therefore, \displaystyle\innerproduct{{\psi_f}}{\psi_g} \displaystyle\leq 2\sqrt{\delta\cdot(1-\delta)} (7) \displaystyle\implies{\left(\sum_{x\neq x^{\prime}}\sqrt{\mathcal{U}(x)}\right)}^{Q} \displaystyle\leq 2\sqrt{\delta\cdot(1-\delta)} (8) \displaystyle\implies{\left(1-{\mathcal{U}(x^{\prime})}\right)}^{Q/2} \displaystyle\leq 2\sqrt{\delta\cdot(1-\delta)}. (9) Let \varepsilon={\mathcal{U}(x^{\prime})}=\frac{1}{2^{n}} . Then, we have, \displaystyle{\left(1-\varepsilon\right)}^{Q/2} \displaystyle\leq 2\sqrt{\delta\cdot(1-\delta)} (10) \displaystyle\implies{\left(1-\varepsilon\right)}^{Q} \displaystyle\leq 4\delta (11) \displaystyle\implies Q\log\left(1-\varepsilon\right) \displaystyle\leq\log\left(4\delta\right) (12) \displaystyle\implies\frac{-Q\varepsilon}{1-\varepsilon} \displaystyle\leq\log\left(4\delta\right). (13) The inequality in Eq. 13 follows from applying the inequality \log(1+x)\geq\nicefrac{{x}}{{1+x}},\,\forall x>-1 to the LHS of Eq. 12 . Hence, we have that Q={\Omega\left(\frac{1}{\varepsilon}\log\left(\frac{1}{\delta}\right)\right)} , i.e., the number of queries is superpolynomial. Therefore, there exists no query-efficient learner A^{\text{\acs{QEX}}} that can distinguish between \ket{\psi_f} and \ket{\psi_g} with prob \geq 1-\delta . ∎ Remark 3.5 (Unconditional separation between \mathrm{QMEM} and QEX w.r.t. uniform) . Even though \mathrm{QMEM} cannot be exactly simulated by QEX w.r.t. uniform, we can simulate the QEX oracle by 1 query to the \mathrm{QMEM} oracle as follows: \mathrm{QMEM}(f)H^{\otimes n}\ket{0}^{\otimes n}\ket{0}=\sum_{x\in\mathbb{F}^{n}_{2}}\frac{1}{2^{n/2}}\ket{x,f(x)} (14) This shows us that at least w.r.t. the uniform distribution, \mathrm{QMEM} queries are unequivocally stronger than QEX queries, and therefore, also its noisy counterparts in QREX and QAEX queries. The proof of Theorem 3.4 shows us that if there exist two functions that differ on exactly one coordinate, no polynomial query quantum algorithm can distinguish the corresponding quantum states. We now formalize this notion to define the concept of approximate simulatability. Definition 3.9 ( \varepsilon -far functions) . A pair of Boolean functions f,g are \varepsilon -far if f\neq g only on an \varepsilon -fraction of the domain, for any \varepsilon>0 . We are now interested in the following question: Can a learning algorithm with access to (promise) sampling oracles efficiently distinguish between f and g w.h.p., for any \varepsilon -far pair f,g\in\mathcal{F} ? Definition 3.10 (Approximate Simulatibility of \mathrm{QMEM} ) . Consider an arbitrary pair of \varepsilon -far Boolean functions \{f,g\} , for \varepsilon>0 , and let h\in\{f,g\} . For any \delta>0 , a class of quantum (resp. classical) example oracles \mathcal{O} can (\varepsilon,\delta) -simulate (or approximately simulate) \mathrm{QMEM} (resp. MQ ) for a Boolean concept class \mathcal{F} w.r.t. a distribution \mathfrak{D} , if there exists a BQP (resp. BPP) algorithm A with query access to any \mathcal{O}\left(\mathfrak{D},h\right) A can figure out if h=f or if h=g , w.p. \geq 1-\delta . Theorem 3.5 . QEX cannot (\varepsilon,\delta) -simulate \mathrm{QMEM} w.r.t. \mathcal{U}\left(\{0,1\}^{n}\right) . Proof. Suppose f and g are Boolean functions that differ on a polynomial sized subset \mathcal{S}\subset\mathbb{F}^{n}_{2} , i.e., \absolutevalue{\ccS}=\operatorname{poly}\left(n\right) . Therefore, \norm{f-g}_{1}=\frac{1}{2^{n}}\sum_{x}\absolutevalue{f(x)-g(x)}=\frac{\absolutevalue{\ccS}}{2^{n}}=\nicefrac{{\operatorname{poly}\left(n\right)}}{{2^{n}}}=\varepsilon . Suppose a quantum learner A makes Q queries to a QEX oracle \operatorname{QEX}\left(\mathcal{U},h\right) and wants to discriminate between the states \ket{\psi_f} and \ket{\psi_g} as described in Eq. 6 . From Fact 2.1 , we know that the best success probability of distinguishing between \ket{\psi_f} and \ket{\psi_g} is \frac{1}{2}+\frac{1}{2}D\left(\ket{\psi_f},\ket{\psi_g}\right) . If this probability is greater than 1-\delta for any \delta\in(0,\nicefrac{{1}}{{2}}) , then \innerproduct{\psi_f}{\psi_g}\leq 2\sqrt{\delta\cdot(1-\delta)} . Therefore, \displaystyle\innerproduct{{\psi_f}}{\psi_g} \displaystyle\leq 2\sqrt{\delta\cdot(1-\delta)} (15) \displaystyle\implies{\left(\sum_{x\notin\mathcal{S}}\sqrt{\mathcal{U}(x)}\right)}^{Q} \displaystyle\leq 2\sqrt{\delta\cdot(1-\delta)} (16) \displaystyle\implies{\left(1-\sum_{x\in\mathcal{S}}\sqrt{\mathcal{U}(x)}\right)}^{Q} \displaystyle\leq 2\sqrt{\delta\cdot(1-\delta)} (17) \displaystyle\implies{\left(1-\varepsilon\right)}^{Q} \displaystyle\leq 2\sqrt{\delta\cdot(1-\delta)} (18) \displaystyle\implies{\left(1-\varepsilon\right)}^{2Q} \displaystyle\leq 4\delta (19) \displaystyle\implies 2Q\log\left(1-\varepsilon\right) \displaystyle\leq\log\left(4\delta\right) (20) \displaystyle\implies\frac{-2Q\varepsilon}{1-\varepsilon} \displaystyle\leq\log\left(4\delta\right). (21) The inequality in Eq. 21 follows from applying the inequality \log(1+x)\geq\nicefrac{{x}}{{1+x}},\,\forall x>-1 to the LHS of Eq. 20 . Plugging in the value of \varepsilon , we see that Q={\Omega\left(\frac{2^{n}}{\operatorname{poly}\left(n\right)}\log\left(\frac{1}{\delta}\right)\right)} . Hence, there does not exist any query efficient quantum learner A^{\text{\acs{QEX}}} that can distinguish between \ket{\psi_f} and \ket{\psi_g} with probability \geq 1-\delta . ∎ Table 1: A Taxonomy of Classical and Quantum PAC Learning Oracles. Classical Sampling oracles produce a random sample, while Quantum Sampling oracles produce a quantum state. Active oracles allow arbitrary queries. The representation column contrasts classical bit-pairs with quantum superposition states. Name Paradigm Description Sample/State Obtained Classical Oracles EX Sampling Standard Example (x,c(x)) where x\sim\mathfrak{D} REX Sampling R. Class. Noise (x,y^{\prime}) where y^{\prime} flipped w.p. \eta AEX Sampling Agnostic Example (x,y)\sim\mathfrak{D}_{\mathcal{X}\times\mathcal{Y}} (Joint Dist.) MEM Active Membership Query Input x\to Returns c(x) Quantum Oracles QEX Sampling Quantum Example \sum_{x}\sqrt{\mathfrak{D}(x)}\ket{x, c(x)} QREX Sampling Quantum RCN \sum_{x}(\sqrt{(1-p)\mathfrak{D}(x)}\ket{x, c(x)}+\newline \sqrt{p\mathfrak{D}(x)}\ket{x, \overline{c(x)}}) QAEX Sampling Quantum Agnostic \sum_{(x,y)}\sqrt{\mathfrak{D}(x,y)}\ket{x, y} QMEM Active Quantum Mem. \ket{x}\ket{0}\mapsto\ket{x}\ket{c(x)} (Superposition) 3.4 Separations in other Query Models To address concerns levied against the unrestricted nature of queries the learner can make to an MQ oracle, 13 introduced the local MQ oracle model, where the learner can only query the MQ oracle on some neighborhood 5 5 5 Fix some metric over the instance space \mathcal{X} , e.g., consider Hamming distance d when instances are sampled from the Boolean hypercube. Now, we are only allowed to query samples that are within an open ball of radius d around any instance in the training set. of a training set \mathcal{S} provided to the learner. Unfortunately, it was shown by 15 that even though learning with q -local MQ , for any constant q>0 is stronger than vanilla PAC learning, it is not sufficient to learn relatively simple classes of Boolean functions such as juntas or Decision Trees in a distribution-free setting. A similar oracle model is the Random Walk Query (RWQ) oracle model introduced by 26 , where the first point given to the learner is uniformly sampled from \mathbb{F}^{n}_{2} , while every succeeding point is obtained by a uniform random walk over \mathbb{F}^{n}_{2} . Remark 3.6 . We note here that local MQ and RWQ oracles can be used to obtain efficient PAC learners for DNF with respect to the uniform distribution 13 ; 26 . 33 showed that there is an exponential separation between Random Walk Queries and Continuous time Quantum Walk Queries (CQWQ) when performing graph traversal over certain classes of finite graphs. The following questions immediately come to mind: Open Problem 1 (Separation between Local MQ and CQWQ query learning) . Can we find a natural concept class where there is a separation between learning with RWQ (or local MQ) queries and learning with CQWQ queries? Open Problem 2 (Simulating QMQ using CQWQ queries) . Can CQWQ queries exactly or approximately simulate QMQ w.r.t. \mathcal{U}\left(\{0,1\}^{n}\right) .? 4 Sample Complexity separations In the noiseless setting, 23 and 59 showed that the classical (\varepsilon,\delta) -PAC sample complexity of learning a concept class \mathcal{C} with VC-dimension d is {{\Theta}\left(\frac{d}{\varepsilon}+\frac{\log{\left(\nicefrac{1}{\delta}\right)}}{\varepsilon}\right)} . In the agnostic setting, 95 and 90 showed that the (\varepsilon,\delta) -agnostic PAC sample complexity of learning a concept class \mathcal{C} with VC-dimension d is {{\Theta}\left(\frac{d}{\varepsilon^{2}}+\frac{\log{\left(\nicefrac{1}{\delta}\right)}}{\varepsilon^{2}}\right)}. We recall that having access to k classical samples (or quantum samples) is analogous to making k queries to the EX oracle (respectively, the QEX oracle) in the realizable case, and making k queries to the AEX oracle (respectively, the QAEX oracle) in the agnostic case. The first results on quantum vs classical sample complexity were given by 86 who showed that quantum and classical sample complexities were polynomially related in the noiseless setting as D={\operatorname{O}\left(nQ\right)} , for any concept class \mathcal{C} that is PAC learnable using D queries to the EX oracle and Q queries to the QEX oracle. This result was later improved by 9 , who showed that the quantum sample complexity in both the noiseless and agnostic settings is equal to the respective classical sample complexities up to a constant factor, thereby proving that quantum samples are not inherently more powerful than classical samples. The proof techniques of 9 included a state identification argument using “Pretty Good Measurement” and Fourier analysis. 58 later reproved the results of 9 using information-theoretic arguments. Lemma 4.1 (Quantum Sample Complexity 9 ; 58 ) . Given a benchmark concept class \mathcal{C} with VC-dimension d , the (\varepsilon,\delta) -quantum PAC sample complexity of learning \mathcal{C} is {{\Theta}\left(\frac{d}{\varepsilon}+\frac{\log{\left(\nicefrac{1}{\delta}\right)}}{\varepsilon}\right)} , while the (\varepsilon,\delta) -quantum agnostic PAC sample complexity of learning \mathcal{C} is {{\Theta}\left(\frac{d}{\varepsilon^{2}}+\frac{\log{\left(\nicefrac{1}{\delta}\right)}}{\varepsilon^{2}}\right)}. When marginal distributions over the instances are assumed, however, Lemma 4.1 may not hold. For example, 30 gives quantum sample complexity speedups for Boolean linear functions under bounded noise settings when the samples are drawn from a product distribution. This raises the following question: Open Problem 3 (Quantum Sample Complexity separations under non-uniform marginals) . Does there exist a natural concept class of non-linear Boolean functions for which we can demonstrate quantum sample complexity speedups over non-uniform marginal distributions? In the case of non-uniform marginals, one can restrict our attention to special marginals such as product distributions, smoothed product distributions, or isotropic log-concave distributions. We note that even in the case of a negative answer to Open problem 3 , this still leaves open the possibility for computational separations, as discussed in upcoming sections. 4.1 Generalized Quantum Example Oracles Recently, 29 proposed a new type of quantum agnostic example oracle, which they term mixture-of-superpositions (MOS) oracle \mathcal{O}_{\mathfrak{D}} . For any arbitrary distribution \mathfrak{D} over \mathcal{X}\times\mathbb{F}_{2} , querying \mathcal{O}_{\mathfrak{D}} yields the mixed state \rho_{\mathfrak{D}}=\underset{f\sim\mathcal{F}_{\mathfrak{D}}}{\mathbb{E}}\,\left[\,\ket{\psi_{\fD_\cX,f}}\bra{\psi_{\fD_\cX,f}}\,\right], (22) where \mathfrak{D}_{\mathcal{X}} is the marginal distribution over \mathcal{X} , and \mathcal{F}_{\mathfrak{D}} is the probability distribution over all labeling functions f:\mathcal{X}\mapsto{\{0,1\}} induced by \mathcal{D} . Measuring all n+1 qubits of \rho_{\mathfrak{D}} produces a sample from \mathfrak{D} as follows: \displaystyle\bra{x,y}\rho_{\mathfrak{D}}\ket{x,y} \displaystyle=\underset{f\sim\mathcal{F}_{\mathfrak{D}}}{\mathbb{E}}\,\left[\,\absolutevalue{\bra{x,y}\ket{\psi_{\fD_\cX,f}}}\,\right]=\underset{f\sim\mathcal{F}_{\mathfrak{D}}}{\mathbb{E}}\,\left[\,\mathfrak{D}_{\mathcal{X}}(x)\cdot\mathbb{I}_{f(x)=y}\,\right] (23) \displaystyle\implies\bra{x,y}\rho_{\mathfrak{D}}\ket{x,y} \displaystyle=\mathfrak{D}_{\mathcal{X}}(x)\cdot\underset{f\sim\mathcal{F}_{\mathfrak{D}}}{\operatorname{Pr}}\mathbb{I}_{f(x)=y}]=\mathfrak{D}(x,y). (24) The MOS oracle straightforwardly generalizes the \mathrm{QEX} , \mathrm{QREX} , and \mathrm{QAEX} oracles, and it is admittedly more general than the \mathrm{QAEX} oracle since it allows us to model correlated label noise. Later in Section 5.2 , we shall see results that indicate the power of the MOS oracle. However, with respect to the sample complexity, 29 proves that in the agnostic setting, quantum (MOS) sample complexity is equivalent to classical sample complexity up to logarithmic factors. Concretely, the MOS quantum agnostic sample complexity is {\Omega\left(\frac{d}{\varepsilon^{2}\log{d}}+\frac{\nicefrac{{1}}{{\delta}}}{\varepsilon^{2}}\right)} . This naturally leads us to the following question. Open Problem 4 (Optimal Mixture-of-Superposition Sample Complexity Lower Bound) . Is the \frac{d}{\varepsilon^{2}\log{d}} term in the mixture-of-superpositions sample complexity tight? If there is a positive answer to Open problem 4 , it would indicate that the MOS model provides a slight (but non-trivial) advantage over the standard quantum example models even in terms of sample complexity. 4.2 Sample Complexity in the Multi-class setting 79 investigated a host of different learning settings, such as noisy and agnostic offline and online quantum PAC learning, where \absolutevalue{\cY}<\infty , and showed that quantum and classical sample complexities are equivalent up to constant factors in all but one of these cases (the bounds in the online multi-class agnostic setting are not tight and differ from the best-known classical bounds by a log factor 6 6 6 See section 5.4 of 79 for a detailed discussion on this setting ). The results of 79 naturally lead to the following questions. Open Problem 5 (Multi-class Agnostic Sample Complexity Separation) . Are the classical and quantum query/sample complexities equivalent (up to constant factors) in the online multi-class agnostic setting? Open Problem 6 (Sample Complexity Separation for Unbounded Labels) . Are the classical and quantum query/sample complexities equivalent (up to constant factors) in the unbounded label case, even in the realizable offline PAC setting? Open Problem 7 (Multi-class Mixture-of-Superposition Sample Complexity) . What is the mixture-of-superposition sample complexity 29 in the multi-class realizable and agnostic settings? Finally, we may ask the above questions in terms of other recently introduced quantum online learning frameworks as well. Open Problem 8 (Sample Complexity separations in Different Frameworks) . Does the online learning framework of 79 extend to the more general quantum online-learning framework introduced by 14 ? 4.3 Sample Complexity separations via Unitary Access In Definitions 3.4 and 3.5 , instead of assuming query access to the \mathrm{QEX} and \mathrm{QAEX} oracles, the learner can instead be provided with access to copies of the corresponding quantum states in the RHS of Eqs. 3 and 5 . The results of 9 ; 58 ; 79 also hold in this equivalent setting. The learning algorithms throughout this survey assume this setup. On the other hand, if we assume a white-box setting, where the quantum learner has unitary access to the quantum oracles generating the quantum samples directly (instead of only being able to access the quantum samples), then 85 showed that the sample complexity of (\varepsilon,\delta) - (noiseless) PAC learning a concept class \mathcal{C} with VC-dimension d is \operatorname{\tilde{O}}\left(\frac{d}{\sqrt{\varepsilon}}+\frac{\log{\left(\nicefrac{1}{\delta}\right)}}{\sqrt{\varepsilon}}\right). Open Problem 9 (White-Box Agnostic Sample Complexity Separations) . Does the quantum sample complexity advantage of 85 extend to the agnostic setting? The proof of 85 critically uses the fact that having unitary access implies having access to the inverses of the unitaries. One might ask the following question, in terms of a more grey-box setting. Open Problem 10 (Grey-Box Sample Complexity Separations) . What is the quantum (realizable/agnostic) sample complexity of learning when the quantum learner has access to a quantum channel that generates quantum examples? Here, we assume that having access to a quantum channel does not necessarily imply access to its inverse. This question becomes very interesting in light of a recent work by 91 , who show that access to the inverse is a crucial component in quantum speedups involving amplification and estimation. Finally, we re-examine the sample complexity results of 79 under this new approach. Open Problem 11 (White-Box Multi-class Sample Complexity Separations) . Does the quantum sample complexity advantage of 85 extend to the multi-class setting as explored by 79 ? 5 Time Complexity separations The results in Section 4 are information-theoretic in nature and do not disallow quantum vs classical separations in the computational sense. In other words, the results in Section 4 indicate that every concept class \mathcal{C} that is learnable by quantum learners using a polynomial number of samples/queries is also learnable by classical learners using a polynomial number of samples/queries. However, Lemma 4.1 does not imply that if a concept class \mathcal{C} is efficiently learnable by a quantum learner, it must be efficiently learnable by a classical learner. In this section, we investigate separations in the running times between quantum and classical learners. 5.1 Separations via the Hidden Subgroup Problem 86 first provided strong evidence that there is a separation between quantum and classical learning by using a concept class \mathcal{C} based on factoring Blum integers 7 7 7 A Blum integer is an integer N=pq where p,q are m -bit primes congruent to 3\mod{4} . 70 . Factoring Blum integers is believed to be computationally intractable classically 70 ; 3 , but can be efficiently solved by quantum algorithms for the Abelian Hidden Subgroup Problem (Abelian HSP ( HSP )) 88 . A similar separation between classical and quantum was later demonstrated by 75 , using a concept class \mathcal{C}_{\text{DLP}} based on the DLP ( DLP ). Definition 5.1 ( DLP ) . Given a large prime p , a generator g of \mathbb{Z}^{*}_{p}=\{1,2,\ldots,p-1\} , and an input x\in\mathbb{Z}^{*}_{p} , compute \log_{g}x in time \operatorname{poly}\left(\left\lceil\log_{2}p\right\rceil\right) . It is widely believed that the DLP problem is classically intractable 22 , but we can efficiently solve the DLP problem using Shor’s algorithm 88 . Using this technique, 75 obtained a quantum kernel estimation procedure to learn \mathcal{C}_{\acs{DLP}} . 5.1.1 The Hidden Subgroup Problem over finite Abelian groups The results obtained by 86 ; 75 are not surprising, especially in light of Simon’s algorithm and Shor’s algorithm, which are textbook examples of quantum speedups. Both Simon’s algorithm and Shor’s algorithm solve restricted instances of a more general problem known as the Hidden Subgroup Problem ( HSP ), defined below. Definition 5.2 (The Hidden Subgroup Problem) . Let \mathcal{G} be a known finite group, \mathcal{S} be a finite set, and a black-box function f:\mathcal{G}\mapsto\mathcal{S} s.t. f(x)=f(y)\iff x\mathcal{H}=y\mathcal{H}, where \mathcal{H}\leq\mathcal{G} is some unknown subgroup, and h\in\mathcal{H} . Determine a generating set for \mathcal{H} . In Definition 5.2 , the black-box function f is said to hide the subgroup \mathcal{H} . Alternatively, f can be thought of as separating the cosets of \mathcal{H} . Most exponential separations between quantum and classical computing are a consequence of quantum speedups with respect to HSP over Abelian groups. Example 5.1 . Restricted versions of the Abelian- HSP problem amenable to quantum speedups include • Deutsch’s problem: \mathcal{G}=\mathbb{Z}_{2} and \mathcal{H} is either 0 (balanced) or \mathbb{Z}_{2} (constant), • Simon’s problem: \mathcal{G}=\mathbb{Z}^{n}_{2} and \mathcal{H}=\{0,s\} , where s\in\mathbb{Z}^{n}_{2} is some secret, and • DLP : \mathcal{G}=\mathbb{Z}_{p}\times\mathbb{Z}_{p} , and \mathcal{H}=\{(0,0),(1,\log_{g}x),\ldots,(p-1,(p-1)\log_{g}x)\} . In fact, we know how to efficiently solve any Abelian HSP problem. Lemma 5.1 (Efficiently solving Abelian HSP , Theorem 2.2 of 47 ) . Let \mathcal{G} be a known finite group, \mathcal{S} be a finite set, f:\mathcal{G}\mapsto\mathcal{S} be a black-box function that hides a subgroup \mathcal{H}\leq\mathcal{G} . There exists a quantum algorithm that has size {\operatorname{O}\left(\operatorname{polylog}\left(\absolutevalue{\cG}\right)\right)} and runs in time \log{\abs{\cG}} to output a generating set of \mathcal{H} w.p. at least 1-\nicefrac{{1}}{{\absolutevalue{\cG}}} . A critical component in efficiently solving the HSP problem over finite Abelian groups is the existence of an efficient Quantum Fourier Transform (QFT) over \mathcal{G} . 34 showed the existence of a {\operatorname{O}\left(\log n+\operatorname{polylog}\left(\nicefrac{{1}}{{\varepsilon}}\right)\right)} depth and {\operatorname{O}\left(n\log{\nicefrac{n}{\varepsilon}}\right)} size circuit to approximate QFT over the group \mathbb{Z}_{2^{n}} . 32 proposed an efficient quantum decomposition algorithm, where given a generating set \{g_{1},\ldots,g_{s}\} of a finite Abelian group \mathcal{G} , we can output a set of elements d_{1},\ldots,d_{\ell} s.t. \mathcal{G}=\mathbb{Z}_{d_{1}}\times\ldots\times\mathbb{Z}_{d_{\ell}} in time \operatorname{polylog}\left(\absolutevalue{G}\right) . Combining the results of 34 ; 32 gives us Shor’s factoring algorithm (via Lemma 10.1 ). 5.1.2 HSP as a Concept class We now define a new concept class induced by the HSP problem. Definition 5.3 ( HSP induced Concept class) . Any decision problem over an HSP instance {\mathsf{P}}=(\mathcal{G},\mathcal{H}) that can be posed as a membership problem over a set of instances \mathcal{X} is said to be a concept class \mathcal{C}:\mathcal{X}\mapsto\{0,1\} induced by \acs{HSP}_{{\mathsf{P}}} . Example 5.2 . Let {\mathsf{P}}=(\mathcal{G},\mathcal{H}) be an HSP instance s.t. \absolutevalue{\cG}=2^{n} . The following decision problems \mathcal{C}:\mathbb{F}^{n}_{2}\mapsto\{0,1\} are concept classes induced by \acs{HSP}_{{\mathsf{P}}} : • Given a string x\in\mathbb{F}^{n}_{2} , is \absolutevalue{\cH}\geq\absolutevalue{x}? • Given a string x\in\mathbb{F}^{n}_{2} , does \mathcal{H} have a generating set of size at least \absolutevalue{x} ? Remark 5.1 . Definition 5.3 is not restricted to the Abelian HSP case and can be defined for HSP over arbitrary finite groups. Classically, obtaining efficient learners for concept classes induced by HSP over arbitrary finite Abelian groups is subject to various hardness assumptions, while concept classes induced by HSP over finite Abelian groups seem to admit efficient quantum learning algorithms. This leads us to the following open question. Open Problem 12 (Separation for Abelian HSP -induced concept classes) . If \mathcal{C}:\mathbb{F}^{n}_{2}\mapsto\{0,1\} is any concept class induced by some HSP over a finite Abelian group \mathcal{G} , can we show that there exists an efficient quantum learning algorithm for \mathcal{C} ? Does the same hold under restricted and unrestricted noise models? Remark 5.2 . We conjecture that Open problem 12 is true at least in the noiseless case. Observation 5.1 . Assuming the hardness of DLP 70 ; 3 , Open problem 12 implies the separation between quantum and classical learning for several HSP -induced concept classes even in the noiseless case (as seen in 86 ; 75 ). 5.1.3 The Hidden Subgroup Problem over Arbitrary Groups Even though known efficient algorithms for HSP over Abelian groups require efficient subroutines for QFT, it is unknown if the ability to efficiently perform QFT over a group G is either a necessary or a sufficient condition for efficiently solving HSP over \mathcal{G} in the non-Abelian case. 46 show that there exist QFT based quantum algorithms to solve HSP over arbitrary finite groups \mathcal{G} , which make only \log\absolutevalue{G} queries to O_{f} but requires exponential running time. Efficient algorithms exist for exactly calculating or approximating QFT over classes of well-behaved non-Abelian groups, such as metacyclic groups 8 8 8 A metacyclic group \mathcal{G} is a group having a cyclic normal subgroup \mathcal{N} s.t. \mathcal{G}/\mathcal{N} is also cyclic. , or even metabelian groups 9 9 9 A metabelian group \mathcal{G} is a group having a normal subgroup \mathcal{N} s.t. \mathcal{N} and \mathcal{G}/\mathcal{N} are both Abelian. 80 . The reader is encouraged to peruse the surveys by 76 and 98 for a comprehensive overview of HSP over arbitrary finite groups, which is an important problem in its own right, even outside the context of learning theory. Efficient quantum algorithms for HSP over certain classes of finite non-abelian groups imply very interesting results in theoretical computer science, such as efficient solvability of Graph Isomorphism ( GI ) and Shortest Vector Problem ( SVP ( SVP )). SVP , in particular, is central to the field of post-quantum cryptography, and its connection to learning is discussed in the next section. 5.1.4 Other open questions Consider the symmetric group S_{n} . Since S_{n} is a group with n! elements, defining any HSP -induced concept class that displays a separation between quantum and classical learnability would be very interesting. It might also be worthwhile looking at concept classes induced by subgroups of S_{n} with more structure in pursuit of efficient quantum learning algorithms. Open Problem 13 (Separations for non-abelian HSP -induced concept classes) . Does there exist a concept class induced by HSP on S_{n} or any subgroup of S_{n} (such as a permutation group or an alternating group), such that there is a super-polynomial separation between quantum and classical learning algorithms? We note here that the answer to Open problem 13 is likely to be negative when we require the additional notion of efficient learnability for quantum algorithms. We specifically highlight the important case of dihedral groups (see Definition 10.1 ) due to their close connection to Lattice-based cryptography. Informally, an efficient quantum algorithm for solving dihedral HSP implies that \acs{SVP}\in{\mathsf{BQP}} 84 . This would essentially imply that {\mathsf{NP}}\subseteq{\mathsf{BQP}} since SVP has been shown to be {\mathsf{NP}} -hard under restricted settings 18 . The best-known algorithm for solving the dihedral HSP is a subexponential time algorithm by 72 . The following open question underscores the above discussion. Open Problem 14 (Hardness of learning Dihedral HSP -induced concept classes) . Can we give hardness guarantees for efficient quantum learning of any concept class induced by HSP on an arbitrary dihedral group \mathcal{G} for N\geq 3 ? 5.2 Separations based on Lattice-Based Problems In computational hardness, we usually care about problems with known worst-case hardness guarantees since we want to design algorithms that run efficiently even on the worst possible input. However, for cryptographic schemes to be secure, we require hardness guarantees to hold even for random keys, i.e., we require average-case hardness guarantees . This is a challenging task since it is not immediately apparent how to create hard instances of problems even when it has worst-case hardness guarantees. In fact, for many {\mathsf{NP}} -hard problems like Graph coloring (see 44 ), such a guarantee does not exist. 5.2.1 Introducing the Learning with Errors Problem 1 showed that for certain lattice-based problems, such a reduction from worst-case to average-case hardness exists. Following this, 84 introduced the Learning with Errors ( LWE ) problem and showed that an efficient algorithm to solve the LWE problem gives us an efficient algorithm 10 10 10 Efficiently solving LWE actually implies an efficient solution to the Gap- SVP problem. for SVP . We define the decision version of the LWE problem now. Definition 5.4 (Decision Version of LWE ) . We are given m independent samples (x,y)\in\mathbb{Z}^{n}_{q}\times\mathbb{Z}_{q} , for some prime q\geq 2 , with the promise that they are sampled according to one of the following distributions: 1. The uniform distribution: (x,y)\sim\mathfrak{U}\left(\mathbb{Z}^{n}_{q}\times\mathbb{Z}_{q}\right) . 2. The LWE distribution: The marginal distribution of x\in\mathbb{Z}^{n}_{q} is uniform and y=\left\langle s,x\right\rangle+\varepsilon\mod q , where s\in\mathbb{Z}^{n}_{q} is a secret string, and \varepsilon\sim{\mathfrak{D}} is some noise parameter. Determine if the samples are drawn from the LWE distribution. The LWE problem is also a generalization of another important learning problem - Learning Parities with Noise ( LPN ) where q=2 and \mathcal{\mathfrak{D}} is a Bernoulli distribution over \mathbb{Z}_{2} . LPN is an average-case version of the NP-hard problem decoding a linear code 78 . Observation 5.2 . Without the presence of the random noise term \varepsilon , LWE and LPN can be efficiently solved using Gaussian elimination over the samples. Remark 5.3 . Unless explicitly specified, the LWE and LPN problems are assumed to be in the RCN setting, i.e., \varepsilon is RCN noise. In the previous section, we saw that SVP reduces to the Dihedral HSP , similar to LWE . We make the connection between these two classes of problems explicit below. Remark 5.4 (Connection between LWE and the Dihedral HSP ) . LWE can be reduced (average-worst case reduction) to a stronger variant of the Dihedral HSP , known as the robust Dihedral HSP . Since known subexponential (quantum) algorithms for solving dihedral HSP 72 do not quite work for robust Dihedral HSP , there do not exist any known subexponential (quantum) learning algorithms for LWE . 5.2.2 Learning algorithms for LWE and LPN 21 provided the first classical sub-exponential time and sample learning algorithm for LWE (and hence LPN ) that requires 2^{{\operatorname{O}\left(n/\log{n}\right)}} time and samples. Interestingly, 48 showed that LPN with respect to uniform marginals in the agnostic setting reduces to LPN with respect to uniform marginals in the RCN setting. Hence, the algorithm by 21 also implies a sub-exponential time/sample learning algorithm for LPN in the agnostic setting (under uniform marginals). In the quantum setting, however, there exist efficient quantum learning algorithms for LWE 55 and LPN 35 , with access to a special oracle that we denote as the \mathrm{QREX}_{\text{\acs{LWE} }}^{s,\varepsilon} oracle, and define as follows: \mathrm{QREX}_{\text{\acs{LWE} }}^{s,\varepsilon}\ket{0}\ket{0}\mapsto\frac{1}{\sqrt{q^{n}}}\underset{x\in\mathbb{F}^{n}_{q}}{\sum}\ket{x}\ket{\inprod{s}{x}+\varepsilon\mod{q}}\;\;,\varepsilon\sim\mathfrak{D}. It is important to note that the results of 55 only hold when the quantum learner is provided oracle access to the \mathrm{QREX}_{\text{\acs{LWE} }}^{s,\varepsilon} oracle, unlike in the classical case, where we only have access to m classical labeled examples. Remark 5.5 . The efficient learning results of LWE and LPN 55 ; 35 also follow from the MOS model 29 as outlined in Section 4.1 . Despite the presence of powerful oracle models providing separations, it is important to understand the exact avenue of speedup for quantum learners. The following question therefore naturally comes to mind: Open Problem 15 (Quantum learning for LWE under random examples) . Given access to quantum examples of the form: \frac{1}{\sqrt{\absolutevalue{\ccS}}}\underset{x\in\mathcal{S}\subseteq[m]}{\sum}\ket{x}\ket{\inprod{s}{x}+\varepsilon\mod{q}}, where \mathcal{S} is unknown and x\sim\mathfrak{U}\left(\mathbb{Z}^{n}_{q}\right) , does there exist an efficient quantum learning algorithm for LWE ? We note that it is likely that the answer Open problem 15 to is a negative one, since LWE is believed to be hard for many reasons. If efficient quantum algorithms exist for LWE under random examples, then there would exist efficient quantum algorithms for breaking the LWE cryptosystem. This is highly unlikely since such a quantum algorithm would also imply an efficient algorithm for SVP . If SVP is believed to be {\mathsf{NP}} -complete, a positive answer to Open problem 15 would imply {\mathsf{NP}}\subseteq{\mathsf{BQP}} . Unlike LWE , cryptographic applications for LPN have been limited in scope 83 . Recently, a series of works 24 ; 99 showed that the worst-case hardness of the NCP ( NCP ) under very low noise rates is implied by the hardness of LPN at very high noise rates. However, unlike the hardness guarantees of SVP , NCP is not believed to be {\mathsf{NP}} -hard 24 . Therefore, it is important to question the existence of an efficient quantum algorithm for LPN as a separate question from LWE . Open Problem 16 (Quantum learning for LPN under random examples) . Given access to quantum examples of the form: \frac{1}{\sqrt{\absolutevalue{\ccS}}}\underset{x\in\mathcal{S}\subseteq[m]}{\sum}\ket{x}\ket{\inprod{s}{x}+\varepsilon\mod{2}}, where \mathcal{S} is unknown, x\sim\mathfrak{U}\left(\mathbb{Z}^{n}_{2}\right) , and \varepsilon\sim\mathrm{Ber}(\mathbb{Z}_{2}) , does there exist an efficient quantum learning algorithm for LPN ? 5.3 Learning separations for Halfspaces Halfspaces are a class of Boolean functions that are extremely important to the field of learning algorithms. Boosting algorithms, SVMs, and neural networks all employ some variant of the halfspace learning problem under the hood. A halfspace is a Boolean function c\in\mathcal{C}:\mathbb{R}^{d}\mapsto\mathbb{F}_{2} defined as follows: c(x)=\operatorname{sign}\left(\left\langle a,x\right\rangle-\theta\right)=\operatorname{sign}\left(\sum_{i\in[m]}a_{i}x_{i}-\theta\right),\;\;\;\;a,x,\theta\in\mathbb{R}^{d}. Any learner that takes labeled samples drawn according to a distribution \mathfrak{D} over \mathbb{R}^{d}\times\mathbb{F}_{2} and outputs a hypothesis h s.t. \operatorname{err}_{\mathfrak{D},\mathcal{C}}\left(h\right)\leq\operatorname{opterr}_{\mathfrak{D}}\left(\mathcal{C}\right)+\beta+\varepsilon is a beta -optimal learner. The learner is considered to be efficient if it runs in time \operatorname{poly}\left(d,\frac{1}{\varepsilon}\right) . It is easy to see that in the realizable case/noiseless setting, halfspaces can be efficiently learnt using linear programming techniques. Classical efficient learners for halfspaces also exist for bounded noise models such as RCN 20 , Massart noise 41 and Tsybakov noise 39 under log-concave marginal distributions. The most interesting case of halfspace learning seems to be beyond bounded noise models. Learning halfspaces in the agnostic setting under the uniform marginal assumption directly implies learning algorithms for LPN . Hence, halfspace learning seems to be a much harder problem than LPN . Various hardness results are known for improper 37 ; 92 as well as proper 57 ; 48 ; 40 classical learning of halfspaces in the agnostic setting. It is important to note that the hardness results are in the random classical example setting (without queries). Earlier, we have seen evidence of quantum and classical learning separations in the case of LWE 55 or LPN 35 when the quantum learner has query access to the \mathrm{QREX} oracle. It is worthwhile to ask if such a separation is possible even for halfspace learning. Open Problem 17 (Efficient Quantum Agnostic Learning of Halfspaces) . Does there exist a sample/query/time efficient quantum agnostic learner with access to \mathrm{QAEX} queries for halfspaces assuming uniform marginal over the instances? 5.4 Learning separations for Decision Trees The decision tree representation of a Boolean function f:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2} is a binary tree such that every path from the root to any leaf corresponds to a truth table row of f . The leaf nodes are labeled by \{0,1\} or \{\pm 1\} , the internal nodes are labeled by the literals: variables x_{i} (or their negations), and every internal node has two outgoing edges labeled true and false. The number of leaves (or the number of internal nodes) of the decision tree is known as its size while the longest path from the root of the decision tree to any leaf node is known as the depth of the decision tree. Since the decision tree representation of a Boolean function is not unique, computationally, we would prefer to represent f in terms of the “smallest” decision tree. However, 62 showed that constructing the optimal decision tree corresponding to an arbitrary Boolean function is an {\mathsf{NP}} -complete problem. The study of efficient learning algorithms for decision trees with polynomially bounded depth was initiated by 45 , who gave a classical proper quasi-polynomial time and sample learning algorithm in the noiseless setting. It was shown recently by 71 that the results of 45 are essentially optimal (even with MQ access). 73 in their seminal work circumvented the superpolynomial lower bound for decision tree learning by considering the improper learning setting. Their results were later extended to the agnostic setting 54 ; 49 ; 67 . However, all of these algorithms required access to membership queries. 31 gave quantum algorithms for learning decision trees in all noise models that are strictly polynomial in all parameters while only requiring access to sampling query oracles. 5.4.1 Techniques and Open Questions 73 showed that if a Boolean function f is computed by a decision tree with size t , then \norm{\spectrum{f}}_{1}\leq t . Alternatively, if a Boolean function f is computed by a decision tree with at most {\operatorname{O}\left(t\right)} nodes, then \norm{\spectrum{f}}_{1}={\operatorname{O}\left(t\right)} . Hence, we can straightforwardly apply Corollary 9.4 to yield a polynomial-time learning algorithm for polynomial-sized decision trees using MQ queries. The tricky part is removing the dependence on MQ or \mathrm{QMQ} queries for efficient learnability. Below, we discuss how to achieve this in the noiseless case, and defer the discussion on learning under more restrictive noise settings to 31 . 28 showed how to obtain an approximate Fourier sampling state 11 11 11 see Lemma 8.1 using 1 call to the \operatorname{QEX}\left(\mathcal{U},f\right) oracle as follows: \frac{1}{\sqrt{2}}\sum_{\mathcal{S}\subseteq[n]}\hat{f}(\mathcal{S})\ket{\ccS}\ket{1}+\frac{1}{\sqrt{2}}\ket{0\ldots 0}\ket{0}. (25) Applying Lemma 7.1 (Amplitude Amplification) . to the state obtained in Eq. 25 , we can now obtain the Fourier sampling state \ket{\psi}=\sum_{\mathcal{S}\subseteq[n]}\hat{f}(\mathcal{S})\ket{\ccS} using an additional {{\Theta}\left(1\right)} queries to the \operatorname{QEX}\left(\mathcal{U},f\right) oracle. In the spirit of Corollary 9.4 , it is now straightforward to obtain a weak learner for decision trees by sampling from the Fourier distribution, and obtain a corresponding strong learner using (quantum or classical) Boosting algorithms. As the observant reader must have deduced, learning algorithms for improper decision tree learning (especially in the agnostic setting), both in the classical and quantum settings, assume a uniform marginal over the instances. This raises the following question: Open Problem 18 (Efficient Quantum Agnostic Learning of Decision Trees under non-uniform marginals) . Can we obtain efficient quantum (agnostic) learners for polynomially bounded decision trees with non-uniform marginal over the instances, without access to QMQ? 5.5 Learning separations for DNFs A DNF function f is a disjunction of DNF clauses, which in turn are conjunctions of Boolean literals \tilde{x} . Mathematically, f(x)=C_{1}(x)\lor C_{2}(x)\lor\ldots\lor C_{m}(x), where each clause C(x)=\land_{i\in\mathcal{S}}\tilde{x}_{i} is defined with respect to some \mathcal{S}\in[n] . The width of DNF f is the maximum number of literals in any clause of f , and the size of DNF f is the total number of clauses of f . When the learner only has access to random examples, 36 showed that even improperly learning DNFs would imply an efficient algorithm for refuting random k -SAT formulas. 12 12 12 If {\mathsf{P}}\neq{\mathsf{NP}} , it is hard to refute k -SAT formulas 60 . Since learning DNFs (in the realizable/RCN settings) reduces to learning LPN 48 , the results of 36 also give hardness results for classically learning LPN with random examples. Classically, we know of efficient improper learning algorithms for DNF (depth-2 {\mathsf{AC}}^{0} circuits) in the noiseless/ RCN settings under the uniform (or “near”-uniform) marginal assumption, only when the learner has access to membership queries 65 . In the quantum learning regime, however, 28 gave efficient improper quantum learning algorithms for DNFs in the realizable and RCN settings using quantum learners with access to \mathrm{QEX} or \mathrm{QREX} oracles. In the non-uniform marginal setting, 50 showed that an efficient classical learning algorithm for DNFs exists under the membership query model when the instances are sampled from any product distribution. They also show that a DNF learning algorithm exists for random examples only when the instances are sampled from a smoothed product distribution 89 . 68 showed that DNFs can be efficiently PAC learned by quantum learners with access to the \mathrm{QEX} when the samples are drawn from a product distribution. 5.5.1 Techniques and Open Problems 64 showed that any s -term DNF is spectrally concentrated on at most \nicefrac{{1}}{{2}}+\nicefrac{{1}}{{\operatorname{poly}\left(s\right)}} fraction of its domain. This allows us to straightforwardly apply Lemma 9.2 to learn DNFs classically in the noiseless setting (with a polynomial blowup in s and the noise parameter for the bounded noise setting). Using techniques similar to the ones described in the decision tree learning section, 28 got rid of the dependence on MQ by using quantum sampling oracles. This leaves us with the following open question on learning DNFs in the unrestricted noise settings: Open Problem 19 (Efficient Quantum Agnostic Learning of DNFs) . Does there exist an efficient agnostic quantum learning algorithm (with access to the \mathrm{QAEX} oracle) for learning DNF formulas over uniform marginals? We would also like to pose the following open question as a follow-up to the results of 50 and 68 . Open Problem 20 (Efficient Quantum Agnostic Learning of DNFs under non-uniform marginals) . Does there exist an efficient agnostic quantum learning algorithm (with access to the \mathrm{QAEX} oracle) for learning DNF formulas when the marginal distribution over the instances is a smoothed product distribution? 5.6 Learning separations for Juntas A junta is a Boolean function that only depends on a subset of its input variables. More formally, a k -junta is a Boolean function on n variables that depends only on an unknown subset of k variables and is invariant under the remaining n-k variables. Fact 5.1 . Every k -junta can be expressed as a decision tree of size 2^{k} or a DNF formula of size k . Every decision tree of size k can be expressed as a DNF formula of size k . Although the problem of learning k -juntas straightforwardly reduces to that of learning DNF functions of width k , we mention the results related to learning k -juntas separately here. Trivially, learning a k -junta from random classical examples can be done using 2^{k}\log{n} samples and {\operatorname{O}\left(n^{k}\right)} time (by solving linear equations). 81 gave the first non-trivial algorithm for learning k -juntas which takes time {\operatorname{O}\left(n^{\nicefrac{{\omega k}}{{\omega+1}}}\operatorname{poly}\left(n\right)\right)} , where matrix multiplication can be solved in time {\operatorname{O}\left(n^{\omega}\right)} . 13 13 13 Here, \omega<2.376 is the matrix multiplication exponent. Hence 81 takes time {\operatorname{O}\left(n^{\nicefrac{{2k}}{{3}}}\right)} . This was later improved by 93 to {\operatorname{O}\left(n^{0.6k}\operatorname{poly}\left(n\right)\right)} . 93 also gave a {\operatorname{O}\left(n^{0.8k}\operatorname{poly}\left(n,\nicefrac{{1}}{{\varepsilon}}\right)\right)} for learning k -juntas in the RCN setting with noise rate \varepsilon>0 . In the quantum setting, the DNF learning algorithm of 28 implies a {\operatorname{O}\left(2^{6k}\operatorname{poly}\left(n,\nicefrac{{1}}{{\varepsilon}}\right)\right)} time and sample learning algorithm for k -juntas using QEX queries. 12 improved upon this result by giving a {\operatorname{O}\left(\frac{k}{\varepsilon}\log k\right)} time and 2^{k}\log{\nicefrac{1}{\varepsilon}} sample learning algorithm using QEX queries. Both of these results also hold in the RCN setting with noise rate \eta with an additional multiplicative factor of \operatorname{poly}\left(\nicefrac{{1}}{{\eta}}\right) . 31 design the first quantum algorithm that learns k -juntas in the agnostic setting. However, the running time of their algorithm depends on n and has far worse dependence on k and \varepsilon . This brings us to the following question: Open Problem 21 (Separations for Agnostic Learning of Juntas) . What is the best time and sample complexity for (quantum) learning k -juntas in the agnostic setting without using membership queries? 5.7 Learning separations for Shallow Circuits In this section, we focus on learning shallow classical circuits as concept classes. We start by considering the simplest classical circuit - the {\mathsf{NC}}^{0}_{d} class. An {\mathsf{NC}}^{0} circuit is a constant-depth, polynomial-size Boolean circuit on n -bits that consists of NOT, and bounded fan-in AND and OR gates. When the circuit has depth d={\operatorname{O}\left(1\right)} , we use the notation {\mathsf{NC}}^{0}_{d} . Since {\mathsf{NC}}^{0}_{d} circuits have bounded fan-in (say b={\operatorname{O}\left(1\right)} ) and constant depth (say d={\operatorname{O}\left(1\right)} ), the output bit 14 14 14 Recall that we are only considering 1 -bit output Boolean functions, i.e., decision problems as concept classes in this survey. is influenced by at most b^{d}={\operatorname{O}\left(1\right)} input variables. Hence, {\mathsf{NC}}^{0}_{d} circuits are {\operatorname{O}\left(b^{d}\right)} juntas! We refer the reader to the earlier discussion on learning juntas in Section 5.6 , for a more detailed understanding of learning concept classes generated by {\mathsf{NC}}^{0} circuits. We now move the discussion on separations between quantum and classical learning algorithms to learning the {\mathsf{AC}}^{0} and {\mathsf{TC}}^{0} circuit classes as concepts. These circuit classes are ubiquitous in complexity theory, cryptography, and learning theory. We formally define these circuit classes below. Definition 5.5 ( {\mathsf{AC}}^{0}_{d} circuits and {\mathsf{TC}}^{0}_{d} circuits) . An {\mathsf{AC}}^{0} circuit is a constant-depth, polynomial-size Boolean circuit on n -bits that consists of NOT, and unbounded fan-in AND and OR gates. A {\mathsf{TC}}^{0} circuit is a constant-depth, polynomial-size Boolean circuit on n -bits that consists of NOT, and unbounded fan-in AND, OR, and MAJ gates. When the circuit has depth d={\operatorname{O}\left(1\right)} , we use the notation {\mathsf{AC}}^{0}_{d} and {\mathsf{TC}}^{0}_{d} respectively. Fact 5.2 . For any d>0 , {\mathsf{AC}}^{0}_{d}\subset{\mathsf{TC}}^{0}_{d} . In the context of Boolean functions and learning theory, {\mathsf{AC}}^{0} and {\mathsf{TC}}^{0} circuit classes are quite important. We know that \mathrm{DNF}\in{\mathsf{AC}}^{0}_{2} and intersections/majority of halfspaces can be computed by {\mathsf{TC}}^{0} circuits. Hence, efficient learning algorithms for {\mathsf{AC}}^{0} and {\mathsf{TC}}^{0} circuits would imply efficient learning algorithms for \mathrm{DNF} and intersections of halfspaces. However, 11 showed the following impossibility results on quantum learning of {\mathsf{AC}}_{0} and {\mathsf{TC}}_{0} circuits. Lemma 5.2 (Impossibility of quantum learning shallow classical circuits 11 ) . The following impossibility results hold for learning {\mathsf{TC}}_{0} circuits. 1. If there does not exist a {\mathsf{BQP}} algorithm to solve the LWE problem with random examples, then no quantum learner can efficiently learn {\mathsf{TC}}^{0}_{2} even with access to membership queries. 2. If there does not exist a {\mathsf{BQP}} algorithm to solve the Ring- LWE problem 15 15 15 See 77 for a formal definition of the RLWE problem and its applications to cryptography. with random examples, then no quantum learner can efficiently learn {\mathsf{TC}}^{0} even with access to membership queries. Further, if there does not exist a strongly subexponential time quantum algorithm to solve the Ring- LWE problem with random examples, then there is no quasi-polynomial time quantum learner for {\mathsf{AC}}^{0} even with access to membership queries. We note that Lemma 5.2 implies that there are no efficient quantum learning algorithms for learning intersections of halfspaces (this class of Boolean functions is in {\mathsf{TC}}^{0}_{2} ), even with membership queries, assuming the hardness of LWE . Unlike the strong hardness of learning {\mathsf{TC}}^{0} circuits, all hope is not lost in the case of {\mathsf{AC}}^{0} circuits. We have seen previously that the class {\mathsf{AC}}^{0}_{2} is much easier to learn quantumly using just \mathrm{QEX} and \mathrm{QREX} queries 28 , while efficient algorithms are known for classical learners only with access to membership queries. The best-known classical learning algorithm for learning {\mathsf{AC}}^{0}_{3} circuits (AND of DNFs) with bounded top fan-in stems due to 42 in a distribution-free setting. This leads us to the following questions: Open Problem 22 (Separations for learning {\mathsf{AC}}^{0}_{d} circuits) . Does there exist an efficient quantum learner (with access to queries) for {\mathsf{AC}}^{0}_{3} circuits (with bounded top fan-in) under uniform marginals? Alternatively, what is the smallest d>1 for which there does not exist an efficient quantum learner (with access to queries) for {\mathsf{AC}}^{0}_{d} circuits (with bounded top fan-in) under uniform marginals? Remark 5.6 . Although a natural progression to this section is to focus on learning quantum counterparts of shallow circuits, we note that such a discussion does not fall under the purview of this survey. 6 Conclusion Upon closer examination of the numerous results surveyed above, a pattern begins to emerge. For many inherently classical problems, quantum oracles/quantum examples seem to capture the essence of the learning task more naturally compared to their corresponding classical counterparts. We motivate the above statement with the following open question. Open Problem 23 (Sampling oracle vs Random Examples in the Classical setting) . Does there exist a learning task where classical learning algorithms can demonstrate a separation between access to a succinct representation of the distribution (for example, in the form of access to sampling oracles) over learning with random examples? In fact, at first glance, it seems to be extremely difficult to formally distinguish between these two models in the context of classical PAC learning. On the other hand, this is a perfectly natural question to ask for quantum learning algorithms, since quantum algorithms naturally manipulate the succinct representations before the measurement/sampling step. Answering this question for classical learning problems in either direction represents an interesting step towards future research in comparing the relative power of learning oracles and their separations. A negative answer to the above question (the more likely scenario), cements the theoretical advantages of quantum algorithms with respect to learning quantum-encoded classical functions. 7 Quantum Computing Classical Boolean circuits are finite directed acyclic graphs with And, Or, and Not gates which take n -input bits and outputs m -output bits to compute some function f\in\mathbb{Z}^{n}_{2}\mapsto\mathbb{Z}^{m}_{2} . Classical circuits take n -bits as input and output m -bits. A quantum circuit is a generalization of a classical circuit where the input is an n -qubit state, the output is an m -qubit state, and the And, Or, and Not gates are replaced by quantum gates . In this survey, we consider the following augmented (non-minimal) universal gate set as the canonical quantum basis gates: \left\{X,Y,Z,H,CNOT,S,T\right\} . Sometimes, in quantum circuits, we assume that we are given black-box access to a unitary operator (also known as an oracle ), which encodes some information only accessible by queries. See Fig. 1 for examples of oracles. Phase Oracles. O^{\pm}_{x}:\ket{i,a}\mapsto{(-1)}^{a.x_{i}}\ket{i,a} Function Oracles. O_{f}:\ket{x,a}\mapsto\ket{x,a\oplus f(x)} Probability Oracles. O_{p}:\ket{x,0,0}\mapsto\sqrt{p_{x}}\ket{x,1,\psi^1_x}+\sqrt{1-p_{x}}\ket{x,0,\psi^0_x} Figure 1: Some common oracles used in quantum algorithms In the standard quantum query model formally introduced by 17 , a quantum query algorithm has 3 sets of registers - ancillas \mathcal{A} , workspace \mathcal{W} , and query registers \mathcal{Q} all initialized to \ket{0} . A k -query quantum query algorithm proceeds by making k rounds of interleaved unitary operations and calls to some quantum query oracle. The algorithm ends by measuring the ancilla register. We now list two important quantum subroutines that have historically provided most of the speedups in quantum learning theory. Suppose we have access to a unitary U that prepares a quantum state \ket{\psi}=\sqrt{\alpha_{\mathrm{good}}}\ket{\psi_\mathrm{good}}+\sqrt{1-\alpha_{\mathrm{good}}}\ket{\alpha_{\mathrm{bad}}}, and we wanted to obtain the ”good” state \ket{\psi_\mathrm{good}} with high probability. Simply measuring \ket{\psi} would only give us \ket{\psi_\mathrm{good}} with probability {\absolutevalue{\alpha_\mathrm{good}}}^{2} . Hence, on expectation it would take us \nicefrac{{1}}{{{\absolutevalue{\alpha_\mathrm{good}}}^{2}}} independent measurements to obtain \ket{\psi_\mathrm{good}} with high probability. However, 25 showed that this can be improved using Lemma 7.1 (Amplitude Amplification) . as stated below. Lemma 7.1 (Amplitude Amplification) . Let p>0 be a constant, and U be a unitary operator s.t. U\ket{0}=\sqrt{p_{0}}\ket{\phi_0}\ket{0}+\sqrt{1-p_{0}}\ket{\phi_1}\ket{1} for an unknown p_{0}\geq p>0 . There exists a quantum algorithm that makes \Theta(\sqrt{p^{\prime}/p}) expected number of calls to U and U^{-1} and outputs the state \ket{\phi_0} with a probability p^{\prime}>0 . Let \ket{\phi_0}=\ket{\psi_\mathrm{good}} , and p_{0}=\absolutevalue{\alpha_\mathrm{good}}^{2} in Lemma 7.1 . Then, setting p^{\prime}=1 in Lemma 7.1 gives us \ket{\psi_\mathrm{good}} by making {\operatorname{O}\left(\nicefrac{{1}}{{{\absolutevalue{\alpha_\mathrm{good}}}}}\right)} queries to U and U^{-1} in expectation. This gives us a quadratic speedup over the classical case. One issue with Lemma 7.1 (Amplitude Amplification) . is that we may not know p_{0} and hence, how many times we need to invoke U and U^{-1} in order to obtain \ket{\psi_\mathrm{good}} . We use the following result by 2 to obtain an estimate of p_{0} with relative error. Lemma 7.2 (Relative Amplitude Estimation) . Given a constant p>0 , an error parameter \varepsilon>0 , a constant k\geq 1 , and a unitary U such that U\ket{0}=\sqrt{p_{0}}\ket{\phi_0}\ket{0}+\sqrt{1-p_{0}}\ket{\phi_1}\ket{1} where either {p_{0}}\geq p or p_{0}=0 . Then there exists a quantum algorithm that produces an estimate \tilde{p}_{0} of the success probability p_{0} with probability at least 1-\nicefrac{{1}}{{2^{k}}} such that \left|p_{0}-\tilde{p}_{0}\right|\leq\varepsilon\cdot p_{0} when p_{0}\geq p , and makes O\left(\frac{k}{\varepsilon\sqrt{p}}\left(1+\log{\log{\frac{1}{p}}}\right)\right) calls to U and U^{-1} in expectation. Classically, we can use multiplicative Chernoff bounds to perform mean estimation with relative error by sampling \operatorname{\tilde{O}}\left(\frac{1}{\varepsilon^{2}}\right) independent copies of U\ket{0} and setting p={\operatorname{O}\left(1/m\right)} , where \ket{\phi_0} is a superposition over m basis states. Hence, using Lemma 7.2 (Relative Amplitude Estimation) . , we can perform mean estimation with relative error \varepsilon with a quadratic speedup over classical mean estimation techniques in terms of dependence on \varepsilon and m . 8 Boolean functions continued There are many semantically equivalent representations of Boolean functions. In this survey, we are concerned with three main types of representations of Boolean functions, as listed below. • Truth Table : In this representation, we explicitly list the value of the Boolean function for all of its 2^{n} possible inputs. • Boolean Circuits : A Boolean circuit is a finite DAG with clearly designated input nodes, internal nodes, and an output node. For this survey, every node has a fan-in of at most 2 . The input nodes are the bits of the input string, and have fan-in 0 ; the internal nodes consist of rudimentary Boolean functions belonging to some basis set of Boolean functions (eg. ANDs, ORs, and NOTs), and the output node (with fan-out 0 ) stores a binary value corresponding to the output of the evaluation of the input bits. • Boolean Formulas / Propositional Formulas : We can express any arbitrary Boolean function f as an algebraic formula consisting of rudimentary Boolean functions belonging to some basis set of Boolean functions, applied to its input bits. Formally, any Boolean circuit where every node has fan-out at most 1 is a Boolean formula. Some well-known canonical representations of Boolean functions are the DNF and CNF ( CNF ) representations, defined with respect to ORs and ANDs over the input literals. Unlike Truth tables or Circuits, Boolean formulas correspond to a covering of f^{-1}(0) or f^{-1}(1) . Remark 8.1 . Given a universal basis set \mathcal{B} for Boolean functions, we can define Boolean circuits such that the internal nodes only contain gates from \mathcal{B} . For example, consider the basis sets \mathcal{B}_{1}=\{\textrm{NAND}\} or \mathcal{B}_{1}=\{\textrm{NOR}\} . Similar to Boolean circuits, we can also write a formula in terms of different universal basis sets over Boolean functions. However, for this survey, the canonical basis set for classical Boolean circuits and formulas is \{\textrm{AND},\textrm{OR},\textrm{NOT}\} . The representation size of a Boolean function can be defined depending on the underlying choice of representation. Example 8.1 . A standard representation choice for a Boolean function f is the depth of the minimal binary decision tree representation of f . Another standard choice would be the size of the minimal width DNF representation of f . 8.1 Fourier Analysis of Boolean functions Fourier-analytic techniques constitute a very powerful family of tools for designing learning algorithms in general and particularly for learning over the Boolean hypercube 74 . In this section, we will limit our discussions to Fourier analysis for \mathbb{F}_{2} -valued ( \pm 1 -valued) or \mathbb{Z}_{2} -valued ( \{0,1\} -valued) functions, but most results will also apply to real-valued functions over the Boolean hypercube. Every Boolean function f(x) , can be uniquely represented as a multilinear polynomial known as the Fourier representation of f , as follows. f(x)=\underset{\mathcal{S}\subseteq[n]}{\sum}\hat{f}(\mathcal{S})\,\raisebox{2.0pt}{$\chi$}_{\mathcal{S}}(x),\;\;f:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2}. (26) In Eq. 26 , \raisebox{2.0pt}{$\chi$}_{\mathcal{S}}(x)=\prod_{i\in\mathcal{S}}x_{i} (we define explicitly \raisebox{2.0pt}{$\chi$}_{\mathcal{S}}(\varnothing)=-1 ) is known as a parity monomial , and \hat{f}(\mathcal{S})=\mathbb{E}\,\left[\,f\cdot\raisebox{2.0pt}{$\chi$}_{\mathcal{S}}\,\right] is known as the Fourier coefficient of f with respect to to the subset of literals \mathcal{S} . Note that if f:{\{0,1\}}^{n}\mapsto\mathbb{F}_{2} , then \raisebox{2.0pt}{$\chi$}_{\mathcal{S}}(x)={(-1)}^{\sum_{i\in\mathcal{S}}x_{i}} . The set of all parity monomials \mathbb{P}=\big\{\raisebox{2.0pt}{$\chi$}_{\mathcal{S}}\;|\;\mathcal{S}\subseteq[n]\big\} forms a basis for all real-valued functions on the Boolean hypercube \mathbb{F}^{n}_{2} . The vector space spanned by \mathbb{P} forms an inner product space, i.e., for any f,g:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2} , \left\langle f,g\right\rangle=\frac{1}{2^{n}}\underset{x\in\mathbb{F}^{n}_{2}}{\sum}f(x)\cdot g(x)=\underset{\mathcal{U}\left(\mathbb{F}^{n}_{2}\right)}{\mathbb{E}}\,\left[\,f(x)\cdot g(x)\,\right]1-2\underset{\mathcal{U}\left(\mathbb{F}^{n}_{2}\right)}{\operatorname{Pr}}\left[f\neq g\right]. (27) The above definition of inner product captures the notion of distance between two Boolean functions, and also shows us that the set of all parity monomials forms an orthonormal basis set, since \left\langle\raisebox{2.0pt}{$\chi$}_{\mathcal{S}},\raisebox{2.0pt}{$\chi$}_{\mathcal{S}}\right\rangle=1 for all \mathcal{S}\subseteq[n] , and \left\langle\raisebox{2.0pt}{$\chi$}_{\mathcal{S}},\raisebox{2.0pt}{$\chi$}_{\mathcal{T}}\right\rangle=0 if \mathcal{S}\neq\mathcal{T} . This allows us to obtain the following observation. Observation 8.1 (Fourier spectrum of a Boolean function) . For any Boolean function f , the set of squared Fourier coefficients forms a probability distribution known as the Fourier spectrum or Fourier distribution of f , and is denoted by \operatorname{FS}\left(f\right) . \underset{\mathcal{S}\subseteq[n]}{\sum}{{\hat{f}(\mathcal{S})}^{2}}=1\;f,g:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2}. We now state the Lemma 8.1 (Fourier Sampling) . lemma by 19 . Lemma 8.1 (Fourier Sampling) . Given access to a function oracle O_{f} (see Fig. 1 ), there exists a quantum algorithm (see Algorithm 1 ) that produces the state \sum_{\mathcal{S}\in[n]}\hat{f}(\mathcal{S})\ket{\ccS} , using only 1 query to O_{f} and {\operatorname{O}\left(n\right)} gates. Unlike in the quantum case, explicitly constructing the distribution \operatorname{FS}\left(f\right) is harder classically, since any \hat{f}(\mathcal{S})=\mathbb{E}\,\left[\,f\cdot\raisebox{2.0pt}{$\chi$}_{\mathcal{S}}\,\right] depends on all 2^{n} values of f . The state produced in Lemma 8.1 (Fourier Sampling) . allows us to sample from \operatorname{FS}\left(f\right) , i.e., sample \mathcal{S} with probability {\hat{f}(\mathcal{S})}^{2} . We can use Lemma 8.1 (Fourier Sampling) . to learn linear functions f using one query to O_{f} 19 , whereas, classically, this takes {\operatorname{O}\left(n\right)} queries. Input: Oracle O_{f}:\ket{x}\mapsto f(x)\ket{x} , providing black-box access to f . Start with \ket{0^n} and apply H^{\otimes n} to obtain \ket{+^{\otimes n}}=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\mathbb{F}^{n}_{2}}\ket{x}. 1 Query O_{f} to obtain the state \ket{\psi}=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\mathbb{F}^{n}_{2}}f(x)\ket{x}. 2 Apply H^{\otimes n} to \ket{\psi} . 3 Output: The state \sum_{\mathcal{S}\in[n]}\hat{f}(\mathcal{S})\ket{\ccS} . Algorithm 1 The Fourier Sampling Algorithm 9 Computational Learning Theory 9.1 The Hypothesis Class associated with a Learner An implicit point central to the study of computational aspects of learning theory is that every learning algorithm A has its own associated hypothesis class \mathcal{H}_{A} . The learner A can only output a hypothesis from \mathcal{H}_{A} . 16 16 16 We drop the subscript from the hypothesis class when the choice of the learner is clear. We also assume here that all hypothesis classes \mathcal{H}_{A} are polynomially evaluatable by A , i.e., given any x\in\mathcal{X} and h\in\mathcal{H}_{A} , if A can compute h(x) in time \operatorname{poly}\left(n,\operatorname{size}\left(\mathcal{H}_{A}\right)\right) . Observation 9.1 . We note that certain learning algorithms are more expressive than others, courtesy of their respective associated hypothesis classes. However, a learning algorithm with the most expressive hypothesis class may not always be the best choice since learners with larger hypothesis classes would need more computational resources to find the optimal hypothesis in their associated hypothesis class. Observation 9.2 . Note that given an arbitrary choice of distribution \mathfrak{D} over the \mathcal{X} and some unknown labeling concept c\in\mathcal{C} , assuming that a learning algorithm A can output an ideal hypothesis is not always realistic. For example, consider scenarios when \mathcal{H}_{A} is extremely large or the concept c does not belong to \mathcal{H}_{A} . In settings where obtaining an ideal hypothesis is both computationally and mathematically impossible, the main objective of a learning algorithm is to efficiently output a hypothesis h such that h\approx c with respect to some accuracy metric such as error. 9.2 Classifying PAC learners based on output hypotheses 9.2.1 Proper and Improper PAC learning Recall Remark 2.5 and the preceding discussions while defining the notions of learnability and efficient learnability. In Definition 2.3 , the choice of representation of the output hypothesis h\in\mathcal{H}_{A} produced by a learning algorithm A need not necessarily be the same as the unknown target concept class \mathcal{C} it is trying to learn. If the choice of representation of \mathcal{H}_{A} is the same as the choice of representation as \mathcal{C} , i.e., h\in\mathcal{C} , then the learner A is a proper PAC learner for \mathcal{C} . Otherwise, when h\notin\mathcal{C} , A is considered an improper PAC learner for \mathcal{C} . 17 17 17 (Im)Proper learning is also known as representation-(in)dependent learning. Similar to the realizable setting, in the agnostic setting, if A outputs a hypothesis from the benchmark class h\in\mathcal{C} , then A is a proper agnostic learner for \mathcal{C} . Otherwise, A is an improper agnostic learner for \mathcal{C} . 9.2.2 Weak and Strong Learning Directly designing a PAC learner for an unknown target concept with respect to an unknown distribution is often challenging. In practice, it is easier to design a weak PAC learner - something that succeeds with \sim 51\% accuracy, and then amplify the success probability of such learners to be arbitrarily close to 100\% . In other words: Given an ensemble of learning algorithms that are PAC learners in a weak sense, we can combine the above ensemble of weak learners using ensemble learning algorithms to obtain strong PAC learners 18 18 18 In the realizable setting, strong PAC learners satisfy Definition 2.3 ( (\varepsilon,\delta) -PAC learnability) . . . Later, we formalize the notions of weak and strong PAC learners under the various noise models explored earlier. 9.3 Criticisms of MQ oracles and their variants Even though a significant portion of the learning theory literature has been dedicated to constructing PAC learning algorithms with access to MQ oracles for various Boolean concept classes, it has not been the subject of much practical work. This is possibly due to the paradoxical nature of MQ oracles themselves: If it were possible to construct MQ oracles for some target concept class \mathcal{C} in practice, there would be no need to construct PAC learners for \mathcal{C} . On the other hand, sampling query oracles such as EX , REX , AEX (and their quantum counterparts) simply extend the usual notion of supervised learning by reframing the definitions in terms of oracle queries. Remark 9.1 . An infamous experiment was conducted by 16 where they tried to learn a linear classifier for handwritten characters and digits using human annotators as MQ oracles. It was seen that, in addition to making out-of-distribution queries, sometimes the learner tended to make out-of-domain queries as well. This may be noted as anecdotal evidence in support of the hypothesis that MQ oracles may not be useful in practice. 9.4 PAC learning under various Label Noise Models 9.4.1 The Realizable / Noiseless setting The learning setup introduced in Section 2.3 is called the realizable setting since we assume that there always exists a target concept c\in\mathcal{C} that realizes the labeling of the instances. We also denote this setting as the noiseless setting since the labels in the training set are available to the learner without change. 9.4.2 Bounded Noise setting We can generalize the realizable setting to account for more realistic learning scenarios as follows. Let \mathcal{S}=\{(x_{1},c(x_{1})),\ldots,(x_{m},c(x_{m}))\} be the training set used to train a learning algorithm A . Suppose an adversary corrupts the labels of the training set \mathcal{S} before it is obtained by the learner A and used to formulate the hypothesis. It is straightforward to see that the sample complexity and time complexity guarantees of Definition 2.3 ( (\varepsilon,\delta) -PAC learnability) . would have to depend on the noise rate. In the RCN setting introduced by 4 , we assume that the labels of the training set are flipped with probability 0\leq\eta<\nicefrac{{1}}{{2}} , i.e., given training set \mathcal{S}={(x_{i},y_{i})}_{i\in[m]} , set each y_{i}=\overline{y_{i}} independently with probability \eta . In this setting, the sample and time complexity of a PAC learner depends on \operatorname{poly}\left(\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}},n,\operatorname{size}\left(\mathcal{C}\right),\nicefrac{{1}}{{1-2\eta}}\right) . Later, we will redefine the RCN setting in terms of noisy oracles. An example of a more challenging class of bounded noise is Massart noise , where each label y_{i} is flipped with probability \eta_{i}\leq\eta<\nicefrac{{1}}{{2}} . 9.4.3 Unbounded Noise setting A far more challenging noise model is the agnostic PAC setting 61 ; 69 . In this noise model, each label y_{i} is corrupted with probability \eta_{i}<\nicefrac{{1}}{{2}} . Here, we note that there is no bound \eta s.t. \eta_{i}<\eta,\forall i\in[\absolutevalue{\ccS}] . If the rate of corruption of labels is unbounded, it is unclear whether a learning algorithm A , which was an efficient learner for \mathcal{C} , even remains a PAC learner for \mathcal{C} after the noise has been added to the training set. In the unbounded noise model, we no longer assume that there is a fixed underlying concept c\in\mathcal{C} that labels the instances x\in\mathcal{X} , since the training set itself can be inconsistent. 19 19 19 If, for some i\in[\absolutevalue{\ccS}] , the noise rate \eta_{i} is very close to \nicefrac{{1}}{{2}} , the training set can contain samples \{x_{i},+1\} and \{x_{i},-1\} . Hence, the labeling of instances is no longer considered a function. 20 20 20 Inconsistency also arises in the bounded noise model, but can be resolved easily by majority vote. Rather, we assume that the labeled instances (x,y) are jointly sampled from a distribution \mathfrak{D} over \mathcal{X}\times\mathcal{Y} . Therefore, the learning algorithm is agnostic to the choice of the target concept. 9.5 Fourier analytic techniques for Learning The crux of learning techniques for a Boolean function f is as follows: • Given some information about the Fourier spectrum of f , explicitly construct a weak learner for f . • Use an ensemble learning algorithm such as Boosting to obtain an approximate strong learner for f w.h.p., i.e., obtain a PAC learner for f . The Fourier weight of a Boolean function f at degree k is defined as the sum of squared Fourier coefficients of subsets of Hamming weight exactly equal to k , i.e., \mathcal{W}^{=k}{f}=\underset{\mathcal{S}\subseteq[n],\absolutevalue{\ccS}=k}{\sum}{{\hat{f}(\mathcal{S})}^{2}}. We can similarly define the quantities \mathcal{W}^{\leq k}{f} and \mathcal{W}^{\geq k}{f} . A Boolean function f is \varepsilon -spectrally concentrated on a set \mathcal{A}\subseteq 2^{[n]} if \underset{\mathcal{S}\subseteq[n],\mathcal{S}\notin\mathcal{A}}{\sum}{{\hat{f}(\mathcal{S})}^{2}}\leq\varepsilon. Therefore, a Boolean function f is \varepsilon -spectrally concentrated on degree \leq k , if \mathcal{W}^{>k}{f}\leq\varepsilon. We now outline some important results. Lemma 9.1 (Low Degree Learning 74 ) . If a Boolean function f is \varepsilon -concentrated on a set \mathcal{A} , and we know \mathcal{A} explicitly, then there exists a learning algorithm A that can (\varepsilon,\delta) -PAC learn f in time \operatorname{poly}\left(\absolutevalue{\cA},n,\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}}\right) with query access to a \operatorname{EX}\left(\mathcal{U},f\right) oracle. If f is \varepsilon -concentrated up to degree k , then A can learn f in time \operatorname{poly}\left(n^{k},\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}}\right) with query access to a \operatorname{EX}\left(\mathcal{U},f\right) oracle. Remark 9.2 . If k is not a constant, then the learner in Lemma 9.1 does not yield an efficient PAC learner for f . One shortcoming of Lemma 9.1 is the requirement that we have explicit knowledge of the subsets of literals on which the Boolean function is spectrally concentrated. We can get around this requirement by upgrading our choice of oracle from the \operatorname{EX}\left(\mathcal{U},f\right) oracle to the \operatorname{MEM}_{f} oracle. Lemma 9.2 (Learning from Spectral Concentration 53 ; 73 ) . Let \varepsilon,\delta>0 , and f:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2} . If f is \varepsilon -concentrated up to degree k , \exists a learning algorithm A with query access to a \operatorname{MEM}_{f} oracle that (\varepsilon,\delta) -PAC learns f in time \operatorname{poly}\left(n^{k},\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}}\right) . There are two important corollaries of Lemma 9.2 . The first result allows us to improve upon Lemma 9.1 by learning a function that is spectrally concentrated on a subset \mathcal{S} , without explicit knowledge of \mathcal{S} . Corollary 9.3 (Learning from \varepsilon -concentrated subset of parity monomials) . Let \varepsilon,\delta>0 , and f:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2} . If f is \varepsilon -concentrated on a subset \mathcal{S} , \exists a learning algorithm A with query access to a \operatorname{MEM}_{f} oracle that (\varepsilon,\delta) -PAC learns f in time \operatorname{poly}\left(\absolutevalue{\ccS},\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}}\right) . The next corollary helps us define PAC learners from parity monomials that have large Fourier coefficients. Let f be a Boolean function. Then, the \ell_{1} norm of \operatorname{FS}\left(f\right) is defined as \norm{\spectrum{f}}_{1}=\sum_{\mathcal{S}\subseteq[n]}\absolutevalue{\hat{f}(\ccS)}. (28) Corollary 9.4 (Learning from parity monomials with large Fourier coefficients) . Let \varepsilon,\delta>0 , and f:\mathbb{F}^{n}_{2}\mapsto\mathbb{F}_{2} . \exists a learning algorithm A with query access to a \operatorname{MEM}_{f} oracle that (\varepsilon,\delta) -PAC learns f in time \operatorname{poly}\left(\norm{\spectrum{f}}_{1},\nicefrac{{1}}{{\varepsilon}},\nicefrac{{1}}{{\delta}}\right) . Observation 9.3 . Corollary 9.4 tells us that if the \ell_{1} norm of any Boolean function is polynomially bounded, then we can construct a PAC learner for f using queries to an MQ oracle. 10 Group Theory A group is a non-empty set \mathcal{G} is a set with an associative binary operation (\cdot):\mathcal{G}\times\mathcal{G}\mapsto\mathcal{G} , such that there exists an identity element in \mathcal{G} with respect to (\cdot) , and every element of \mathcal{G} has an inverse element in \mathcal{G} w.r.t (\cdot) . If for all x,y\in\mathcal{G} , x(\cdot)y=y(\cdot)x , then \mathcal{G} is an Abelian group. A generating subset \mathcal{H} of \mathcal{G} is a subset s.t. every element of \mathcal{G} can be expressed as a combination of finitely many elements of \mathcal{H} and their inverses. If \mathcal{G} is a cyclic group, it has an element x that serves as the generator of the group. Any arbitrary finite Abelian group can be decomposed into cyclic groups as follows: Lemma 10.1 (Fundamental Structure Theorem for Finite Abelian Groups) . Every Abelian group \mathcal{G} is isomorphic to a group of the form {\mathbb{Z}}_{p^{a_{1}}_{1}}\times{\mathbb{Z}}_{p^{a_{2}}_{2}}\times\ldots\times{\mathbb{Z}}_{p^{a_{k}}_{k}}, where p_{1},\ldots,p_{k} are prime numbers (not necessarily unique), and the decomposition is unique up to the order in which the factors \left\{p_{1}^{a_{1}},\ldots,p_{k}^{a_{k}}\right\} are written. Remark 10.1 . \mathbb{Z}_{k} is a finite Abelian group of order k with respect to the +_{\mathrm{mod}\,k} operation. \mathbb{Z}_{k} is also a cyclic group if k=1,2,4 or some power of an odd prime. Definition 10.1 (Dihedral Groups) . A dihedral group D_{2N} is a non-abelian group of order 2N that is generated by two elements x and y s.t. x^{N}=1,\;\;\;y^{2}=1,\;\;\;yxy=-x. D_{2N} is group of symmetries of a regular polygon of 2N sides. The elements x and y are rotation and reflection operations about the vertical axis.