Квантовые компьютеры. Квантовый компьютер – гипотетическое вычислительное устройство, которое с помощью квантовых алгоритмов

Квантовый компьютер – гипотетическое вычислительное устройство, которое с помощью квантовых алгоритмов, использую квантовые эффекты (квантовый параллелизм или квантовая запутанность).

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

Квантовая запутанность (квантовая суперпозиция) – на примере. Атом мог подвергнуться радиоактивному разложению за период времени. Или не мог. Мы можем ожидать что есть два возможных состояния – распад и нераспад. Но в квантовой механике подразумевается третье состояние – суперпозиция («распад-нераспад»).

Идея квантовых вычислений следующая (впервые высказана Ю.И. Маниным и Э. Фельдманом): если квантовая система состоит из L двухуровневых элементов (т.н. квантовых битов или кубитов), то она имеет 2^L линейно-независимых состояний. Т.о. квантовое ВУ L-кубит может выполнить 2^L параллельных операций.

Кубит (q-bit, quantum bit) – наименьший элемент для хранения информации в квантовом компьютере. Допускает два состояния, но может находиться в состоянии суперпозиции. В общем случае состояние кубита оценивается формулой |A|^2 + |B|^2 = 1, где А и В – комплексные числа. При любом измерении состояния кубита, он случайно переходит в одно из состояний. Кубиты могут быть запутаны друг с другом, т.е. при всяком измерении над одним или несколькими кубитами, остальные изменяются вместе с ними. Т.о. можно представить, что последовательность кубитов может интерпретироваться как квантовый регистр. Кроме того, кубиты могут обмениваться состоянием друг с другом и преобразовываться в зависимости от этого, т.е. возможно создать компьютер, способный к параллельным вычислениям на уровне своей физики и проблемой остается только конечный результат.

Следует отметить, что не все вычисления (например, доступные для фоннеймановской машины) могут быть преобразованы в квантовые. Оказывается, что квантовые компьютеры позволяют расшифровать сообщения, зашифрованные при помощи алгоритма RSA.

Т.к. квантовый компьютер – гипотетическое образование, оно не имеет размеров, его можно телепортировать по каналам связи («квантовая телепортация»).

Упрощенная схема вычислений выглядит так. Берется система кубитов, на которой записывается начальное состояние. Затем состояние системы изменяется посредством базовых квантовых операций и в конце измеряется. Получаем результат решения.