Квантовый бит
С каждым годом компьютеры становятся быстрее и быстрее, а их структурные элементы - все меньше и меньше. Если темпы миниатюризации будут оставаться неизменными ближайшие 10-20 лет, то структурные элементы уменьшатся настолько, что должны будут описываться законами квантовой физики. Это, с одной стороны, потребует коренного пересмотра существующих принципов работы компьютера, а с другой стороны, открывает новые возможности.
Фундаментальная единица информации - бит. Обычный (классический) бит может принимать два значения: 0 или 1. Иначе говоря, с помощью одного бита можно закодировать два различных состояния. С помощью двух битов можно закодировать 4 раличных состояния: 00, 01, 10, 11. С помощью трех битов - 8 различных состояний: 000, 001, 010, 011, 100, 101, 110, 111. С помощью 8 бит (то есть 1 байта) - 256 различных состояний: от 00000000 до 11111111.
Когда мы измеряем значение классического бита, оно всякий раз получается одним и тем же. Если в бите единица, то мы видим единицу, если ноль, то видим ноль. С квантовым битом все иначе. Один и тот же квантовый бит при измерении может давать то ноль, то единицу. У разных квантовых битов лишь разные вероятности наблюдения 0 и 1.
Например, квантовый бит в состоянии
|ψ> = 0.6 |0> + 0.8 |1>
будет при измерении давать 0 с вероятностью 0.36 и 1 - с вероятностью 0.64.
Вообще же любой квантовый бит можно представить как сумму
|ψ> = a0 |0> + a1 |1>,
где a0 и a1 - произвольные числа между 0 и 1, связанные соотношением, сумма квадратов которых равна 1, a0^2 - вероятность наблюдать 0, a1^2 - вероятность наблюдать 1.
Сколько информации содержится в одном квантовом бите? Казалось бы, если a0 - любое число между 0 и 1, то в него можно записать сколько угодно информации просто добавляя "знаки после запятой". В действительности это не совсем так: из-за квантового шума точность коэффициентов a0 и a1 ограничена. Тем не менее, информации в квантовом бите содержится явно больше, чем в классическом бите. Условимся считать, что в одном квантовом бите содержится один байт информации.
Сколько информации содержится в двух квантовых битах? Квантовый регистр из двух квантовых битов будет иметь вид:
|ψ> = a00 |00> + a01 |01> + a10 |10> + a11 |11>.
Имеем четыре коэффициента - значит, в двух квантовых битах содержится четыре классических байта.
Квантовый регистр из трех квантовых битов имеет вид
|ψ> = a000 |000> + a001 |001> + a010 |010> + a011 |011> + a100 |100> + a101 |101> + a110 |110> + a111 |111>
Значит, в 3 квантовых битах 8 классических байтов!
В 10 квантовых битах - 1024 классических байта.
В 20 квантовых битах - 1048576 классических байта, то есть целый мегабайт информации!
В 100 квантовых битах - 2^100 классических байта. Это - порядка 2000000000000000000000000000000000 байтов, в каких-то 100 квантовых битах!
При всем при этом, если мы произведем с состоянием |ψ> какое-то действие, все коэффициенты a000, a001 и т.д. будут обрабатываться одновременно. Время выполнения операции с 2^N байтами (N квантовыми битами) - 1 вместо 2^N на классическом компьютере.
Но все не так радужно, как может показаться из этих рассуждений. Проблема - в измерениях, мы не можем измерить коэффициенты a000, a001 непосредственно, всякий раз при измерении мы получаем 000, 001 и т.п., разные состояния квантового регистра отличаются лишь вероятностями получить тот или иной результат. Тем не менее, при должном хитроумии мы можем научиться использовать это огромное количество информации. Этим пользуется алгоритм факторизации Шора, алгоритм поиска Гровера, квантовое преобразование Фурье. Гипотетическая выгода во времени от использования квантовых вычислений огромна.
Фундаментальная единица информации - бит. Обычный (классический) бит может принимать два значения: 0 или 1. Иначе говоря, с помощью одного бита можно закодировать два различных состояния. С помощью двух битов можно закодировать 4 раличных состояния: 00, 01, 10, 11. С помощью трех битов - 8 различных состояний: 000, 001, 010, 011, 100, 101, 110, 111. С помощью 8 бит (то есть 1 байта) - 256 различных состояний: от 00000000 до 11111111.
Когда мы измеряем значение классического бита, оно всякий раз получается одним и тем же. Если в бите единица, то мы видим единицу, если ноль, то видим ноль. С квантовым битом все иначе. Один и тот же квантовый бит при измерении может давать то ноль, то единицу. У разных квантовых битов лишь разные вероятности наблюдения 0 и 1.
Например, квантовый бит в состоянии
|ψ> = 0.6 |0> + 0.8 |1>
будет при измерении давать 0 с вероятностью 0.36 и 1 - с вероятностью 0.64.
Вообще же любой квантовый бит можно представить как сумму
|ψ> = a0 |0> + a1 |1>,
где a0 и a1 - произвольные числа между 0 и 1, связанные соотношением, сумма квадратов которых равна 1, a0^2 - вероятность наблюдать 0, a1^2 - вероятность наблюдать 1.
Сколько информации содержится в одном квантовом бите? Казалось бы, если a0 - любое число между 0 и 1, то в него можно записать сколько угодно информации просто добавляя "знаки после запятой". В действительности это не совсем так: из-за квантового шума точность коэффициентов a0 и a1 ограничена. Тем не менее, информации в квантовом бите содержится явно больше, чем в классическом бите. Условимся считать, что в одном квантовом бите содержится один байт информации.
Сколько информации содержится в двух квантовых битах? Квантовый регистр из двух квантовых битов будет иметь вид:
|ψ> = a00 |00> + a01 |01> + a10 |10> + a11 |11>.
Имеем четыре коэффициента - значит, в двух квантовых битах содержится четыре классических байта.
Квантовый регистр из трех квантовых битов имеет вид
|ψ> = a000 |000> + a001 |001> + a010 |010> + a011 |011> + a100 |100> + a101 |101> + a110 |110> + a111 |111>
Значит, в 3 квантовых битах 8 классических байтов!
В 10 квантовых битах - 1024 классических байта.
В 20 квантовых битах - 1048576 классических байта, то есть целый мегабайт информации!
В 100 квантовых битах - 2^100 классических байта. Это - порядка 2000000000000000000000000000000000 байтов, в каких-то 100 квантовых битах!
При всем при этом, если мы произведем с состоянием |ψ> какое-то действие, все коэффициенты a000, a001 и т.д. будут обрабатываться одновременно. Время выполнения операции с 2^N байтами (N квантовыми битами) - 1 вместо 2^N на классическом компьютере.
Но все не так радужно, как может показаться из этих рассуждений. Проблема - в измерениях, мы не можем измерить коэффициенты a000, a001 непосредственно, всякий раз при измерении мы получаем 000, 001 и т.п., разные состояния квантового регистра отличаются лишь вероятностями получить тот или иной результат. Тем не менее, при должном хитроумии мы можем научиться использовать это огромное количество информации. Этим пользуется алгоритм факторизации Шора, алгоритм поиска Гровера, квантовое преобразование Фурье. Гипотетическая выгода во времени от использования квантовых вычислений огромна.