Learning DNF over the uniform distribution using a Quantum Example Oracle

Summary:

Details:

Definitions: DTM: 6-tuple (Q, sigma, delta, q_o, q_a, q_r) where Q: set of finite states, sigma: alphabet, delta: transition function from Q x sigma to Q x sigma x {L,S,R} - deterministic and unique mapping, q_o: initial state, q_a: accepting state and q_r:rejecting state. configuration of the TM, c(current state, tape content, tape head/next symbol). Language L is decideable if QTM:

my hand written notes[PDF]