О квантовых компьютерах, биткоине и превосходстве. Лекция открытого курса qmlcourse04.08.2021 15:32

Предисловие

Всем привет! Меня зовут Семён, и моя работа связана с Data Science и Data Engineering. Но также я очень увлекаюсь квантовыми вычислениями и особенно квантовым машинным обучением. Вместе с другими энтузиастами из сообщества Open Data Science мы готовим к запуску открытый курс по квантовому машинному обучению (страница курса, GitHub курса, последняя сборка курса). Это проект во многом похожий на другие курсы ODS, такие как mlcourse.ai или курс по графам знаний. Лекции планируется выкладывать в том числе сюда на Хабр. Это самая первая вводная лекция. А в конце этой статьи я расскажу подробнее о самом курсе, как на него записаться, а также как можно принять участие в его создании.

Описание лекции

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

что это за вычисления такие?
зачем вообще это все нужно?
и когда взломают биткоин?
что за превосходство, о котором все говорят?

Что это вообще за компьютеры такие?

Количественная эволюция компьютеров

Сегодня классические компьютеры, построенные на идеях Тьюринга, фон Неймана и Шокли, стали неотъемлемой частью нашей жизни. Все мы привыкли к тому, что с каждым годом наши компьютеры становятся все мощнее и мощнее. И то, что сегодня является бюджетным ноутбуком 15 лет назад было аналогом суперкомпьютера!

Иллюстрация закона Мура — рост числа транзисторов с 1970-х

Так называемый закон Мура, сформулированный Гордоном Муром еще в конце 60-х годов, говорит нам о том, что число транзисторов на кристалле интегральной схемы будет удваиваться каждые два года. И этот закон стабильно выполняется.

Качественная эволюция компьютеров

Но, к сожалению, по сугубо физическим причинам, выполнение закона Мура не может длиться вечно — рано или поздно, но прямое увеличение количества транзисторов станет невозможно. Поэтому сегодня все чаще можно услышать слова о том, что современным компьютеры ждет качественная революция. Кто-то говорит о переходе на новые материалы для изготовления транзисторов. Кто-то говорит о создании транзисторов на новых принципах, например, об оптических компьютерах. Но часто можно услышать слова о том, что следующим революционным прорывом станет создание квантовых компьютеров. О них мы и будем говорить.

Идея о квантовом компьютере

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

Ричард Фейнман, 1918-1988 Ричард Фейнман, 1918–1988

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

Что это за компьютер такой?

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

А зачем это вообще нужно?

Факториазация больших чисел

Мне кажется, что именно открытие алгоритма Шора для эффективного решения задачи факторизации послужило наибольшим толчком в популяризации квантовых вычислений. Именно после этого большое число специалистов устремилось в эту область, военные и корпорации начали вкладывать деньги, а журналисты стали писать о будущем крахе банковских платежей и вообще всего мира. Вероятно, алгоритм Шора является самым раскрученным квантовым алгоритмом.

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

Питер Шор, тот, кто переполошил весь мир своим алгоритмом

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

Комбинаторные и NP-трудные задачи

Помимо уже озвученных проблем с выполнением закона Мура, есть также и другая проблема. А именно то, что существуют задачи, которые скорее всего никогда не получится эффективно решать на классическом компьютере Тьюринга. Даже на фотонном или графеновом. Хороший пример это задача о рюкзаке. Когда у нас есть рюкзак ограниченного объема, а также есть много предметов разного веса и стоимости. И нам надо наполнить наш рюкзак так, чтобы предметы внутри него имели максимальную суммарную стоимость. Задача кажется легкой, но она относится к так называемым NP-полным задачам. Такие задачи, например, в случае большого рюкзака и набора предметов, невозможно точно решить за разумное время. Да и вообще их решить с приемлемой точностью, пусть даже приближенно это сегодня большая проблема!

Замечание

Здесь я не зря написал «скорее всего». Дело в том, что этот вопрос является одним из так называемых вопросов тысячелетия. Так, для известной задачи о наполнении рюкзака, мы не знаем сегодня эффективного алгоритма решения на классическом компьютере. Но мы также и не можем пока доказать, что такого алгоритма не существует. Ну то есть скорее всего такого алгоритма и правда не существует, а также скорее всего $P \neq NP$ , но доказать это пока ни у кого не вышло. Но это скорее лирическое отступление.

Так вот, дело в том, что для квантовых компьютеров уже сегодня известны алгоритмы, которые позволяют потенциально эффективно, пусть и приближенно решать такие задачи на квантовом компьютере. Это задача коммивояжера, задача о рюкзаке, задача кластеризации графа и много других задач комбинаторной оптимизации. В нашем курсе будет целый блок, посвященный таким квантовым алгоритмам как Variational Quantum Eigensolver и Quantum Approximate Optimization Algorithm.

Визуализация решения задачи коммивояжера — кратчайший путь, чтобы объехать 12 немецких городов — очень важная задача современной логистики

Симуляция квантовой механики

Это то, ради чего Фейнман предложил создать квантовые компьютеры. Это отдельная большая тема, где много квантовой механики. Ей будет посвящено сразу несколько отдельных лекций нашего курса. Но попробуем объяснить в двух словах, не вдаваясь в детали.

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

Эрвин Шрёдингер, 1887-1961, создатель знаменитого уравнения и мема про кота Эрвин Шрёдингер, 1887–1961, создатель знаменитого уравнения и мема про кота

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

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

Машинное обучение и искусственный интеллект

За последние 10–15 лет машинное обучение достигло поистине небывалых высот в своем развитии. Многие задачи, решение которых силами компьютера, раньше казалось невозможным сегодня успешно решаются при помощи машинного обучения. Примеры таких задач это, например, игра в Go, различение пород чихуа-хуа по фотографии, распознавание лиц в видеопотоке, составление относительно осмысленных текстов и генерация картин в стиле Пикассо из простых фотографий. Но оно все еще очень далеко от возможностей человеческого мозга. Так, наиболее масштабные искусственные нейронные сети, по примерным оценкам, имеют сегодня размер, эквивалентный 15 миллионам нейронов, в то время как человеческий мозг имеет порядка 85 миллиардов! Вызывает вопросы также и скорость обучения современных нейронных сетей. Так, самые большие языковые модели сегодня обучаются неделями на кластерах из тысяч видеокарт, в то время как человек с его, относительно скромными вычислительными возможностями учится говорить всего 2–3 года.

И тут тоже на помощь могут прийти квантовые компьютеры. В данном случае, квантовые аналоги нейронных сетей, а также их комбинации с классическими нейронными сетями уже сегодня показывают впечатляющие результаты. Так, есть работы, где показано, что 4 квантовых нейрона по своей выразительности эквивалентны классической искусственной нейронной сети с $\sim 250$ нейронами!

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

Ну и когда взломают биткоин?

Наверное это один из главных вопросов, которые возникают при чтении подобных статей. И ответим сразу: взломают нескоро, времени еще много, 10 лет точно есть.

Биткоин, как и многие другие электронные средства вынуждены будут перейти на пост-квантовую криптографию Биткоин, как и многие другие электронные средства вынуждены будут перейти на пост-квантовую криптографию

Сколько нужно кубитов под разные задачи?

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

Алгоритм Шора и взлом современной криптографии (включая биткоин): $\sim 20\cdot 10^6$ (20 миллионов) кубитов
Задачи оптимизации: $\sim 100 \cdot 10^3$ (100 тысяч) кубитов
Первые полезные задачи в квантовой химии: $\sim 1\cdot 10^3$ (тысяча) кубитов
Квантовое машинное обучение: $\sim 100-500$ кубитов

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

Логические vs Физические кубиты

Есть еще такая проблема, что вся квантовая механика вероятностная. А еще, что квантовые компьютеры работают в области микромира и очень чувствительны к любым шумам извне. Это ведет к совершенно недопустимому уровню ошибок в вычислениях и их низкой детерминированности. Например, сегодня хорошим уровнем точности для квантовых компьютеров является 99% на одну операцию. Но ведь каждый алгоритм включает в себя сотни или даже тысячи операций! И тогда уровень ошибок становится совсем печальным.

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

Сколько кубитов есть сегодня?

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

Квантовый компьютер компании IMB выглядит примерно так

Есть квантовые компьютеры с разной архитектурой. Одни имеют больше кубитов, но и более высокий уровень ошибок. Другие имеют низкий уровень ошибок, но их трудно масштабировать. Теме квантового железа в нашем курсе будет посвящен отдельный блок из нескольких лекций. Но если кратко, то можно назвать примерно такие цифры.

рекорд в относительно легко масштабируемых, но шумных квантовых компьютерах это $\sim 55$ кубитов
рекорд в относительно точных, но медленных и плохо масштабируемых компьютерах это $\sim 20$ кубитов
рекорд в точных и масштабируемых, но очень трудно программируемых компьютерах это $\sim 25$ кубитов

Пояснение

Тут мы имеем ввиду соответственно:

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

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

Какие планы имеют ведущие игроки на этом рынке?

Казалось бы, с такими масштабами биткоину боятся нечего, да и в целом область выглядит не самой перспективной. Но есть один нюанс. Все крупные игроки на рынке создания квантовых компьютеров (Google Quantum, IBM Quantum, IonQ, Xanadu) озвучили планы к 2030-му году иметь порядка одного миллиона физических кубитов, что эквивалентно порядка тысяче логических кубитов. Для криптографии это еще не страшно, но вот многие полезные задачи уже можно будет попробовать решать. Ну и стоит еще раз посмотреть на график закона Мура для классических компьютеров, которые каждые десять лет показывают примерно такой же прогресс!

О квантовом превосходстве

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

Понятие квантового превосходства

Само понятие было сформулировано еще в 2012-м году известным физиком теоретиком Джоном Прескиллом.

Джон Прескил, который и придумал этот термин. Еще он известен своим знаменитым пари с другим физиком Стивеном Хокингом (которое Хокинг проиграл) Джон Прескил, который и придумал этот термин. Еще он известен своим знаменитым пари с другим физиком Стивеном Хокингом (которое Хокинг проиграл)

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

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

Хронология событий

Ну и в конце приводим краткую хронологию событий.

2019 год, компания Google заявляет о достижении квантового превосходства. Задача выбрана максимально удобная для квантового компьютера и полностью лишенная практического смысла. По словам разработчиков из Google их квантовый компьютер за 4 минуты решил задачу, которую классический суперкомпьютер решал бы 10 тысяч лет. Их квантовый компьютер имел 54 кубита;
2019 год, компания IBM заявляет, что Google не учли, что их задачу можно решать на классическом компьютере более оптимально, но без экспериментов;
2020 год, компания Alibaba реализует алгоритм IBM на своем суперкомпьютере и решает задачу за $\sim 20$ дней;
2021 год, группа китайских ученых оптимизирует классический алгоритм и решает задачу на 60 видеокартах NVIDIA за 7 дней;
2021 год, группа других китайских ученых заявляет, что достигла нового превосходства на квантовом компьютере из 56 кубит;

В общем сейчас идет довольно интересный процесс войны меча и щита. Пока одни ученые строят более мощные квантовые компьютеры, другие придумывают более продвинутые алгоритмы их симуляции. Хотя конечно все ученые говорят, что уже где-то на 60–70 кубитах эта история окончательно закончится в пользу квантовых компьютеров.

А как это вообще выглядит? И сколько стоит?

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

сверхнизкие температуры
сверхвысокий вакуум
сверхточная юстировка лазеров на оптическом столе

Или даже всего сразу. Поэтому сегодня почти все квантовые компьютеры продаются через облачные сервисы. Например, относительно недавно ведущий поставщик облачных технологий — компания Amazon добавила в свой сервис AWS новый продукт Amazon Braket. Этот продукт позволяет взять в аренду самый настоящий компьютер точно также, как мы привыкли брать в аренду процессоры, видеокарты или жесткие диски. Аналогичные продукты сейчас предоставляют и другие крупные игроки на рынке облачных услуг. Хотя это все пока исключительно для целей исследования. Ведь как мы уже поняли, сегодня квантовые компьютеры еще не способны решать реальные задачи. Стоит такое развлечение не очень дорого, например, можно запустить свою квантовую программу на 32-х кубитном компьютере Aspen-9 всего за 0.3 USD.

Некоторые производители идут дальше и предлагают относительно компактные решения. Так, недавно было представлено 24-х кубитное решение, которое помещается в две стандартных серверных стойки. Но масштабируемость таких устройств вызывает вопросы.

В любом случае, в ближайшие 15–20 лет точно не стоит ждать появление карманного квантового компьютера, или хотя бы квантового сопроцессора в домашнем ПК. Да и в этом нет особого смысла, ведь мало кому дома нужно взламывать биткоин, решать логистическую проблему или разрабатывать высокотемпературный сверхпроводник.

Заключение

Это вводная лекция, она не даст вам каких-то особых знаний. Скорее, ее цель заинтересовать читателя. Самое интересное будет в основной части курса, где мы будем разбирать квантовые алгоритмы, пытаться симулировать квантовую механику и обучать самые настоящие квантовые нейросети! Ждем вас на курсе!

Подробнее о самом курсе

Как попасть на курс?

Основной страницей курса будет страница на платформе Open Data Science, хотя лекции будут также выкладываться на Хабр и будут в GitHub Pages. Курс планируется к запуску в сентябре, но уже сегодня можно подписаться на новостную рассылку курса! Для этого необходимо зарегистрироваться в ODS и нажать кнопку «Start the track» на главной странице курса. Будет предложено оставить свою почту и согласиться получать рассылку.

Как поучаствовать в создании курса?

Курс является полностью Open Source и разрабатывается в GitHub. Команда курса будет рада любой помощи! Это может быть как создание полноценной лекции, так и участие в открытых ревью материалов, поиск и исправление ошибок, либо предложения по наполнению курса, материалу или программе. Можно присоединиться к обсуждению курса в GitHub Discussions, взяться за одну из открытых проблем или завести новую. Обсуждение курса также происходит в Slack сообщества Open Data Science и тут есть инструкция, как туда присоединиться. Планируется, что Slack вообще станет основным местом обсуждения в том числе домашних заданий курса, так что рекомендуем присоединиться! Также можно писать любые идеи, предложения или замечания на почту курса: qmlcourse.ods@gmail.com. Мы будем рады любой обратной связи!