Learning depth-3 circuits via quantum agnostic boosting

Abstract

We initiate the study of quantum agnostic learning of phase states with respect to a function class C ⊆c:0,1^n→0,1: given copies of an unknown n-qubit state |ψ⟩ which has fidelity with a phase state |ϕ_c⟩=1/√(2^n)∑_x∈0,1^n(-1)^c(x)|x⟩ for some c∈ C, output |ϕ⟩ which has fidelity |⟨ϕ | ψ ⟩|^2 ≥-ε. To this end, we give agnostic learning protocols for the following classes: 1. Size-t decision trees which runs in time (n,t,1/ε). This also implies k-juntas can be agnostically learned in time (n,2^k,1/ε). 2. s-term DNF formulas in time (n,(s/ε)^loglog (s/ε) ·log(1/ε)). Our main technical contribution is a quantum agnostic boosting protocol which converts a “weak” agnostic learner, which outputs a parity state |ϕ⟩ such that |⟨ϕ|ψ⟩|^2≥/(n), into a “strong” learner which outputs a superposition of parity states |ϕ’⟩ such that |⟨ϕ’|ψ⟩|^2≥ - ε. Using quantum agnostic boosting, we give a n^O(log(n/ε)·loglog n)-time algorithm for ε-learning (n)-sized depth-3 circuits (consisting of , , gates) in the uniform model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the model and our work answers this given quantum examples.