Информация

Дата основания
Местоположение
Россия
Сайт
www.dentsu.com
Численность
1 001–5 000 человек
Дата регистрации

Блог на Хабре

Обновить

Сократить время вычислений от нескольких лет до минут. Разбираемся с квантовым машинным обучением

Блог компании dentsu russiaМатематикаМашинное обучениеКвантовые технологии
Recovery mode
Рейтинг +14
Количество просмотров 8,3k Добавить в закладки 63 Читать комментарии 48
Комментарии 48
К примеру, если для 1024 потоков в обычном компьютере потребуется такое же количество логических процессоров, то в квантовом — всего 10.

Не понятно, поясните, пожалуйста!
Если взять 10 кубитов, то число возможных состояний будет равно 2^10. Для каждого из них можно проводить вычисления.

Сравнение некорректное. На обычном компьютере можно будет запустить 1024 разные задачи параллельно.
На квантовом — одну задачу, но с 1024 разными входами. При этом КК сможет вернуть результат только 10 успешно завершенных задач.

Не все результаты вычисления нужно выводить. Например, нейронная сеть может иметь миллионы весов в своих внутренних вычислениях, но на выходе нужны только несколько цифр — либо классы, либо результат задачи регрессии.
Имхо, подмена понятий бита и логического процессора

Начиная с определенного количества кубитов уже можно сравнивать с процессорами. Например, в 64-кубитной системе возможны вычисления с большим количеством потоков, чем на 64 логических процессорах, причем на несколько порядков.

Строго говоря, нет там никаких потоков. Исходное квантовое состояние трансформируется таким образом, чтобы амплитуда правильных ответов была максимальной. Далеко не все задачи могут быть ускорены преобразованием к такому виду.

Да, скорее речь идёт о квантовом параллелизме.

Если в нашем распоряжении есть 66 кубитов, то переведя их в суперпозицию, можно закодировать более триллиона цветных изображений в формате 4K.

Можно закодировать, но извлечь нельзя. Теорема Холево: максимальный объем информации, который можно извлечь из системы n кубитов — n бит.

Здесь имеется в виду, что изображения кодируются не для извлечения, а для подачи на вход нейросети, а она также находится в системе кубитов. Требуется извлечь небольшое количество информации — например, класс изображения. Если класса два, то для одного изображения потребуется один бит.
К квантовому машинному обучению есть один глобальный вопрос. Имеется «узкое горлышко». Если у вас есть исходно классические данные (а так почти всегда и есть), то вам придется сначала перегнать их в соответствующее квантовое состояние контролируемым образом (например, создав требуемые амплитуды вероятностей). Для этого потребуется применение огромного числа квантовых операций, и выигрыш от ускоренной обработки уже квантовых данных квантовым компьютером, а также от возможности сохранить огромный объем информации в небольшом числе кубитов, могут запросто быть съедены проигрышем на стадии приготовления. Это даже для идеального квантового компьютера.

Вот если данные исходно были квантовыми, тогда другое дело. Такие данные может генерировать, например, квантовый сенсор, а их ведь надо обрабатывать. Однако квантовая сенсорика находится в зачаточном состоянии.

Еще один возможный выход — квантовые устройства не алгоритмического, а скорее аналогового характера.

По поводу кодирования информации есть разные подходы: Сет Ллойд говорит о кодировании посредством амплитуд или вероятностей, Скотт Ааронсон пишет про использование квантового оракула. Я думаю, это будет постепенно развиваться. А что вы имеете в виду под квантовыми устройствами аналогового характера?

Я думаю, можно в качестве аналоговых устройств предложить такие фото-матрицы, где можно попавшие фотоны сразу преобразовывать в кубиты без усреднения. Тогда и будет нечто наподобие квантового глаза.

Да, например, что-то такое, что описано выше. Какая-то принимающая квантовая матрица, чувствительная к характеристикам входящих квантовых состояний. С взаимодействием между элементами, составляющими матрицу.
В сентябре 2019 года появилась неофициальная информация о том, что Google достиг квантового превосходства, решив на квантовом компьютере одну из задач со скоростью, недоступной даже для самого мощного суперкомпьютера. Даже если новость преждевременная, такие сообщения говорят о том, что квантовое превосходство уже близко.

Просто для информации, новость таки не преждевременная, статья вышла в Nature вчера. Заодно хороший комментарий тут.
Да, новость действительно прорывная. Интересно будет наблюдать за соперничеством Google и IBM в этой области.
Интересная статья. Я далек от темы. А в интернете противоречивая информация насчет квантовых алгоритмов в машин лернинг. Ааронсон кажется писал, что на данный момент все туманно. Можете вы расскахать подробнее про какие-то простые алгоритмы но полезные, которые сильно ускоряются на квантовых компьютерах? было бы интеренсо.Например, про обратную матрицу. Думаю все знают, что это такое, знают библиотеки и алгоритмы, которые ее считают. А как с квантовым случаем?
Если интересуют квантовые вычисления для машинного обучения, то могу порекомендовать лекцию Сета Ллойда.
Более подробно эта тема разбирается в курсе Университета Торонто Quantum Machine Learning.
Для квантовых вычислений в Python есть библиотеки qiskit и cirq, в качестве бэкенда можно использовать как симулятор, так и реальный квантовый компьютер (в облаке).

Посмотрите две книжки:


  1. Peter Wittek. Quantum Machine Learning
  2. Francesco Petruccione, Maria Schuld, Ilya Sinayskiy. Supervised Learnin with Quantum Computers.

Теоретически достигается ускорение в квантовом SVM, квантовом k-средних. Обычно из квадратичного становится субквадратичным или линейным. Но если данные в квантовом виде, то ускорение может быть экспоненциальным. Можно примеры посмотреть в моей лекции: https://drive.google.com/a/nsu.ru/file/d/1U3qIjO7c6yGOcGpyXytNJjJ7E6yUW8e1/view?usp=drivesdk

Хотелось бы посмотреть лекцию, не откроете доступ по ссылке?
Нужно также понимать, что алгоритмы, которые использует квантовый компьютер, отличаются от алгоритмов, изучаемых в Computer Science. Разумеется, нельзя перенести классический алгоритм в квантовый компьютер, не изменив его предварительно.

Это настолько корявые предложения, что становятся неправдой. Разумеется, CS изучает и квантовые алгоритмы; квантовых алгоритмов нет в типичных универских курсах. И тот же самый CS показывает, что любой классический алгоритм исполняется на квантовых машинах, естественно, при изменении реализации.

Всё-таки отличие большое: в квантовых вычислениях нет циклов. Помимо того, в квантовых вычислениях возможны алгоритмы, аналогов которым нет в классических компьютерах.

Это никак не отменяет факты, о которых я написал: CS по определению изучает все алгоритмы, любой классический алгоритм вычислим на квантовой машине.

Мне кажется, CS в итоге разделится на две ветки: будет классический CS и квантовый.

Помимо того, в квантовых вычислениях возможны алгоритмы, аналогов которым нет в классических компьютерах.

Это не так. Любой квантовый алгоритм может быть симулирован на классических машинах.

Но не все квантовые алгоритмы могут быть выполнены на классическом компьютере за время оставшееся до тепловой смерти вселенной.

Ну, во-первых, это не доказано. Вполне может быть, что классические машины способны решать быстро те же самые задачи, на которых эффективны квантовые машины. Хоть это и маловероятно. Но тем не менее возможно.


А, во-вторых, в том комментарии, что я процитировал ничего не говорилось об эффективном выполнение квантовых алгоритмов на обычных компьютерах. Говорилось, что существуют квантовые алгоритмы, которые обычный компьютер не способен симулировать. Очевидно, что это не так.

Квантовую связь не получится в полной мере симулировать, так как это нелокальное взаимодействие, используется квантовая запутанность (в алгоритме квантовой телепортации). Не получится также полноценно симулировать один из методов оптимизации — квантовый отжиг, так как он работает за счет квантового туннелирования. В этих случаях можно только имитировать квантовые вычисления.

Я не настолько хорошо знаю, что такое квантовая телепортация, чтоб по этому поводу что-то утверждать, но, судя по всему, это никакой не алгоритм, а просто процесс. Поэтому к моему комментарию никакого отношения иметь не должен.


По поводу квантового отжига. Создатель D-Wave сначала эмулировал свою схему квантового отжига в матлабе в системе из 2 (или 2х2?) кубитов, прежде, чем воплощать ее физически. Да и с чего Вы взяли, будто это невозможно? Для каждого текущего состояния перебираете всех соседей, считаете их энергию и дальше "прыгаете" в новое состояние в зависимости от разницы энергий и "толщины" туннеля. Другое дело, что для систем с даже относительно небольшим количеством степеней свободы эта задача становится невыполнимой за разумное время для классических машин. Но тем не менее, в теории это вполне возможно.


Более того, очень просто эмулировать любой квантовый алгоритм на классических машинах, а вот как сделать наоборот — тут я уже не знаю. Это совсем неочевидно, можно ли на квантовых машинах эмулировать классические алгоритмы.

Другое дело, что для систем с даже относительно небольшим количеством степеней свободы эта задача становится невыполнимой за разумное время для классических машин.

Вот это и не было продемонстрировано. Процитирую Скотта Ааронсона: "The skeptics, like me, didn’t much care what speedup over classical benchmarks there was or wasn’t today: we cared about the increase in the speedup as D-Wave upgraded its hardware, and the trouble was that we never saw a convincing case that there would be one."


"Скептиков вроде меня не волнует насколько [D-Wave] обогнал или не обогнал классические компьютеры на текущий момент. Нас интересует во сколько раз D-Wave ускорится после апгрейда своего оборудования. И проблема в том, что не были продемонстрированы убедительные доказательства возможности [экспоненциального] ускорения."

К сожалению, я не совсем понимаю, как Ваш комментарий отвечает или дополняет то, что Вы процитировали у меня.


Я ничего про машину D-Wave не говорил. Я всего-лишь говорил, что систему из 2 кубитов (или все же 4х?) для квантового обжига можно было симулировать на обычном компьютере. И дальше предоставил наивный алгоритм для эмуляции квантового обжига для классической машины. Да, никто в здравом уме не будет запускать этот алгоритм для сколь-нибудь крупных задач, но главное — в теории это можно сделать.


Иначе говоря, аргумент, будто квантовый отжиг нельзя эмулировать на классических машинах — неверен.

Просто уточнил, что D-Wave, по всей видимости, не демонстрирует потенциала для ускорения классических вычислений. Так что о ней можно не упоминать в контексте этого разговора.

Единственная проблема при расчётах квантовых систем — экспоненциальный рост необходимых вычислительных мощностей при увеличении количества взаимодействующих частиц. Расчитать квантовую телепортацию состояния одной частицы не представляет никакой проблемы.

Я ещё забыл упомянуть генерацию случайных чисел. На классическом компьютере это псевдослучайные числа, на квантовом — настоящие случайные числа.

Ох уж этот отдел маркетинга.


Вы вообще в курсе, что квантовые ГСЧ уже лет семь как вышли на рынок, и никакого отношения к квантовым компьютерам не имеют?

Кубит может играть роль генератора случайных чисел. Или вы про что-то другое?

А на суперкомпьютере "Ломоносов" можно играть в тетрис. Но стоит ли?

Справедливости ради, кажется КК — наиболее подходящий источник сертифицированных КСЧ, не требующий нелокальности и прочих ухищрений, собсна тот же Ааронсон об этом пишет.

Это не так. Во-первых, квантовые ГСЧ оптимизированы под стабильность в широком диапазоне внешних условий во избежание атак по сторонним каналам. В КК этого нет, они под гейты заточены.


Во-вторых, КК на рынке пока что нет, а квантовых ГСЧ на первой странице гугла аж четыре штуки, и стоят они всего лишь порядка 2к.

Ну, смотря что не так. В этих ГСЧ с первой странице гугла будет сложно доказать удаленному скептику, что это реально случайные числа. Как сертифицировать их? Там разные есть варианты протоколов, основанные на нелокальности и т.п. КК один из хороших варианатов, где СЧ генерятся доказанно случайными.

Но заметь, я совсем не говорю, что КК — это лучший ГСЧ или самый быстрый, или самый дешевый, или самый компактный, или самый устойчивый к внешним воздействиям. Только одно: сертифицированные СЧ. Так что каждому свой юзкейс, думается. Когда ты в казино делаешь рулетку — тебе достаточно ГСЧ с первой страницы гугла. А если у тебя криптопротокол с удаленными пользователями — там вот может понадобиться КК.

UPD: вот из блога Ааронсона:
As I explicitly said in the post, the whole point of my scheme is to prove to a faraway skeptic—one who doesn’t trust your hardware—that the bits you generated are really random. If you don’t have that requirement, then generating random bits is obviously trivial with existing technology. If you do have the requirement, on the other hand, then you’ll have to do something interesting—and as far as I know, as long as it’s rooted in physics, it will either involve Bell inequality violation or quantum computation.

А, ясно, это хитрые запутывание+сэмплинг с нормализацией. Да, любопытная схема. Топикстартер просто про кубиты говорил, что, очевидно, совсем из другой оперы.

Да, конечно, мне просто эта схема показалась остроумной, и я новообретенным знанием спешу делиться со всеми окружающими:) Тем более, что гугл, кажется, ее будет на своем КК делать в ближайшее время.

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

Этот вопрос (BQP ?= P) из категории P ?= NP. Ещё очень долго может быть непонятно.


А потом всё-таки выяснится, что неравно, скорее всего.

Простите, но статья не имеет никакого отношения к заголовку. У вас здесь куча, кони, люди, тонны маркетинговой воды про "классический ML может работать на квантовом компьютере" и "квантовый компьютер крут на многих задачах, а значит, и в ML", а также мечты о светлом будущем, где не будет ни книг, ни газет, одни сплошные квантовые вычисления. И абсолютно ничего по сути дела.

Статья задумывалась больше как вводная, для подробного описания алгоритмов машинного обучения на квантовом компьютере нужен цикл статей.

А будет цикл статей? Было бы очень интересно! Давно поглядываю на сборник ссылок — там много материала, которого хватило бы на серию статей, но для таких вещей перевода недостаточно: материал приходится пропускать через себя

Да, будет цикл статей, но начну, наверное, с квантовых вычислений, а потом, если получится уложиться в формат статей, продолжу про квантовый ML. Спасибо за ссылку!

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.