Сентябрь 2019 — Заметка №7

Я тут почитал про квантовые компьютеры и вроде понял основной принцип и почему они сулят крутое ускорение некоторых действий. Сильно-сильно упрощая, все работает вот так.

Вот есть обычные компьютеры. Они оперируют битами: 0 и 1. Над битами можно делать операции: NOT, AND, OR. Биты формируются в цепочки: байты (например “10001110”). В этом суть, из этих кирпичиков строится все остальное.

Квантовый компьютер оперирует не битом, а кубитом. Кубит это штука, которая может одновременно находится в двух состояниях: 0 и 1. Ну он как бы и одновременно и 0 и 1 и одновременно не 0 и не 1.

C одной стороны кубит может быть и просто 0 или 1 — они обычно обозначаются просто ∣0> и ∣1> (по факту можно считать, что это те же 0 и 1). Дальше я буду для простоты просто писать 0 или 1. Но также кубит может быть в состоянии α×0+β×1, то есть как бы и там и там одновременно (α и β — числовые коэффициенты, например 0.6×0+0.8×1)

Также есть логические элементы, аналоги AND, OR, NOT — квантовые вентили (quantum gates). Например есть квантовый вентиль NOT, который работает так: NOT(0)=1, NOT(1)=0, NOT(α×0+β×1)=β×0+α×1.

Их на самом деле достаточно много разных, некоторые работают с одним кубитом (как NOT). Некоторые с двумя и тремя, меняют состояние кубита в зависимости от другого кубита. Главная суть: эти преобразования берут на вход кубит, как-то с ним работают и на выходе дают тоже кубит, но уже с другими α и β.

Особенность квантового компьютера в том, что пока он работает мы никак не может узнать какие там у этого кубита конкретные α и β. Согласно квантовой механике это невозможно. В момент же измерения наблюдатель воздействует на систему и она схлопывается. Кубит α×0+β×1 с вероятностью α² будет в состоянии 0 и с вероятностью β² в состоянии 1.

То есть квантовое преобразование меняет вероятность нахождения кубита в том или ином состоянии.

Теперь все как это вместе работает. Чуваки берут и выставляют кубит (или несколько) в исходное значение. Например в 0. Потом пропускают через набор разных квантовых вентилей (например превращая 0 в α×0+β×1), которые этот кубит (кубиты) модифицируют (мы не знаем точно как, не можем заглянуть в середину процесса). В самом конце происходит измерение, кубиты схлопываются и мы получаем конечный результат — это ответ c какой-то точностью.

Понятно, что там сложная математика, чтобы вот работая с вероятностями α×0+β×1 сложить например 5 и 7.

Все эти кубиты и квантовые вентили реализуются хитрыми физическими штуками связанные с электронами, ионами, светом и так далее.

Умная математика говорит, что

А быстрее получается, потому что все состояния в этих преобразованиях обрабатываются как бы одновременно. Вот допустим у нас есть классический компьютер и 8 битов. Их комбинации выглядят вот так:

00000000
00000001
00000010
…
01111111
11111111

Если мы хотим обработать каждый бит и каждую комбинацию, нам надо пройти через 2⁸ = 256 отдельных состояний.

Если же у нас квантовый компьютер и 8 кубитов, то каждый кубит одновременно и 0 и 1 (и не 0 и не 1). Получается:

0или1, 0или1, 0или1, 0или1, 0или1, 0или1, 0или1, 0или1

Система из 8 кубитов может быть с разной вероятностью одновременно в одном из 256 классических состояний. Но вот преобразования в квантовом компьютере можно делать сразу над кубитом, то есть как бы над всеми состояниями сразу. Там где классическая система работает над 2 состояниями, квантовая работает с 1 кубитом. Классическая работает с 256 состояниями (2⁸), квантовая с 8 кубитами. Классическая работает с 1267650600228229401496703205376 состояниями (2¹⁰⁰), а квантовая всего со 100 кубитами. То есть все круто параллелизируется.

Всей этой штуке лет 50 всего, достаточно недавно появились теории и математические обоснования. (как только выяснилось, что можно шифры вскрывать быстрее — стали сильно энергичней заниматься). И вот уже Гугл пишет, что сделал компьютер на 52 кубитах. Короче мы как в 40-х при зарождении компьютерной эры — теория есть, дело за имплементацией. Наверное еще лет через 20-30 это прям многое измененит (супер-крутое моделирование молекул для нахождения новых лекарств, AI и моделирование мозга и тд).

Кому интересно подробнее можно почитать например Quantum computing for the very curious и потом Scott’s Supreme Quantum Supremacy FAQ.