Квантовые технологии

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

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

Квантовые компьютеры обещают решить эту проблему, однако пока в реальности созданы только экспериментальные квантовые установки, которые ещё не показали «квантового превосходства» — значимой прибавки в скорости вычислений по сравнению с обычными компьютерами.

В этом модуле вы узнаете:

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

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

Идею квантовых вычислительных устройств впервые высказал в 1980 году советский математик Юрий Манин. В книге «Вычислимое и невычислимое», говоря о сложности процесса считывания и записи биологической информации с молекул ДНК, он замечает, что для моделирования этого процесса могли бы подойти квантовые устройства.

Годом позже, в мае 1981 года, идею квантового компьютера сформулировал физик и нобелевский лауреат Ричард Фейнман в докладе, посвящённом возможности моделирования физических процессов. Физик подчёркивает, что все явления подчиняются квантовым законам (а классическая физика — только приближение). Если поведение одиночного квантового объекта достаточно легко поддаётся моделированию с помощью компьютера, то нарастание количества элементов ведёт к экспоненциальному росту сложности вычислений. Из этого следовало два варианта, говорил Фейнман: первый — признать, что квантовые системы не поддаются моделированию с помощью компьютеров, и второй — построить вычислительную машину из квантовых элементов, которые будут подчиняться тем же квантовым законам, что и моделируемая система.

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

Работа одного из элементов квантового компьютера в представлении Фейнмана

В 1985 году Дэвид Дойч из Оксфордского университета разрабатывает теорию универсального квантового компьютера как квантовой машины Тьюринга.

Однако первый в мире квантовый компьютер мог появиться намного раньше, ещё до статей Манина и Фейнмана, в 1950-е годы. Тогда японский учёный Гото Эйичи экспериментировал с низкотемпературной электроникой для разработки миниатюрного магнитно-управляемого бита, то есть системы, которая может находиться в двух состояниях и служить, как и обычный полупроводниковый транзистор, основным элементом компьютера.

Эйичи назвал свой бит параметроном, и его первый прототип был создан в 1958 году в Токийском университете.

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

Пределы роста для классических компьютеров

Современные компьютеры, включая самые мощные, основаны на использовании множества полупроводниковых «переключателей» — транзисторов, их вычислительная мощность в конечном счёте зависит от количества этих транзисторов и скорости их срабатывания. С 1960-х годов, когда началось интенсивное развитие электроники, в мире компьютеров действует закон Мура — замеченная основателем Intel Гордоном Муром закономерность, согласно которой число транзисторов на чипе удваивается каждые два года, а производительность процессоров (как и мощность, доступная за 1 доллар) — каждые 18 месяцев.

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

Согласно расчётам Сета Ллойда из Массачусетского технологического института, умозрительный «окончательный ноутбук», в котором предельная вычислительная мощность «упакована» в объём 1 литр и массу 1 килограмм, мог бы выполнять 10^51 операцию в секунду на 10^31 битов, что примерно на 40 порядков выше возможностей современных вычислительных машин. Это означает, что закон Мура должен действовать ещё примерно 250 лет, чтобы добраться до этого окончательного предела.

Однако большинство экспертов считают, что рост возможностей современной электроники упрётся в потолок намного раньше, и закон Мура перестанет работать. Пределы роста связывают с ограничениями на миниатюризацию самих транзисторов — уже сейчас слои диэлектрика в них могут иметь лишь несколько атомов в толщину, на работе их начинают сказываться квантовые эффекты, например, туннелирование. Сложности создаёт и пропускная способность межсоединений между транзисторами. Еще в 2013 году некоторые учёные объявили о конце закона Мура (пока лишь в области твёрдотельных накопителей).

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

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

Устройство квантового компьютера: биты и кубиты

Классические компьютеры оперируют битами — объектами, у которых есть только два возможных состояния, например, 1 или 0. В качестве такого максимально простого классического объекта можно рассматривать, например, монету, у которой виден либо аверс, либо реверс, то есть орёл или решка.

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

Состояние кубитов описывает волновая функция Ψ, которую можно представить как точку на единичной сфере — сфере Блоха. Положение этой точки задаётся двумя комплексными числами (ɑ и ꞵ). Это означает, что при каждом измерении кубита может получиться одно из двух значений |0> или |1>, с вероятностями, заданными ɑ и ꞵ.

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

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

Квантовое преимущество

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

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

Квантовый способ найти бракованную монету

Это означает, что использование квантовых битов сильно увеличивает возможности для расчётов. Например, если один классический бит может содержать только 0 или 1, то в кубите можно закодировать уже два бита, суперпозицию 0 и 1, в двух кубитах можно закодировать уже четыре бита, три кубита — восемь, и так далее. То есть в N кубитов можно закодировать 2^N бит информации, то есть всего лишь в 500 кубитах можно закодировать фантастический объём информации — 2^500 бит.

Такие параметры теоретически позволяют решить некоторые задачи, которые фактически недоступны самым мощным современным суперкомпьютерам. В их числе — расчёт поведения атомов и молекул. В частности, расчёты поведения даже самых простых молекул на «обычных» компьютерах требуют гигантских вычислительных мощностей. Ещё в 1975 году советский физик Роман Поплавский приводил данные, согласно которым для расчёта квантово-механических параметров простейшей органической молекулы — молекулы метана — требуется провести вычисления в 10^42 точках, на что потребуется энергия всех электростанций Земли примерно за 100 лет.

Для того чтобы описать механику работы квантового вычислительного устройства, можно использовать многомировую интерпретацию квантовой механики (известную также как интерпретация Эверетта). Аспирант из Принстона Хью Эверетт в своей диссертации пытался справиться с проблемой квантовой неопределённости путём умножения вселенных. Каждый раз, когда происходит некоторое вероятностное событие, возникает две Вселенных, в одной из которых кот Шрёдингера погиб, а во второй выжил.

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

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

Квантовые алгоритмы

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

Алгоритм Дойча — Йожи 

Был предложен в 1992 году Давидом Дойчем и Ричардом Йожей. Это было первое описание вычислительной процедуры, в которой использовалось квантовое преимущество, то есть квантовые эффекты запутанности и суперпозиции давали значительный прирост скорости расчёта по сравнению с классическими алгоритмами.

Суть этой задачи Дойча — Йожи состоит в процедуре поиска бракованной монеты, описанной выше. Математически она формулируется так:

Дано: «чёрный ящик», который вычисляет функцию

f: {0,1}ⁿⁿ→ {0,1}.

Заранее известно: выполняется одно из двух:

(к) функция f — константа;

(б) функция f сбалансирована, т. е. число нулей и единиц у неё одинаково.

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

Другими словами, есть «чёрный ящик», который может быть устроен двумя способами, и нужно определить, каким именно. Этот алгоритм был специально разработан так, чтобы квантовое вычислительное устройство показало при его решении серьёзное преимущество.

Алгоритм Шора

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

Дело в том, что умножение и противоположная ему процедура разложения на множители асимметричны — «трудозатраты» на факторизацию растут гораздо быстрее, чем сложность умножения соответствующих чисел. Скажем, компьютер может без особенных усилий перемножить два двухсотзначных числа. А вот для того, чтобы разложить на множители 400-значное число, самому мощному современному суперкомпьютеру потребуется примерно 10 миллиардов лет.

Алгоритм, придуманный Питером Шором в 1994 году, позволяет решить эту задачу на квантовом компьютере всего лишь за три года.

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

RSA — один из распространённых алгоритмов шифрования, который станет уязвимым из-за алгоритма Шора.