18-летний Ювин Тан доказал, что классические компьютеры могут решать «задачу рекомендаций» почти так же быстро, как квантовые. Этот результат аннулирует один из наилучших примеров квантового ускорения расчётов.
Подросток из Техаса осадил развитие квантовых вычислений. В опубликованной в этом месяце в интернете работе 18-летний Ювин Тан доказал, что обычные компьютеры могут решать важную вычислительную задачу со скоростью, потенциально сравнимой с квантовыми компьютерами.
В наиболее практичном виде проблема рекомендаций связана с тем, как сервисы вроде Amazon и Netflix определяют, какие продукты могут вам понравиться. Специалисты по информатике считали её одним из наилучших примеров задач, решать которые на квантовых компьютерах будет экспоненциально быстрее – что подчёркивало потенциальные возможности этих футуристических машин. И вот теперь Тан опроверг это мнение.
«Это был один из определяющих примеров квантового ускорения – и теперь он исчез», — говорит Тан, весной окончивший учёбу в Техасском университете в Остине, и начинающий этой осенью подготовку к получению докторской степени в Вашингтонском университете.
В 2014 году, в 14-летнем возрасте, Тан перепрыгнул через 4, 5 и 6 классы, и поступил в Техасский университет, где закончил обучение математике и информатике. Весной 2017 Тан прошёл курс квантовой информации, где преподавал Скотт Ааронсон, известный исследователь в области квантовых вычислений. Ааронсон распознал в Тане необычно талантливого студента и предложил ему стать его советником в независимом исследовательском проекте. Ааронсон дал Тану несколько задач на выбор, включая и проблему рекомендаций. Тан выбрал её несколько неохотно.
«Я колебался, поскольку она казалась довольно сложной, но это была простейшая из всех задач, которые он мне предложил», — сказал Тан.
Задача рекомендаций состоит в выдаче рекомендаций по продуктам, которые могут понравиться пользователю. Рассмотрим Netflix. Он знает, какие фильмы вы посмотрели. Он знает, что посмотрели миллионы его пользователей. Имея такую информацию, можно ли узнать, что вам захочется посмотреть дальше?
Эти данные можно представить в виде огромной решётки, или матрицы, сверху которой перечислены все фильмы, сбоку – все пользователи, а внутри стоят значения, оценивающие, насколько каждому из пользователей понравился каждый фильм. Хороший алгоритм выдаст список рекомендаций, быстро и точно обнаружив сходство между фильмами и пользователями, и заполнив пустые клетки матрицы.
В 2016 году специалисты по информатике Иорданис Керенидис и Анупам Пракаш опубликовали квантовый алгоритм, решавший задачу рекомендаций экспоненциально быстрее любого из известных классических алгоритмов. Они получили такое квантовое ускорение, в частности, благодаря упрощению задачи. Вместо того, чтобы заполнять всю матрицу, и определять единственный наилучший продукт для рекомендации, они придумали способ, как можно разбить пользователей на небольшое количество категорий – нравятся ли им блокбастеры или независимое кино? – и обработать существующие данные так, чтобы выдать рекомендацию, которая просто была бы достаточно неплохой.
Ко времени появления работы Керенидиса и Пракаша существовало очень мало примеров задач, которые квантовые компьютеры должны были решать экспоненциально быстрее классических. По большей части эти задачи были специализированными – узкие проблемы, специально разработанные для того, чтобы пользоваться сильными сторонами квантовых компьютеров (включая проблему "форреляции", о которой мы уже писали). Работа Керенидиса и Пракаша оказалась интересной потому, что освещала реальную проблему, важную для людей, в которой квантовые компьютеры обгоняли классические.
«С моей точки зрения, это был один из первых примеров машинного обучения и обработки больших данных, в котором мы показали, что квантовые компьютеры могут делать нечто такое, что мы пока не знаем, как сделать классическими методами», — сказал Керенидис, специалист по информатике из Исследовательского института основ информатики Парижа.
Керенидис и Пракаш доказали, что квантовый компьютер может решить задачу рекомендаций экспоненциально быстрее любого из известных алгоритмов, но они не доказали, что не существует быстрого классического алгоритма. Поэтому, когда Ааронсон начал работать с Таном в 2017 году, он поставил именно такую задачу – доказать отсутствие быстрого классического алгоритма, подтвердив квантовое ускорение Керенидиса и Пракаша.
«Мне казалось, что это будет важной точкой, которую мы поставим для завершения этой истории», — сказал Ааронсон, в то время считавший, что быстрого классического алгоритма не существует.
Тан начал работать над этим осенью 2017 года, рассчитывая, что задача рекомендаций будет темой его диссертации. Несколько месяцев Тан пытался доказать невозможность существования классического алгоритма. Время шло, и Тан начал думать, что, возможно, такой алгоритм всё-таки существует.
«Я начал верить в существование классического алгоритма, но не мог убедить себя в этом, поскольку Скотт думал, что его не существует, а он был для меня авторитетом», — сказал Тан.
Наконец, когда срок сдачи диссертации уже поджимал, Тан написал письмо Ааронсону, где признался в растущих у него подозрениях. «Тан написал мне, по сути, следующее: Я думаю, что быстрый классический алгоритм существует», — сказал Ааронсон.
Всю весну Тан записывал результаты и работал с Ааронсоном над прояснением некоторых шагов доказательства. Обнаруженный Таном быстрый классический алгоритм был вдохновлён быстрым квантовым алгоритмом, найденным Керенидисом и Пракашем за два года до этого. Тан продемонстрировал, что квантовую выборку, использованную в их алгоритме, можно воспроизвести в классических условиях. Алгоритм Тана, как и алгоритм Керенидиса и Пракаша, исполнялся за полилогарифмическое время – то есть, время вычислений оценивалось логарифмом от таких параметров, как количество пользователей и продуктов – и был экспоненциально быстрее любого другого из известных ранее классических алгоритмов.
После завершения Таном алгоритма, Ааронсон хотел удостовериться в его правильности перед публикацией. «Я всё ещё нервничал по поводу того, что если после публикации Таном работы она окажется неверной, то первая большая работа в карьере Тана окажется пшиком», — сказал Ааронсон.
Ааронсон планировал посетить рабочую встречу по квантовым вычислениям в Калифорнийском университете в Беркли в июне. Там должны были собраться светила этой области, включая и Керенидиса с Пракашем. Ааронсон пригласил Тана с собой в Беркли для того, чтобы неформально представить его алгоритм после официальной части конференции.
Утром 18 и утром 19 июня Тан прочёл две лекции, отвечая на вопросы аудитории. По истечению четырёх часов был выработан консенсус: классический алгоритм Тана похож на правильный. Чего многие присутствующие не поняли, так это того, насколько Тан был юным. «Я не знал, что Ювину 18 лет, и определённо мне так не показалось по результатам разговоров. Мне казалось, что Ювин ведёт беседу как вполне взрослый человек», — сказал Керенидис. Теперь алгоритму предстоит формальная экспертная оценка перед тем, как его опубликуют.
Для квантовых вычислений результат Тана служит шагом назад. Или нет. Тан устранил один из самых понятных и лучших примеров квантового преимущества. В то же время, работа Тана является ещё одним свидетельством наличия плодотворного взаимодействия исследований классических и квантовых алгоритмов.
«Тан устраняет квантовое ускорение Керенидиса и Пракаша, но в другом смысле Тан способствует большим улучшением и основывается на их работе. Тан никогда бы не придумал свой классический алгоритм, если бы они не опубликовали свой квантовый», — сказал Ааронсон.
Комментарии (61)
anonymous
15.08.2018 11:27Теперь компьютеры как люди в свое время перейдут на расчеты логарифмами для уменьшения объема вычислений, то есть алгоритмом будет решать вопрос несовершенства железа, это никак не остановит развитие квантовых компьютеров.
roscomtheend
16.08.2018 12:06На расчёты за что они перейдут логарифмами? За электроэнергию? Вы не спутали O большое с самими алгоритмами? (далеко не всё можно упростить по аналогии с рекомендациями).
vitaliy2
17.08.2018 01:46Автор имел ввиду, что вместо того, чтобы компьютеры работали невероятно быстрее, программисты вынуждены писать быстрые алгоритмы. Вот только он не учёл, что для квантового алгоритмы ещё сложнее =)? Да и применимы только к некоторым задачам.
А по факту автор не прав, т.?к. прогресс можно достигать двумя путями — улучшая железо и улучшая алгоритмы. Правда во втором случае это нужно делать много раз, но важно совмещать оба пути.vitaliy2
17.08.2018 02:02*важно совмещать оба пути, т.?к. первый путь тоже непростой, и тоже требует алгоритмов. А по факту так, как подсказывает рыночная ситуация. Если дешевле сделать железку, можно взять и более медленный алгоритм, а деньги потратить на железку. Но, думаю, сделать алгоритм проще, чем сделать фантастическую железку.
Если производство железки позволит сэкономить на производстве алгоритмов, то можно делать железку (если она вообще возможна), и тогда она сама себя окупит. Но пока железку никто не делает, мы либо пишем алгоритмы, либо платим за железо (но чаще всего железо не спасёт).
stalinets
15.08.2018 11:36Для сервисов рекомендаций можно было бы сделать по-другому. Просто попросить пользователей-старожилов после просмотра фильма перечислить, какие бы фильмы, на их взгляд, стоило бы посмотреть другим людям, которым этот фильм понравится. За это предложить им какой-нибудь маленький бонус. Всё!
knstqq
15.08.2018 12:00не всё так просто. Это очень много данных, которые нужно обрабатывать правильно
Hardcoin
15.08.2018 12:48+1Да, можно и так решать. Более того, таких рекомендаций от старожилов сколько угодно. Просто это решение менее качественное, оно не учитывает специфичные интересы. Старожил предложит похожий фильм по смыслу, например, а посетителю интересен какой-то герой второго плана.
Welran
15.08.2018 13:07Ага и тысяча старожилов порекомендуют пятьсот разных фильмов :) большая часть из которых пользователю даже не интересна. А надо оценить выборку что понравилось пользователю и на чью выборку из старожилов она похожа, и рекомендовать не просмотренные фильмы из этой выборки. Вот эту задачу и ускорил Тан.
ariklus
15.08.2018 18:04Так давно на том же MAL например это реализовано.
ValdikSS
16.08.2018 20:10И имеем такое:
adictive_max
17.08.2018 04:58Ну в общем-то логично. Если у вас настолько низкие запросы, что вам понравилось «Боку но Пико», то вам зайдёт вообще что угодно.
maxzhurkin
16.08.2018 18:59Дайте угадаю, вы уже прошли тот самый опрос, за который обещают несколько десятков тысяч ? в русскоязычном спаме?
bro-dev0
17.08.2018 20:53А почему мнение старожил весомее новичков? Мой имхо, но когда посмотрел кучу фильмов, вкус уже сильно отличается от новичков, и советовать им эффективно уже не получится, тут наоборот новички должны советовать новичкам.
Zettabyte
15.08.2018 12:47+1Подросток из Техаса
Ювин Тан
Шутка про то, что его система рекомендаций использует не столь удачливых соотечественников, оставшихся на родине и рекомендующих тысячу фильмов за два доллара, уже была?denisromanenko
15.08.2018 19:31+6Если бы мне давали пенни и спрашивали, какой фильм стоит посмотреть — разве это не удача?
В обычной жизни и бесплатно никому не навяжешь...
WinPooh73
15.08.2018 13:43+1Что-то сразу вспомнился 15-летний подросток-вундеркинд из «Теории Большого Взрыва» (S01E12).
OnelaW
15.08.2018 15:59+1Научрук, молодец. Не всем менторам дано предвидеть способности учеников.
maxzhurkin
16.08.2018 19:05Предвидеть или всего лишь (да, я понимаю, чего стоит это «всего лишь») видеть?
OnelaW
16.08.2018 19:29Извините, под вечер сломался интерпретатор. я пытаюсь осмыслить и корректно ответить, не получается.
isam_os
15.08.2018 19:18-1Я начал верить в существование классического алгоритма
попахивает… не очень…Hardcoin
15.08.2018 20:11+3Какая разница, как это "попахивает", если в итоге он выдал строгое доказательство? Он же верил, что его можно найти и искал, а не говорил "я верю и этого достаточно, вам тоже нужно просто верить".
IvanTamerlan
15.08.2018 21:06+2для того, чтобы что-то открыть, нужно верить, что это что-то можно открыть.
Неверящий сделает мало или ни одной попытки
Верящий — сделает очень много попыток, зависит от фанатизма и веры. Фанатик будет долбится об один и тот же метод, даже если он неверен, творческий человек придумает, в том числе, другие методы, креативный человек один метод по-разному приспособит, специалист по продажам или проповедник заставит верить других людей, чтобы они делали попытки.
И т.д.BD9
16.08.2018 10:12Чем отличается творческий человек от креативного?
IvanTamerlan
16.08.2018 10:44Мороженное в вафельном стаканчике разрезать по диагонали — креативно, но никакого особого творчества, зато дизайн, наценка и продажи.
Изобрести лекарство от рака — творческая задача, но не креативная.
Словарь Ожегова-Шведовой определяет творчество как «создание новых по замыслу культурных или материальных ценностей». В этом определении объединены как духовные, моральные, высокие, так и материальные, бытовые ценности.
Творчество создает, а креатив — продает.
Но некоторые считают, что креатив больше значит, чем творчество. В современном мире, где деньги правят балом — умение продать ценится выше умения создать.
Chupaka
16.08.2018 13:52Generation „П“:
— Пойдёшь ко мне в штат?
Татарский ещё раз посмотрел на плакат с тремя пальмами и англоязычным обещанием вечных метаморфоз.
— Кем? — спросил он.
— Криэйтором.
— Это творцом? — переспросил Татарский. — Если перевести?
Ханин мягко улыбнулся.
— Творцы нам тут на хуй не нужны, — сказал он. — Криэйтором, Вава, криэйтором.
AxeFizik
15.08.2018 23:13+1Это типичная проблема перевода с английского, в котором слово «believe» переводится не только как «верить», но и как «пологать» или «считать».
Igor_O
16.08.2018 14:44Это типичная проблема перевода с английского, что значение перевода из словаря — можно выкинуть и забыть. Believe — это очень много всего. Во всех случаях, полагаете вы, или считаете — если вы believe, это значит, что у вас нет подтверждений или доказательств, но вы не знаете ни опровержений, ни доказательств обратного. Очень мощный юридическо-лингвистический казус. Когда вроде бы вы что-то обещаете, но не несете никакой ответственности, если ваши обещания не будут выполнены.
Arris
16.08.2018 19:22Попахивает верой?
Ну, это не самый плохой запах, потому что за верой лежит интуиция. Если вы не верите в свою интуицию — ну, беда…
Интуиция помогла найти ответ, а вера в свои силы помогла его искать.
Все еще плохо пахнет?
NB! Я написал вера, а не религия.
geisha
15.08.2018 22:26+5В статье ни слова о задаче, поэтому просто оставлю это здесь.
Постановка задачиИдея состоит в том, чтобы (к примеру) описать понравившиеся фильмы некоей матрицей A[i,j], где i-фильмы, j-люди. (К примеру,) можно считать, что A — оценки, выставленные пользователем j фильму i. Всех значений матрицы мы не знаем, но хотели бы угадать.
Мы предполагаем, что матрица A — низкого ранга. По-человечески, это означает, что все строки матрицы A[:,j] (что есть оценки человека j выставленные всем существующим фильмам) являются линейной комбинацией небольшого набора «фенотипов», A[:, j] = a1 * v1 + a2 * v2 +… + aN * vN, где «a» — какие-то коэффициенты, а «v» — вектора, характеризующие «типичного любителя блокбастеров», «типичного любителя комедий» и т. п. Ключевое предположение — что N много меньше и фильмов и людей, а каждый анонимус выставляет уникальный, но типичный и предсказуемый набор оценок.
Под решением задачи понимается нахождение «a» и «v». Это можно сделать классически за линейное время O(Ni, Nj) и квантово — за логарифмическое O(log(Ni), log(Nj)). Очевидно, нахождение всех элементов матрицы A возможно не меньше, чем за линейное время, но, похоже, это не требуется по условиям задачи. Чтобы рекомендовать конкретный фильм конкретному пользователю, будут использоваться какие-то другие приближения.ToSHiC
15.08.2018 23:28Конечно можно посмеяться, только потом надо вспомнить, что количество фильмов порядка десятков тысяч, а количество активных пользователей того же нетфликса больше ста миллионов.
geisha
15.08.2018 23:59+1Сто миллионов это жалкие 1e8. Да и дело не в этом, просто при добавлении ещё ста миллионов пользователей в рамках этой задачи нужно, всего лишь, удвоить вычислительные мощности, что вполне реально. Если же вы удвоите показатель степени и получите 1e16, то ваши проблемы окажутся совсем другого характера.
Welran
16.08.2018 06:41+1Это какие же экспоненциальные задачи нам хочется решить :)? Просто в статье утверждается что задач имеющих практическое значение, для которых существуют квантовые алгоритмы быстрее чем классические, не так уж и много. Было бы интересно узнать, какие задачи имеют быстрое квантовое решение и нужны в жизни (не синтетические задачи).
geisha
16.08.2018 09:23Берёте комбинаторику и находите на свой вкус: задача коммивояжера, задача сравнения графов (хотя, вроде, появилось доказательство существования полиномиального алгоритма). В науке вся численная квантовая химия, численная квантовая физика, все эти сворачивания белков. Алгоритм Шора и все эти простые числа. Отсутствие квантового превосходства доказано в считанных случаях, все остальные ждут своего квантового симулятора.
А то, что пишется во введении — это личное мнение автора, так к этому и относитесь.
nurik_6
15.08.2018 23:12Мне вот интересно, а какие задачи ему еще предложили решить? Мне кажется что, этот паренёк просто благодаря своему таланту и гибкости ума, решил бы любую задачу, просто выразив сомнение в истинности постулатов.
G0rDi
15.08.2018 23:21На мой взгляд предложенный алгоритм решает задачу так скажем не точно,
– и обработать существующие данные так, чтобы выдать рекомендацию, которая просто была бы достаточно неплохой.
а квантовый подход к решению данной задачи вернёт наилучшую рекомендацию из возможных.avost
16.08.2018 13:09а квантовый подход к решению данной задачи вернёт наилучшую рекомендацию из возможных
Так нет же! Именно квантовый алгоритм, на основании которого проводилась работа, расчитан на нахождение не наилучшего решения, а "достаточно неплохого" и именно поэтому квантовый алгорим теоретически был экспоненциально быстрее. Об этом прямо в статье так и написано.
Sabubu
16.08.2018 00:08+2Я по заголовку подумал, что этот подросток сломал квантовый компьютер или сорвал эксперимент, а оказалось, он научную работу написал. Молодец.
adson
16.08.2018 06:52Пардон, конечно, но до какого возраста он будет подростком? Учитывая, что он к этому времени уже закончил университет…
vbifkol
16.08.2018 07:09teenager же. До 20 по определению. Только я бы тинейджера как подростка не перевел, для нашего понимания (12-16 лет) есть adolescent или juvenile
adson
16.08.2018 07:14Извините за занудство, где такое определение? В 14 лет паспорт получить можно, уголовная ответственность уже светит, в 18 — совершеннолетие. Как можно быть одновременно и подростком, и совершеннолетним?
AlexSpirit
16.08.2018 07:39+1В большинстве штатов Cша совершеннолетие наступает в 18 лет, но в Алабаме, Вайоминге и Небраске – в 19, в Миссисипи и штате Нью-Йорк – в 21
maxzhurkin
16.08.2018 19:17Но многим совершеннолетним нельзя алкоголь (крепкий или некрепкий, не знаю, но крепкий точно нельзя до 21-го, как я понимаю)?
vbifkol
16.08.2018 07:49определение в Webster
Получить паспорт можно и в полтора года (загранпаспорт вроде с года дают), ни к подростковости, ни к тинейджерству, ни к совершеннолетию это отношения не имеет. Уголовная ответственность — тем более.
Подростком и совершеннолетним быть, наверное, нельзя (хотя подросток не имеет точного возрастного определения, это во многом культурально-обусловленное понятие). Тинейджером и совершеннолетним — почему нет?
yea
16.08.2018 11:49Тинейджер — teenager. Человек, возраст которого заканчивается на '-teen'. Это прямо в этом слове вот прямо так и написано, даже определения дополнительного не нужно.
apapacy
16.08.2018 13:41Ближе всего по сути юноша см. ru.m.wiktionary.org/wiki/юноша
Хотя так редко говорят разве что по приколу.
Юноша бледный со взором горящим
Ныне тебе я даю три совета…
Jecky
16.08.2018 14:30Да, -teen в age есть только с 13 по 19, потому для неанглоязычных не всегда понятно. Но в US это важный рубеж, можно увидеть, например, в мультике Гравити Фолз.
APXEOLOG
Я думаю развитие квантовых компьютеров это не остановит, а вот рекомендации станут лучше гораздо быстрее. Все в выигрыше!
maxbrown
У рекомендательных сервисов кроме проблемы вычисления рекомендаций есть ещё проблема накрутки. Она катастрофична для сервисов с открытыми рекомендациями (зная все рекомендации некоего заданного пользователя, бот-злоумышленник выставляет в точности такие же плюс рекомендацию рекламируемого предложения), но считалось, что при закрытых оценках такой проблемы нет. Зондирование же рекомендательных сервисов в поисках крупных групп единомышленников и их предпочтений раньше было ограничено вычислительной сложностью задачи.
Если теперь, благодаря Тану, эта сложность уменьшится, то как бы это не стало концом самой идеи рекомендательных сервисов. Заспамят же.