Многие слышали о том, что с помощью квантовых компьютеров злоумышленники могут взламывать современные системы шифрования. В отличие от классических компьютеров, для которых RSA и подобные ему криптографические алгоритмы являются хорошим препятствием для взлома, квантовые компьютеры находят простые множители за считанные минуты. Это означает, что перехваченная хакерами информация рано или поздно будет расшифрована.
Безусловно, некоторых такие области применения отпугивают от квантовых компьютеров. В этой статье мы сосредоточимся на позитивной стороне и рассмотрим, что нового квантовые вычисления смогут дать для такой области, как машинное обучение.
Что такое квантовое машинное обучение и в чем его отличие от обычного
В современных компьютерах, в том числе и для целей машинного обучения, вычисления производятся с помощью классических битов. В квантовых же компьютерах, которые в последнее время набирают популярность и активно развиваются, используются биты особого рода — квантовые биты, или сокращенно кубиты.
Для классического бита существуют два состояния — 0 и 1, тогда как для кубита возможно бесконечное количество комбинаций двух состояний — это так называемая суперпозиция. Если кот Шрёдингера из известного мысленного эксперимента до того, как открывают ящик, и жив, и мертв одновременно, то кубит до того, как его измерить, может находиться в суперпозиции, то есть равняться и нулю, и единице в один и тот же момент.
Если же используется несколько кубитов, то количество возможных состояний растет экспоненциально: для двух кубитов, находящихся в суперпозиции, число состояний равно четырем:
А для трех кубитов — уже восемь состояний:
Эти состояния нельзя непосредственно измерить, но ими можно управлять. При этом квантовая схема находится с разной вероятностью в нескольких состояниях одновременно, что можно использовать для параллельных вычислений.
Множители при значениях кубитов называются амплитудами — это комплексные числа. Если вычислить модуль амплитуды и возвести его в квадрат, то получится вероятность состояния. Сумма вероятностей всех комбинаций состояний кубитов, как и следует ожидать, в итоге должна быть равна единице.
В качестве примеров разных состояний кубита можно привести спин электрона либо поляризацию фотона, но также возможны и другие варианты. Главное, чтобы в них также могли наблюдаться квантовые эффекты. Таким образом, кубитом может быть практически любая частица: электрон, фотон, ион и так далее.
Как частица может находиться в двух состояниях одновременно и почему при измерении кубита информация об одном из состояний полностью теряется? Наиболее распространены две интерпретации:
Копенгагенская интерпретация утверждает, что объяснять положение частицы до ее измерения не имеет смысла, так как физика — наука, основанная на точных измерениях, и не должна объяснять те явления, которые нельзя наблюдать. Таким образом, если принимать Копенгагенскую интерпретацию, можно сделать вывод об отсутствии объективной реальности на физическом микроуровне.
Часть ученых придерживается многомировой интерпретации, согласно которой существует бесконечное множество параллельных вселенных, причем в какой-то доле этих вселенных частица может принимает нулевое состояние, а в остальных — единичное. Наиболее подробное описание и философское обоснование многомировой интерпретации можно найти в книге Дэвида Дойча “Структура реальности”.
В любом случае независимо от того, какая из этих интерпретаций вам больше нравится, можно считать, что при измерении кубита происходит коллапс волновой функции (то есть он перестает вести себя как волна и проявляет свойства частицы), при этом кубит принимает одно из состояний, то есть фактически становится классическим битом.
В общем, классические биты — это подмножество кубитов, так что классический Computer Science можно было бы считать подмножеством науки о квантовых вычислениях. Как говорилось выше, любой кубит после измерения становится классическим битом, который, тем не менее, в дальнейшем можно перевести в состояние суперпозиции.
Для того, чтобы все-таки получить хоть какую-то информацию о суперпозиции кубита, можно применить довольно простой лайфхак: много раз создавать одну и туже суперпозицию (действовать на кубит одними и теми же операторами) и каждый раз измерять кубит. Из полученного при измерениях распределения нулей и единиц можно получить представление о вероятностях, то есть узнать, чему могут быть приблизительно равны модули амплитуд состояний кубитов.
В чем преимущества квантового машинного обучения
Какие преимущества для вычислений дает суперпозиция? Если на обычном компьютере при выполнении многопоточных программ для каждого потока требуется один логический процессор, то в квантовом компьютере число потоков может расти экспоненциально по мере увеличения количества кубитов в схеме.
К примеру, если для 1024 потоков в обычном компьютере потребуется такое же количество логических процессоров, то в квантовом — всего 10. Правда, использовать эти потоки можно только опосредованно, то есть непосредственно наблюдать за их работой не получится.
Нужно также понимать, что алгоритмы, которые использует квантовый компьютер, отличаются от алгоритмов, изучаемых в разделах Computer Science, посвященных классическим компьютерам. Разумеется, нельзя перенести классический алгоритм в квантовый компьютер, не изменив его предварительно. Причем вряд ли от первоначального алгоритма останется что-то существенное. Скорее всего, он будет основательно изменен, так что от него останется только общая идея (если вообще что-то останется).
То же самое можно сказать и про машинное обучение. Для квантовых компьютеров уже существуют аналоги классических алгоритмов машинного обучения (например, Random Forest, KNN, нейронные сети). Но, во-первых, реализованы они по-другому, а во-вторых, скорее всего, рано или поздно появятся абсолютно новые алгоритмы, которые будут в полной мере использовать выгодные стороны квантовых вычислений.
Всем специалистам из области больших данных и искусственного интеллекта известны ситуации, когда дата сайентисту приходится долго ждать, пока обучится модель.
Конечно, бывают простые модели (такие как линейная регрессия), которые обучаются на небольших данных за считанные секунды, но в случае более сложных моделей, например, нейронных сетей, обучение может длиться от нескольких минут до нескольких недель. Для того, чтобы перебрать несколько вариантов таких моделей, требуется недюжинное терпение.
Есть также такие модели, от использования которых откажется даже самый терпеливый дата сайентист. В частности, модели с огромным количеством весов либо такие, где требуется перебор экспоненциально растущего числа комбинаций. Именно для таких задач подходит использование квантовых компьютеров, позволяющих сократить время вычисления от нескольких лет до нескольких минут.
Почему искусственный интеллект нуждается в ускорении алгоритмов
В последние два-три года произошло стремительное развитие технологий компьютерного зрения, а за последний год придумано много нового в обработке естественного языка.
При этом обучение сложных моделей длится очень долго. Но если предположить, что модели такой же или даже большей сложности занимали бы на порядок меньше времени, то проверять гипотезы и тестировать модели можно было бы гораздо быстрее.
Соответственно, прогресс в этих областях происходил бы ускоренными темпами: вместо одного-двух заметных открытий в месяц мы могли бы слышать о таких ежедневно. Двойной экспоненциальный рост в прогрессе квантовых вычислений может привести к такой же скорости прогресса в машинном обучении.
Механизмы квантовых вычислений
В качестве кубита может выступать фотон, электрон, ион либо какая-то еще частица. Если это электрон, то можно измерить его спин (собственный момент импульса) и так получить 0 или 1. В обозначении Дирака эти состояния обозначаются таким образом:
Состояние кубита можно выразить также с помощью вектора. Это вектор состояния кубита, равного 0:
А это вектор кубита, равного 1:
Важную роль в квантовых вычислениях играет оператор Адамара:
Один из способов получить суперпозицию — применить к кубиту, находящемуся в одном из двух базисных состояний, оператор Адамара. В этом случае мы получим такое состояние кубита, когда вероятности получить 0 или 1 после измерения равны. Вот так будет получена суперпозиция в том случае, если изначальное состояние кубита — нулевое:
А вот такая суперпозиция получится, если начальное состояние единичное:
Еще один распространенный вариант работы с кубитами — использование квантовой запутанности — такой взаимосвязи между двумя кубитами, когда даже при их разнесении на большое расстояние они проявляют 100-процентную корреляцию. При прямой корреляции если один из кубитов после измерения принимает определенное состояние, то точно такое же состояние приобретает и другой кубит. При обратной взаимосвязи кубиты принимают противоположные состояния после измерения.
Какие сейчас возможности квантовых вычислений и квантового машинного обучения
Использовать квантовые вычисления для машинного обучения смогут все специалисты, которые захотят сэкономить время. Такие операции, как быстрое преобразование Фурье, нахождение обратной матрицы, вычисление собственных значений и векторов матрицы на квантовом компьютере происходят с экспоненциальным ускорением.
Конечно, не сильно затратную по ресурсам работу (например, визуализация данных) можно будет продолжать делать на обычном компьютере, но алгоритмы машинного обучения или хотя бы те их части, которые можно ускорить с использованием кубитов, можно будет отдать квантовому компьютеру.
Один из вопросов, который беспокоит специалистов: как работать с данными в условиях квантовых вычислений? Представим ситуацию, что у нас есть изображение (чтобы было проще, пусть оно будет черно-белое), которое мы хотим подать на вход квантовой нейронной сети. Картинка имеет размер 256 на 256 пикселей — вполне стандартный размер для распознавания изображений.
Для того, чтобы представить это изображение в виде чисел, закодируем каждый пиксель 64-битным числом с плавающей запятой (на самом деле хватило бы и 8-битного целого числа, но на практике матрицу со значениями пикселя масштабируют перед подачей на вход нейросети, так что матрица заполняется 32- или 64-битными числами). Такое изображение может быть представлено в виде матрицы из 65536 чисел, которая будет весить 512 килобайт (нейронная сеть принимает на вход несжатое изображение), то есть потребуется 4194304 бит.
Если же закодировать это изображение с помощью кубитов, то их число будет значительно меньшим: мы переведем n кубитов в суперпозицию, и значение каждого пикселя можно будет представить в виде амплитуды при каждом из возможных состояний. Число таких состояний равняется двум в степени n. Чтобы найти n, найдем двоичный логарифм из количества пикселей.
Как видите, действия достаточно простые, так что даже не приходится писать формулы. В итоге число n получается равным 16. Именно столько потребуется кубитов, чтобы закодировать данное изображение, то есть в 262144 раз меньше, чем при использовании классических битов.
Если в нашем распоряжении есть 66 кубитов, то переведя их в суперпозицию, можно закодировать более триллиона цветных изображений в формате 4K.
Таким образом, квантовое кодирование позволяет достичь логарифмического сжатия информации. Соответственно, ускорение методов машинного обучения при работе с такими данными может быть экспоненциальным.
Специализированные языки программирования и библиотеки
Сегодня во многих языках программирования есть библиотеки для квантовых вычислений. Некоторые из этих библиотек работают только с симуляцией квантовых вычислений, но многие поддерживают в качестве бэкенда и настоящие квантовые компьютеры, в том числе и облачные.
Если оперировать непосредственно кубитами, то это сродни написанию низкоуровневого кода на Ассемблере на классических компьютерах. Как ни странно, одним из таких “низкоуровневых” языков программирования, используемых для программирования вычислений на квантовых компьютерах, стал Python.
Одна из библиотек для этого языка — Qiskit — работает как на симуляторе, так и на квантовом бэкенде, а также позволяет на низком уровне производить операции над кубитами. Для более высокоуровневого программирования удобно использовать PennyLane — библиотеку для квантового машинного обучения. В репозитории этой библиотеки есть примеры реализации алгоритмов машинного обучения, в том числе, квантовой нейронной сети.
Перспективы квантовых вычислений
В январе 2019 года был выпущен первый коммерческий квантовый компьютер — IBM Q System One. Также сейчас для квантовых вычислений можно использовать облачные системы как исследователям, так и коммерческим компаниям.
Каждый желающий может запустить свой квантовый алгоритм на облачной платформе IBM Q Experience, причем для создания квантовой схемы даже не обязательно владеть языками программирования, так как помимо ввода команд можно воспользоваться графическим интерфейсом под названием Circuit Composer.
В сентябре 2019 года появилась неофициальная информация о том, что Google достиг квантового превосходства, решив на квантовом компьютере одну из задач со скоростью, недоступной даже для самого мощного суперкомпьютера. Даже если новость преждевременная, такие сообщения говорят о том, что квантовое превосходство уже близко.
Сразу несколько IT-гигантов занимаются поисками лучших решений для квантовых компьютеров. Некоторые исследователи прогнозируют, что для квантовых компьютеров будет действовать закон, подобный закону Мура.
Правда, скорость развития в отличие классических компьютеров, скорее всего, будет не обычной одинарной экспонентой, а двойной, так что программистам, работающим с квантовыми вычислениями, в ближайшем будущем придется создавать большое количество программ.
Что касается сферы рекламы и маркетинга, в которой я сейчас работаю, то применяемые модели машинного обучения должны претерпеть полную трансформацию. То, что работает на классических компьютерах, будет как по скорости, так и по качеству значительно уступать моделям будущего.
Не меньшие изменений привнесут новейшие технологии и в процесс сканирования целевых аудиторий. Неуловимые боты, руководимые квантовыми компьютерами, будут бороздить просторы социальных сетей, улавливая мельчайшие изменения вкусов и настроений аудитории. Кто знает, может быть, и сами рекламные кампании можно будет запускать, лишь высказав компьютеру общие пожелания об их целях.
Комментарии (45)
red75prim
24.10.2019 10:51+2Если в нашем распоряжении есть 66 кубитов, то переведя их в суперпозицию, можно закодировать более триллиона цветных изображений в формате 4K.
Можно закодировать, но извлечь нельзя. Теорема Холево: максимальный объем информации, который можно извлечь из системы n кубитов — n бит.
sergei_shirkin Автор
24.10.2019 10:56Здесь имеется в виду, что изображения кодируются не для извлечения, а для подачи на вход нейросети, а она также находится в системе кубитов. Требуется извлечь небольшое количество информации — например, класс изображения. Если класса два, то для одного изображения потребуется один бит.
Ququmber
24.10.2019 12:43+1К квантовому машинному обучению есть один глобальный вопрос. Имеется «узкое горлышко». Если у вас есть исходно классические данные (а так почти всегда и есть), то вам придется сначала перегнать их в соответствующее квантовое состояние контролируемым образом (например, создав требуемые амплитуды вероятностей). Для этого потребуется применение огромного числа квантовых операций, и выигрыш от ускоренной обработки уже квантовых данных квантовым компьютером, а также от возможности сохранить огромный объем информации в небольшом числе кубитов, могут запросто быть съедены проигрышем на стадии приготовления. Это даже для идеального квантового компьютера.
Вот если данные исходно были квантовыми, тогда другое дело. Такие данные может генерировать, например, квантовый сенсор, а их ведь надо обрабатывать. Однако квантовая сенсорика находится в зачаточном состоянии.
Еще один возможный выход — квантовые устройства не алгоритмического, а скорее аналогового характера.sergei_shirkin Автор
24.10.2019 19:32По поводу кодирования информации есть разные подходы: Сет Ллойд говорит о кодировании посредством амплитуд или вероятностей, Скотт Ааронсон пишет про использование квантового оракула. Я думаю, это будет постепенно развиваться. А что вы имеете в виду под квантовыми устройствами аналогового характера?
EuXsun
25.10.2019 10:12Я думаю, можно в качестве аналоговых устройств предложить такие фото-матрицы, где можно попавшие фотоны сразу преобразовывать в кубиты без усреднения. Тогда и будет нечто наподобие квантового глаза.
Shkaff
24.10.2019 13:13+1В сентябре 2019 года появилась неофициальная информация о том, что Google достиг квантового превосходства, решив на квантовом компьютере одну из задач со скоростью, недоступной даже для самого мощного суперкомпьютера. Даже если новость преждевременная, такие сообщения говорят о том, что квантовое превосходство уже близко.
Просто для информации, новость таки не преждевременная, статья вышла в Nature вчера. Заодно хороший комментарий тут.sergei_shirkin Автор
24.10.2019 13:23Да, новость действительно прорывная. Интересно будет наблюдать за соперничеством Google и IBM в этой области.
Sychuan
24.10.2019 14:06Интересная статья. Я далек от темы. А в интернете противоречивая информация насчет квантовых алгоритмов в машин лернинг. Ааронсон кажется писал, что на данный момент все туманно. Можете вы расскахать подробнее про какие-то простые алгоритмы но полезные, которые сильно ускоряются на квантовых компьютерах? было бы интеренсо.Например, про обратную матрицу. Думаю все знают, что это такое, знают библиотеки и алгоритмы, которые ее считают. А как с квантовым случаем?
sergei_shirkin Автор
24.10.2019 14:43Если интересуют квантовые вычисления для машинного обучения, то могу порекомендовать лекцию Сета Ллойда.
Более подробно эта тема разбирается в курсе Университета Торонто Quantum Machine Learning.
Для квантовых вычислений в Python есть библиотеки qiskit и cirq, в качестве бэкенда можно использовать как симулятор, так и реальный квантовый компьютер (в облаке).
EuXsun
25.10.2019 10:20Посмотрите две книжки:
- Peter Wittek. Quantum Machine Learning
- 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
homocomputeris
24.10.2019 18:28Нужно также понимать, что алгоритмы, которые использует квантовый компьютер, отличаются от алгоритмов, изучаемых в Computer Science. Разумеется, нельзя перенести классический алгоритм в квантовый компьютер, не изменив его предварительно.
Это настолько корявые предложения, что становятся неправдой. Разумеется, CS изучает и квантовые алгоритмы; квантовых алгоритмов нет в типичных универских курсах. И тот же самый CS показывает, что любой классический алгоритм исполняется на квантовых машинах, естественно, при изменении реализации.sergei_shirkin Автор
24.10.2019 18:33Всё-таки отличие большое: в квантовых вычислениях нет циклов. Помимо того, в квантовых вычислениях возможны алгоритмы, аналогов которым нет в классических компьютерах.
homocomputeris
24.10.2019 19:05Это никак не отменяет факты, о которых я написал: CS по определению изучает все алгоритмы, любой классический алгоритм вычислим на квантовой машине.
sergei_shirkin Автор
24.10.2019 19:16Мне кажется, CS в итоге разделится на две ветки: будет классический CS и квантовый.
toyban
24.10.2019 21:15Помимо того, в квантовых вычислениях возможны алгоритмы, аналогов которым нет в классических компьютерах.
Это не так. Любой квантовый алгоритм может быть симулирован на классических машинах.
red75prim
24.10.2019 21:25Но не все квантовые алгоритмы могут быть выполнены на классическом компьютере за время оставшееся до тепловой смерти вселенной.
toyban
24.10.2019 22:24Ну, во-первых, это не доказано. Вполне может быть, что классические машины способны решать быстро те же самые задачи, на которых эффективны квантовые машины. Хоть это и маловероятно. Но тем не менее возможно.
А, во-вторых, в том комментарии, что я процитировал ничего не говорилось об эффективном выполнение квантовых алгоритмов на обычных компьютерах. Говорилось, что существуют квантовые алгоритмы, которые обычный компьютер не способен симулировать. Очевидно, что это не так.
sergei_shirkin Автор
24.10.2019 23:56Квантовую связь не получится в полной мере симулировать, так как это нелокальное взаимодействие, используется квантовая запутанность (в алгоритме квантовой телепортации). Не получится также полноценно симулировать один из методов оптимизации — квантовый отжиг, так как он работает за счет квантового туннелирования. В этих случаях можно только имитировать квантовые вычисления.
toyban
25.10.2019 00:12Я не настолько хорошо знаю, что такое квантовая телепортация, чтоб по этому поводу что-то утверждать, но, судя по всему, это никакой не алгоритм, а просто процесс. Поэтому к моему комментарию никакого отношения иметь не должен.
По поводу квантового отжига. Создатель D-Wave сначала эмулировал свою схему квантового отжига в матлабе в системе из 2 (или 2х2?) кубитов, прежде, чем воплощать ее физически. Да и с чего Вы взяли, будто это невозможно? Для каждого текущего состояния перебираете всех соседей, считаете их энергию и дальше "прыгаете" в новое состояние в зависимости от разницы энергий и "толщины" туннеля. Другое дело, что для систем с даже относительно небольшим количеством степеней свободы эта задача становится невыполнимой за разумное время для классических машин. Но тем не менее, в теории это вполне возможно.
Более того, очень просто эмулировать любой квантовый алгоритм на классических машинах, а вот как сделать наоборот — тут я уже не знаю. Это совсем неочевидно, можно ли на квантовых машинах эмулировать классические алгоритмы.
red75prim
25.10.2019 08:03Другое дело, что для систем с даже относительно небольшим количеством степеней свободы эта задача становится невыполнимой за разумное время для классических машин.
Вот это и не было продемонстрировано. Процитирую Скотта Ааронсона: "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 ускорится после апгрейда своего оборудования. И проблема в том, что не были продемонстрированы убедительные доказательства возможности [экспоненциального] ускорения."
toyban
25.10.2019 08:25К сожалению, я не совсем понимаю, как Ваш комментарий отвечает или дополняет то, что Вы процитировали у меня.
Я ничего про машину D-Wave не говорил. Я всего-лишь говорил, что систему из 2 кубитов (или все же 4х?) для квантового обжига можно было симулировать на обычном компьютере. И дальше предоставил наивный алгоритм для эмуляции квантового обжига для классической машины. Да, никто в здравом уме не будет запускать этот алгоритм для сколь-нибудь крупных задач, но главное — в теории это можно сделать.
Иначе говоря, аргумент, будто квантовый отжиг нельзя эмулировать на классических машинах — неверен.
red75prim
25.10.2019 09:01Просто уточнил, что D-Wave, по всей видимости, не демонстрирует потенциала для ускорения классических вычислений. Так что о ней можно не упоминать в контексте этого разговора.
red75prim
25.10.2019 07:40Единственная проблема при расчётах квантовых систем — экспоненциальный рост необходимых вычислительных мощностей при увеличении количества взаимодействующих частиц. Расчитать квантовую телепортацию состояния одной частицы не представляет никакой проблемы.
sergei_shirkin Автор
25.10.2019 13:42Я ещё забыл упомянуть генерацию случайных чисел. На классическом компьютере это псевдослучайные числа, на квантовом — настоящие случайные числа.
qbertych
25.10.2019 20:33Ох уж этот отдел маркетинга.
Вы вообще в курсе, что квантовые ГСЧ уже лет семь как вышли на рынок, и никакого отношения к квантовым компьютерам не имеют?
sergei_shirkin Автор
25.10.2019 20:40Кубит может играть роль генератора случайных чисел. Или вы про что-то другое?
Shkaff
25.10.2019 21:34Справедливости ради, кажется КК — наиболее подходящий источник сертифицированных КСЧ, не требующий нелокальности и прочих ухищрений, собсна тот же Ааронсон об этом пишет.
qbertych
26.10.2019 03:34Это не так. Во-первых, квантовые ГСЧ оптимизированы под стабильность в широком диапазоне внешних условий во избежание атак по сторонним каналам. В КК этого нет, они под гейты заточены.
Во-вторых, КК на рынке пока что нет, а квантовых ГСЧ на первой странице гугла аж четыре штуки, и стоят они всего лишь порядка 2к.
Shkaff
26.10.2019 09:49+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.
qbertych
26.10.2019 19:34А, ясно, это хитрые запутывание+сэмплинг с нормализацией. Да, любопытная схема. Топикстартер просто про кубиты говорил, что, очевидно, совсем из другой оперы.
Shkaff
26.10.2019 20:49Да, конечно, мне просто эта схема показалась остроумной, и я новообретенным знанием спешу делиться со всеми окружающими:) Тем более, что гугл, кажется, ее будет на своем КК делать в ближайшее время.
toyban
26.10.2019 22:30К сожалению, невозможность быстрого сэмплинга из квантовых гейтов для классических компьютеров — тоже открытый вопрос. Так что тут еще ничего до конца непонятно.
red75prim
27.10.2019 00:39+1Этот вопрос (BQP ?= P) из категории P ?= NP. Ещё очень долго может быть непонятно.
А потом всё-таки выяснится, что неравно, скорее всего.
qbertych
24.10.2019 21:44+1Простите, но статья не имеет никакого отношения к заголовку. У вас здесь куча, кони, люди, тонны маркетинговой воды про "классический ML может работать на квантовом компьютере" и "квантовый компьютер крут на многих задачах, а значит, и в ML", а также мечты о светлом будущем, где не будет ни книг, ни газет, одни сплошные квантовые вычисления. И абсолютно ничего по сути дела.
sergei_shirkin Автор
24.10.2019 22:16Статья задумывалась больше как вводная, для подробного описания алгоритмов машинного обучения на квантовом компьютере нужен цикл статей.
sinc
Не понятно, поясните, пожалуйста!
sergei_shirkin Автор
Если взять 10 кубитов, то число возможных состояний будет равно 2^10. Для каждого из них можно проводить вычисления.
Deosis
Сравнение некорректное. На обычном компьютере можно будет запустить 1024 разные задачи параллельно.
На квантовом — одну задачу, но с 1024 разными входами. При этом КК сможет вернуть результат только 10 успешно завершенных задач.
sergei_shirkin Автор
Не все результаты вычисления нужно выводить. Например, нейронная сеть может иметь миллионы весов в своих внутренних вычислениях, но на выходе нужны только несколько цифр — либо классы, либо результат задачи регрессии.
subcommande
Имхо, подмена понятий бита и логического процессора
doktr
Начиная с определенного количества кубитов уже можно сравнивать с процессорами. Например, в 64-кубитной системе возможны вычисления с большим количеством потоков, чем на 64 логических процессорах, причем на несколько порядков.
red75prim
Строго говоря, нет там никаких потоков. Исходное квантовое состояние трансформируется таким образом, чтобы амплитуда правильных ответов была максимальной. Далеко не все задачи могут быть ускорены преобразованием к такому виду.
sergei_shirkin Автор
Да, скорее речь идёт о квантовом параллелизме.