18-летний Ювин Тан доказал, что классические компьютеры могут решать «задачу рекомендаций» почти так же быстро, как квантовые. Этот результат аннулирует один из наилучших примеров квантового ускорения расчётов.
Подросток из Техаса осадил развитие квантовых вычислений. В опубликованной в этом месяце в интернете работе 18-летний Ювин Тан доказал, что обычные компьютеры могут решать важную вычислительную задачу со скоростью, потенциально сравнимой с квантовыми компьютерами.
В наиболее практичном виде проблема рекомендаций связана с тем, как сервисы вроде Amazon и Netflix определяют, какие продукты могут вам понравиться. Специалисты по информатике считали её одним из наилучших примеров задач, решать которые на квантовых компьютерах будет экспоненциально быстрее – что подчёркивало потенциальные возможности этих футуристических машин. И вот теперь Тан опроверг это мнение.
«Это был один из определяющих примеров квантового ускорения – и теперь он исчез», — говорит Тан, весной окончивший учёбу в Техасском университете в Остине, и начинающий этой осенью подготовку к получению докторской степени в Вашингтонском университете.
В 2014 году, в 14-летнем возрасте, Тан перепрыгнул через 4, 5 и 6 классы, и поступил в Техасский университет, где закончил обучение математике и информатике. Весной 2017 Тан прошёл курс квантовой информации, где преподавал Скотт Ааронсон, известный исследователь в области квантовых вычислений. Ааронсон распознал в Тане необычно талантливого студента и предложил ему стать его советником в независимом исследовательском проекте. Ааронсон дал Тану несколько задач на выбор, включая и проблему рекомендаций. Тан выбрал её несколько неохотно.
«Я колебался, поскольку она казалась довольно сложной, но это была простейшая из всех задач, которые он мне предложил», — сказал Тан.
Задача рекомендаций состоит в выдаче рекомендаций по продуктам, которые могут понравиться пользователю. Рассмотрим Netflix. Он знает, какие фильмы вы посмотрели. Он знает, что посмотрели миллионы его пользователей. Имея такую информацию, можно ли узнать, что вам захочется посмотреть дальше?
Эти данные можно представить в виде огромной решётки, или матрицы, сверху которой перечислены все фильмы, сбоку – все пользователи, а внутри стоят значения, оценивающие, насколько каждому из пользователей понравился каждый фильм. Хороший алгоритм выдаст список рекомендаций, быстро и точно обнаружив сходство между фильмами и пользователями, и заполнив пустые клетки матрицы.
В 2016 году специалисты по информатике Иорданис Керенидис и Анупам Пракаш опубликовали квантовый алгоритм, решавший задачу рекомендаций экспоненциально быстрее любого из известных классических алгоритмов. Они получили такое квантовое ускорение, в частности, благодаря упрощению задачи. Вместо того, чтобы заполнять всю матрицу, и определять единственный наилучший продукт для рекомендации, они придумали способ, как можно разбить пользователей на небольшое количество категорий – нравятся ли им блокбастеры или независимое кино? – и обработать существующие данные так, чтобы выдать рекомендацию, которая просто была бы достаточно неплохой.
Ко времени появления работы Керенидиса и Пракаша существовало очень мало примеров задач, которые квантовые компьютеры должны были решать экспоненциально быстрее классических. По большей части эти задачи были специализированными – узкие проблемы, специально разработанные для того, чтобы пользоваться сильными сторонами квантовых компьютеров (включая проблему "форреляции", о которой мы уже писали). Работа Керенидиса и Пракаша оказалась интересной потому, что освещала реальную проблему, важную для людей, в которой квантовые компьютеры обгоняли классические.
«С моей точки зрения, это был один из первых примеров машинного обучения и обработки больших данных, в котором мы показали, что квантовые компьютеры могут делать нечто такое, что мы пока не знаем, как сделать классическими методами», — сказал Керенидис, специалист по информатике из Исследовательского института основ информатики Парижа.
Керенидис и Пракаш доказали, что квантовый компьютер может решить задачу рекомендаций экспоненциально быстрее любого из известных алгоритмов, но они не доказали, что не существует быстрого классического алгоритма. Поэтому, когда Ааронсон начал работать с Таном в 2017 году, он поставил именно такую задачу – доказать отсутствие быстрого классического алгоритма, подтвердив квантовое ускорение Керенидиса и Пракаша.
«Мне казалось, что это будет важной точкой, которую мы поставим для завершения этой истории», — сказал Ааронсон, в то время считавший, что быстрого классического алгоритма не существует.
Тан начал работать над этим осенью 2017 года, рассчитывая, что задача рекомендаций будет темой его диссертации. Несколько месяцев Тан пытался доказать невозможность существования классического алгоритма. Время шло, и Тан начал думать, что, возможно, такой алгоритм всё-таки существует.
«Я начал верить в существование классического алгоритма, но не мог убедить себя в этом, поскольку Скотт думал, что его не существует, а он был для меня авторитетом», — сказал Тан.
Наконец, когда срок сдачи диссертации уже поджимал, Тан написал письмо Ааронсону, где признался в растущих у него подозрениях. «Тан написал мне, по сути, следующее: Я думаю, что быстрый классический алгоритм существует», — сказал Ааронсон.
Всю весну Тан записывал результаты и работал с Ааронсоном над прояснением некоторых шагов доказательства. Обнаруженный Таном быстрый классический алгоритм был вдохновлён быстрым квантовым алгоритмом, найденным Керенидисом и Пракашем за два года до этого. Тан продемонстрировал, что квантовую выборку, использованную в их алгоритме, можно воспроизвести в классических условиях. Алгоритм Тана, как и алгоритм Керенидиса и Пракаша, исполнялся за полилогарифмическое время – то есть, время вычислений оценивалось логарифмом от таких параметров, как количество пользователей и продуктов – и был экспоненциально быстрее любого другого из известных ранее классических алгоритмов.
После завершения Таном алгоритма, Ааронсон хотел удостовериться в его правильности перед публикацией. «Я всё ещё нервничал по поводу того, что если после публикации Таном работы она окажется неверной, то первая большая работа в карьере Тана окажется пшиком», — сказал Ааронсон.
Ааронсон планировал посетить рабочую встречу по квантовым вычислениям в Калифорнийском университете в Беркли в июне. Там должны были собраться светила этой области, включая и Керенидиса с Пракашем. Ааронсон пригласил Тана с собой в Беркли для того, чтобы неформально представить его алгоритм после официальной части конференции.
Утром 18 и утром 19 июня Тан прочёл две лекции, отвечая на вопросы аудитории. По истечению четырёх часов был выработан консенсус: классический алгоритм Тана похож на правильный. Чего многие присутствующие не поняли, так это того, насколько Тан был юным. «Я не знал, что Ювину 18 лет, и определённо мне так не показалось по результатам разговоров. Мне казалось, что Ювин ведёт беседу как вполне взрослый человек», — сказал Керенидис. Теперь алгоритму предстоит формальная экспертная оценка перед тем, как его опубликуют.
Для квантовых вычислений результат Тана служит шагом назад. Или нет. Тан устранил один из самых понятных и лучших примеров квантового преимущества. В то же время, работа Тана является ещё одним свидетельством наличия плодотворного взаимодействия исследований классических и квантовых алгоритмов.
«Тан устраняет квантовое ускорение Керенидиса и Пракаша, но в другом смысле Тан способствует большим улучшением и основывается на их работе. Тан никогда бы не придумал свой классический алгоритм, если бы они не опубликовали свой квантовый», — сказал Ааронсон.
Автор: Вячеслав Голованов
