Фон
Функции в могут быть изучены PAC в квазиполиномиальном времени с помощью классического алгоритма, который требует случайно выбранных запросов, чтобы изучить схему глубины d [1]. Если нет факторинг-алгоритма , то это оптимально [2]. Конечно, на квантовом компьютере мы знаем, как учитывать, поэтому эта нижняя граница не помогает. Кроме того, оптимальный классический алгоритм использует спектр функции Фурье, крича "квантовать меня!" O ( 2 l o g ( n ) O ( d ) ) 2 n o ( 1 )
[1] Н. Линиаль, Ю. Мансур и Н. Нисан. [1993] «Контуры с постоянной глубиной, преобразование Фурье и обучаемость», журнал ACM 40 (3): 607-620.
[2] М. Харитонов. [1993] "Криптографическая стойкость обучения, специфичного для распределения", Слушания ACM STOC'93, с. 372-381.
Фактически, 6 лет назад Скотт Ааронсон назвал обучаемость одним из своих Десяти Полуградовых Задач для Квантовой Вычислительной Теории .
Вопрос
Мой вопрос в три раза:
1) Существуют ли примеры семейств естественных функций, которые квантовые компьютеры могут изучать быстрее, чем классические компьютеры с учетом криптографических предположений?
2) Был ли какой-либо прогресс в изучении в частности? (или немного более амбициозный ) T C 0
3) Что касается обучаемости , Ааронсон комментирует: «тогда квантовые компьютеры будут иметь огромное преимущество перед классическими компьютерами в изучении весов, близких к оптимальным для нейронных сетей». Может кто-нибудь дать ссылку на то, как соотносится обновление веса для нейронных сетей и цепей ? ( за исключение того факта , что порог ворот выглядит как сигмовидные нейроны) (Этот вопрос был задан и ответил уже )
источник