КВАНТОВЫЕ ВЫЧИСЛЕНИЯ

13.1 Ключевые (основные) вопросы (моменты)

— понятие о квантовых вычислениях;

— особенности квантового процессора.

13.2 Текст лекции

13.2.1 Квантовые вычисления

Кардинально новой является идея квантовых вычислений, которая впервые была высказана советским математиком Ю.И. Маниным в 1980 году и стала активно обсуждаться после опубликования в 1982 году статьи американского физика-теоретика нобелевского лауреата Р. П. Фейнмана (R.P. Feynman ). В статье Фейнмана были рассмотрены физические ограничения процесса вычислений и показано, что термодинамических ограничений, типа второго начала термодинамики, не существует и если уменьшать потери энергии, шумы, то можно сделать сколь угодно длинные вычисления со сколь угодно малыми затратами энергии. В этой же работе Фейнман обратил внимание на то, что если имеется устройство, подчиняющееся законам квантовой механики, то его вычислительные возможности совершенно не обязательно должны совпадать с возможностями обычного устройства. Возникают некоторые дополнительные возможности, но априори непонятно, позволяют они получить какой-то выигрыш, или нет.

В середине восьмидесятых годов появились работы Д. Дойча (D. Deutsch), Е. Бернстейна и У. Вазирани (E. Bernstein, U. Vazirani), А. Яо (A. Yao), в которых были построены формальные модели квантового компьютера. В 1985 году Д. Дойч предложил конкретную математическую модель – квантовую машину Тьюринга, а в 1989 – эквивалентную, но более удобную модель – квантовые схемы. После появления данных работ перспективы квантовых вычислений стали связывать с ожиданием экспоненциального ускорения решения NP-полных проблем, которые, как уже было отмечено, не могут быть решены за полиномиальное время на классических компьютерах.

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

Такое состояние электрона, когда он находится сразу в нескольких точках пространства, называют суперпозицией квантовых состояний и обычно описывают волновой функцией y, введенной в 1926 году немецким физиком Эрвином Шрёдингером (E. Schrödinger). Модуль значения волновой функции в любой точке, возведенный в квадрат, определяет вероятность нахождения частицы в этой точке в данный момент. После измерения положения частицы ее волновая функция как бы стягивается (коллапсирует) в ту точку, где частица была обнаружена, а затем опять начинает расплываться. Свойство квантовых частиц быть одновременно во многих состояниях, называемое квантовым параллелизмом, успешно используется в квантовых вычислениях.

Элементарным шагом при квантовых вычислениях является унитарная операция над L-кубитовой суперпозицией состояний регистра из L кубитов, при этом выполняется параллельная обработка сразу всех 2^L комплексных амплитуд (векторов с произвольными комплексными коэффициентами), тогда как для классического компьютера подобная операция потребовала бы 2^L отдельных элементарных шагов. Квантовый параллелизмв работе квантовых устройств приводит к экспоненциальному ускорению вычислительного процесса.

Долгое время оставалось неясным, можно ли использовать гипотетическую вычислительную мощь квантового компьютера для ускорения решения практических задач. Ситуация изменилась с появлением в 1994 году статьи П. Шора (P. W. Shor, "Algorithms for Quantum Computation: Discrete log and Factoring"), в которой был предложен эффективный квантовый алгоритм вычисления дискретного логарифма. Шор предложил алгоритм, позволяющий проводить быструю факторизацию больших чисел, который позволял разложить на простые множители число из n знаков за n³(log n)^k шагов (k – const). По сравнению с лучшим из известных на сегодня классических методов квантовый алгоритм Шора дает многократное ускорение вычислений, причем, чем длиннее факторизуемое число, тем значительней выигрыш в скорости.

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

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

В 1996 году Л. Гровер (L. Grover) предложил квантовый алгоритм быстрого поиска в неупорядоченной базе данных, который позволяет не только ускорить процесс поиска, но и увеличить примерно в два раза число параметров, учитываемых при выборе оптимума. Правда выигрыш во времени здесь не столь значителен: для нахождения одной записи из n потребуется порядка Ħn операций на квантовом компьютере вместо n на классическом.

В настоящее время квантовые компьютеры, которые имели бы квантовые регистры, включающие не менее 1000 кубитов, а также удовлетворяли ряду других требований, в частности, вытекающих из условия помехозащищенности квантовых вычислений, существуют только теоретически. Предполагается, что большого числа кубитов в квантовом регистре можно будет достигнуть лишь при твердотельном исполнении квантовых компьютеров, работающих в условиях низких температур. Это могут быть, в частности, твердотельные ядерные магнито-резонансные (ЯМР) квантовые компьютеры, использующие в качестве кубитов ядерные спины со спиновым квантовым числом I = 1/2.

Однако пока созданы лишь простейшие прототипы жидкостных ЯМР квантовых компьютеров на органических молекулах с числом ядерных спинов-кубитов L ~ 7, молекулы в которых представляют собой большой ансамбль независимо работающих компьютеров. На них были экспериментально продемонстрированы некоторые квантовые алгоритмы решения трудно разрешимых на классических компьютерах задач (таких, как алгоритм Шора), опробованы эффективные методы коррекции квантовых ошибок. Однако путь, связанный с созданием полномасштабного жидкостного ЯМР квантового компьютера, оказывается невозможным из-за быстро уменьшающегося с числом кубитов выходного сигнала ЯМР.

Дата добавления: 2014-11-24; просмотров: 498; Нарушение авторских прав

Мы поможем в написании ваших работ!