Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9807052

A Quantum Computational Learning Algorithm

Dan A. Ventura, Tony R. Martinez

Published Jul 18, 1998• 10 citations
arXivHTMLPDF

Abstract

An interesting classical result due to Jackson allows polynomial-time learning of the function class DNF using membership queries. Since in most practical learning situations access to a membership oracle is unrealistic, this paper explores the possibility that quantum computation might allow a learning algorithm for DNF that relies only on example queries. A natural extension of Fourier-based learning into the quantum domain is presented. The algorithm requires only an example oracle, and it runs in O(sqrt(2^n)) time, a result that appears to be classically impossible. The algorithm is unique among quantum algorithms in that it does not assume a priori knowledge of a function and does not operate on a superposition that includes all possible states.

DOI
10.48550/arxiv.quant-ph/9807052

Related papers

Learning DNFs under product distributions via mu--biased quantum Fourier sampling

Varun Kanade, Andrea Rocchetto, Simone Severini B

We show that DNF formulae can be quantum PAC-learned in polynomial time under product distributions using a quantum example oracle. The current best classical algorithm runs in superpolynomial time. Our result extends the work by Bshouty and Jackson (1998) that proved that DNF formulae are efficiently learnable under the uniform distribution using a quantum example oracle. Our proof is based on a new quantum algorithm that efficiently samples the coefficients of a μ–biased Fourier transform.

arXiv:1802.05690•Quantum Information and Computation•Dec 1, 2019•16 citations

Advances in quantum computational learning theory

Rocco A. Servedio, Alp Atıcı

This dissertation explores results at the intersection of two important branches of theoretical computer science: quantum computation, which studies the power of devices based on quantum physical phenomena, and computational theory, which studies the foundations of machine algorithms. We refer to the area of research at this intersection as quantum computational theory. Like its classical counterpart, quantum computational theory aims to understand the computational and information theoretic requirements of problems and algorithms. However unlike the classical models, the models for quantum learners generally involve quantum sources of information and quantum gates employing quantum physical phenomena such as superposition and entanglement, which do not have classical equivalents. Our results can be summarized as follows: (1) In Chapter 3, we study the information theoretic requirements of quantum learning, partition and Probably Approximately Correct (PAC) learning. First, we develop a new general quantum algorithm, resolving a conjecture by Hunziker et al. [HMP+03]. Next, we present positive and negative results towards the rather general problem of partition of which both exact learning and computing a binary property are special cases. Finally, we derive an improved lower bound on the number of quantum examples required for PAC learning. (2) In Chapter 4, we consider the problem of unions of high dimensional rectangles over the domain [b]n using membership queries and uniform quantum examples. These classes oral generalizations of classes of DNF formulae over {0,1}n that have been extensively studied in the theory literature. (3) In Chapter 5, we develop quantum algorithms for and testing juntas (Boolean functions that depend on a few variables) and sparse functions. These algorithms are based on the quantum subroutine due to Bshouty and Jackson [BJ99] that enables sampling from the Fourier spectrum.

•Jan 1, 2006•2 citations

Learning DNF over the Uniform Distribution Using a Quantum Example Oracle

Nader H. Bshouty, Jeffrey C. Jackson

We generalize the notion of probably approximately correct (PAC) learning from an example oracle to a notion of efficient learning on a quantum computer using a quantum example oracle. This quantum example oracle is a natural extension of the traditional PAC example oracle, and it immediately follows that all PAC-learnable function classes are learnable in the quantum model. Furthermore, we obtain positive quantum learning results for classes that are not known to be PAC learnable. Specifically, we show that disjunctive normal form (DNF) is efficiently learnable with respect to the uniform distribution by a quantum algorithm using a quantum example oracle. While it was already known that DNF is uniform-learnable using a membership oracle, we prove that a quantum example oracle with respect to uniform is less powerful than a membership oracle.

SIAM Journal on Computing•Jan 1, 1998•95 citations

Quantum algorithms and learning theory

Srinivasan Arunachalam

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.

•Apr 25, 2018•1 citation

A Quantum Analog to Basis Function Networks

Dan A. Ventura

A Fourier‐based quantum computational learning algorithm with similarities to classical basis function networks is developed. Instead of a Gaussian basis, the quantum algorithm uses a discrete Fourier basis with the output being a linear combination of the basis. A set of examples is considered as a quantum system that undergoes unitary transformations to produce learning. The main result of the work is a quantum computational learning algorithm that is unique among quantum algorithms as it does not assume a priori knowledge of a function f.

AIP conference proceedings•Jan 1, 2002•0 citations

Fast Quantum Algorithms for Learning Linear Threshold Functions

Aleksandrs Krivcenko, Tuyen Nguyen, Ronald de Wolf

Linear threshold functions (LTFs) are $\{-1,1\}$-valued functions $f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)$, where $w\in\mathbb R^n$ has unit norm, $θ\in\mathbb R$, and $x\in\mathbb R^n$ or $\{-1,1\}^n$. If $θ=0$, the LTF is homogeneous, denoted $f_w=f_{w,0}$. LTFs are fundamental linear classifiers. We give three results: one for general LTFs and two for homogeneous LTFs. (1) With real-domain membership queries evaluating $f_{w,θ}(x)$ at any chosen $x\in\mathbb R^n$, we learn an LTF with classification error at most $\varepsilon$ under the standard Gaussian distribution using $O(\log(n/\varepsilon))$ queries and $\widetilde{O}(n)$ other gates. Classically, $Ω(n\log(1/\varepsilon))$ queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF $f_w$ over $\{-1,1\}^n$ whose $k$ nonzero weights are equal and positive is Majority on the support of $w$. We identify this hidden support exactly using $O(\log k)$ queries, exponentially improving Belovs' $O(k^{1/4})$ upper bound. Our algorithm uses $O(n\log n\log k)$ gates and has $O(\log n\log k)$ non-oracle depth. Classical algorithms require $Ω(k\log(n/k))$ queries. (3) Suppose a unitary $U$ prepares discretized Gaussian quantum examples, corresponding to $\int_x\sqrt{γ_n(x)}|x\rangle|f_w(x)\rangle\,dx$. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most $\varepsilon$ under the Gaussian distribution using $O(n^{1/4}/\sqrt{\varepsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})$ other gates. Classically, $Ω(n/\varepsilon)$ examples are needed, giving a quartic quantum speedup in $n$. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.

quant-pharXiv:2609.40331•Oct 1, 2026•0 citations
An interesting classical result due to Jackson allows polynomial-time learning of the function class DNF using membership queries. Since in most practical learning situations access to a membership oracle is unrealistic, this paper explores the possibility that quantum computation might allow a learning algorithm for DNF that relies only on example queries. A natural extension of Fourier-based learning into the quantum domain is presented. The algorithm requires only an example oracle, and it runs in O(sqrt(2^n)) time, a result that appears to be classically impossible. The algorithm is unique among quantum algorithms in that it does not assume a priori knowledge of a function and does not operate on a superposition that includes all possible states.
This dissertation explores results at the intersection of two important branches of theoretical computer science: quantum computation, which studies the power of devices based on quantum physical phenomena, and computational theory, which studies the foundations of machine algorithms. We refer to the area of research at this intersection as quantum computational theory. Like its classical counterpart, quantum computational theory aims to understand the computational and information theoretic requirements of problems and algorithms. However unlike the classical models, the models for quantum learners generally involve quantum sources of information and quantum gates employing quantum physical phenomena such as superposition and entanglement, which do not have classical equivalents. Our results can be summarized as follows: (1) In Chapter 3, we study the information theoretic requirements of quantum learning, partition and Probably Approximately Correct (PAC) learning. First, we develop a new general quantum algorithm, resolving a conjecture by Hunziker et al. [HMP+03]. Next, we present positive and negative results towards the rather general problem of partition of which both exact learning and computing a binary property are special cases. Finally, we derive an improved lower bound on the number of quantum examples required for PAC learning. (2) In Chapter 4, we consider the problem of unions of high dimensional rectangles over the domain [b]n using membership queries and uniform quantum examples. These classes oral generalizations of classes of DNF formulae over {0,1}n that have been extensively studied in the theory literature. (3) In Chapter 5, we develop quantum algorithms for and testing juntas (Boolean functions that depend on a few variables) and sparse functions. These algorithms are based on the quantum subroutine due to Bshouty and Jackson [BJ99] that enables sampling from the Fourier spectrum.
We generalize the notion of probably approximately correct (PAC) learning from an example oracle to a notion of efficient learning on a quantum computer using a quantum example oracle. This quantum example oracle is a natural extension of the traditional PAC example oracle, and it immediately follows that all PAC-learnable function classes are learnable in the quantum model. Furthermore, we obtain positive quantum learning results for classes that are not known to be PAC learnable. Specifically, we show that disjunctive normal form (DNF) is efficiently learnable with respect to the uniform distribution by a quantum algorithm using a quantum example oracle. While it was already known that DNF is uniform-learnable using a membership oracle, we prove that a quantum example oracle with respect to uniform is less powerful than a membership oracle.
This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.
A Fourier‐based quantum computational learning algorithm with similarities to classical basis function networks is developed. Instead of a Gaussian basis, the quantum algorithm uses a discrete Fourier basis with the output being a linear combination of the basis. A set of examples is considered as a quantum system that undergoes unitary transformations to produce learning. The main result of the work is a quantum computational learning algorithm that is unique among quantum algorithms as it does not assume a priori knowledge of a function f.
Linear threshold functions (LTFs) are {−1,1}\{-1,1\}{−1,1}-valued functions fw,θ(x)=sgn(⟨w,x⟩−θ)f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)fw,θ​(x)=sgn(⟨w,x⟩−θ), where w∈Rnw\in\mathbb R^nw∈Rn has unit norm, θ∈Rθ\in\mathbb Rθ∈R, and x∈Rnx\in\mathbb R^nx∈Rn or {−1,1}n\{-1,1\}^n{−1,1}n. If θ=0θ=0θ=0, the LTF is homogeneous, denoted fw=fw,0f_w=f_{w,0}fw​=fw,0​. LTFs are fundamental linear classifiers. We give three results: one for general LTFs and two for homogeneous LTFs. (1) With real-domain membership queries evaluating fw,θ(x)f_{w,θ}(x)fw,θ​(x) at any chosen x∈Rnx\in\mathbb R^nx∈Rn, we learn an LTF with classification error at most ε\varepsilonε under the standard Gaussian distribution using O(log⁡(n/ε))O(\log(n/\varepsilon))O(log(n/ε)) queries and O~(n)\widetilde{O}(n)O(n) other gates. Classically, Ω(nlog⁡(1/ε))Ω(n\log(1/\varepsilon))Ω(nlog(1/ε)) queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF fwf_wfw​ over {−1,1}n\{-1,1\}^n{−1,1}n whose kkk nonzero weights are equal and positive is Majority on the support of www. We identify this hidden support exactly using O(log⁡k)O(\log k)O(logk) queries, exponentially improving Belovs' O(k1/4)O(k^{1/4})O(k1/4) upper bound. Our algorithm uses O(nlog⁡nlog⁡k)O(n\log n\log k)O(nlognlogk) gates and has O(log⁡nlog⁡k)O(\log n\log k)O(lognlogk) non-oracle depth. Classical algorithms require Ω(klog⁡(n/k))Ω(k\log(n/k))Ω(klog(n/k)) queries. (3) Suppose a unitary UUU prepares discretized Gaussian quantum examples, corresponding to ∫xγn(x)∣x⟩∣fw(x)⟩ dx\int_x\sqrt{γ_n(x)}|x\rangle|f_w(x)\rangle\,dx∫x​γn​(x)​∣x⟩∣fw​(x)⟩dx. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most ε\varepsilonε under the Gaussian distribution using O(n1/4/ε)O(n^{1/4}/\sqrt{\varepsilon})O(n1/4/ε​) applications of UUU and U†U^\daggerU† and O~ ⁣(n5/4ε+nε2)\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})O(ε​n5/4​+ε2n​) other gates. Classically, Ω(n/ε)Ω(n/\varepsilon)Ω(n/ε) examples are needed, giving a quartic quantum speedup in nnn. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.