Размышления о думающих машинах. Тьюринг. Компьютерное исчисление

Также нужно уточнить, что двоичная система счисления (база два) оперирует двумя возможными символами, 0 или 1, а десятичная система (база десять) — десятью возможными символами (0, 1, 2,..., 9). Число в каждой системе счисления представляет собой комбинацию символов. Так как двоичная система является внутренним языком компьютеров, преобразование чисел из одной системы в другую является обычной практикой. Для перевода двоичного числа в десятичный вид необходимо представить это число как сумму произведений последовательных степеней основания двоичной системы счисления (2) на соответствующие цифры в разрядах двоичного числа справа налево. Так, если в двоичной системе перед нами число 1011, мы действуем следующим образом: первый знак 1 справа умножаем на 2° (нулевая степень любого числа равна единице), следующий знак 1 умножаем на 20 знак 0 — на 2², знак 1 — на 2³. Теперь вычислим сумму полученного выражения 1 · 2³ + 0 · 2² + 1 · 2¹ + 1 · 20. Результат будет эквивалентным десятичным числом, в нашем случае — 11. На практике если двоичные числа состоят из четырех разрядов, результаты, полученные с помощью описанного метода, можно занести в таблицу.

Двоичная

0000

0001

0010

0011

0100

0101

0110

0111

Десятичная

0

1

2

3

4

5

6

7

Двоичная

1000

1001

1010

1011

1100

1101

1110

НИ

Десятичная

8

9

10

11

12

13

14

15

Как мы можем представить число в кубитах?

Например, нам нужно представить число 9 (схема 2). В двоичной системе его эквивалентом будет 1001, так как вычислив 1 · 2³ + 0 · 2² + 0 · 2¹ + 1 -20 (помним, что 20 = 1), получим 9.

Следовательно, |9 соответствует 11001. А число 8? |8) соответствует 11000. Это означает, что квантовый компьютер представляет числа 8 и 9 так же, как и обычный.

Однако он также может представлять и выполнять операции суперпозиции, например с |8 + |9.

РИС. 2

Теперь, когда мы попытаемся выяснить экспериментальными методами, в каком состоянии суперпозиции находится кубит из всех возможных состояний между 0 и 1, проявляется принцип интерференции, состоящий в том, что, как говорят квантовые физики, происходит коллапс кубита. То есть кубит превращается в классический бит, теряет состояние суперпозиции и принимает значение, равное 0 или 1. Это означает, что квантовый компьютер может выполнять операции согласно правилам квантовой механики, чем и объясняется его потенциал, при этом результат будет представлен пользователю, как и в обычном компьютере.

Еще одно явление, имеющее место в квантовых компьютерах, — квантовая запутанность частиц. Согласно этому свойству, можно получить пару фотонов, находящихся в запутанном состоянии, так что изменение одного фотона повлияет на другой. Этот феномен очень важен для квантовых вычислительных машин и применяется в криптографии — области, в которой Алан Тьюринг преуспел во время работы в Блетчли- парке.

У нас есть два кубита, которые обозначим А и В, в состояниях 0 и 1. Представим их, согласно системе счисления, в виде |0A и |1B соответственно. Если они запутаны, нужно использовать символ ®, применяемый в математике для обозначения операции тензорного произведения, как показано далее:

В предыдущем выражении 1/2

является величиной от применения тензорного произведения к системе из двух кубитов. Не вдаваясь в детальные объяснения, можно сказать: предполагается, что кубиты находятся в так называемом гильбертовом пространстве — обобщении евклидова пространства. Возведя эту величину в квадрат:

(1/2)2,

получаем 1/2. Это позволяет измерить состояния в квантовом эксперименте и получить результаты |01 или |10.

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

РИС.З

В данном эксперименте интересно то, что если, например, Алан первым измерит состояние своего кубита (А), он узнает, что оно равно |0A или |1A, и вероятность того и другого события, как и при подкидывании монетки, составляет 50%. Однако фантастический аспект квантового исчисления состоит в том, что измерение Аланом кубита станет причиной коллапса, который произойдет после выяснения его состояния. В результате для Эндрю, находящегося в другой комнате, учитывая, что кубиты запутаны, эксперимент потеряет характер случайности. Если теперь Эндрю все же будет измерять свой кубит (В), результат его наблюдений заведомо известен. То есть для Эндрю результаты эксперимента уже не эквивалентны подбрасыванию монетки, так как в 100% наблюдений он получит результат, обратный результату Алана (схема 3). Например, если Алан увидел, что запутанный кубит А находится в состоянии |0A, произойдет коллапс пары кубитов |0A и |1B. Если же Алан увидел обратную ситуацию, а именно что А находится в состоянии |1A, тогда произойдет коллапс пары кубитов |1A и |0B. То есть измерения, проведенные Аланом, «изменили» кубиты таким образом, что однозначно определили наблюдения Эндрю.