Гейт
Cтраница 2
Главная проблема с этим гейтом заключается в том, что он требует три бита на входе и три на выходе. [17]
 |
Диаграмма квантового цикла для XOR-гейта. Низший бит В инвертируется всякий раз, когда верхний бит А является единицей. [18] |
Здесь первая частица действует как условный гейт для инвертирования состояния второй частицы. [19]
Для небольших чисел лучшим массивом гейтов, осуществляющих умножение, по существу является тот, который реализует элементарное перемножение бинарных чисел на бумаге, которому учат в школе. Этот метод требует 0 ( / 2) шагов для перемножения двух / - битных чисел, и, следовательно, возведение в степень по модулю требует О ( 13) шагов в соответствии с этим методом. [20]
Заметим, что выбор последовательности гейтов ( логической цепи) как классической модели вычисления существенен в следующем смысле: квантовая программа не может использовать условных команд. Действительно, для того, чтобы выполнить такую команду, нам надо наблюдать память в середине вычисления, но наблюдение в общем случае изменит текущее квантовое состояние. [21]
Тем не менее, использование двубитных гейтов все же необходимо в течение шага факторизации по возведению в степень по модулю и алгоритмов вычисления дискретных логарифмов. [22]
По этому алгоритму можно построить массив гейтов, выполняющих умножение целых чисел, использующий O ( l log / log log /) гейтов для перемножения двух / - битных чисел. Таким образом, асимптотически возведение в степень по модулю требует О ( / 2 log / log log. [23]
Эти рассуждения легко перенести на случай нетривиального гейта. [24]
Основной используемый конструктивный блок представляет собой массив гейтов, который берет число Ъ на входе, дает Ъ с ( mod n) на выходе. Заметим, что здесь b поступает в массив гейтов на вход, в то время как сип встроены в структуру массива квантовых гейтов. Так как сложение по ( mod n) вычислимо по классическим алгоритмам в O ( logn) шагов, такой обратимый массив квантовых гейтов может состоять только из O ( logn) гейтов и O ( logn) рабочих битов, используя методы, ранее описанные в этом разделе. [25]
Этот псевдокод может быть легко реализован через массив гейтов. Для того чтобы это сделать, нам необходимо использовать довольно сложный массив гейтов в качестве подпрограммы. Напомним, что х2 mod n может быть классически вычислена и после этого встроена в структуру квантовых гейтов. К счастью, этот случай нам и нужен для алгоритма факторизации. [26]
Однако, в принципе, многие из этих гейтов могли бы работать параллельно. Если предположить, что квантовое оборудование высоко параллелизуемо, то время вычислений слабо зависит от размера блока. [27]
Сложность рассматриваемого квантового вычисления определена его длиной ( числом гейтов т) и сложностью каждого из них. Последний пункт содержит тонкость: непрерывные параметры, например, фазовые сдвиги, от которых может зависеть С /, делают объем информации каждого Ui потенциально бесконечным и приводят к подозрению, что квантовый компьютер будет в действительности выполнять аналоговое вычисление, лишь реализованное иначе. Очень интересное обсуждение этого в [ Ts ] ( лекция 9) убедительно отвергает эту точку зрения демонстрацией тех черт квантового вычисления, которые отличают его как от классической аналоговой, так и от классической цифровой обработки информации. Это обсуждение основано на технике вычислений, устойчивых к сбоям с использованием квантовых кодов для создания непрерывных переменных в высокой степени защищенных от внешнего шума. [28]
Фактически для того, чтобы переработать классический алгоритм ( последовательность булевых гейтов) для вычисления F в квантовый, мы заменяем каждый классический гейт соответствующим обратимым квантовым гейтом, т.е. унитарным оператором, соответствующим ему в тензорной форме. Кроме двух регистров для хранения х) и F ( x)) этот трюк также вводит дополнительные кубиты, в которых мы практически не заинтересованы. Более детально этот вопрос рассмотрен в следующем разделе. [29]
Даже если трудно улучшить указанную величину ошибки порядка 10 - 6 на гейт, устройство, которое приближается к этому уровню точности, уже может быть пригодным для настоящих крупномасштабных квантовых вычислений. [30]
Страницы: 1 2 3