В октябре 2023 года появился первый квантовый компьютер на 1000 кубитов. Кубиты - это квантовые биты (от англ. qubit - quantum bit), которые заменяют обычные 0 и 1 в классическом компьютере. Так вот, 1000 кубитов это много или мало? Ответ на этот вопрос - учитывая, что мы говорим про одну из самых запутанных (во всех смыслах) областей знания - зависит от области применения квантовых компьютеров.
В первую очередь, это криптография. Именно квантовая механика может, что называется, в одну секунду раскрыть частную жизнь всех людей на планете, вскрыть секреты государств мира и повергнуть в хаос системы криптовалют. Сделает она это, взломав криптографические ключи. Так вот, пока волноваться не стоит - для криптографии названного количества кубитов чрезвычайно мало. Более того, из этих 1000 кубитов реально будут что-то считать только 10. Почему так мало? И сколько надо, чтобы уже волноваться за свой криптокошелек? Давайте разберемся, если не боитесь вконец запутаться.
И нули, и единицы
Простейший квантовый компьютер можно представить в форме уменьшенного аппарата МРТ (магнитно-резонансная томография). С помощью двух катушек создаем однородное магнитное поле. Помещаем в это поле атомы, оси которых параллельны. Атом, «смотрящий» вверх, соответствует 0, вниз - 1. Если послать через катушку электромагнитный импульс, то положение атомов изменится - с 0 на 1, и наоборот. Вот мы и произвели вычисление. Конечно, современные квантовые компьютеры устроены посложнее, но принцип действия в них схож - он затрагивает манипуляции с элементарными частицами.
Но что же здесь квантового, спросите вы? А то, что атомы используют феномен квантовой интерференции. Допустим, к исходу 0 ведут два пути, но один из них более вероятен, чем другой. Это значит, что в процессе квантового вычисления вероятности 1 исключат друг друга и останется 0. Речь здесь не идет о том, что квантовый компьютер будет считать быстрее обычного компьютера - речь о том, что некоторые процессы будут выполняться на нем значительно быстрее.
Простая сложность
Мы сейчас обратимся ненадолго к математике, потому что на самом деле квантовые компьютеры возникли из нужд математиков, а не физиков, как можно подумать. А именно - поговорим о двух классах математических задач: P-сложности и NP-сложности. Задачи P-сложности решаются за полиномиальное время (отсюда и буква P в названии: P - polynomial). Не будем углубляться в определение того, что такое «полиномиальный», поскольку придется рисовать много таблиц и формул. Согласно грубой модели, задачи, решаемые за полиномиальное время, оцениваются как быстрые, в противовес задачам, решаемым за экспоненциальное время (как следует из названия, их сложность возрастает экспоненциально). Так вот - для задач P-сложности алгоритмы найти нетрудно, и эти задачи разрешимы.
Тогда что же такое NP-сложные задачи, ведь там тоже есть P в названии? Они тоже, получается, полиномиальные? Не совсем, эти задачи «недетерминированные полиномиальные» (или, по-английски, non-deterministic polynomial). Это значит, что для таких задач алгоритм «быстрого» решения может существовать, но он пока не найден. Более того, дело обстоит таким образом, что все NP-задачи представляют собой задачу одного рода. Если математики смогут найти алгоритм для одной какой-то задачи NP-сложности, то этот алгоритм подойдет для всех задач. Все NP-задачи станут P-задачами.
Мы бы не стали говорить о теоретических исканиях математиков, если бы решение задачи «P равно или не равно NP» не имело бы практических последствий. А они как раз были бы огромными. Современный мир не может функционировать без компьютеров и вычислений. Доказательство, что P = NP означало бы создание алгоритмов для автоматизации множества процессов. Например, существует так называемая «задача коммивояжера». Она заключается в поиске самого выгодного маршрута, проходящего через определенные города хотя бы по одному разу с последующим возвратом в исходный город. Методом перебора ее не решить уже при количестве городов около 60. Это, как понятно, задача из логистики. Также произошли бы серьезные сдвиги в медицине, поскольку можно было бы легко предсказать структуру белка.
Однако больше всего изменений произошло бы в системах компьютерной безопасности. Большинство криптографических систем - от открытого ключа до хэш-функций - легко бы взламывались алгоритмами, будь P=NP. И вот теперь настало время вернуться к квантовым компьютерам, поскольку в 1994 году появился алгоритм, который очень близко подобрался к решению NP-задач.
Вычисление до конца Вселенной
Задайте себе вопрос: что сложнее для вычисления - умножение больших чисел (например, семизначных) или же разложение большого числа на множители? Впрочем, долго думать не придется, так как очевидно, что умножение можно даже огромных чисел можно разложить на операции, которые выполнялись бы последовательно без значительного увеличения времени. Напротив, разложение большого числа на множители будет занимать время, растущее в экспоненциальной прогрессии. Ведь множители нужно будет искать методом перебора. Например, для числа 10 949 769 651 859 множители это 4 220 851 и 2 954 209. Однако, чтобы найти их, придется делить изначальное число до тех пор, пока введенное число не разделится без остатка. И чем больше число, множители которого мы ищем, тем больше времени (в экспоненциальной прогрессии) это займет. Как вы думаете, сколько займет у компьютера разложение на множители 250-значного числа? Возьмем даже не один компьютер, а миллион. Так вот, вычисление шло бы тоже миллион лет. Напротив, умножение 250-значных чисел занимает секунды.
Что такого важного в трудности вычисления множителей? А именно тот факт, что это сложная математическая задача, позволил создать надежные криптографические системы, которыми пользуется сегодня каждый человек, выходящий в интернет. Если вы покупаете что-то в интернет-магазине, то оставляете номер платежной карты. Этот номер шифруется как раз с помощью множителей. Злоумышленники эти множители не знают, зато их знает система интернет-магазина. Конечно, речь не только о местах торговли, но и обо всех сайтах, где содержится не предназначенная для публики информация. Им всем требуется криптографическая система.
В 1994 году появился так называемый алгоритм Шора, который позволяет за короткое время раскладывать даже большие числа на множители. Однако есть загвоздка - для выполнения алгоритма требуется квантовый компьютер. Получается, что тот, кто первым изобретет квантовое вычислительное устройство, способное работать по алгоритму Шора, сломает весь интернет? Хакер с таким компьютером мог бы шантажировать не только интернет-магазины, но и крупные корпорации, и даже государства. Обнаружение математического алгоритма и положило начало гонке в создании квантовых компьютеров. Крупные страны, вроде США, стали выделять на это миллионы не просто так - ведь речь уже шла о государственной безопасности.
Холодная математика
Вот мы и подходим к кубитам - единицам вычисления квантового компьютера. Сколько кубитов потребуется, чтобы запустить алгоритм Шора и сломать всю кибербезопасность, разложить все секретные ключи на множители? Довольно много - около 20 000. Тут еще нужно брать в расчет уникальную природу такого устройства. Вычислительная способность квантового компьютера определяется именно квантовыми эффектами - то есть, способностью частицы быть одновременно в состоянии 0 и 1 - но в этом кроется и трудность. Нам нужно всеми силами удержать частицы в полезном для вычисления состоянии, а для этого надо оградить их от влияния других частиц. Каких? Да практически любых - от случайных фотонов, молекул воздуха, космического излучения, геотермального излучения и т.д. Идеальная вычислительная квантовая система должна быть полностью изолирована от внешнего мира. Но тогда ее невозможно измерить. Вот и получается, что кубиты полезны, если они не взаимодействуют с окружением, а избежать этого невозможно. В конце концов, для измерения состояний и последующего вычисления на квантовом компьютере нужно подвергнуть кубиты влиянию окружения. Этот феномен называется декогеренция.
Создатели квантовых компьютеров видят декогеренцию как необходимое зло и воспринимают ее просто как потерю информации. Из этого следует, что количество физических кубитов для вычисления (т.е. реальных атомов) всегда превышает количество логических кубитов (т.е. тех, которые фактически производят вычисление). Поэтому в начале статьи мы и сказали, что из 1000 кубитов анонсированного квантового компьютера реально что-то вычислять будут только 10. В среднем, соотношение пользы составляет 100 к 1, т.е. из 100 физических кубитов производить полезные вычисления будет в среднем 1.
Вот и получается, что даже для запуска алгоритма Шора вычислительная мощность современных квантовых компьютеров не просто низка - она ничтожна. Ведь нужно 20 000 логических кубитов для его запуска, что означает примерно 2 млн физических кубитов. Примите во внимание, что такой компьютер потребует много энергии и охлаждения для работы. Например, при текущих технологиях для работы квантового компьютера на 100 000 кубитах понадобится атомная электростанция и миллиард долларов. По сути, это большие холодильники, в которых находятся полупроводниковые материалы для вычислений. Почему холодильники? Чем ниже температура, тем меньше тепла, и, соответственно, меньше «шума» для кубитов.
Короче говоря, до создания потенциальных убийц кибербезопасности пока далеко. Технологии создания кубитов должны радикально измениться, а также нужно менять соотношение физических и логических кубитов в сторону уменьшения. IBM и Google обещают создать 100 000-кубитную машину в течение ближайших 10 лет. Что ж, посмотрим что получится. Будет достаточно тривиально, если все сведется лишь к вопросам кибербезопасности. Но вот если квантовые вычисления позволят нам создавать алгоритмы, доказывающие, что P=NP (или хотя бы автоматизируют задачи, считающиеся сложными для классических компьютеров), тогда наш мир действительно радикально изменится.
***
Если вам понравилась статья, вы можете поставить отметку «нравится». Если есть с чем поспорить, пишите в комментарии - мне интересно альтернативное мнение. Также вы можете подписаться на канал. Я пишу материалы о науке, истории и психологии.
