Доклад на тему Квантовый компьютер

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

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

Одно из основных положений, которое иначе как магическим не назовешь, – принцип суперпозиции. Заключается он в следующем: если субатомная частица может находиться в нескольких состояниях, то она находится во всех этих состояниях одновременно. Принцип суперпозиции легко продемонстрировать на примере всем известного электрона. Электрон имеет некоторую внутреннюю характеристику, называемую спином. Электрон может находиться в двух состояниях – спин вверх (Spin Up) и спин вниз (Spin Down). В соответствии с принципом суперпозиции он находится в обоих состояниях сразу, каждое из которых присутствует со своей вероятностью (эти вероятности не обязательно равны, но сумма их – всегда 1).

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

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

Обычные компьютеры хранят информацию в ячейках, каждая из которых либо имеет электрический заряд, либо нет. Каждая такая ячейка соответствует минимальной единице информации – биту. Бит может быть равен нулю или единице. Хороший пример бита – это рубильник, который включает электролампу. Его значение либо 0 (лампа выключена), либо 1 (лампа включена). В квантовом компьютере аналогом бита является кубит (квантовый бит), который благодаря принципу суперпозиции находится в двух состояниях одновременно. Как в классических, так и в квантовых компьютерах биты или кубиты объединены в последовательности – регистры. Обычный двухбитовый регистр может хранить 4 значения – 00, 01, 10 или 11, но только одно из них в данный конкретный момент времени. А вот в двухкубитовом регистре одновременно находятся все 4 возможных значения. (Вообще в регистре размером N кубитов одновременно живут все возможные 2ⁿ значений.)

Упрощённая схема вычисления на квантовом компьютере выглядит так: берется система кубитов, на которой записывается начальное состояние. Затем состояние системы или её подсистем изменяется посредством унитарных преобразований, выполняющих те или иные логические операции. В конце измеряется значение, и это результат работы компьютера. Роль проводов классического компьютера играют кубиты, а роль логических блоков классического компьютера играют унитарные преобразования. Такая концепция квантового процессора и квантовых логических вентилей была предложена в 1989 году Дэвидом Дойчем. Также Дэвид Дойч в 1995 году нашёл универсальный логический блок, с помощью которого можно выполнять любые квантовые вычисления.

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

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

Чем же квантовый компьютер лучше классического? Большая часть современных ЭВМ работают по такой же схеме: n бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае система из n кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2ⁿ базовых состояний одновременно. Теоретически новая схема может работать намного (в экспоненциальное число раз) быстрее классической. Практически (квантовый) алгоритм Гровера поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов.

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

Допустим, вы хотите провести какое‑то действие над каждым из 4 возможных чисел в регистре из 2 битов на обычном компьютере. Решение этой задачи потребует 4 шага, выполняемых последовательно, поскольку в 2 обычных бита в каждый момент времени записано только 1 из 4 возможных чисел. Мы должны их последовательно перебрать и над каждым выполнить нужную операцию. В квантовом компьютере с регистром из 2 кубитов задача будет решена за один шаг, ведь действие производится сразу над всеми числами, которые одновременно хранятся в регистре. Это называется квантовый параллелизм. Именно квантовый параллелизм позволяет сделать некоторые вычисления намного более эффективными по сравнению с вычислениями на классическом компьютере.

Дальнейшее движение по пути создания квантового компьютера показало, что, несмотря на плодотворность идеи кубитов, праздновать победу еще рано. Тот самый квантовый параллелизм, который позволяет достичь фантастической производительности, порождает и новые проблемы: интересующий нас результат действия над квантовым регистром в действительности оказывается спрятан внутри суперпозиции. Если просто прочитать ответ, он окажется первым попавшимся из всех возможных (в системе с N состояниями правильный ответ будет выведен с вероятностью 1/N). Более того, в процессе считывания суперпозиция разрушается и система становится непригодной для дальнейших вычислений. И только заново настроив систему, можно снова попытаться получить правильный ответ. Весь выигрыш в быстродействии, который дает квантовый параллелизм, теряется!

Возник вопрос – как же быстро получить результат, который будет правильным с приемлемой вероятностью? Первым на него ответил американский математик Питер Шор в 1994 году. Он опубликовал работу, в которой описал квантовый алгоритм разложения на множители большого числа (алгоритм факторизации). Операции в этом алгоритме подобраны таким образом, что неправильные результаты с большой вероятностью взаимоуничтожаются, и потому вероятность правильного ответа увеличивается.

Зачем нужна факторизация? Задача факторизации, кажущаяся на первый взгляд чисто теоретической, имеет важное практическое приложение. Дело в том, что один из самых распространенных сегодня методов шифрования с открытым ключом – RSA – построен на очень простом утверждении: если у вас есть два простых числа (M и N), то вычислить их произведение (К) проблемы не представляет. Но вот, зная K, найти M и N – задача, на сегодняшний день разрешимая только путем прямого перебора всех возможных чисел. А если M и N – очень большие простые числа (более 100 цифр), то мощность (а скорее – немощность) сегодняшних компьютеров делает ее неразрешимой. Например, чтобы с помощью обычного компьютера разложить на простые множители 250‑значное число, потребуются многие тысячи лет. То есть алгоритм Шора, по сути, есть не что иное, как алгоритм взлома шифров. Таким образом, определилась идеальная область для применения квантового компьютера – криптография.

Ходят слухи, что сразу после публикации доклада Шора Агентство национальной безопасности США (NSA) запустило проект построения квантового компьютера, по масштабам сопоставимый с проектом создания атомной бомбы. Это вполне вероятно – ведь задачи криптографии представляют интерес в первую очередь для спецслужб, накопивших огромное количество информации, расшифровать которую существующими способами вряд ли удастся в обозримое время.

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

Эра соперничества квантового и классического компьютеров еще не наступила, ведь преимущество квантового вычислителя становится заметным, только если он состоит по крайней мере из 1000 кубитов. И хотя компания D‑wave анонсирует свои квантовые компьютеры, они подвергаются серьезной критике. Так, профессор Массачусетского Технологического Института Скотт Ааронсон считает, что D‑Wave пока не смогла доказать ни того, что ее компьютер решает какие‑либо задачи быстрее, чем обычный компьютер, ни того, что используемые 128 кубитов удается ввести в состоянии квантовой запутанности. Если же кубиты не находятся в запутанном состоянии, то это не квантовый компьютер.

Газеты вновь пишут о революции: Михаил Лукин из Российского квантового центра осуществил прорыв в постройке квантового компьютера. Ученые смогли достаточно долго сохранить данные в квантовой вычислительной системе – исследователи считают что мы стоим в одном шаге от создания реального квантового компьютера. В действительности команда Лукина создала кубит, функционирующий при комнатной температуре примерно 2 секунды, но и это уже прорыв, правда пока не понятно как создать из этих кубитов квантовый регистр.

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

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

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

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