Закон Мура, сформулированный одним из основателей фирмы Intel Гордоном Муром, гласил, что число транзисторов интегральной схемы удваивается каждые два года. Это возможно при условии уменьшения размеров транзисторов. В 2017 году этот размер имел порядок 10 нанометров, что соответствует слою толщиной не более 50 атомов. Уже при этих масштабах становятся существенными квантовые эффекты, такие как квантовые туннельные эффекты, когда частица преодолевает барьер, который, согласно законам классической механики, она преодолеть не может из-за нехватки энергии.
Очевидно, что, следуя траектории закона Мура, принятая парадигма построения архитектуры компьютера должна натолкнуться на непроходимую стену, поскольку размер транзистора не может быть меньше межатомного расстояния в кристалле. Более того при приближении к барьеру, квантовые эффекты становятся определяющими.
В нашей повседневной жизни мы имеем дело с объектами, состоящими из многих атомов (число атомов в одной песчинке составляет примерно $$10^{20}$$. В больших коллекциях атомов квантовые эффекты взаимно поглощаются и в результате для макроскопических объектов нет необходимости в учете законов квантовой механики. И все же в современных технологиях растет интерес к использованию квантовых эффектов, например, светодиодные фонарики работают на основе квантовых принципов.
Идея квантовых вычислений основана на том, что не следует сражаться с влиянием квантовых эффектов, - необходимо научиться использовать возможности квантового мира. Это не просто, но дает большие преимущества. Квантовые компьютеры - это устройства, которые используют квантовые системы в качестве процессоров.
Какие же возможности открываются при использования квантовых компьютеров? В сравнении с обычными компьютерами мы получаем:
А что же мы теряем при этом?
Квантовые компьютеры имеют серьезную теоретическую базу как в физике, так и в математике. Однако проблемы их создания остаются весьма сложными и здесь для достижения успеха требуется существенный технологический прорыв.
Необходим существенный прогресс и в разработке квантовых алгоритмов. К счастью, для выполнения этой работы нет необходимости иметь настоящий работающий квантовый компьютер. Здесь достаточно пера, бумаги и понимания теории квантовых вычислений.
Давайте же попытаемся понять разницу между классическими и квантовыми компьютерами. В классическом компьютере данные хранятся в памяти в виде последовательности 0 и 1. Минимальной единицей памяти является бит, и он может хранить либо ноль, либо единицу Для целей нашего обсуждения 0 и 1 следует рассматривать как символы.
Единица памяти квантового компьютера называется кубит, и он может хранить одновременно как 0, так и 1. Более точно, значение кубита можно рассматривать как вектор единичной длины на плоскости:
Для установления связи с классическим битом пометим горизонтальную ось символом 0, а вертикальную -1. Соответственно для единичных векторов, расположенных на наших координатных осях, будем использовать нотацию, традиционную для квантовой механики:
$$\mid 0 \rangle ={1\choose0}// \mid 1\rangle ={0\choose1}$$Тогда значение кубита может быть записано как:
$${a\choose b}=a \mid 0\rangle +b |1\rangle $$Значение кубита в этом случае можно интерпретировать как суперпозицию с весами а и b двух классических битов 0 и 1, где $$а^2 + b^2 = 1$$. Заметьте, что мы рассматриваем здесь $$|10\rangle $$ не как вектор длины 0, а как вектор единичной длины, расположенный на оси, помеченной символом "0".
Когда мы строим компьютер как физическую машину, нам необходимо использовать физические объекты, способные реализовать абстрактные конструкции бита и кубита. Конденсатор (электронное устройство, способное сохранять электрический заряд) может служить в качестве единицы памяти классического компьютера. Заряженное состояние конденсатора может рассматриваться как 1, а разряженное- 0.
Фотон может рассматриваться как физическая реализация кубита. Фотон - это квант электромагнитной волны. Представьте фотон, летящий в трехмерном пространстве вдоль оси Z. В процессе полета возникает колебание (осцилляция) электрического и магнитного полей во взаимно перпендикулярных направлениях в плоскости ХУ
Специфический способ проявления осцилляции называется поляризацией фотона. Существуют два возможных типа поляризация - круговая и линейная. При круговой поляризации при перемещении фотона направление электрического поля вращается в плоскости ХУ В этом курсе мы будем рассматривать только простейший случай линейной поляризации, когда электрическое поле осциллирует в фиксированном направлении перпендикулярно оси Z. Линейно поляризованные фотоны могут быть получены пропусканием светового потока через поляризационный фильтр.
Поляризованный свет используется в кинотеатрах 3D. Для создания 3D эффекта правый и левый глаз должны видеть слегка отличные картинки. Для этого фильм проецируется двумя камерами, разнесенными на некоторое расстояние. Изображение обеих камер одновременно проецируется на экран, но свет от двух проекторов поляризован различными способами. Очки для просмотра фильма имеют поляризационные фильтры, каждый из которых способен пропускать свет только от одного проектора. В результате два глаза получают различающиеся изображения, что и создает 3D эффект.
Вообразите, фотон с линейной поляризацией под углом а в плоскости ХУ Такой фотон может быть использован в качестве физической реализации кубита со значением
$$\cos(\alpha)|0\rangle+\sin(\alpha)|1\rangle $$Небольшое техническое замечание относительно положительного и отрицательного состояний фотона $$|0\rangle $$ и - $$|0\rangle $$. Оба состояния соответствуют фотону с теми же осями поляризации, однако осцилляция электрического поля для отрицательного состояния - $$|0\rangle $$ находится в противофазе относительно состояния $$0\rangle $$. Для одного фотона невозможно различить, в каком состоянии он находится, но для пары фотонов можно обнаружить разницу в фазах и рассматривать их состояния как два различных значений кубита.
Давайте перейдем теперь к рассмотрению множества кубитов - мультикубитам. 2-кубит - это вектор с четырьмя компонентами в форме:
$$а_0 |00\rangle + а_1|01\rangle + а_2 |10\rangle + а_3 |11\rangle ,$$
где $$а_0^2 + а_1^2 + а_2^2 + а_3^2 = 1$$. Базисные вектора в пространстве 2-кубитов: $$|00\rangle, |01\rangle, |10\rangle, |11\rangle $$, называемые также чистыми состояниями, соответствуют 4-м возможным состояниям пары классических битов. В общем случае значение 2-кубита представляет комбинацию значений 4-х классических битов. У каждого бита в этой комбинации есть свой весовой коэффициент. Эту комбинацию принято называть суперпозицией.
Например, 2-кубит $$0.3|00\rangle + 0.1|01\rangle + 0.9|10\rangle + 0.3|11\rangle $$ представляет суперпозицию 4-х классических значений, но 2-бит значение "10" в этой комбинации наиболее весомо.
Как вы уже могли догадаться, 3-кубит - это вектор с 8-мю компонентами:
$$а_0 |000\rangle + а_1 |001\rangle + а_2 |010\rangle + а_3 |011\rangle + а_4|100\rangle + а_5 |101\rangle + а_6 |110\rangle + а_7|111\rangle $$Обратите внимание на соответствие в нашей нотация между индексом коэффициента а и меткой, которой мы помечаем базисные вектора. Возьмем, например, терм (слагаемое) $$а_6|110\rangle $$ . Значение 110 в этом терме совпадает с двоичной записью значения индекса $$(6_{10} = 110_2)$$.
Нетрудно также заметить, что число термов удваивается при увеличении на единицу числа кубитов. Для 1-кубита термов - 2, для 2-кубита - 4, для 3-кубита- 8. В общем случае для N кубитов термов 2^N. Для 8-кубита тeрмов будет 256:
В качестве упражнения давайте определим индекс коэффициента "а" для терма с меткой $$|11010011\rangle $$. Каждая цифра в позиционной системе счисления является коэффициентом основания системы счисления в степени k,
где k - определяется позицией цифры. Для двоичной системы счисления основание равно 2, так что цифры 0 и 1- это коэффициенты при соответствующих степенях основания 2. Для 8-битного выражения самая левая цифра соответствует степени $$2^7$$, самая правая - $$2^0$$. Бинарное выражение "11010011" следует рассматривать как:
Аналогично, десятичный индекс 117 в двоичном 8-битном представлении имеет вид:
$$117=64+53=64+32+21=64+32+16+5=64+32+16+4+1 =// 0*2^7+1*2^6+1*2^5+1*2^4+0*2^3+1*2^2+0*2^1+1*2^0= 01110101 (binary).$$Для более компактной закиси мы иногда будем записывать 8-кубит в десятичной форме:
$$а_0 |0\rangle+ а_1 |1\rangle + а_2 |2\rangle +\dots + а_{255} |255\rangle $$При этом мы понимаем, что все десятичные целые, появляющиеся в записи базисных векторов необходимо перевести в 8-битную двоичную форму записи.
При увеличении числа битов такие выражения становятся чрезмерно длинными. Эффективный математический способ записи таких сумм использует $$\sum$$ нотацию. При использовании этой нотации 8-кубит компактно записывается в виде:
$$\sum_{k=0}^255 a_k|k\rangle $$Здесь k - индекс суммирования пробегает все значения от 0 до 255, так что сумма включает все 255 термов. При k=0 в сумму включается терм $$а_0 |0\rangle $$ при $$k=1$$ в сумму включается терм $$а_1 |1\rangle $$ и так далее. Для каждого базисного вектора $$|k\rangle $$ целое $$k$$ следует переводить в двоичную форму записи.
Как мы увидим в следующей главе, состояние объединенной поляризации n взаимодействующих кубитов описывается как n-кубит. Объем памяти требуемой для записи такого состояния в классическом компьютере растет экспоненциально в зависимости от n. Если отводить 1 байт для записи значения каждого а-коэффициента, то нам потребуется 2 байта для хранения 1-кубита, один килобайт для хранения 10-кубит, один мегабайт для 20-кубитов, один гигабайт для 30-кубит, один терабайт для 40-кубит, один петабайт для 50-кубит. Даже если нам удастся использовать всю материю нашей вселенной для построения гигантского чипа памяти, основываясь на современных способах построения компьютерной памяти, то нам не удастся построить память для хранения 100-кубит. В то же время совокупность из 100 взаимодействующих фотонов - это то, что нас повсеместно окружает. Осознание того, что природа широко использует квантовые принципы работы, стало отправной точкой возникновения самой идеи квантовых вычислений.
Идея использования квантовых систем в вычислительных устройствах была независимо высказана в 1980 году Юрием Маниным и Паулем Бениофом (Yuri Manin, Раи1 Вепго). Эта идея также рассматривалась Рихардом Фейнманом (Richard Feynmann) в 1982 году Основания этой теории систематически разрабатывались Дэвидом Дейтчем (David Deutsch), но настоящий взрывной интерес к этой области появился с открытием алгоритма Шора в 1994 году Квантовый алгоритм, который разработал Питер Шор (Реег Shor), может взломать широко используемый в криптографии алгоритм шифрования с открытым ключом. Такой алгоритм сегодня повсеместно используется при передаче секретных данных в интернете. Конечно, для реализации алгоритма требуется построить достаточно большой квантовый компьютер, что пока технологически недостижимо.
Цель этого курса объяснить алгоритм Шора и все детали, требуемые для его понимания.
Закон Мура, сформулированный одним из основателей фирмы Intel Гордоном Муром, гласил, что число транзисторов интегральной схемы удваивается каждые два года. Это возможно при условии уменьшения размеров транзисторов. В 2017 году этот размер имел порядок 10 нанометров, что соответствует слою толщиной не более 50 атомов. Уже при этих масштабах становятся существенными квантовые эффекты, такие как квантовые туннельные эффекты, когда частица преодолевает барьер, который, согласно законам классической механики, она преодолеть не может из-за нехватки энергии.
Очевидно, что, следуя траектории закона Мура, принятая парадигма построения архитектуры компьютера должна натолкнуться на непроходимую стену, поскольку размер транзистора не может быть меньше межатомного расстояния в кристалле. Более того при приближении к барьеру, квантовые эффекты становятся определяющими.
В нашей повседневной жизни мы имеем дело с объектами, состоящими из многих атомов (число атомов в одной песчинке составляет примерно $$10^{20}$$. В больших коллекциях атомов квантовые эффекты взаимно поглощаются и в результате для макроскопических объектов нет необходимости в учете законов квантовой механики. И все же в современных технологиях растет интерес к использованию квантовых эффектов, например, светодиодные фонарики работают на основе квантовых принципов.
Идея квантовых вычислений основана на том, что не следует сражаться с влиянием квантовых эффектов, - необходимо научиться использовать возможности квантового мира. Это не просто, но дает большие преимущества. Квантовые компьютеры - это устройства, которые используют квантовые системы в качестве процессоров.
Какие же возможности открываются при использования квантовых компьютеров? В сравнении с обычными компьютерами мы получаем:
А что же мы теряем при этом?
Квантовые компьютеры имеют серьезную теоретическую базу как в физике, так и в математике. Однако проблемы их создания остаются весьма сложными и здесь для достижения успеха требуется существенный технологический прорыв.
Необходим существенный прогресс и в разработке квантовых алгоритмов. К счастью, для выполнения этой работы нет необходимости иметь настоящий работающий квантовый компьютер. Здесь достаточно пера, бумаги и понимания теории квантовых вычислений.
Давайте же попытаемся понять разницу между классическими и квантовыми компьютерами. В классическом компьютере данные хранятся в памяти в виде последовательности 0 и 1. Минимальной единицей памяти является бит, и он может хранить либо ноль, либо единицу Для целей нашего обсуждения 0 и 1 следует рассматривать как символы.
Единица памяти квантового компьютера называется кубит, и он может хранить одновременно как 0, так и 1. Более точно, значение кубита можно рассматривать как вектор единичной длины на плоскости:
Для установления связи с классическим битом пометим горизонтальную ось символом 0, а вертикальную -1. Соответственно для единичных векторов, расположенных на наших координатных осях, будем использовать нотацию, традиционную для квантовой механики:
$$\mid 0 \rangle ={1\choose0}// \mid 1\rangle ={0\choose1}$$Тогда значение кубита может быть записано как:
$${a\choose b}=a \mid 0\rangle +b |1\rangle $$Значение кубита в этом случае можно интерпретировать как суперпозицию с весами а и b двух классических битов 0 и 1, где $$а^2 + b^2 = 1$$. Заметьте, что мы рассматриваем здесь $$|10\rangle $$ не как вектор длины 0, а как вектор единичной длины, расположенный на оси, помеченной символом "0".
Когда мы строим компьютер как физическую машину, нам необходимо использовать физические объекты, способные реализовать абстрактные конструкции бита и кубита. Конденсатор (электронное устройство, способное сохранять электрический заряд) может служить в качестве единицы памяти классического компьютера. Заряженное состояние конденсатора может рассматриваться как 1, а разряженное- 0.
Фотон может рассматриваться как физическая реализация кубита. Фотон - это квант электромагнитной волны. Представьте фотон, летящий в трехмерном пространстве вдоль оси Z. В процессе полета возникает колебание (осцилляция) электрического и магнитного полей во взаимно перпендикулярных направлениях в плоскости ХУ
Специфический способ проявления осцилляции называется поляризацией фотона. Существуют два возможных типа поляризация - круговая и линейная. При круговой поляризации при перемещении фотона направление электрического поля вращается в плоскости ХУ В этом курсе мы будем рассматривать только простейший случай линейной поляризации, когда электрическое поле осциллирует в фиксированном направлении перпендикулярно оси Z. Линейно поляризованные фотоны могут быть получены пропусканием светового потока через поляризационный фильтр.
Поляризованный свет используется в кинотеатрах 3D. Для создания 3D эффекта правый и левый глаз должны видеть слегка отличные картинки. Для этого фильм проецируется двумя камерами, разнесенными на некоторое расстояние. Изображение обеих камер одновременно проецируется на экран, но свет от двух проекторов поляризован различными способами. Очки для просмотра фильма имеют поляризационные фильтры, каждый из которых способен пропускать свет только от одного проектора. В результате два глаза получают различающиеся изображения, что и создает 3D эффект.
Вообразите, фотон с линейной поляризацией под углом а в плоскости ХУ Такой фотон может быть использован в качестве физической реализации кубита со значением
$$\cos(\alpha)|0\rangle+\sin(\alpha)|1\rangle $$Небольшое техническое замечание относительно положительного и отрицательного состояний фотона $$|0\rangle $$ и - $$|0\rangle $$. Оба состояния соответствуют фотону с теми же осями поляризации, однако осцилляция электрического поля для отрицательного состояния - $$|0\rangle $$ находится в противофазе относительно состояния $$0\rangle $$. Для одного фотона невозможно различить, в каком состоянии он находится, но для пары фотонов можно обнаружить разницу в фазах и рассматривать их состояния как два различных значений кубита.
Давайте перейдем теперь к рассмотрению множества кубитов - мультикубитам. 2-кубит - это вектор с четырьмя компонентами в форме:
$$а_0 |00\rangle + а_1|01\rangle + а_2 |10\rangle + а_3 |11\rangle ,$$
где $$а_0^2 + а_1^2 + а_2^2 + а_3^2 = 1$$. Базисные вектора в пространстве 2-кубитов: $$|00\rangle, |01\rangle, |10\rangle, |11\rangle $$, называемые также чистыми состояниями, соответствуют 4-м возможным состояниям пары классических битов. В общем случае значение 2-кубита представляет комбинацию значений 4-х классических битов. У каждого бита в этой комбинации есть свой весовой коэффициент. Эту комбинацию принято называть суперпозицией.
Например, 2-кубит $$0.3|00\rangle + 0.1|01\rangle + 0.9|10\rangle + 0.3|11\rangle $$ представляет суперпозицию 4-х классических значений, но 2-бит значение "10" в этой комбинации наиболее весомо.
Как вы уже могли догадаться, 3-кубит - это вектор с 8-мю компонентами:
$$а_0 |000\rangle + а_1 |001\rangle + а_2 |010\rangle + а_3 |011\rangle + а_4|100\rangle + а_5 |101\rangle + а_6 |110\rangle + а_7|111\rangle $$Обратите внимание на соответствие в нашей нотация между индексом коэффициента а и меткой, которой мы помечаем базисные вектора. Возьмем, например, терм (слагаемое) $$а_6|110\rangle $$ . Значение 110 в этом терме совпадает с двоичной записью значения индекса $$(6_{10} = 110_2)$$.
Нетрудно также заметить, что число термов удваивается при увеличении на единицу числа кубитов. Для 1-кубита термов - 2, для 2-кубита - 4, для 3-кубита- 8. В общем случае для N кубитов термов 2^N. Для 8-кубита тeрмов будет 256:
В качестве упражнения давайте определим индекс коэффициента "а" для терма с меткой $$|11010011\rangle $$. Каждая цифра в позиционной системе счисления является коэффициентом основания системы счисления в степени k,
где k - определяется позицией цифры. Для двоичной системы счисления основание равно 2, так что цифры 0 и 1- это коэффициенты при соответствующих степенях основания 2. Для 8-битного выражения самая левая цифра соответствует степени $$2^7$$, самая правая - $$2^0$$. Бинарное выражение "11010011" следует рассматривать как:
Аналогично, десятичный индекс 117 в двоичном 8-битном представлении имеет вид:
$$117=64+53=64+32+21=64+32+16+5=64+32+16+4+1 =// 0*2^7+1*2^6+1*2^5+1*2^4+0*2^3+1*2^2+0*2^1+1*2^0= 01110101 (binary).$$Для более компактной закиси мы иногда будем записывать 8-кубит в десятичной форме:
$$а_0 |0\rangle+ а_1 |1\rangle + а_2 |2\rangle +\dots + а_{255} |255\rangle $$При этом мы понимаем, что все десятичные целые, появляющиеся в записи базисных векторов необходимо перевести в 8-битную двоичную форму записи.
При увеличении числа битов такие выражения становятся чрезмерно длинными. Эффективный математический способ записи таких сумм использует $$\sum$$ нотацию. При использовании этой нотации 8-кубит компактно записывается в виде:
$$\sum_{k=0}^255 a_k|k\rangle $$Здесь k - индекс суммирования пробегает все значения от 0 до 255, так что сумма включает все 255 термов. При k=0 в сумму включается терм $$а_0 |0\rangle $$ при $$k=1$$ в сумму включается терм $$а_1 |1\rangle $$ и так далее. Для каждого базисного вектора $$|k\rangle $$ целое $$k$$ следует переводить в двоичную форму записи.
Как мы увидим в следующей главе, состояние объединенной поляризации n взаимодействующих кубитов описывается как n-кубит. Объем памяти требуемой для записи такого состояния в классическом компьютере растет экспоненциально в зависимости от n. Если отводить 1 байт для записи значения каждого а-коэффициента, то нам потребуется 2 байта для хранения 1-кубита, один килобайт для хранения 10-кубит, один мегабайт для 20-кубитов, один гигабайт для 30-кубит, один терабайт для 40-кубит, один петабайт для 50-кубит. Даже если нам удастся использовать всю материю нашей вселенной для построения гигантского чипа памяти, основываясь на современных способах построения компьютерной памяти, то нам не удастся построить память для хранения 100-кубит. В то же время совокупность из 100 взаимодействующих фотонов - это то, что нас повсеместно окружает. Осознание того, что природа широко использует квантовые принципы работы, стало отправной точкой возникновения самой идеи квантовых вычислений.
Идея использования квантовых систем в вычислительных устройствах была независимо высказана в 1980 году Юрием Маниным и Паулем Бениофом (Yuri Manin, Раи1 Вепго). Эта идея также рассматривалась Рихардом Фейнманом (Richard Feynmann) в 1982 году Основания этой теории систематически разрабатывались Дэвидом Дейтчем (David Deutsch), но настоящий взрывной интерес к этой области появился с открытием алгоритма Шора в 1994 году Квантовый алгоритм, который разработал Питер Шор (Реег Shor), может взломать широко используемый в криптографии алгоритм шифрования с открытым ключом. Такой алгоритм сегодня повсеместно используется при передаче секретных данных в интернете. Конечно, для реализации алгоритма требуется построить достаточно большой квантовый компьютер, что пока технологически недостижимо.
Цель этого курса объяснить алгоритм Шора и все детали, требуемые для его понимания.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.