Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
незначительный эффект интерференции, который приводит к следующему
преобразованию
___________________________Ца\в) = \Щв + ф)), (41)
4Т. е. задач типа "NP", для которой сложно найти решение, но легко
проверить правильность какого-либо предложенного решения.
7.3. Алгоритм поиска Гровера
77
где sin 0 = 2\/N - 1/N. При этом коэффициент при определяемом элементе
принимает несколько большее значение, чем коэффициенты при остальных
составляющих. Суть данного метода заключается в повторении преобразования
Ug тп раз, где т ~ (п/4)\/N. Вследствие медленного вращения значение 9
неограниченно приближается к 7г/2, и поэтому квантовое состояние почти
абсолютно становится равным |j). После 771 повторений результатом
измерения состояния становится величина j (вероятность ошибки равна
0(1/N)). Следует отметить, что важно изначально определить значение тп
(это было сделано Бойером (Boyer et. at. 1996)), поскольку при увеличении
числа повторений вероятность верного решения задачи снижается. Кристен
Фачс (Kristen Fuchs) сравнивает данный метод с приготовлением суфле:
состояние помещается в "квантовую печь", и правильный ответ начинает
медленно "приготавливаться". Важно вовремя, не слишком рано и не слишком
поздно, открыть печь. В противном случае приготовление суфле окончится
неудачей - квантовое состояние станет ошибочным.
Два представленных алгоритма очень просты в описании. С их помощью можно
проиллюстрировать разнообразие методов квантовых вычислений. Однако
вопрос о существовании других методов остается открытым. Китаев (Kitaev
1996) показал решение задачи разложения на множители и сопутствующих ей
посредством методики, фундаментально отличающейся от методики Шора. Метод
Китаева был любезно уточнен Джозса (1997), который также показал общие
черты нескольких квантовых алгоритмов, основанных на преобразовании
Фурье. Таким образом, инструментарий квантового программиста постепенно
увеличивается. Однако с уверенностью можно сказать, что класс задач, для
которых квантовый компьютер окажется предпочтительнее классического,
будет особым и, следовательно, небольшим. С другой стороны, любая задача,
решение которой сложно найти, но легко проверить, может, по крайней мере,
быть решена путем утомительного поиска данного решения. В этом случае
алгоритм Гровера может очень пригодиться.
Глава 8
Экспериментальные процессоры, оперирующие квантовой информацией
За последние 50 лет в различных физических экспериментах были показаны
наиболее элементарные квантовые логические операции. Например, операция
НЕ (X) есть не что иное, как вынужденный переход между двумя
энергетическими уровнями |0) и |1). Имеющая определенное значение
операция XOR может быть определена как управляемый переход в
четырехуровневой системе. Однако для рассмотрения работы квантового
компьютера необходимо найти систему достаточно управляемую, чтобы в
нужный момент задействовать какой-нибудь квантовый логический гейт, и
достаточно сложную, чтобы хранить определенное количество кубитов
квантовой информации.
Поиск таких систем очень сложен. Можно надеяться создать квантовые
устройства на основе твердых микросхем. Это явилось бы логическим
следствием развития технологии микропроизводства, которая привела к
появлению современных мощных компьютеров. Однако квантовые вычисления
опираются на сложные интерференционные эффекты и основной трудностью, с
которой приходится сталкиваться при их реализации, являются помехи. Ни
одна квантовая система не может считаться абсолютно изолированной, а ее
взаимодействие с окружающей средой ведет к потере когерентности и, как
следствие, к нарушению квантового вычисления. В твердых элементах роль
окружающей среды играет подложка, и взаимодействие с ней очень сильно.
Данное взаимодействие приводит к типичной потере когерентности через
интервалы времени порядка пикосекунд. Очень важно понять, что
недостаточно иметь два различных состояния |0) и 11), которые сами по
себе являются стабильными (например, состояния различных токов в
сверхпроводнике). Необходимо, чтобы при такой суперпозиции, как (0) Ч-11)
сохранялась фаза данных состояний. Однако именно в этом случае интервал
времени между потерями когерентности слишком мал.
8.1. Ионная ловушка
79
На сегодняшний день существует две перспективные системы, способные
реализовать квантовое вычисление для 10-40 кубитов. Первая система была
предложена Кираком и Золлером (Cirac and Zoller 1995) и заключается в
использовании ряда атомов, несущих единичный элементарный заряд,
помещенных в ионную ловушку и охлажденных в ее вакууме. Вторая система
была предложена Гершенфельдом и Чуангом (Gershenfeld and Chuang 1997)
одновременно с Кори (Cory et. al. 1996). Ее суть состоит в применении
методов объемного ядерного магнитного резонанса. Оба эти предложения
опираются на достойные восхищения усилия больших групп исследователей,
которые разработали экспериментальные методики. Одни, более ранние
