کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427390 | 686499 | 2010 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved lower bound on query complexity for quantum PAC learning
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An improved lower bound on query complexity for quantum PAC learning An improved lower bound on query complexity for quantum PAC learning](/preview/png/427390.png)
چکیده انگلیسی
In this paper, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. For a concept class with VC dimension d , the lower bound is Ω(1ϵ(d1−e+log(1δ))) for ϵ accuracy and 1−δ1−δ confidence, where e can be an arbitrarily small positive number. The lower bound is very close to the best lower bound known on query complexity for the classical PAC learning model, which is Ω(1ϵ(d+log(1δ))).
Research highlights
► The query complexity in the quantum PAC learning model is almost the same as that in the classical PAC learning model.
► A quantum PAC learning algorithm can be considered as a POVM measurement.
► There exists a set of lower bounds on query complexity in the quantum PAC learning model.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 1, 15 December 2010, Pages 40–45
Journal: Information Processing Letters - Volume 111, Issue 1, 15 December 2010, Pages 40–45
نویسندگان
Chi Zhang,