Подсказка
Часть 2. Биты, кубиты и прочая квантовая информация
И снова здравствуйте! В прошлом посте я криво и с опечатками попробовал рассказать немного про квантовую механику. Вы мои труды вниманием не обделили, спасибо за это. Покритиковали, вопросы позадавали, в общем, пост, что называется, зашёл. Меня попросили добавить мемов и убавить матана. На счёт матана не обещаю, но мемасиков я добавил.
В этом посте я, как и обещал, постараюсь уже чуть менее криво и без опечаток рассказать про квантовую информацию, что в ней есть и для чего она годится. Поехали.
На дворе шёл транзисторный 1980 год. Москва жила спокойной, мирной, застойной жизнью. Идиллию спокойного городского бытия нарушал только один профессор Московского университета, который порывался всё время что-нибудь посчитать. Вот и в этом году он думал, как бы так ловко взять и обсчитать какую-нибудь систему многих частиц и не умереть от старости в процессе. Профессор был прогрессивным, любил всё новое, читал журнал "Техника - молодёжи", а потому предложил изящное и смелое решение: нам нужны квантовые вычисления. Этим профессором был Альберт Эйнштейн Юрий Иванович Манин.
Для чего оно нужно? Давайте разбираться. Для начала поймём, как с тех пор и до наших дней большинство физиков решают численные задачи.
Численный расчёт - приближённое решение математической задачи путём арифметической работы со значениями функций - числами. Численный расчёт можно выполнить несколькими способами. Первый - собрать много девушек в одном месте и заставить с помощью таблиц сложения , умножения и счётов вычислять то, что нужно.
Однако это долго, дорого и нудно. Кто захочет считать одно и то же целыми днями? (хотя тогда у них особо выбора не было). Поэтому пришлось человечеству изобрести кое-что получше комнаты с женщинами и счётами (я не сексист и ничего не имею против счётов). Это что-то стали называть ЭВМ. Или компьютер. С тех пор (вернее около 40 лет спустя) жизнь у человечества забила ключом. То, что приходилось делать сотням людей напрягая мозг и тратя нервы, стали делать машины. Ну не чудо ли? Но с первых мгновений существования стало понятно, что у такого вычислителя есть принципиальные ограничения. Поглядим, как сие чудо техники работает и по сей день. Это нужно, чтобы понять, почему квантовые вычисления так всех возбуждают.
Ответственно заявляю, что в области классических компьютерных вычислений я являюсь антиспециалистом, по этому возможно всевозможное косноязычие, неточности , кровотечение в области глаз и разжижение мозга у ИТ-шников
Физическую сторону процесса я опущу, она всем знакома, а если нет, то она легко гуглится. Остановимся на принципиальной схеме. Основой хранения и обработки всего нужного нам с вами, учёным, в компьютере - это регистр. Например такой 4-х битный.
Ну, ясно дело, что нужен он для того, что бы туда что-нибудь двоичное число записать. Например, запишем туда число 2. (в том регистре мы тоже записали кое-какое число, попробуйте определить, какое)
Поздравляю! Мы с Вами почти программисты (нет) (ну кто-то, может, и да, но остальные, включая меня, нет). Чтобы стать совсем программистами, нам надо это число как-нибудь преобразовать, читай что-нибудь повычислять. Например, сложим нашу двойку с чей-нибудь ещё двойкой. (схема очень общая)
Конечно, возможны и другие операции с записанными в регистрах числами, но расписывать я это не буду, тем более, что большинство тут и так лучше меня всё про это знает. Отметим одну очень важную для нас деталь: состояние каждой ячейки (бита) регистра определено в каждый момент времени. Это принципиально для классических компьютеров.
-Ну, вроде, отлично - скажете вы - Что же ещё нужно? Наклепаем таких регистров, сделаем транзисторы меньше, регистры и вычислители больше, распараллелим что-нибудь, ядер побольше напихаем. Живём же?
- Да - скажу я - Живём. Но не полной жизнью, товарищи
Представим теперь, что есть у нас один регистр. Он состоит из 4-х битов (как до этого). Теперь все дружно вспоминаем комбинаторику (или гуглим её) и считаем, что всего различных комбинаций нулей и единиц - чисел то есть - может с четырьмя битами быть 2^4 =16
И правда, если перечислить, это 0000, 0001, 0010, 00... нечего нам казённую память тратить. как мы выясним, её у нас пока не так и много. напомню, что за один такт в регистре может находиться только одно число.
Теперь давайте как-нибудь число в регистре преобразовывать, например, находить значения целочисленной функции y=2*n. Означает это, что нам надо все возможные числа умножить на 2. И что же выходит? Нам надо проделать целых мать их 16 вычислений! Кажется не много? Тем более, битов-то мы уже наплодили, деть некуда. Но теперь представьте, что вычислять нам надо какие-нибудь системы уравнений с 100 неизвестными? Там, я вам доложу, к умножению на постоянную всё не сводится, там надо на сетку пространство разбивать, перебором каким-нибудь или секущими корни искать, девственниц в жертву IT-демону приносить. Не буду приводить расчёты (потому что сам их никогда не делал), но для решения системы 100 (а бывает и больше) диф.уравнений (например, для описания квантовых систем) сегодня может понадобиться 10^7 лет. А для разложения небольшого, всего из 400 цифр, числа на множители, потребуется 10^9 годиков. Как вам такое?
И самое обидное, что как ни старайся, бесконечно увеличивать мощность таких компов не возможно. С одной стороны невозможно бесконечное уменьшение транзисторов, так как на характерных размерах у же в 3 нм проявляются квантовые эффекты и т.н. кулоновская блокада (электрон не может пройти через транзистор, хотя ему уже пора). С другой стороны, бесконечно увеличивать мощности в ширь не только ограниченная скорость сигнала не позволяет, но и ограниченные финансы человечества.
Теперь уже суматошный московский профессор не кажется таким ненужным? Хотя, не станем забегать вперёд. Про квантовые вычисления-то мы не знаем ещё ничего...
И вот, движимые идеей что-нибудь посчитать до коллапса Вселенной, учёные стали думать. В кой-то веки. И придумали они квантовые вычисления. После того, как тов.Манин предложил считать не как в школе учили, а как надо, один сумрачный гений от мира квантов по имени Ричард и фамилии Фейнман предложил первую физическую модель такой ЭВМки. Про неё говорит не будем, ибо это долго и не про то.
Но давайте разберём, как квантовые вычисления устроены и чем они так хороши.
Все же знают, как образовалось слово бит? Кто нет, скажу: оно образовалось от двух слов binary digit (двоичное число, спасибо, вики). Но то в классике, у нас то всё квантовое. Ну, мы же теоретики, а не маркетологи, изощряться не будем. И просто единицу информации в квантовых вычислениях назовём квантовый (quantum) бит, или кубит. О них-то дальше речь и пойдёт.
Как можно догадаться, кубит выполняет в квантовом компьютере те же задачи, что бит в классическом, то бишь служит элементарной ячейкой памяти. Но тут есть принципиальное отличие: если бит может находиться одновременно только в одном состоянии, то кубит, в силу принципа суперпозиции, до того, как мы его померяем, находится одновременно в двух. В этом сила и слабость кубита.
Про силу
Вернёмся к нашим регистрам. Пусть теперь у нас есть 4-х кубитная система
И нам надо проделать с ней операцию. Например, опять вычислить значение функции y=2*n.
И опять тут у нас есть 2^4 = 16 возможных чисел в регистре. НО! Вы же помните, что каждый кубит, пока мы его не померили, находится в суперпозиции, то есть содержит и 0 и 1? И весь регистр, следовательно, тоже находится в суперпозиции, и содержит в себе одновременно 16 чисел. Сразу.
И тут мы подходим к самому вкусному. К квантовому параллелизму.
Так как в регистре записаны все числа одновременно, то проводя над ним операцию, мы преобразуем сразу все числа, которые содержит регистр. Делаем мы это параллельно. Убиваем все 16 зайцев, так сказать.
Это замечательно, но как же его, наш кантовый компьютер, программировать? Проще говоря, как на нём вычислять.
Тут, ребята, буде ещё чуть-чуть матана, кому не интересно, не читайте и сразу переходите к слабостям (Второй мемас после этой записи)
ВНИМАНИЕ! СЛЕДУЮЩИЕ ОБЪЯСНЕНИЯ СОДЕРЖАТ ЭКСПОНЕНЦИАЛЬНО БОЛЬШОЕ ЧИСЛО УПРОЩЕНИЙ, ДОПУЩЕНИЙ И НЕТОЧНОСТЕЙ! ЕСЛИ ВЫ БУДЕТЕ ТАК ОТВЕЧАТЬ НА ЭКЗАМЕНЕ, ВАМ В СУДЕБНОМ ПОРЯДКЕ ЗАПРЕТЯТ ЗАНИМАТЬСЯ КВАНТОВОЙ МЕХАНИКОЙ И ИНФОРМАТИКОЙ!!!
Помните, в прошлом посте мы говорили про состояния и про то, что они бывают базисные? так вот, 1 и 0 - это базисные состояния кубита. Запишем их так:
Эти треугольно-прямые скобочки называются кеты, а если они смотрят в другую сторону, то бра. Их придумал Дирак и они очень удобные, сейчас поймём почему.
К каждому нашему состоянию есть состояние сопряжённое, которое обозначается как раз с помощью бра.
Умножение состояния на своё или чужое сопряжённое справа называется скалярным произведением,и в результате мы получим просто число
Но не надо забывать, что состояния-то у нас базисные, а значит очень хорошие. Хорошесть их в том, что при скалярном произведении на само себя (первые две строки), получается единица, а если наоборот, то ноль
Но что же будет, если умножить состояние на сопряжённое не справа, а слева, то есть вот так?
Это уже называется внешнее произведение, и его результат - это оператор, потому что он производит операцию(в том числе и над нашими кубитами). Причём такое умножение на само себя, как в строке (1) даёт эрмитов оператор, то есть хороший, а произведение, как в строке (2) даёт, вообще говоря, неэрмитовый оператор, то есть не очень хороший.
Теперь нам осталось выяснить, чем же так хороши эти Дираковские обозначения? А тем, что они позволяют избегать матриц, интегралов, сверток, комплексной записи и много чего ещё.
Замечательно, мы овладели основами мат.аппарата квантовой механики и информатики. Теперь давайте уже вычислим чего-нибудь?
Представим теперь систему из двух вторых кубитов с помощью уже понравившихся нам обозначений
Здесь представлены все возможные состояния двух кубитов. Откуда взялись альфы и пр. - смотри прошлый пост, принцип суперпозиции.
А теперь составим простую логическую схему. Например: возьмём оператор, умножающий всё на единицу I, и оператор, превращающий нулевое состояние в единичное, а единичное в нулевое σ. На языке базисных состояний это выглядит так
Теперь возьмём два первых кубита, развернём их носами друг к другу, причём единицу к единице, а ноль к нулю. К нулям справа мы приставим I, а к единицам σ. Получим двухкубитный вентиль или гейт Control NOT (CNOT). Он и будет преобразовывать наши два последних кубита
Крестик в кружочке означает тензорное произведение. Тензорное произведение можно очень просто выразить через наши нули и единицы
Ну, теперь совсем всё просто и понятно. Видно, что наш CNOT - это такой вентиль, который содержит два входи и выхода. Один кубит (первый) - контролирующий (control), если он равен нулю, то второй кубит - контролируемый - остаётся таким же. А если контролирующий кубит равен 1, то контролируемый меняется на противоположный (операция NOT), потому вентиль так и называется: Control Not. Действительно, если у нас состояние
|0>|1>, то при умножении слева оно даст нули со всеми слагаемыми, кроме
|0>|1><0|<1|. Можете повычислять ради интереса остальные возможные двухкубитовые состояния. Я только отмечу ещё, что для того, чтобы построить любую логическую схему, достаточно вентиле CCNOT - то же, что и CNOT, только там два контролирующих кубита.
Ну я вас всех окончательно поздравляю! Теперь мы не просто программисты, а квантовые программисты! Ура, товарищи!
Обрадовались уже? А рано.
Про слабость
Принцип суперпозиции нам помог всё быстро посчитать. И он же, а точнее вытекающее из него свойство декогеренции, не позволит нам результаты из регистра извлечь.
Что такое декогеренция? Это то самое разрушение состояния квантовой системы при измерении. Ведь что бы нам узнать, что в итоге получилось, нам надо померить состояние регистра. А регистр-то квантовый, а значит как только мы один раз его померили, получив при этом одно число, мы навсегда избавились от остальных чисел, которые в нём были до измерения. То есть, сколько бы мы дальше регистр не мерили, получать будем одно и то же. Вот так. Как это обойти? Никак. Это штука непреодолима (кто-бы что не писал и какая-бы природа за ней не стояла). И что же делать? Зачем нам такой сложный и, главное, дорогой компьютер, если вся его польза съедается какой-то декогеренцией?
А вот съедается, да не до конца. Существуют алгоритмы, которые позволяют решать некоторые классы задач, которые не доступны классическим компьютерам, квантово. Вам уже интересно, что это за алгоритмы?(надеюсь, да). Но это, а так же как реализовать кубиты физически и, надеюсь, о том, как их реализовал товарищ Лукин в своём чуде, в следующем посте.
Поиграем в бизнесменов?
Одна вакансия, два кандидата. Сможете выбрать лучшего? И так пять раз.