Квантовые технологии
Математика
Комментарии 77
+13

Я думаю развитие квантовых компьютеров это не остановит, а вот рекомендации станут лучше гораздо быстрее. Все в выигрыше!

0
У рекомендательных сервисов кроме проблемы вычисления рекомендаций есть ещё проблема накрутки. Она катастрофична для сервисов с открытыми рекомендациями (зная все рекомендации некоего заданного пользователя, бот-злоумышленник выставляет в точности такие же плюс рекомендацию рекламируемого предложения), но считалось, что при закрытых оценках такой проблемы нет. Зондирование же рекомендательных сервисов в поисках крупных групп единомышленников и их предпочтений раньше было ограничено вычислительной сложностью задачи.
Если теперь, благодаря Тану, эта сложность уменьшится, то как бы это не стало концом самой идеи рекомендательных сервисов. Заспамят же.
-31
Теперь компьютеры как люди в свое время перейдут на расчеты логарифмами для уменьшения объема вычислений, то есть алгоритмом будет решать вопрос несовершенства железа, это никак не остановит развитие квантовых компьютеров.
0
На расчёты за что они перейдут логарифмами? За электроэнергию? Вы не спутали O большое с самими алгоритмами? (далеко не всё можно упростить по аналогии с рекомендациями).
0
Автор имел ввиду, что вместо того, чтобы компьютеры работали невероятно быстрее, программисты вынуждены писать быстрые алгоритмы. Вот только он не учёл, что для квантового алгоритмы ещё сложнее =)  Да и применимы только к некоторым задачам.

А по факту автор не прав, т. к. прогресс можно достигать двумя путями — улучшая железо и улучшая алгоритмы. Правда во втором случае это нужно делать много раз, но важно совмещать оба пути.
0
*важно совмещать оба пути, т. к. первый путь тоже непростой, и тоже требует алгоритмов. А по факту так, как подсказывает рыночная ситуация. Если дешевле сделать железку, можно взять и более медленный алгоритм, а деньги потратить на железку. Но, думаю, сделать алгоритм проще, чем сделать фантастическую железку.

Если производство железки позволит сэкономить на производстве алгоритмов, то можно делать железку (если она вообще возможна), и тогда она сама себя окупит. Но пока железку никто не делает, мы либо пишем алгоритмы, либо платим за железо (но чаще всего железо не спасёт).
-8
Для сервисов рекомендаций можно было бы сделать по-другому. Просто попросить пользователей-старожилов после просмотра фильма перечислить, какие бы фильмы, на их взгляд, стоило бы посмотреть другим людям, которым этот фильм понравится. За это предложить им какой-нибудь маленький бонус. Всё!
+1
не всё так просто. Это очень много данных, которые нужно обрабатывать правильно
+6

Да, можно и так решать. Более того, таких рекомендаций от старожилов сколько угодно. Просто это решение менее качественное, оно не учитывает специфичные интересы. Старожил предложит похожий фильм по смыслу, например, а посетителю интересен какой-то герой второго плана.

-1
Потому что проблема что старожилов, что алгоритма вместо них, в том, что анализируется выборка по критериям, заранее определённым кем-то другим, но не самим пользователем, которому собираются рекомендовать фильм. Вот и получается, что ему подбирают блокбастер/не блокбастер, а он лишь хотел увидеть конкретного эпизодического актёра.
+1

У алгоритма нет такой проблемы. Во всяком случае не у любого.

0

Если пользователь знает что именно он хочет — он идет и пользуется поиском. Рекомендации нужны для случая когда не знаешь точно что нужно, либо когда активно не ищешь вообще. И в таких случаях нет проблемы "пользователь хотел эпизодического актера". А в случае когда человек фанатеет от конкретного актера, то это как раз алгоритм может выяснить если у него будет достаточно данных.

0
Подобных ошибок можно избежать, если фильм довольно популярный. Но фильм, от которого я помню маленький отрывок, я так и не нашёл.
+2
Ага и тысяча старожилов порекомендуют пятьсот разных фильмов :) большая часть из которых пользователю даже не интересна. А надо оценить выборку что понравилось пользователю и на чью выборку из старожилов она похожа, и рекомендовать не просмотренные фильмы из этой выборки. Вот эту задачу и ускорил Тан.
0
Ну в общем-то логично. Если у вас настолько низкие запросы, что вам понравилось «Боку но Пико», то вам зайдёт вообще что угодно.
0
Дайте угадаю, вы уже прошли тот самый опрос, за который обещают несколько десятков тысяч ₽ в русскоязычном спаме?
0
А почему мнение старожил весомее новичков? Мой имхо, но когда посмотрел кучу фильмов, вкус уже сильно отличается от новичков, и советовать им эффективно уже не получится, тут наоборот новички должны советовать новичкам.
0
Задача сервиса — втягивать пользователей в некую деятельность и показывать им рекламу. А вы всё разрушаете… айяйяй…
+9
Подросток из Техаса
Ювин Тан
Шутка про то, что его система рекомендаций использует не столь удачливых соотечественников, оставшихся на родине и рекомендующих тысячу фильмов за два доллара, уже была?
+7
отдает расизмом
Широко известный факт в сфере компьютерной техники:
Computers are racist / компьютеры - расисты
+6

Если бы мне давали пенни и спрашивали, какой фильм стоит посмотреть — разве это не удача?


В обычной жизни и бесплатно никому не навяжешь...

+2
Что-то сразу вспомнился 15-летний подросток-вундеркинд из «Теории Большого Взрыва» (S01E12).
0
Посмотрите детство Шелдона и впадете в депрессию. В детстве был гениальным, а вырос обычным кандидатом наук, таким же каких тысячи.
+15
Научрук, молодец. Не всем менторам дано предвидеть способности учеников.
0
Предвидеть или всего лишь (да, я понимаю, чего стоит это «всего лишь») видеть?
0
Извините, под вечер сломался интерпретатор. я пытаюсь осмыслить и корректно ответить, не получается.
-2
Я начал верить в существование классического алгоритма


попахивает… не очень…
+5

Какая разница, как это "попахивает", если в итоге он выдал строгое доказательство? Он же верил, что его можно найти и искал, а не говорил "я верю и этого достаточно, вам тоже нужно просто верить".

+3
для того, чтобы что-то открыть, нужно верить, что это что-то можно открыть.
Неверящий сделает мало или ни одной попытки
Верящий — сделает очень много попыток, зависит от фанатизма и веры. Фанатик будет долбится об один и тот же метод, даже если он неверен, творческий человек придумает, в том числе, другие методы, креативный человек один метод по-разному приспособит, специалист по продажам или проповедник заставит верить других людей, чтобы они делали попытки.
И т.д.
0
Чем отличается творческий человек от креативного?
+1
Мороженное в вафельном стаканчике разрезать по диагонали — креативно, но никакого особого творчества, зато дизайн, наценка и продажи.
Изобрести лекарство от рака — творческая задача, но не креативная.

Словарь Ожегова-Шведовой определяет творчество как «создание новых по замыслу культурных или материальных ценностей». В этом определении объединены как духовные, моральные, высокие, так и материальные, бытовые ценности.

Творчество создает, а креатив — продает.
Но некоторые считают, что креатив больше значит, чем творчество. В современном мире, где деньги правят балом — умение продать ценится выше умения создать.
+1
Generation „П“:
— Пойдёшь ко мне в штат?
Татарский ещё раз посмотрел на плакат с тремя пальмами и англоязычным обещанием вечных метаморфоз.
— Кем? — спросил он.
— Криэйтором.
— Это творцом? — переспросил Татарский. — Если перевести?
Ханин мягко улыбнулся.
— Творцы нам тут на хуй не нужны, — сказал он. — Криэйтором, Вава, криэйтором.
+7
Это типичная проблема перевода с английского, в котором слово «believe» переводится не только как «верить», но и как «пологать» или «считать».
0
Это типичная проблема перевода с английского, что значение перевода из словаря — можно выкинуть и забыть. Believe — это очень много всего. Во всех случаях, полагаете вы, или считаете — если вы believe, это значит, что у вас нет подтверждений или доказательств, но вы не знаете ни опровержений, ни доказательств обратного. Очень мощный юридическо-лингвистический казус. Когда вроде бы вы что-то обещаете, но не несете никакой ответственности, если ваши обещания не будут выполнены.
0
Igor_O, т.о. если это слово не подразумевает мыслительный процесс, то только «верить»? Ведь слово «доверять» в английском имеет свой собственный корень.
0
Попахивает верой?
Ну, это не самый плохой запах, потому что за верой лежит интуиция. Если вы не верите в свою интуицию — ну, беда…

Интуиция помогла найти ответ, а вера в свои силы помогла его искать.

Все еще плохо пахнет?

NB! Я написал вера, а не религия.
+8
В статье ни слова о задаче, поэтому просто оставлю это здесь.
Постановка задачи
Идея состоит в том, чтобы (к примеру) описать понравившиеся фильмы некоей матрицей 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 возможно не меньше, чем за линейное время, но, похоже, это не требуется по условиям задачи. Чтобы рекомендовать конкретный фильм конкретному пользователю, будут использоваться какие-то другие приближения.

ИМХО многие специалисты из самых разных областей посмеются этой возне с линейной-логарифмической сложностью, поскольку большая часть задач, которые нам хочется решить, имеют экспоненциальную сложность.
+1
Конечно можно посмеяться, только потом надо вспомнить, что количество фильмов порядка десятков тысяч, а количество активных пользователей того же нетфликса больше ста миллионов.
+1
Сто миллионов это жалкие 1e8. Да и дело не в этом, просто при добавлении ещё ста миллионов пользователей в рамках этой задачи нужно, всего лишь, удвоить вычислительные мощности, что вполне реально. Если же вы удвоите показатель степени и получите 1e16, то ваши проблемы окажутся совсем другого характера.
+1
Это какие же экспоненциальные задачи нам хочется решить :)? Просто в статье утверждается что задач имеющих практическое значение, для которых существуют квантовые алгоритмы быстрее чем классические, не так уж и много. Было бы интересно узнать, какие задачи имеют быстрое квантовое решение и нужны в жизни (не синтетические задачи).
+1
Берёте комбинаторику и находите на свой вкус: задача коммивояжера, задача сравнения графов (хотя, вроде, появилось доказательство существования полиномиального алгоритма). В науке вся численная квантовая химия, численная квантовая физика, все эти сворачивания белков. Алгоритм Шора и все эти простые числа. Отсутствие квантового превосходства доказано в считанных случаях, все остальные ждут своего квантового симулятора.

А то, что пишется во введении — это личное мнение автора, так к этому и относитесь.
0
Мне вот интересно, а какие задачи ему еще предложили решить? Мне кажется что, этот паренёк просто благодаря своему таланту и гибкости ума, решил бы любую задачу, просто выразив сомнение в истинности постулатов.
0
Это не самая интересная проблема в программировании. ;-)
-1
На мой взгляд предложенный алгоритм решает задачу так скажем не точно,
– и обработать существующие данные так, чтобы выдать рекомендацию, которая просто была бы достаточно неплохой.

а квантовый подход к решению данной задачи вернёт наилучшую рекомендацию из возможных.
0
а квантовый подход к решению данной задачи вернёт наилучшую рекомендацию из возможных

Так нет же! Именно квантовый алгоритм, на основании которого проводилась работа, расчитан на нахождение не наилучшего решения, а "достаточно неплохого" и именно поэтому квантовый алгорим теоретически был экспоненциально быстрее. Об этом прямо в статье так и написано.

0

Процитированное вами упрощение алгоритма было сделано как раз в квантовой версии. Насколько я понял, версия Тана не уступает по качеству рекомендаций

+5
Я по заголовку подумал, что этот подросток сломал квантовый компьютер или сорвал эксперимент, а оказалось, он научную работу написал. Молодец.
0
Пардон, конечно, но до какого возраста он будет подростком? Учитывая, что он к этому времени уже закончил университет…
0
teenager же. До 20 по определению. Только я бы тинейджера как подростка не перевел, для нашего понимания (12-16 лет) есть adolescent или juvenile
-1
Извините за занудство, где такое определение? В 14 лет паспорт получить можно, уголовная ответственность уже светит, в 18 — совершеннолетие. Как можно быть одновременно и подростком, и совершеннолетним?
+2
В большинстве штатов Cша совершеннолетие наступает в 18 лет, но в Алабаме, Вайоминге и Небраске – в 19, в Миссисипи и штате Нью-Йорк – в 21
0
Но многим совершеннолетним нельзя алкоголь (крепкий или некрепкий, не знаю, но крепкий точно нельзя до 21-го, как я понимаю)?
0
определение в Webster
Получить паспорт можно и в полтора года (загранпаспорт вроде с года дают), ни к подростковости, ни к тинейджерству, ни к совершеннолетию это отношения не имеет. Уголовная ответственность — тем более.
Подростком и совершеннолетним быть, наверное, нельзя (хотя подросток не имеет точного возрастного определения, это во многом культурально-обусловленное понятие). Тинейджером и совершеннолетним — почему нет?
0

JFI: Загранпаспорт сразу после свидетельства о рождении можно получить

+1
Тинейджер — teenager. Человек, возраст которого заканчивается на '-teen'. Это прямо в этом слове вот прямо так и написано, даже определения дополнительного не нужно.
0
Ближе всего по сути юноша см. ru.m.wiktionary.org/wiki/юноша
Хотя так редко говорят разве что по приколу.
Юноша бледный со взором горящим
Ныне тебе я даю три совета…
0
Да, -teen в age есть только с 13 по 19, потому для неанглоязычных не всегда понятно. Но в US это важный рубеж, можно увидеть, например, в мультике Гравити Фолз.
0
> Извините за занудство, где такое определение?
teenager
13 — thirteen

19 — nineteen
20 — twelve
0

Все это очень сильно похоже на обычный метод ближайших соседей (nearest neighbors, https://en.m.wikipedia.org/wiki/Nearest_neighbor_search). Есть алгоритмы, которые обеспечивают точный поиск ближайших соседей, но это очень ресурсоемко. А есть алгоритмы приближенного поиска, время работы которых как раз логарифмически зависит от количества входных данных. Но и результат получается не точный, а приближенный. Есть куча фреймворков, которые давно уже умеют это делать.

0
Ясно, что перевод, но все же заголовок желтоват. Существование быстрого классического алгоритма не опровергает более раннюю работу Керенидиса и Пракаша, а скорее дополняет ее. Если бы «подросток» Тан нашел там ошибки или сорвал какой-нибудь эксперимент — другое дело.
0
А ссылка на статью, пример кода\псевдокода есть? Интересно посмотреть, что за алгоритм.
0
Как же надоели эти рекомендации. Стоит послушать несколько песен и поставить несколько оценок, как сервис начинает тебя одолевать своими «рекомендациями».
0
… и нафига ломать голову придумывая алгоритмы, занимаясь оптимизацией… А давайте будем строить квантовый процессор, а все имеющиеся не-квантовые процессоры просто объявим слишком маломощными для наших задач. И можно с умным видом надувать щеки, и вещать что мы супер умные и все пишем правильно, вот когда появится квантовый процессор, то это сразу станет понятно. А пока жрите что дают…
0
Дальше выпустят программы, которые даже 2+2 без квантового процессора складывать не умеют и обязательно будут требовать квантовый процессор именно последней, а не предпоследней модели. И помимо обновления ПО придется обновлять и железо.
Позже одни компании только на суде признаются, что они намеренно замедляли квантовые процессоры до уровня калькуляторов; другие компании будут запрещать публиковать результаты бенчмарков; третьи будут искать и таки находить критичные уязвимости, когда квантовые процессоры могут получить «случайное квантовое запутывание» во время производства или во время транспортировки, причем это будет работать как квантовая связь с третьими лицами без возможности засечь и все данные будут оказываться у АНБ злоумышленников практически мгновенно, а заплатки не смогут избавить от утечек, только замедлить квантовую связь на порядок и злоумышленник получит данные не через секунде, а через 10 секунд, но заплатки будут вызвать 90%-падение производительности.
Игроделы также не будут отставать — полностью забьют на оптимизацию и будут выпускать игры с 16М-текстурами даже иконок, которые еле заметны на самых лучших мониторах 32к! Если пользователей игра будет лагать и жутко тормозить — попросят приобрести более новое железо.
Короче, процветание индустрии. И где-то я это уже видел…
Только полноправные пользователи могут оставлять комментарии. , пожалуйста.