?

Log in

No account? Create an account

eslitak

Previous Entry Поделиться Next Entry
11:16 pm: Квантовый ликбез 22. Классическое вычисление.
Предыдущие посты

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


Что такое вычисление, если сказать в самом общем виде? Это преобразование исходных чисел в результат по определённым правилам. Исходя из этого принципа мы можем представить себе компьютер как устройство, имеющее в составе:


- ячейки памяти для хранения исходных чисел и результатов вычисления;

- вычислитель, совершающий ряд операций с ячейками памяти по строго определённый программе.

Пусть нам надо, например, найти сумму двух чисел x + y . Тогда мы настраиваем (программируем) вычислитель на расчёт суммы, затем записываем во «входные» ячейки памяти значения чисел x, y и нажимаем кнопку «пуск». Вычислитель обрабатывает полученные данные согласно загруженному алгоритму, записывает результат в «выходную» ячейку памяти и зажигает лампочку «готово». Теперь нам остаётся только прочитать результат из выходной ячейки. Попутно замечу, что «выходными» и «выходными» могут быть одни и те же физичекие ячейки памяти. Например, мы можем загрузить числа x и y в ячейки памяти №1 и №2 и запрограммировать вычислитель таким образом, чтобы результат записался в ячейку №1. Тогда в этом конкретном примере нам достаточно всего двух ячеек памяти для «входа» и «выхода». В зависимости от того, как организована программа вычислений, могут понадобиться также дополнительные ячейки для хранения промежуточных результатов. Короче, суть работы компьютера заключается в том, что он совершает определённый (программой) набор операций с группой ячеек памяти. Эту группу ячеек памяти, необходимых компьютеру для вычислений, будем называть – «регистр». Подчёркиваю существенный момент: под регистром мы здесь подразумеваем только ячейки, необходимые для хранения входных, выходных и промежуточных данных. Та память, где хранится программа вычислений, нас сейчас не интересует.

Теперь поговорим о том, что такое, собственно, ячейка памяти. Это некий физический объект, способный находиться в одном из нескольких устойчивых и хорошо различимых состояний. Ячейки памяти имеют вполне конкретную информационную ёмкость, которая определяется как раз количеством устойчивых состояний. Минимальная, элементарная ячейка памяти – это физический объект с двумя состояниями, способный хранить один бит информации. Просто для примера: битом памяти может служить лежащая на столе монета (два состояния – «орёл», «решка»), выключатель (включено/выключено), стакан (полный/пустой) и так далее. Именно такие элементарные ячейки памяти – биты – используются в подавляющем большинстве современных компьютеров. Ну не монеты и стаканы, конечно, а специальные электронные штучки.

Мы собираемся что-то вычислять, а стало быть, нам нужно хранить в памяти числа. Если говорить о числовой ёмкости бита, то он способен «запомнить» лишь одно из двух чисел. Ячейка памяти в два бита имеет уже четыре возможных состояния, и способна «запоминать», соответственно, одно из четырёх чисел. Три бита – восемь состояний, четыре бита – шестнадцать  состояний и так далее. Обобщённо, количество возможных состояний регистра памяти, состоящего из элементарных ячеек – битов, равняется 2n, где n – количество битов. Это всё к тому, что дальше мы будем измерять размер регистра не в количестве ячеек памяти, выделенных для хранения отдельных чисел, а в количестве битов. Это удобнее, ведь количество битов – это универсальный показатель, в то время как распределение памяти под числа зависит от конкретной задачи и «произвола» программиста. В нашем примере с суммированием мы могли бы поступить так: взять восемь битов для хранения числа x и результата вычислений, восемь – для числа y. Итого размер регистра составил бы 16 битов.

Значит, работаем с битовыми регистрами. Бит памяти, как мы выяснили, может находиться в одном из двух состояний. Чтобы эти состояния как-то различать, обозначим их как «0» и «1». Таким образом, одиночный бит может представлять одну двоичную цифру, или один значащий разряд двоичного числа. Два бита позволяют разместить двухразрядное двоичное число (сюда вписываются все целые числа от нуля до трёх включительно). Три бита - трёхзначное двоичное число (от нуля до семи) и так далее.

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

Какие вообще возможны операции? Если взять одиночный бит, то тут только два варианта.

Вариант 1:

можно «перевернуть» состояние ячейки. Если бит изначально находится в состоянии "0", то операция инвертирования меняет это состояние на "1". И наоборот, "1" инвертируется в "0". Дальше нам придётся пользоваться логическими схемами, вот и начнём с простейшей. Операцию инвертирования изобразим следующим образом:



Слева – начальное (входное) состояние, справа – конечное (выходное) состояние, посредине – символ операции инвертирования «NOT». Надпись «№1» просто обозначает номер бита в регистре. Для однобитной операции его можно было бы и не указывать, но на будущее пригодится.

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

В классической и квантовой логике простейшие операции принято называть «гейтами». Так и будем говорить: в данном случае мы использовали гейт «NOT»

Вариант 2: не делать с битом ничего. Да, да, формально такая операция тоже существует. Математическим аналогом такой операции является умножение на единицу.

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



Следующая операция инвертирует оба бита:



В этих операциях, как мы видим, каждый бит, независимо от «партнера» подвергается (или не подвергается) однобитной операции инвертирования. То есть, никакого взаимодействия состояний битов между собой тут не происходит. По сути дела, это не двухбитный гейт, а два однобитных гейта, действующих параллельно и независимо друг от друга.

Теперь рассмотрим двухбитный гейт, который называется «AND» - логическое «И». Математический смысл операции в следующем: результат операции равен единице в том и только в том случае, если оба бита равны единице. Для этой операции требуется два входных бита и один выходной бит. Можно организовать эту операцию, имея в распоряжении всего два бита:



Эту схему надо понимать так, что результат операции записывается в бит №2. Состояние бита №1 влияет на результат, но само оно в ходе операции не изменяется.

Всего возможны 16 различных двухбитных гейтов, но нам нет резона все их тут разбирать. Потому что, имея в распоряжении только два гейта – «AND » и «NOT», можно, комбинируя их определённым образом, реализовать любой другой гейт или вообще построить  вычислительную схему любой сложности. В этом смысле гейты «AND» и «NOT» составляют полный вычислительный базис. Но следует отметить один важный момент: в квантовой логике, которую мы будем дальше изучать, допустимы исключительно ОБРАТИМЫЕ операции. То есть такие, которые после их применения позволяют восстановить исходное состояние битового регистра. Однобитная операция «NOT» является, конечно, обратимой. А вот двухбитная операция «AND» - не является. Смотрите, если у нас на входе гейта «AND» (рисунок 22.4) вот такая комбинация:

№1 = 0
№2 = 0

Или вот такая:

№1 = 0
№2 = 1

То в обоих этих случаях на выходе будет:

№1 = 0
№2 = 0

Таким образом, результат операции мы аккуратно получаем, но информацию об исходном состоянии бита №2 теряем безвозвратно.

Примером обратимой операции является двухбитный гейт «CNOT» (Controlled-NOT). Квантовый гейт такого типа мы уже применяли в процессе телепортации, и ещё не раз он нам встретится. Но пока взглянем на классический гейт «CNOT».



Состояние контроллирующего бита №1 в результате такой операции не изменяется. А состояние «рабочего» бита №2, там, где такой кружок с плюсиком внутри, изменяется только в том случае, если бит №1 находится в состоянии «1». Чтобы обратить результат действия этой операции, достаточно просто применить её ещё раз.

Следующим шагом рассмотрим трёхбитный гейт «CCNOT» (Controlled-Controlled-NOT).



Здесь имеются два контролирующих бита, №1 и №2. Их состояние в результате операции не меняется. Состояние контролируемого бита №3 изменяется только тогда, когда оба контролирующих бита находятся в состоянии «1». Гейт «СCNOT» также является обратимым. Более того, он сам себе  полный базис: можно построить любое вычисление имея в распоряжении только гейты типа «СCNOT». Для примера на рисунке 22.7 показан процесс вычисления суммы двух двоичных цифр исключительно с помощью гейтов «СCNOT».



Перед началом вычисления бит №1 устанавливаем в состояние «1», бит №4 - в состояние «0». Биты №2 и №3 - это наши слагаемые двоичные цифры, условно обозначенные как «x», «y». В результате вычисления получается сумма в виде двухразрядного двоичного числа: младший разряд - бит №3, старший разряд – бит №4.

Для тех, кому не приходилось сталкиваться с двоичным исчислением, покажу соответствие между десятичными и двухразрядными двоичными числами, коих всего четыре:

0 - 00
1 - 01
2 - 10
3 - 11

Возможных вариантов суммирования двоичных цифр тоже четыре:

0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10

Если вам не ясно, как работает этот сумматор, тогда смоделируйте его «в натуре». В качестве битового регистра используйте, например, четыре выложенные в ряд монеты. Пусть «орёл» будет означать единицу, а «решка» –  ноль.

Перед началом вычисления монету №1 установите в состояние «1» (положите «орлом» вверх), монету №4 – в состояние «0» («решкой» вверх).  Монеты №2 и №3 будут символизировать слагаемые. Установите их в любую из четырёх возможных комбинаций.

Теперь поработайте сами в качестве трёхбитного гейта «СCNOT». Сначала применительно к монетам №2, №3, №4: только если и №2, и №3 (контролирующие биты) находятся в состоянии «1», переверните №4 (рабочий бит).

Затем применительно к монетам №1, №2, №3: только если и №1, и №2 (контролирующие биты) находятся в состоянии «1», переверните №3 (рабочий бит).

В результате этих двух элементарных операций в битах №3 и №4 сформируется искомая сумма. Проверьте!



На этом краткий курс классических вычислений мы заканчиваем и переходим к квантовым вычислениям.

Продолжение


Tags: ,
Разработано LiveJournal.com