Квантовые технологии. Модуль 3

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

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

История идеи

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

Годом позже, в мае 1981 года, идею квантового компьютера сформулировал физик и нобелевский лауреат Ричард Фейнман в докладе, посвященном возможности моделирования физических процессов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Биты и кубиты

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

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

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

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

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

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

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

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

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

То есть в N кубитов можно закодировать 2^N бит информации, и тогда всего лишь в 500 кубитах уместится фантастический объем информации — 2⁵⁰⁰ бит.

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

Еще в 1975 году советский физик Роман Поплавский приводил данные, по которым для расчета квантово-механических параметров простейшей органической молекулы — молекулы метана — требуется провести вычисления в 10⁴² точках, на что потребуется энергия всех электростанций Земли примерно за 100 лет.

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

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

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

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

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

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

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

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

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

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

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

f: {0,1}ⁿ> {0,1}

О функции заранее известно, что выполняется одно из двух условий:

• функция f — константа, то есть для любого из своих аргументов всегда возвращает либо 0, либо 1;
• функция f сбалансирована, то есть число нулей и единиц у нее одинаково, то есть ровно на половине своих аргументов возвращает 0, а ровно на половине 1.

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

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

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

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

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

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

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

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

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

Узнайте, насколько хорошо вы усвоили материалы модуля.

ПРОВЕРИТЬ СЕБЯ