Квантовые компьютеры: надежды и реальность - Валиев К.А.
Скачать (прямая ссылка):
Вычисление в любом компьютере представляет собой процесс, в ходе которого происходит определенное для каждой логической операции нелинейное взаимодействие потоков информации друг с другом и их преобразование. В зависимости от типа выполняемой операции определенным образом изменяется состояние логического элемента, а поступающая на его входы информация либо передается далее, либо как-то преобразуется (инвертируется, записывается, стирается и т.д.). Соот-
Введение
13
ветствующие процессы происходят на физическом уровне с носителями информации — сигналами.
Беспрецедентные успехи в развитии полупроводниковой микроэлектроники, непрерывно продолжающиеся начиная с изобретения первого планарного транзистора в 1959 году, наиболее наглядно выражаются так называемым «законом Мура» (G. Moore), согласно которому число транзисторов в кристалле одной интегральной схемы (ИС) в течение первых 15 лет удваивалось каждый год, а затем и до сих пор такое удвоение происходит за 1,5 года. По экспоненциальному закону уменьшаются со временем и характерные размеры элементов ИС (в два раза за каждые 1,5 года).
Если самые первые кремниевые ИС изготовлялись с минимальными размерами элементов в плоскости кристалла в несколько десятков микрон, то современная полупроводниковая технология на основе использования оптической, электронной и рентгеновской литографии, сфокусированных ионных пучков позволяет в ряде случаев получать структуры с горизонтальными размерами менее 100 нм, а методы молекулярной эпитаксии обеспечивают уверенный контроль по составу и толщине слоев в 1-10 нм. В конце 1999 года появилось сообщение о создании инженерами Калифорнийского университета в Беркли на островке кремния в форме плавника МОП-транзистора с рекордно малой длиной затвора в 18 нм. В перспективе возможно и дальнейшее продвижение в область малых горизонтальных размеров вплоть до структур, построенных из отдельных атомов или молекул на основе новых методов так называемой нанотехнологии с использованием, в частности, сканирующего туннельного микроскопа (СТМ) в совокупности с методами химического осаждения, применением химического синтеза и методов молекулярной биологии. Эти методы позволили приступить к созданию устройств наноэлектроники и молекулярной электроники. При этом компьютеры остаются классическими, поскольку, несмотря на то, что в отдельных элементах существенную роль начинают играть сугубо квантовые эффекты, такие как размерное квантование в низкоразмерных структурах, баллистический режим переноса носителей, кулоновская блокада, интерференция электронных волн в квантовых нитях, они по-прежнему обрабатывают информацию, передаваемую некогерентными сигналами, носителями которых являются токи и напряжения.
В случае классических компьютеров исключительно важной яв-
14
Введение
ляется проблема уменьшения рассеиваемой энергии в процессе вычислительных операций. Мысль о возможности «логически обратимых» операций, не сопровождающихся рассеянием энергии, впервые высказал Р. Ландауер в 1961 году [1]. Существенный шаг в решении этой проблемы был сделан в 1982 году Ч. Беннеттом [2, 3], который показал, что универсальный цифровой компьютер типа вычислительной машины Тьюринга может быть построен на логически и термодинамически обратимых вентилях таким образом, что энергия будет рассеиваться только за счет необратимых периферийных процессов ввода информации в машину и, соответственно, считывания результата вычислений на выходе. Типичными классическими обратимыми универсальными вентилями являются вентили Фредкина и Тоффоли.
Идея квантовых вычислений, по-видимому впервые высказанная Ю.И.Маниным в 1980 году [4], стала активно обсуждаться в мире с 1982 года, после опубликования статьи американского физика-теоретика, нобелевского лауреата Р. Фейнмана [5]. Эти авторы обратили внимание на то, что каждое состояние квантовой системы из L двухуровневых квантовых элементов (позднее они получили наименование кубитов (quantum bits)), в отличие от классической, может находиться в некоторой когерентной суперпозиции из 2Ь булевых состояний, то есть характеризуется вектором состояния в 2ь-мер-ном гильбертовом пространстве. Для описания такой квантовой суперпозиции в классическом вычислительном устройстве потребуется задать 2Ь комплексных чисел, то есть понадобятся экспоненциально большие вычислительные ресурсы. Уже для L = 100 их число исключительно велико — порядка Ю30! Отсюда делается обратный вывод о том, что эффективное моделирование квантовых систем, содержащих до сотни двухуровневых элементов, практически недоступно классическим компьютерам, но может эффективно осуществляться на основе использования соответствующих квантовых логических операций, которые действуют в 2^-мерном гильбертовом пространстве состояний, и этим принципиально отличаются от операций над булевыми состояниями [6, 7].
Перспективы квантовых вычислений обычно связывают с ожидаемым экспоненциальным ускорением решения так называемой NP-полной (Nondeterministic polynomial-time complete) проблемы, то есть проблемы решения таких задач, для которых очень трудно это решение найти, но очень просто его проверить. Такие задачи относятся к классу невычисляемых задач в том смысле, что они не могут быть решены
