Strengths and weaknessesof quantum examples
Srinivasan Arunachalam (MIT)joint with Ronald de Wolf (CWI, Amsterdam) and others

1/ 18

Machine learning
Classical machine learning

2/ 18

Machine learning
Classical machine learning
Grand goal: enable AI systems to improve themselves

2/ 18

Machine learning
Classical machine learning
Grand goal: enable AI systems to improve themselves
Practical goal: learn“something” from given data

2/ 18

Machine learning
Classical machine learning
Grand goal: enable AI systems to improve themselves
Practical goal: learn“something” from given data
Recent success: deep learning is extremely good at image recognition, natural
language processing, even the game of Go

2/ 18

Machine learning
Classical machine learning
Grand goal: enable AI systems to improve themselves
Practical goal: learn“something” from given data
Recent success: deep learning is extremely good at image recognition, natural
language processing, even the game of Go
Why the recent interest? Flood of available data, increasing computational
power, growing progress in algorithms

2/ 18

Machine learning
Classical machine learning
Grand goal: enable AI systems to improve themselves
Practical goal: learn“something” from given data
Recent success: deep learning is extremely good at image recognition, natural
language processing, even the game of Go
Why the recent interest? Flood of available data, increasing computational
power, growing progress in algorithms

Quantum machine learning
What can quantum computing do for machine learning?

2/ 18

Machine learning
Classical machine learning
Grand goal: enable AI systems to improve themselves
Practical goal: learn“something” from given data
Recent success: deep learning is extremely good at image recognition, natural
language processing, even the game of Go
Why the recent interest? Flood of available data, increasing computational
power, growing progress in algorithms

Quantum machine learning
What can quantum computing do for machine learning?
The learner will be quantum, the data may be quantum

2/ 18

Machine learning
Classical machine learning
Grand goal: enable AI systems to improve themselves
Practical goal: learn“something” from given data
Recent success: deep learning is extremely good at image recognition, natural
language processing, even the game of Go
Why the recent interest? Flood of available data, increasing computational
power, growing progress in algorithms

Quantum machine learning
What can quantum computing do for machine learning?
The learner will be quantum, the data may be quantum
Some examples are known of reduction in time complexity:
clustering (Aı̈meur et al. ’13)
Principal component analysis (Lloyd et al. ’13)
perceptron learning (Wiebe et al. ’16)
recommendation systems (Kerenidis & Prakash ’16)
2/ 18

Learning using classical examples

3/ 18

Learning using classical examples

Basic definitions
Concept class C: collection of Boolean functions on n bits (Known)

3/ 18

Learning using classical examples

Basic definitions
Concept class C: collection of Boolean functions on n bits (Known)
Target concept c: some function c ∈ C (Unknown)

3/ 18

Learning using classical examples

Basic definitions
Concept class C: collection of Boolean functions on n bits (Known)
Target concept c: some function c ∈ C (Unknown)
Distribution D : {0, 1}n → [0, 1]

3/ 18

Learning using classical examples

Basic definitions
Concept class C: collection of Boolean functions on n bits (Known)
Target concept c: some function c ∈ C (Unknown)
Distribution D : {0, 1}n → [0, 1]
Labeled example for c ∈ C: (x, c(x)) where x ∼ D

3/ 18

Classical learner using classical examples
Basic definitions
Concept class C: collection of Boolean functions on n bits (Known)
Target concept c: some function c ∈ C. (Unknown)
Distribution D : {0, 1}n → [0, 1]
Labeled example for c ∈ C: (x, c(x)) where x ∼ D

Learner is trying to learn c
4/ 18

Classical learner using classical examples
Basic definitions
Concept class C: collection of Boolean functions on n bits (Known)
Target concept c: some function c ∈ C. (Unknown)
Distribution D : {0, 1}n → [0, 1]
Labeled example for c ∈ C: (x, c(x)) where x ∼ D

Learner is trying to learn c
4/ 18

Classical learner using classical examples
Basic definitions
Concept class C: collection of Boolean functions on n bits (Known)
Target concept c: some function c ∈ C. (Unknown)
Distribution D : {0, 1}n → [0, 1]
Labeled example for c ∈ C: (x, c(x)) where x ∼ D

Learner is trying to learn c
4/ 18

Classical learner using classical examples
Basic definitions
Concept class C: collection of Boolean functions on n bits (Known)
Target concept c: some function c ∈ C. (Unknown)
Distribution D : {0, 1}n → [0, 1]
Labeled example for c ∈ C: (x, c(x)) where x ∼ D

Learner is trying to learn c
4/ 18

Quantum learning using quantum examples

5/ 18

Quantum learning using quantum examples
Learner is quantum:

5/ 18

Quantum learning using quantum examples
Learner is quantum:

Data is quantum: Bshouty-Jackson’95 introduced a quantum
example as a superposition
X p
D(x) |x, c(x)ix∈{0,1}n5/ 18

Quantum learning using quantum examples
Learner is quantum:

Data is quantum: Bshouty-Jackson’95 introduced a quantum
example as a superposition
X p
D(x) |x, c(x)ix∈{0,1}nMeasuring this state gives a (x, c(x)) with probability D(x),5/ 18

Quantum learning using quantum examples
Learner is quantum:

Data is quantum: Bshouty-Jackson’95 introduced a quantum
example as a superposition
X p
D(x) |x, c(x)ix∈{0,1}nMeasuring this state gives a (x, c(x)) with probability D(x),so quantum examples are at least as powerful as classical

5/ 18

Motivating question for this talkFix a concept class C, distribution D : {0, 1}n → [0, 1]

6/ 18

Motivating question for this talkFix a concept class C, distribution D : {0, 1}n → [0, 1]

6/ 18

Motivating question for this talkFix a concept class C, distribution D : {0, 1}n → [0, 1]

Question
Understanding the concept classes C and distributions D where fewer
quantum examples suffice for a quantum learner
6/ 18

Distribution (in)dependent PAC learning
Focus on Probably Approximately Correct (PAC) model of learning

7/ 18

Distribution (in)dependent PAC learning
Focus on Probably Approximately Correct (PAC) model of learning
Fix C ⊆ {c : {0, 1}n → {0, 1}} and D : {0, 1}n → [0, 1]

7/ 18

Distribution (in)dependent PAC learning
Focus on Probably Approximately Correct (PAC) model of learning
Fix C ⊆ {c : {0, 1}n → {0, 1}} and D : {0, 1}n → [0, 1]
Using i.i.d. labeled examples, learner for C should output
hypothesis h that is close to c w.r.t. D,

7/ 18

Distribution (in)dependent PAC learning
Focus on Probably Approximately Correct (PAC) model of learning
Fix C ⊆ {c : {0, 1}n → {0, 1}} and D : {0, 1}n → [0, 1]
Using i.i.d. labeled examples, learner for C should output
hypothesis h that is close to c w.r.t. D, i.e.,
errD (c, h) = Prx∼D [c(x) 6= h(x)] should be small

7/ 18

Distribution (in)dependent PAC learning
Focus on Probably Approximately Correct (PAC) model of learning
Fix C ⊆ {c : {0, 1}n → {0, 1}} and D : {0, 1}n → [0, 1]
Using i.i.d. labeled examples, learner for C should output
hypothesis h that is close to c w.r.t. D, i.e.,
errD (c, h) = Prx∼D [c(x) 6= h(x)] should be small
Distribution-dependent learning (for a fixed D)
An algorithm (ε, δ)-learns C under D if:∀c ∈ C : Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

7/ 18

Distribution (in)dependent PAC learning
Focus on Probably Approximately Correct (PAC) model of learning
Fix C ⊆ {c : {0, 1}n → {0, 1}} and D : {0, 1}n → [0, 1]
Using i.i.d. labeled examples, learner for C should output
hypothesis h that is close to c w.r.t. D, i.e.,
errD (c, h) = Prx∼D [c(x) 6= h(x)] should be small
Distribution-dependent learning (for a fixed D)
An algorithm (ε, δ)-learns C under D if:∀c ∈ C : Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

PAC learning (Distribution-independent learning for every D)

7/ 18

Distribution (in)dependent PAC learning
Focus on Probably Approximately Correct (PAC) model of learning
Fix C ⊆ {c : {0, 1}n → {0, 1}} and D : {0, 1}n → [0, 1]
Using i.i.d. labeled examples, learner for C should output
hypothesis h that is close to c w.r.t. D, i.e.,
errD (c, h) = Prx∼D [c(x) 6= h(x)] should be small
Distribution-dependent learning (for a fixed D)
An algorithm (ε, δ)-learns C under D if:∀c ∈ C : Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Probably

Approximately Correct

PAC learning (Distribution-independent learning for every D)
An algorithm (ε, δ)-PAC-learns C if:∀D ∀c ∈ C : Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably
7/ 18

Complexity of learning
How to measure the efficiency of the classical or quantum learner?

8/ 18

Complexity of learning
How to measure the efficiency of the classical or quantum learner?
Sample complexity: number of labeled examples used by learner

8/ 18

Complexity of learning
How to measure the efficiency of the classical or quantum learner?
Sample complexity: number of labeled examples used by learner
Time complexity: number of time-steps used by learner

8/ 18

Complexity of learning
How to measure the efficiency of the classical or quantum learner?
Sample complexity: number of labeled examples used by learner
Time complexity: number of time-steps used by learner
In this talkStrengths of quantum examples

8/ 18

Complexity of learning
How to measure the efficiency of the classical or quantum learner?
Sample complexity: number of labeled examples used by learner
Time complexity: number of time-steps used by learner
In this talkStrengths of quantum examples
ACLW’18: Sample complexity of learning Fourier-sparse Booleanfunctions under uniform D

8/ 18

Complexity of learning
How to measure the efficiency of the classical or quantum learner?
Sample complexity: number of labeled examples used by learner
Time complexity: number of time-steps used by learner
In this talkStrengths of quantum examples
ACLW’18: Sample complexity of learning Fourier-sparse Booleanfunctions under uniform D
Bshouty-Jackson’95: Quantum polynomial time learnability of DNFs
under uniform D

8/ 18

Complexity of learning
How to measure the efficiency of the classical or quantum learner?
Sample complexity: number of labeled examples used by learner
Time complexity: number of time-steps used by learner
In this talkStrengths of quantum examples
ACLW’18: Sample complexity of learning Fourier-sparse Booleanfunctions under uniform D
Bshouty-Jackson’95: Quantum polynomial time learnability of DNFs
under uniform D
ACKW’18: Quantum examples can help the coupon collector

8/ 18

Complexity of learning
How to measure the efficiency of the classical or quantum learner?
Sample complexity: number of labeled examples used by learner
Time complexity: number of time-steps used by learner
In this talkStrengths of quantum examples
ACLW’18: Sample complexity of learning Fourier-sparse Booleanfunctions under uniform D
Bshouty-Jackson’95: Quantum polynomial time learnability of DNFs
under uniform D
ACKW’18: Quantum examples can help the coupon collector
Weaknesses of quantum examples
AW’17: Quantum examples are not more powerful than classicalexamples for PAC learning
8/ 18

Fourier sampling: a useful trick under uniform D

9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}.

9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}. Then the Fourier coefficients arecb(S) =

12n

Xc(x)(−1)S·x

for all S ∈ {0, 1}nx∈{0,1}n9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}. Then the Fourier coefficients arecb(S) =

12nParseval’s identity:Xc(x)(−1)S·x

for all S ∈ {0, 1}nx∈{0,1}nb(S)2 =
Sc

P

9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}. Then the Fourier coefficients arecb(S) =

12nParseval’s identity:Xc(x)(−1)S·x

for all S ∈ {0, 1}nx∈{0,1}nb(S)2 = Ex [c(x)2 ]
Sc

P

9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}. Then the Fourier coefficients arecb(S) =

12nParseval’s identity:Xc(x)(−1)S·x

for all S ∈ {0, 1}nx∈{0,1}nb(S)2 = Ex [c(x)2 ] = 1
Sc

P

9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}. Then the Fourier coefficients arecb(S) =

12n

Xc(x)(−1)S·x

for all S ∈ {0, 1}nx∈{0,1}nP
Parseval’s identity: S cb(S)2 = Ex [c(x)2 ] = 1
So {bc (S)2 }S forms a probability distribution

9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}. Then the Fourier coefficients arecb(S) =

12n

Xc(x)(−1)S·x

for all S ∈ {0, 1}nx∈{0,1}nP
Parseval’s identity: S cb(S)2 = Ex [c(x)2 ] = 1
So {bc (S)2 }S forms a probability distribution
Given quantum example under uniform D:
1 X√|x, c(x)i
2n x

9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}. Then the Fourier coefficients arecb(S) =

12n

Xc(x)(−1)S·x

for all S ∈ {0, 1}nx∈{0,1}nP
Parseval’s identity: S cb(S)2 = Ex [c(x)2 ] = 1
So {bc (S)2 }S forms a probability distribution
Given quantum example under uniform D:
X
1 X
Hadamard√
cb(S) |S i|x, c(x)i −→
2n x
S

9/ 18

Fourier sampling: a useful trick under uniform D
Let c : {0, 1}n → {−1, 1}. Then the Fourier coefficients arecb(S) =

12n

Xc(x)(−1)S·x

for all S ∈ {0, 1}nx∈{0,1}nP
Parseval’s identity: S cb(S)2 = Ex [c(x)2 ] = 1
So {bc (S)2 }S forms a probability distribution
Given quantum example under uniform D:
X
1 X
Hadamard√
cb(S) |S i|x, c(x)i −→2n x
SMeasuring allows to sample from the Fourier distribution {bc (S)2 }S

9/ 18

Applications of Fourier sampling

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}n10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)
Consider C2 = {c is a `-junta}, i.e., c(x) depends only on ` bits of x

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)
Consider C2 = {c is a `-junta}, i.e., c(x) depends only on ` bits of x
Classical: Efficient learning is notoriously hard for ` = O(log n) and uniform D

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)
Consider C2 = {c is a `-junta}, i.e., c(x) depends only on ` bits of x
Classical: Efficient learning is notoriously hard for ` = O(log n) and uniform De ` ) quantum examples and in time
Quantum: C2 can be exactly learnt using O(2`2`eO(n2 + 2 ) (Atıcı-Servedio’09)

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)
Consider C2 = {c is a `-junta}, i.e., c(x) depends only on ` bits of x
Classical: Efficient learning is notoriously hard for ` = O(log n) and uniform De ` ) quantum examples and in time
Quantum: C2 can be exactly learnt using O(2`2`eO(n2 + 2 ) (Atıcı-Servedio’09)

Generalizing both these concept classes?
Definition: We say c is k-Fourier sparse if |{S : cb(S) 6= 0}| ≤ k.

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)
Consider C2 = {c is a `-junta}, i.e., c(x) depends only on ` bits of x
Classical: Efficient learning is notoriously hard for ` = O(log n) and uniform De ` ) quantum examples and in time
Quantum: C2 can be exactly learnt using O(2`2`eO(n2 + 2 ) (Atıcı-Servedio’09)

Generalizing both these concept classes?
Definition: We say c is k-Fourier sparse if |{S : cb(S) 6= 0}| ≤ k.
Note that C1 is 1-Fourier sparse and C2 is 2` -Fourier sparse

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)
Consider C2 = {c is a `-junta}, i.e., c(x) depends only on ` bits of x
Classical: Efficient learning is notoriously hard for ` = O(log n) and uniform De ` ) quantum examples and in time
Quantum: C2 can be exactly learnt using O(2`2`eO(n2 + 2 ) (Atıcı-Servedio’09)

Generalizing both these concept classes?
Definition: We say c is k-Fourier sparse if |{S : cb(S) 6= 0}| ≤ k.
Note that C1 is 1-Fourier sparse and C2 is 2` -Fourier sparse
Consider the concept class C = {c : {0, 1}n → {−1, 1} : c is k-Fourier sparse}

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)
Consider C2 = {c is a `-junta}, i.e., c(x) depends only on ` bits of x
Classical: Efficient learning is notoriously hard for ` = O(log n) and uniform De ` ) quantum examples and in time
Quantum: C2 can be exactly learnt using O(2`2`eO(n2 + 2 ) (Atıcı-Servedio’09)

Generalizing both these concept classes?
Definition: We say c is k-Fourier sparse if |{S : cb(S) 6= 0}| ≤ k.
Note that C1 is 1-Fourier sparse and C2 is 2` -Fourier sparse
Consider the concept class C = {c : {0, 1}n → {−1, 1} : c is k-Fourier sparse}
Observe that C1 ⊆ C. C contains linear functions

10/ 18

Applications of Fourier sampling
Consider the concept class of linear functions C1 = {cS (x) = S · x}S∈{0,1}nClassical: Ω(n) classical examples needed
Quantum: 1 quantum example suffices to learn C1 (Bernstein-Vazirani’93)
Consider C2 = {c is a `-junta}, i.e., c(x) depends only on ` bits of x
Classical: Efficient learning is notoriously hard for ` = O(log n) and uniform De ` ) quantum examples and in time
Quantum: C2 can be exactly learnt using O(2`2`eO(n2 + 2 ) (Atıcı-Servedio’09)

Generalizing both these concept classes?
Definition: We say c is k-Fourier sparse if |{S : cb(S) 6= 0}| ≤ k.
Note that C1 is 1-Fourier sparse and C2 is 2` -Fourier sparse
Consider the concept class C = {c : {0, 1}n → {−1, 1} : c is k-Fourier sparse}
Observe that C1 ⊆ C. C contains linear functions
Observe that C2 ⊆ C. C contains (log k)-juntas
10/ 18

Learning C = {c is k-Fourier sparse}

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution D

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C
e 1.5 ) quantum examples √1 P |x, c(x)i are
Quantumly (ACLW’18): O(k2nxsufficient to learn C (independent of the universe size n)

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C
e 1.5 ) quantum examples √1 P |x, c(x)i are
Quantumly (ACLW’18): O(k2nxsufficient to learn C (independent of the universe size n)eΩ(k)examples are necessary to learn C

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C
e 1.5 ) quantum examples √1 P |x, c(x)i are
Quantumly (ACLW’18): O(k2nxsufficient to learn C (independent of the universe size n)eΩ(k)examples are necessary to learn C
Sketch of upper bound11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C
e 1.5 ) quantum examples √1 P |x, c(x)i are
Quantumly (ACLW’18): O(k2nxsufficient to learn C (independent of the universe size n)eΩ(k)examples are necessary to learn C
Sketch of upper boundUse Fourier sampling to sample S ∼ {bc (S)2 }S

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C
e 1.5 ) quantum examples √1 P |x, c(x)i are
Quantumly (ACLW’18): O(k2nxsufficient to learn C (independent of the universe size n)eΩ(k)examples are necessary to learn C
Sketch of upper boundUse Fourier sampling to sample S ∼ {bc (S)2 }SCollect Ss until the learner learns the Fourier span of c, V = span{S : cb(S) 6= 0}

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C
e 1.5 ) quantum examples √1 P |x, c(x)i are
Quantumly (ACLW’18): O(k2nxsufficient to learn C (independent of the universe size n)eΩ(k)examples are necessary to learn C
Sketch of upper boundUse Fourier sampling to sample S ∼ {bc (S)2 }SCollect Ss until the learner learns the Fourier span of c, V = span{S : cb(S) 6= 0}eSuppose dim(V) = r , then O(rk)quantum examples suffice to find V

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C
e 1.5 ) quantum examples √1 P |x, c(x)i are
Quantumly (ACLW’18): O(k2nxsufficient to learn C (independent of the universe size n)eΩ(k)examples are necessary to learn C
Sketch of upper boundUse Fourier sampling to sample S ∼ {bc (S)2 }SCollect Ss until the learner learns the Fourier span of c, V = span{S : cb(S) 6= 0}eSuppose dim(V) = r , then O(rk)quantum examples suffice to find Ve
Use the result of [HR’15] to learn c 0 completely using O(rk)classical examples

11/ 18

Learning C = {c is k-Fourier sparse}

Exact learning C under the uniform distribution DeClassically (Haviv-Regev’15): Θ(nk)classical examples (x, c(x)) are necessary
and sufficient to learn the concept class C
e 1.5 ) quantum examples √1 P |x, c(x)i are
Quantumly (ACLW’18): O(k2nxsufficient to learn C (independent of the universe size n)eΩ(k)examples are necessary to learn C
Sketch of upper boundUse Fourier sampling to sample S ∼ {bc (S)2 }SCollect Ss until the learner learns the Fourier span of c, V = span{S : cb(S) 6= 0}eSuppose dim(V) = r , then O(rk)quantum examples suffice to find Ve
Use the result of [HR’15] to learn c 0 completely using O(rk)classical examples√e k) for every c ∈ C [Sanyal’15], we get O(ke 1.5 ) upper boundSince r ≤ O(

11/ 18

Learning Disjunctive normal Forms (DNF)

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables.

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ s

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D
Classically: Efficient learning using examples is a longstanding open question.
Best known upper bound is nO(log n) [Verbeurgt’90]

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D
Classically: Efficient learning using examples is a longstanding open question.
Best known upper bound is nO(log n) [Verbeurgt’90]
Quantumly: Bshouty-Jackson’95 gave a polynomial-time quantum algorithm!

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D
Classically: Efficient learning using examples is a longstanding open question.
Best known upper bound is nO(log n) [Verbeurgt’90]
Quantumly: Bshouty-Jackson’95 gave a polynomial-time quantum algorithm!
Proof sketch of quantum upper bound12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D
Classically: Efficient learning using examples is a longstanding open question.
Best known upper bound is nO(log n) [Verbeurgt’90]
Quantumly: Bshouty-Jackson’95 gave a polynomial-time quantum algorithm!
Proof sketch of quantum upper boundStructural property: if c is an s-term DNF, then there exists U s.t. |bc (U)| ≥ 1s

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D
Classically: Efficient learning using examples is a longstanding open question.
Best known upper bound is nO(log n) [Verbeurgt’90]
Quantumly: Bshouty-Jackson’95 gave a polynomial-time quantum algorithm!
Proof sketch of quantum upper boundStructural property: if c is an s-term DNF, then there exists U s.t. |bc (U)| ≥ 1s
Fourier sampling! Sample T ∼ {bc (T )2 }T , poly(s) many times to see such a U

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D
Classically: Efficient learning using examples is a longstanding open question.
Best known upper bound is nO(log n) [Verbeurgt’90]
Quantumly: Bshouty-Jackson’95 gave a polynomial-time quantum algorithm!
Proof sketch of quantum upper boundStructural property: if c is an s-term DNF, then there exists U s.t. |bc (U)| ≥ 1s
Fourier sampling! Sample T ∼ {bc (T )2 }T , poly(s) many times to see such a U
Construct a “weak learner” who outputs χU s.t. Pr[χU (x) = c(x)] = 21 + 1s

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D
Classically: Efficient learning using examples is a longstanding open question.
Best known upper bound is nO(log n) [Verbeurgt’90]
Quantumly: Bshouty-Jackson’95 gave a polynomial-time quantum algorithm!
Proof sketch of quantum upper boundStructural property: if c is an s-term DNF, then there exists U s.t. |bc (U)| ≥ 1s
Fourier sampling! Sample T ∼ {bc (T )2 }T , poly(s) many times to see such a U
Construct a “weak learner” who outputs χU s.t. Pr[χU (x) = c(x)] = 21 + 1s
Not good enough! Want an hypothesis that agrees with c on most inputs x’s

12/ 18

Learning Disjunctive normal Forms (DNF)
DNFs
Simply an OR of AND of variables. For example, (x1 ∧ x4 ∧ x3 ) ∨ (x4 ∧ x6 ∧ x7 ∧ x8 )We say a DNF on n variables is an s-term DNF if number of clauses is ≤ sLearning C = {c is an s-term DNF in n variables} under uniform D
Classically: Efficient learning using examples is a longstanding open question.
Best known upper bound is nO(log n) [Verbeurgt’90]
Quantumly: Bshouty-Jackson’95 gave a polynomial-time quantum algorithm!
Proof sketch of quantum upper boundStructural property: if c is an s-term DNF, then there exists U s.t. |bc (U)| ≥ 1s
Fourier sampling! Sample T ∼ {bc (T )2 }T , poly(s) many times to see such a U
Construct a “weak learner” who outputs χU s.t. Pr[χU (x) = c(x)] = 21 + 1s
Not good enough! Want an hypothesis that agrees with c on most inputs x’s
Boosting: Run weak learner many times in some manner to obtain a strong
learner who outputs h satisfying Pr[h(x) = c(x)] ≥ 2/3
12/ 18Pretty good measurement for state identification

13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distribution

13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distributionp
P
For c ∈ C, a quantum example is |ψc i = x∈{0,1}n D(x) |x, c(x)i13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distributionp
P
For c ∈ C, a quantum example is |ψc i = x∈{0,1}n D(x) |x, c(x)iState identification: For uniform c ∈ C (unknown), given |ψc i⊗T , identify c

13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distributionp
P
For c ∈ C, a quantum example is |ψc i = x∈{0,1}n D(x) |x, c(x)iState identification: For uniform c ∈ C (unknown), given |ψc i⊗T , identify c
Optimal measurement could be quite complicated,

13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distributionp
P
For c ∈ C, a quantum example is |ψc i = x∈{0,1}n D(x) |x, c(x)iState identification: For uniform c ∈ C (unknown), given |ψc i⊗T , identify c
Optimal measurement could be quite complicated,
but we can always use the Pretty Good Measurement (PGM)

13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distributionp
P
For c ∈ C, a quantum example is |ψc i = x∈{0,1}n D(x) |x, c(x)iState identification: For uniform c ∈ C (unknown), given |ψc i⊗T , identify c
Optimal measurement could be quite complicated,
but we can always use the Pretty Good Measurement (PGM)
If Popt is the success probability of the optimal measurement,

13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distributionp
P
For c ∈ C, a quantum example is |ψc i = x∈{0,1}n D(x) |x, c(x)iState identification: For uniform c ∈ C (unknown), given |ψc i⊗T , identify c
Optimal measurement could be quite complicated,
but we can always use the Pretty Good Measurement (PGM)
If Popt is the success probability of the optimal measurement,
Ppgm is the success probability of the PGM,

13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distributionp
P
For c ∈ C, a quantum example is |ψc i = x∈{0,1}n D(x) |x, c(x)iState identification: For uniform c ∈ C (unknown), given |ψc i⊗T , identify c
Optimal measurement could be quite complicated,
but we can always use the Pretty Good Measurement (PGM)
If Popt is the success probability of the optimal measurement,
Ppgm is the success probability of the PGM, thenPopt ≥ Ppgm

13/ 18Pretty good measurement for state identification

Consider a concept class C consisting of n-bit Boolean functions.
Let D : {0, 1}n → [0, 1] be a distributionp
P
For c ∈ C, a quantum example is |ψc i = x∈{0,1}n D(x) |x, c(x)iState identification: For uniform c ∈ C (unknown), given |ψc i⊗T , identify c
Optimal measurement could be quite complicated,
but we can always use the Pretty Good Measurement (PGM)
If Popt is the success probability of the optimal measurement,
Ppgm is the success probability of the PGM, then2
Popt ≥ Ppgm ≥ Popt
(Barnum-Knill’02)

13/ 18

Quantum examples help the coupon collector

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons.

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons.

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}.

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ }14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ } before learning i ∗ ?

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ } before learning i ∗ ?
Answer: Same analysis as earlier shows Θ(N log N)

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ } before learning i ∗ ?
Answer: Same analysis as earlier shows Θ(N log N)
What if we are given “quantum examples”

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ } before learning i ∗ ?
Answer: Same analysis as earlier shows Θ(N log N)
What if we are given “quantum examples”
1
Suppose a quantum learner obtains quantum examples √N−1

Pi∈({1,...,N}\{i ∗ }) |i i.

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ } before learning i ∗ ?
Answer: Same analysis as earlier shows Θ(N log N)
What if we are given “quantum examples”
1
Suppose a quantum learner obtains quantum examples √N−1∗
How many quantum examples before learning i ?

Pi∈({1,...,N}\{i ∗ }) |i i.

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ } before learning i ∗ ?
Answer: Same analysis as earlier shows Θ(N log N)
What if we are given “quantum examples”
1
Suppose a quantum learner obtains quantum examples √N−1∗
How many quantum examples before learning i ?

Pi∈({1,...,N}\{i ∗ }) |i i.

Answer [ACKW’..]: Can learn i ∗ using Θ(N) quantum examples

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ } before learning i ∗ ?
Answer: Same analysis as earlier shows Θ(N log N)
What if we are given “quantum examples”
1
Suppose a quantum learner obtains quantum examples √N−1∗
How many quantum examples before learning i ?

Pi∈({1,...,N}\{i ∗ }) |i i.

Answer [ACKW’..]: Can learn i ∗ using Θ(N) quantum examples
Proof idea: Analyze the success probability using the pretty good measurement.

14/ 18

Quantum examples help the coupon collector
Standard coupon collector
Problem: Suppose there are N coupons. How many coupons to draw (withreplacement) before having seen each coupon at least once?
Answer: Simple probability analysis shows Θ(N log N)
Variation to coupon collector
Problem: Suppose there are N coupons. Fix unknown i ∗ ∈ {1, . . . , N}. How many
coupons to draw (with replacement) from {1, . . . , N}\{i ∗ } before learning i ∗ ?
Answer: Same analysis as earlier shows Θ(N log N)
What if we are given “quantum examples”
1
Suppose a quantum learner obtains quantum examples √N−1∗
How many quantum examples before learning i ?

Pi∈({1,...,N}\{i ∗ }) |i i.

Answer [ACKW’..]: Can learn i ∗ using Θ(N) quantum examples
Proof idea: Analyze the success probability using the pretty good measurement.
If T = O(N), then Popt ≥ Ppgm ≥ 2/3
14/ 18

Distribution-independent learning
Recall: PAC learning

15/ 18

Distribution-independent learning
Recall: PAC learning
Given (x, c(x)) examples where x ∼ D, a learner (ε, δ)-PAC-learns C if:∀D ∀c ∈ C

: Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

15/ 18

Distribution-independent learning
Recall: PAC learning
Given (x, c(x)) examples where x ∼ D, a learner (ε, δ)-PAC-learns C if:∀D ∀c ∈ C

: Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

Complexity measure: Number of labelled examples

15/ 18

Distribution-independent learning
Recall: PAC learning
Given (x, c(x)) examples where x ∼ D, a learner (ε, δ)-PAC-learns C if:∀D ∀c ∈ C

: Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

Complexity measure: Number of labelled examples
For a concept class C, associate a combinatorial parameter called VC-dimension of C.

15/ 18

Distribution-independent learning
Recall: PAC learning
Given (x, c(x)) examples where x ∼ D, a learner (ε, δ)-PAC-learns C if:∀D ∀c ∈ C

: Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

Complexity measure: Number of labelled examples
For a concept class C, associate a combinatorial parameter called VC-dimension of C.
Classical PAC learning sample complexity is characterized by the VC-dimension of C

15/ 18

Distribution-independent learning
Recall: PAC learning
Given (x, c(x)) examples where x ∼ D, a learner (ε, δ)-PAC-learns C if:∀D ∀c ∈ C

: Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

Complexity measure: Number of labelled examples
For a concept class C, associate a combinatorial parameter called VC-dimension of C.
Classical PAC learning sample complexity is characterized by the VC-dimension of C
Fundamental theorem of PAC learning

15/ 18

Distribution-independent learning
Recall: PAC learning
Given (x, c(x)) examples where x ∼ D, a learner (ε, δ)-PAC-learns C if:∀D ∀c ∈ C

: Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

Complexity measure: Number of labelled examples
For a concept class C, associate a combinatorial parameter called VC-dimension of C.
Classical PAC learning sample complexity is characterized by the VC-dimension of C
Fundamental theorem of PAC learning
Suppose VC-dim(C) = d

15/ 18

Distribution-independent learning
Recall: PAC learning
Given (x, c(x)) examples where x ∼ D, a learner (ε, δ)-PAC-learns C if:∀D ∀c ∈ C

: Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

Complexity measure: Number of labelled examples
For a concept class C, associate a combinatorial parameter called VC-dimension of C.
Classical PAC learning sample complexity is characterized by the VC-dimension of C
Fundamental theorem of PAC learning
Suppose VC-dim(C) = d
Blumer-Ehrenfeucht-Haussler-Warmuth’86:
log(1/δ)every (ε, δ)-PAC learner for C needs Ω dε +examplesε15/ 18

Distribution-independent learning
Recall: PAC learning
Given (x, c(x)) examples where x ∼ D, a learner (ε, δ)-PAC-learns C if:∀D ∀c ∈ C

: Pr[

errD (c, h) ≤ ε|{z}]≥ 1−δ
| {z }

Approximately Correct

Probably

Complexity measure: Number of labelled examples
For a concept class C, associate a combinatorial parameter called VC-dimension of C.
Classical PAC learning sample complexity is characterized by the VC-dimension of C
Fundamental theorem of PAC learning
Suppose VC-dim(C) = d
Blumer-Ehrenfeucht-Haussler-Warmuth’86:
log(1/δ)every (ε, δ)-PAC learner for C needs Ω dε +examplesε
log(1/δ)Hanneke’16: exists an (ε, δ)-PAC learner for C using O dε +examplesε15/ 18

VC-dimension and quantum sample complexity

16/ 18

VC-dimension and quantum sample complexity
Quantum bounds
Classical upper bound Olog(1/δ)
d
+
ε
ε



carries over to quantum

16/ 18

VC-dimension and quantum sample complexity
Quantum boundslog(1/δ)d+carries over to quantumεε√
log(1/δ)Atıcı-Servedio’04: lower bound Ω εd +εClassical upper bound O

16/ 18

VC-dimension and quantum sample complexity
Quantum boundslog(1/δ)d+carries over to quantumεε√
log(1/δ)Atıcı-Servedio’04: lower bound Ω εd +εClassical upper bound O

AW’17: Showed Ωlog(1/δ)
d
+
ε
ε



quantum examples are necessary

16/ 18

VC-dimension and quantum sample complexity
Quantum boundslog(1/δ)d+carries over to quantumεε√
log(1/δ)Atıcı-Servedio’04: lower bound Ω εd +εClassical upper bound O

AW’17: Showed Ωlog(1/δ)
d
+
ε
ε



quantum examples are necessary

Proof idea: Reduce to state identification.

16/ 18

VC-dimension and quantum sample complexity
Quantum boundslog(1/δ)d+carries over to quantumεε√
log(1/δ)Atıcı-Servedio’04: lower bound Ω εd +εClassical upper bound O

AW’17: Showed Ωlog(1/δ)
d
+
ε
ε



quantum examples are necessary

Proof idea: Reduce to state identification. For a good learner Popt ≥ 2/3, so
2 ≥ 4/9.
Ppgm ≥ Popt

16/ 18

VC-dimension and quantum sample complexity
Quantum boundslog(1/δ)d+carries over to quantumεε√
log(1/δ)Atıcı-Servedio’04: lower bound Ω εd +εClassical upper bound O

AW’17: Showed Ωlog(1/δ)
d
+
ε
ε



quantum examples are necessary

Proof idea: Reduce to state identification. For a good learner Popt ≥ 2/3, so

2 ≥ 4/9. If P
Ppgm ≥ Popt
pgm ≥ 4/9, then T = Ωdε16/ 18

VC-dimension and quantum sample complexity
Quantum boundslog(1/δ)d+carries over to quantumεε√
log(1/δ)Atıcı-Servedio’04: lower bound Ω εd +εClassical upper bound O

AW’17: Showed Ωlog(1/δ)
d
+
ε
ε



quantum examples are necessary

Proof idea: Reduce to state identification. For a good learner Popt ≥ 2/3, so

2 ≥ 4/9. If P
Ppgm ≥ Popt
pgm ≥ 4/9, then T = ΩdεQuantum examples are no better than classical examples for PAC learning

16/ 18

VC-dimension and quantum sample complexity
Quantum boundslog(1/δ)d+carries over to quantumεε√
log(1/δ)Atıcı-Servedio’04: lower bound Ω εd +εClassical upper bound O

AW’17: Showed Ωlog(1/δ)
d
+
ε
ε



quantum examples are necessary

Proof idea: Reduce to state identification. For a good learner Popt ≥ 2/3, so

2 ≥ 4/9. If P
Ppgm ≥ Popt
pgm ≥ 4/9, then T = ΩdεQuantum examples are no better than classical examples for PAC learning
Let’s get real!
In computational learning theory, agnostic learning and learning underclassification noise is a theoretical way to model noise in data

16/ 18

VC-dimension and quantum sample complexity
Quantum boundslog(1/δ)d+carries over to quantumεε√
log(1/δ)Atıcı-Servedio’04: lower bound Ω εd +εClassical upper bound O

AW’17: Showed Ωlog(1/δ)
d
+
ε
ε



quantum examples are necessary

Proof idea: Reduce to state identification. For a good learner Popt ≥ 2/3, so

2 ≥ 4/9. If P
Ppgm ≥ Popt
pgm ≥ 4/9, then T = ΩdεQuantum examples are no better than classical examples for PAC learning
Let’s get real!
In computational learning theory, agnostic learning and learning underclassification noise is a theoretical way to model noise in data
Again, in these realistic models we show thatquantum sample complexity equals classical sample complexity

16/ 18

Future directions

17/ 18

Future directions
More mileage out of Fourier sampling?

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?
Can we PAC-learn DNFs? If so, then we could possibly learn depth-3 circuits
under the uniform distribution

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?
Can we PAC-learn DNFs? If so, then we could possibly learn depth-3 circuits
under the uniform distribution
Scott Aaronson: Can AC0 be learnt in quantum polynomial time?
(One of his ten semi-grand challenges for quantum computing!)

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?
Can we PAC-learn DNFs? If so, then we could possibly learn depth-3 circuits
under the uniform distribution
Scott Aaronson: Can AC0 be learnt in quantum polynomial time?
(One of his ten semi-grand challenges for quantum computing!)
Can TC0 be learnt in quantum polynomial time?
A theoretical way to understand neural networks

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?
Can we PAC-learn DNFs? If so, then we could possibly learn depth-3 circuits
under the uniform distribution
Scott Aaronson: Can AC0 be learnt in quantum polynomial time?
(One of his ten semi-grand challenges for quantum computing!)
Can TC0 be learnt in quantum polynomial time?
A theoretical way to understand neural networks
Can we learn constant-depth quantum circuits?

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?
Can we PAC-learn DNFs? If so, then we could possibly learn depth-3 circuits
under the uniform distribution
Scott Aaronson: Can AC0 be learnt in quantum polynomial time?
(One of his ten semi-grand challenges for quantum computing!)
Can TC0 be learnt in quantum polynomial time?
A theoretical way to understand neural networks
Can we learn constant-depth quantum circuits?
More open questions!

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?
Can we PAC-learn DNFs? If so, then we could possibly learn depth-3 circuits
under the uniform distribution
Scott Aaronson: Can AC0 be learnt in quantum polynomial time?
(One of his ten semi-grand challenges for quantum computing!)
Can TC0 be learnt in quantum polynomial time?
A theoretical way to understand neural networks
Can we learn constant-depth quantum circuits?
More open questions!
Can we learn the concept class of k-Fourier sparse Boolean functions usingO(k log k) samples matching our lower bound?

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?
Can we PAC-learn DNFs? If so, then we could possibly learn depth-3 circuits
under the uniform distribution
Scott Aaronson: Can AC0 be learnt in quantum polynomial time?
(One of his ten semi-grand challenges for quantum computing!)
Can TC0 be learnt in quantum polynomial time?
A theoretical way to understand neural networks
Can we learn constant-depth quantum circuits?
More open questions!
Can we learn the concept class of k-Fourier sparse Boolean functions usingO(k log k) samples matching our lower bound?
Theoretically, one could consider more optimistic PAC-like models where learnerneed not succeed ∀c ∈ C and ∀D

17/ 18

Future directions
More mileage out of Fourier sampling?
Extend result of Bshouty-Jackson from depth-2 circuits (i.e., DNFs) to depth-3?
Can we PAC-learn DNFs? If so, then we could possibly learn depth-3 circuits
under the uniform distribution
Scott Aaronson: Can AC0 be learnt in quantum polynomial time?
(One of his ten semi-grand challenges for quantum computing!)
Can TC0 be learnt in quantum polynomial time?
A theoretical way to understand neural networks
Can we learn constant-depth quantum circuits?
More open questions!
Can we learn the concept class of k-Fourier sparse Boolean functions usingO(k log k) samples matching our lower bound?
Theoretically, one could consider more optimistic PAC-like models where learnerneed not succeed ∀c ∈ C and ∀D
Find more distributions (other than uniform) where quantum provides a speedup
17/ 18

Conclusion
For PAC learning, quantum examples are no better than classical examples

18/ 18

Conclusion
For PAC learning, quantum examples are no better than classical examples

Under uniform D, quantum examples seemto help tremendously in some cases

18/ 18

Conclusion
For PAC learning, quantum examples are no better than classical examples

Under uniform D, quantum examples seemto help tremendously in some cases

Quantum machine learning is stillin its infancy! Not many strong
examples where quantum
significantly improves ML

18/ 18

Conclusion
For PAC learning, quantum examples are no better than classical examples

Under uniform D, quantum examples seemto help tremendously in some cases

Quantum machine learning is stillin its infancy! Not many strong
examples where quantum
significantly improves ML

Many recent surveys on quantum machine learning.

18/ 18