Cтраница 3
Основной используемый конструктивный блок представляет собой массив гейтов, который берет число Ъ на входе, дает Ъ с ( mod n) на выходе. Заметим, что здесь b поступает в массив гейтов на вход, в то время как сип встроены в структуру массива квантовых гейтов. Так как сложение по ( mod n) вычислимо по классическим алгоритмам в O ( logn) шагов, такой обратимый массив квантовых гейтов может состоять только из O ( logn) гейтов и O ( logn) рабочих битов, используя методы, ранее описанные в этом разделе. [31]
Когда в гейте Sjtk разность k - j велика, см. (4.3), фазовый множитель домножается на очень маленькую величину. Фактически такое домножение будет трудно физически точно провести, и если бы это было необходимо делать при квантовых вычислениях, это стало бы серьезной помехой. К счастью, Копперсмит [ Coppersmith, 1994 ] показал, что можно ввести приближенное преобразование Фурье, в котором будут игнорироваться такие малые вклады в фазовый множитель, но такое приближенное преобразование Фурье вполне достаточно, чтобы также использовать его в алгоритме факторизации. В действительности, эта техника заметно уменьшает число квантовых гейтов, необходимых для проведения ( приближенного) преобразования Фурье, исключая большинство гейтов Sjtk - Недавно Гриффите и Ниу [1996] показали, что это преобразование Фурье может быть получено при использовании только однобитных гейтов при измерении еденичных битов. [32]
Первое является стандартным условием того, чтобы создание массива квантовых гейтов требовало полиномиального числа ( классических) шагов. Вторым может стать стандартная часть определения аналоговых классов сложности, хотя в силу того, что аналоговые классы сложности не так хорошо изучены, это требование не так широко известно. Это требование заключается в том, чтобы на вход гейтов, описываемых унитарными матрицами, подавались вычисляемые числа. Это предохраняет невычислимую ( или трудно вычислимую) информацию от потери ее битов, описываемых амплитудами квантовых гейтов. [33]
Требование того, чтобы преобразования векторов состояния соответствовали унитарным матрицам, гарантирует, что сумма вероятностей всех возможных исходов даст единицу. Определение квантовых схем ( и квантовой машины Тьюринга) разрешает только локальные унитарные преобразования; другими словами, унитарные преобразования только над фиксированным числом битов. Таким образом, системы двубитных преобразований формируют конструктивные блоки квантовых схем аналогично тому, как универсальные системы классических гейтов ( таких как AND, OR и NOT гейты) формируют конструктивные блоки классических схем. В действительности, в качестве универсальной системы квантовых гейтов достаточно иметь только однобитные гейты и очень простую разновидность двубитного гейта, контролируемого NOT ( также называемого XOR гейтом), который изменяет значение второго бита тогда и только тогда, когда значение первого равно единице. [34]
В этом разделе мы предлагаем посмотреть, как квантовые вычис-ения можно реализовать на практике. Подчеркнем, что по крайней мере на этих нескольких первых шагах необходимые операции связаны с хорошо известными процедурами в экспериментальной физике. В снове всей этой конструкции лежит кубит ( или квантовый бит) [5] - квантовая система, которая, как и обыкновенный компьютерный бит, имеет два возможных состояния, но, в отличие от обыкновенного бита, может находится в суперпозиции этих двух состояний. В физике известно много таких систем, однако здесь будет использована модель лементарной частицы со спином У2, такой, как электрон или протон. Как и в булевой логике, операции в квантовой логике будут строиться из небольшого набора квантовых гейтов, в которых состояния входных кубитов ( в последующих примерах один или два кубита) преобразуются вполне определенным бразом и покидают гейты в определенных конечных состояниях. В со-тветствии с законами квантовой механики изолированных систем, все возможные операции над этими системами являются унитарными операторами, описывающими эволюцию начального состояния квантовой системы. [35]