EITC/QI/QIF Quantum Information Fundamentals — это европейская программа сертификации ИТ по теоретическим и практическим аспектам квантовой информации и квантовых вычислений, основанная на законах квантовой физики, а не на классической физике, и предлагающая качественные преимущества по сравнению с их классическими аналогами.
Учебная программа EITC/QI/QIF Quantum Information Fundamentals охватывает введение в квантовую механику (включая рассмотрение эксперимента с двумя щелями и интерференцию волн материи), введение в квантовую информацию (кубиты и их геометрическое представление), поляризацию света, принцип неопределенности, квантовую запутанность, парадокс ЭПР, нарушение неравенства Белла, отказ от локального реализма, квантовая обработка информации (включая унитарное преобразование, однокубитные и двухкубитные вентили), теорема о запрете клонирования, квантовая телепортация, квантовое измерение, квантовые вычисления (включая введение в -кубитные системы, универсальное семейство вентилей, обратимость вычислений), квантовые алгоритмы (включая квантовое преобразование Фурье, алгоритм Саймона, расширенный тезис Черха-Тьюринга, алгоритм квантового факторинга Шора, алгоритм квантового поиска Гровера), квантовые наблюдаемые, уравнение Шредингера, реализации кубитов, квантовая теория сложности, адиабатические квантовые вычисления ion, BQP, введение в вращение в следующей структуре, охватывающей всестороннее дидактическое видео в качестве справочного материала для этой сертификации EITC.
Квантовая информация — это информация о состоянии квантовой системы. Это основной объект изучения теории квантовой информации, и им можно манипулировать с помощью методов обработки квантовой информации. Квантовая информация относится как к техническому определению в терминах энтропии фон Неймана, так и к общему вычислительному термину.
Квантовая информация и вычисления — это междисциплинарная область, которая включает в себя квантовую механику, информатику, теорию информации, философию и криптографию среди других областей. Его изучение также имеет отношение к таким дисциплинам, как когнитивная наука, психология и неврология. Основное внимание уделяется извлечению информации из материи в микроскопическом масштабе. Наблюдение в науке — это фундаментальный отличительный критерий действительности и один из важнейших способов получения информации. Следовательно, измерение требуется для количественной оценки наблюдения, что делает его важным для научного метода. В квантовой механике из-за принципа неопределенности некоммутирующие наблюдаемые не могут быть точно измерены одновременно, поскольку собственное состояние в одном базисе не является собственным состоянием в другом базисе. Поскольку обе переменные не являются одновременно хорошо определенными, квантовое состояние никогда не может содержать окончательную информацию об обеих переменных. Благодаря этому фундаментальному свойству измерения в квантовой механике эту теорию в целом можно охарактеризовать как недетерминированную, в отличие от классической механики, которая является полностью детерминированной. Индетерминизм квантовых состояний характеризует информацию, определяемую как состояния квантовых систем. С математической точки зрения эти состояния находятся в суперпозициях (линейных комбинациях) состояний классических систем.
Поскольку информация всегда закодирована в состоянии физической системы, она сама по себе является физической. В то время как квантовая механика занимается изучением свойств материи на микроскопическом уровне, квантовая информатика фокусируется на извлечении информации из этих свойств, а квантовые вычисления манипулируют и обрабатывают квантовую информацию — выполняют логические операции — с использованием методов обработки квантовой информации.
Квантовая информация, как и классическая информация, может обрабатываться с помощью компьютеров, передаваться из одного места в другое, обрабатываться с помощью алгоритмов и анализироваться с помощью компьютерных наук и математики. Точно так же, как базовой единицей классической информации является бит, квантовая информация имеет дело с кубитами, которые могут существовать в суперпозиции 0 и 1 (одновременно являясь чем-то истинным и ложным). Квантовая информация также может существовать в так называемых запутанных состояниях, которые проявляют чисто неклассические нелокальные корреляции в своих измерениях, что позволяет применять такие приложения, как квантовая телепортация. Уровень запутанности можно измерить с помощью энтропии фон Неймана, которая также является мерой квантовой информации. В последнее время область квантовых вычислений стала очень активной областью исследований из-за возможности разрушить современные вычисления, связь и криптографию.
История квантовой информации началась на рубеже 20-го века, когда классическая физика была преобразована в квантовую физику. Теории классической физики предсказывали такие нелепости, как ультрафиолетовая катастрофа или спиральное движение электронов в ядре. Сначала от этих проблем отмахивались, добавляя к классической физике гипотезы ad hoc. Вскоре стало очевидно, что необходимо создать новую теорию, чтобы разобраться в этих нелепостях, и родилась теория квантовой механики.
Квантовая механика была сформулирована Шрёдингером с использованием волновой механики и Гейзенбергом с использованием матричной механики. Эквивалентность этих методов была доказана позже. Их формулировки описывали динамику микроскопических систем, но имели несколько неудовлетворительных аспектов при описании процессов измерения. Фон Нейман сформулировал квантовую теорию, используя операторную алгебру таким образом, что она описывала не только динамику, но и измерение. В этих исследованиях подчеркивались философские аспекты измерения, а не количественный подход к извлечению информации посредством измерений.
В 1960-х годах Стратонович, Хелстром и Гордон предложили формулировку оптической связи с использованием квантовой механики. Это было первое историческое появление квантовой теории информации. В основном они изучали вероятности ошибок и пропускную способность каналов связи. Позже Холево получил верхнюю границу скорости связи при передаче классического сообщения по квантовому каналу.
В 1970-х годах начали разрабатываться методы управления квантовыми состояниями отдельных атомов, такие как атомная ловушка и сканирующий туннельный микроскоп, что позволило изолировать отдельные атомы и размещать их в массивах. До этих разработок точное управление отдельными квантовыми системами было невозможно, и в экспериментах использовался более грубый одновременный контроль над большим количеством квантовых систем. Разработка жизнеспособных методов манипулирования одним состоянием привела к повышенному интересу к области квантовой информации и вычислений.
В 1980-х годах возник интерес к возможности использования квантовых эффектов для опровержения теории относительности Эйнштейна. Если бы было возможно клонировать неизвестное квантовое состояние, можно было бы использовать запутанные квантовые состояния для передачи информации со скоростью, превышающей скорость света, что опровергает теорию Эйнштейна. Однако теорема о запрете клонирования показала, что такое клонирование невозможно. Теорема была одним из первых результатов квантовой теории информации.
Развитие от криптографии
Несмотря на весь ажиотаж и интерес к изучению изолированных квантовых систем и попыткам найти способ обойти теорию относительности, в 1980-х годах исследования в области квантовой теории информации застопорились. Однако примерно в то же время в области квантовой информации и вычислений начала появляться другая область: криптография. В общем смысле криптография — это проблема осуществления связи или вычислений с участием двух или более сторон, которые могут не доверять друг другу.
Беннетт и Брассард разработали канал связи, который невозможно подслушать, не будучи обнаруженным, способ тайного общения на больших расстояниях с использованием квантового криптографического протокола BB84. Ключевой идеей было использование фундаментального принципа квантовой механики о том, что наблюдение мешает наблюдаемому, а введение подслушивателя в защищенную линию связи сразу же позволит двум сторонам, пытающимся общаться, узнать о присутствии подслушивателя.
Развитие из информатики и математики
С появлением революционных идей Алана Тьюринга о программируемом компьютере или машине Тьюринга он показал, что любое реальное вычисление может быть переведено в эквивалентное вычисление с использованием машины Тьюринга. Это известно как тезис Чёрча-Тьюринга.
Достаточно скоро были изготовлены первые компьютеры, и компьютерное оборудование росло такими быстрыми темпами, что рост благодаря производственному опыту был систематизирован в виде эмпирической зависимости, называемой законом Мура. Этот «закон» представляет собой проективную тенденцию, согласно которой количество транзисторов в интегральной схеме удваивается каждые два года. По мере того, как транзисторы становились все меньше и меньше, чтобы упаковывать больше энергии на единицу площади поверхности, в электронике начали проявляться квантовые эффекты, приводящие к непреднамеренным помехам. Это привело к появлению квантовых вычислений, которые использовали квантовую механику для разработки алгоритмов.
На данный момент квантовые компьютеры обещают быть намного быстрее, чем классические компьютеры для определенных конкретных задач. Одна такая примерная проблема была разработана Дэвидом Дойчем и Ричардом Йожой и известна как алгоритм Дойча-Джозы. Однако эта проблема практически не имела практического применения. Питер Шор в 1994 году придумал очень важную и практическую задачу — найти простые множители целого числа. Проблема дискретного логарифма, как ее называли, могла быть эффективно решена на квантовом компьютере, но не на классическом компьютере, что показывает, что квантовые компьютеры более мощные, чем машины Тьюринга.
Развитие теории информации
Примерно в то же время информатика совершала революцию, как и теория информации и коммуникации благодаря Клоду Шеннону. Шеннон разработал две фундаментальные теоремы теории информации: теорему о бесшумном кодировании канала и теорему о кодировании канала с шумом. Он также показал, что коды исправления ошибок можно использовать для защиты отправляемой информации.
Квантовая теория информации также пошла по тому же пути. Бен Шумахер в 1995 году сделал аналог теоремы Шеннона о бесшумном кодировании, используя кубит. Также была разработана теория исправления ошибок, которая позволяет квантовым компьютерам выполнять эффективные вычисления независимо от шума и обеспечивать надежную связь по зашумленным квантовым каналам.
Кубиты и теория информации
Квантовая информация сильно отличается от классической информации, представленной битами, многими поразительными и незнакомыми способами. В то время как основной единицей классической информации является бит, самой основной единицей квантовой информации является кубит. Классическая информация измеряется с помощью энтропии Шеннона, а квантово-механический аналог — энтропия фон Неймана. Статистический ансамбль квантово-механических систем характеризуется матрицей плотности. Многие меры энтропии в классической теории информации также могут быть обобщены на квантовый случай, например, энтропия Холево и условная квантовая энтропия.
В отличие от классических цифровых состояний (которые являются дискретными), кубит имеет непрерывное значение, описываемое направлением на сфере Блоха. Несмотря на то, что кубит постоянно оценивается таким образом, он является наименьшей возможной единицей квантовой информации, и, несмотря на то, что состояние кубита имеет непрерывное значение, невозможно точно измерить значение. Пять известных теорем описывают пределы манипулирования квантовой информацией:
- теорема о запрете телепортации, которая утверждает, что кубит не может быть (полностью) преобразован в классические биты; то есть его нельзя полностью «прочитать»,
- теорема о запрете клонирования, которая предотвращает копирование произвольного кубита,
- теорема об отсутствии удаления, которая предотвращает удаление произвольного кубита,
- теорема о запрете вещания, которая предотвращает доставку произвольного кубита нескольким получателям, хотя его можно транспортировать с места на место (например, с помощью квантовой телепортации),
- Теорема о несокрытии, демонстрирующая сохранение квантовой информации. Эти теоремы доказывают, что квантовая информация во Вселенной сохраняется, и открывают уникальные возможности в обработке квантовой информации.
Квантовая обработка информации
Состояние кубита содержит всю его информацию. Это состояние часто выражается в виде вектора на сфере Блоха. Это состояние можно изменить, применяя к ним линейные преобразования или квантовые вентили. Эти унитарные преобразования описываются как вращения на сфере Блоха. В то время как классические вентили соответствуют знакомым операциям булевой логики, квантовые вентили являются физическими унитарными операторами.
Из-за изменчивости квантовых систем и невозможности копирования состояний хранение квантовой информации намного сложнее, чем хранение классической информации. Тем не менее, при использовании квантовой коррекции ошибок квантовая информация в принципе все еще может быть надежно сохранена. Существование квантовых кодов исправления ошибок также привело к возможности отказоустойчивых квантовых вычислений.
Классические биты могут быть закодированы и впоследствии извлечены из конфигураций кубитов с помощью квантовых вентилей. Сам по себе один кубит может передать не более одного бита доступной классической информации о его приготовлении. Это теорема Холево. Однако при сверхплотном кодировании отправитель, воздействуя на один из двух запутанных кубитов, может передать получателю два бита доступной информации об их совместном состоянии.
Квантовая информация может передаваться по квантовому каналу, аналогично концепции классического канала связи. Квантовые сообщения имеют конечный размер, измеряемый кубитами; квантовые каналы имеют конечную пропускную способность канала, измеряемую в кубитах в секунду.
Квантовая информация и изменения в квантовой информации могут быть количественно измерены с помощью аналога энтропии Шеннона, называемого энтропией фон Неймана.
В некоторых случаях квантовые алгоритмы могут использоваться для выполнения вычислений быстрее, чем в любом известном классическом алгоритме. Наиболее известным примером этого является алгоритм Шора, который может разлагать числа на множители за полиномиальное время по сравнению с лучшими классическими алгоритмами, использующими субэкспоненциальное время. Поскольку факторизация является важной частью безопасности шифрования RSA, алгоритм Шора зародил новую область постквантовой криптографии, которая пытается найти схемы шифрования, которые остаются безопасными, даже когда в игру вступают квантовые компьютеры. Другие примеры алгоритмов, демонстрирующих квантовое превосходство, включают алгоритм поиска Гровера, в котором квантовый алгоритм дает квадратичное ускорение по сравнению с лучшим из возможных классических алгоритмов. Класс сложности задач, эффективно решаемых квантовым компьютером, известен как BQP.
Квантовое распределение ключей (QKD) позволяет безусловно безопасно передавать классическую информацию, в отличие от классического шифрования, которое всегда можно взломать в принципе, если не на практике. Обратите внимание, что некоторые тонкие моменты, касающиеся безопасности КРК, до сих пор являются предметом горячих споров.
Изучение всех вышеперечисленных тем и различий составляет квантовая теория информации.
Отношение к квантовой механике
Квантовая механика изучает динамическое изменение микроскопических физических систем в природе. В области квантовой теории информации изучаемые квантовые системы абстрагируются от каких-либо аналогов в реальном мире. Кубит может, например, физически быть фотоном в линейном оптическом квантовом компьютере, ионом в квантовом компьютере с захваченным ионом или большим набором атомов, как в сверхпроводящем квантовом компьютере. Независимо от физической реализации ограничения и особенности кубитов, подразумеваемые квантовой теорией информации, сохраняются, поскольку все эти системы математически описываются одним и тем же аппаратом матриц плотности над комплексными числами. Другое важное отличие от квантовой механики заключается в том, что, хотя квантовая механика часто изучает бесконечномерные системы, такие как гармонический осциллятор, квантовая теория информации касается как систем с непрерывными переменными, так и конечномерных систем.
Квантовые вычисления
Квантовые вычисления — это тип вычислений, который использует коллективные свойства квантовых состояний, такие как суперпозиция, интерференция и запутанность, для выполнения вычислений. Устройства, которые выполняют квантовые вычисления, известны как квантовые компьютеры.: I-5 Хотя современные квантовые компьютеры слишком малы, чтобы превзойти обычные (классические) компьютеры для практических приложений, считается, что они способны решать определенные вычислительные задачи, такие как факторизация целых чисел. (который лежит в основе шифрования RSA), значительно быстрее, чем классические компьютеры. Изучение квантовых вычислений является подобластью квантовой информатики.
Квантовые вычисления начались в 1980 году, когда физик Пол Бениофф предложил квантово-механическую модель машины Тьюринга. Позже Ричард Фейнман и Юрий Манин предположили, что квантовый компьютер может моделировать вещи, которые классический компьютер не может делать. В 1994 году Питер Шор разработал квантовый алгоритм факторизации целых чисел с возможностью расшифровки сообщений, зашифрованных RSA. В 1998 году Исаак Чуанг, Нил Гершенфельд и Марк Кубинец создали первый двухкубитный квантовый компьютер, способный выполнять вычисления. Несмотря на непрерывный экспериментальный прогресс с конца 1990-х годов, большинство исследователей считают, что «отказоустойчивые квантовые вычисления [являются] все еще довольно далекой мечтой». В последние годы инвестиции в исследования квантовых вычислений увеличились в государственном и частном секторах. 23 октября 2019 года Google AI в партнерстве с Национальным управлением по аэронавтике и исследованию космического пространства США (НАСА) заявил, что выполнил квантовые вычисления, которые были невозможны на любом классическом компьютере, но было ли это утверждение действительным или остается в силе, является предметом обсуждения. активное исследование.
Существует несколько типов квантовых компьютеров (также известных как системы квантовых вычислений), включая модель квантовой цепи, квантовую машину Тьюринга, адиабатический квантовый компьютер, однонаправленный квантовый компьютер и различные квантовые клеточные автоматы. Наиболее широко используемой моделью является квантовая схема, основанная на квантовом бите или «кубите», который чем-то аналогичен биту в классических вычислениях. Кубит может находиться в квантовом состоянии 1 или 0 или в суперпозиции состояний 1 и 0. Однако при измерении он всегда равен 0 или 1; вероятность того или иного исхода зависит от квантового состояния кубита непосредственно перед измерением.
Усилия по созданию физического квантового компьютера сосредоточены на таких технологиях, как трансмоны, ионные ловушки и топологические квантовые компьютеры, которые направлены на создание высококачественных кубитов: 2–13 Эти кубиты могут быть спроектированы по-разному, в зависимости от вычислительной модели полного квантового компьютера. будь то квантовые логические вентили, квантовый отжиг или адиабатические квантовые вычисления. В настоящее время существует ряд серьезных препятствий для создания полезных квантовых компьютеров. Особенно сложно поддерживать квантовые состояния кубитов, поскольку они страдают от квантовой декогеренции и точности состояния. Поэтому квантовые компьютеры требуют исправления ошибок.
Любая вычислительная задача, которую может решить классический компьютер, может быть решена и квантовым компьютером. И наоборот, любая проблема, которую может решить квантовый компьютер, может быть решена и классическим компьютером, по крайней мере, в принципе, при наличии достаточного времени. Другими словами, квантовые компьютеры подчиняются тезису Чёрча-Тьюринга. Это означает, что, хотя квантовые компьютеры не дают дополнительных преимуществ перед классическими компьютерами с точки зрения вычислительности, квантовые алгоритмы для некоторых задач имеют значительно меньшую временную сложность, чем соответствующие известные классические алгоритмы. Примечательно, что считается, что квантовые компьютеры способны быстро решать определенные проблемы, которые ни один классический компьютер не может решить за сколько-нибудь разумное время — подвиг, известный как «квантовое превосходство». Изучение вычислительной сложности задач, связанных с квантовыми компьютерами, известно как квантовая теория сложности.
Преобладающая модель квантовых вычислений описывает вычисления в терминах сети квантовых логических вентилей. Эту модель можно рассматривать как абстрактное линейно-алгебраическое обобщение классической схемы. Поскольку эта модель схемы подчиняется квантовой механике, считается, что квантовый компьютер, способный эффективно управлять этими схемами, физически реализуем.
Память, состоящая из n бит информации, имеет 2^n возможных состояний. Таким образом, вектор, представляющий все состояния памяти, имеет 2 ^ n записей (по одной для каждого состояния). Этот вектор рассматривается как вектор вероятности и представляет собой тот факт, что память должна находиться в определенном состоянии.
В классическом представлении одна запись будет иметь значение 1 (т. е. 100% вероятность пребывания в этом состоянии), а все остальные записи будут равны нулю.
В квантовой механике векторы вероятности могут быть обобщены до операторов плотности. Формализм вектора квантового состояния обычно вводится первым, потому что он концептуально проще и потому что его можно использовать вместо формализма матрицы плотности для чистых состояний, где вся квантовая система известна.
квантовое вычисление можно описать как сеть квантовых логических вентилей и измерений. Однако любое измерение можно отложить до конца квантовых вычислений, хотя эта отсрочка может привести к вычислительным затратам, поэтому большинство квантовых схем изображают сеть, состоящую только из квантовых логических вентилей и без измерений.
Любое квантовое вычисление (которое в приведенном выше формализме является любой унитарной матрицей над n кубитами) может быть представлено как сеть квантовых логических вентилей из довольно небольшого семейства вентилей. Выбор семейства вентилей, который позволяет эту конструкцию, известен как универсальный набор вентилей, поскольку компьютер, который может запускать такие схемы, является универсальным квантовым компьютером. Один общий такой набор включает в себя все однокубитные вентили, а также вентиль CNOT сверху. Это означает, что любые квантовые вычисления могут быть выполнены путем выполнения последовательности однокубитных вентилей вместе с вентилями CNOT. Хотя это множество ворот бесконечно, его можно заменить конечным множеством ворот, обратившись к теореме Соловея-Китаева.
Квантовые алгоритмы
Прогресс в поиске квантовых алгоритмов обычно сосредоточен на этой модели квантовой цепи, хотя существуют исключения, такие как квантовый адиабатический алгоритм. Квантовые алгоритмы можно грубо классифицировать по типу ускорения, достигаемого по сравнению с соответствующими классическими алгоритмами.
Квантовые алгоритмы, которые предлагают более чем полиномиальное ускорение по сравнению с наиболее известным классическим алгоритмом, включают алгоритм Шора для факторизации и связанные с ним квантовые алгоритмы для вычисления дискретных логарифмов, решения уравнения Пелла и, в более общем плане, решения проблемы скрытых подгрупп для абелевых конечных групп. Эти алгоритмы зависят от примитива квантового преобразования Фурье. Не было найдено математического доказательства, показывающего, что столь же быстрый классический алгоритм не может быть обнаружен, хотя это считается маловероятным. находится в модели квантовых запросов, которая представляет собой ограниченную модель, в которой нижние границы гораздо легче доказать и не обязательно приводят к ускорению для практических задач.
Другие проблемы, включая моделирование квантовых физических процессов из химии и физики твердого тела, аппроксимацию некоторых полиномов Джонса и квантовый алгоритм для линейных систем уравнений, имеют квантовые алгоритмы, которые, по-видимому, дают сверхполиномиальное ускорение и являются BQP-полными. Поскольку эти задачи являются BQP-полными, использование столь же быстрого классического алгоритма для них будет означать, что ни один квантовый алгоритм не дает сверхполиномиального ускорения, что считается маловероятным.
Некоторые квантовые алгоритмы, такие как алгоритм Гровера и усиление амплитуды, дают полиномиальное ускорение по сравнению с соответствующими классическими алгоритмами. Хотя эти алгоритмы дают сравнительно скромное квадратичное ускорение, они широко применимы и, таким образом, дают ускорение для широкого круга задач. Многие примеры доказуемых квантовых ускорений для задач запросов связаны с алгоритмом Гровера, включая алгоритм Брассарда, Хойера и Таппа для поиска коллизий в функциях два к одному, который использует алгоритм Гровера, а также алгоритм Фархи, Голдстоуна и Гутмана для вычисления И-НЕ. деревья, что является вариантом задачи поиска.
Криптографические приложения
Заметным применением квантовых вычислений являются атаки на криптографические системы, которые используются в настоящее время. Целочисленная факторизация, которая лежит в основе безопасности криптографических систем с открытым ключом, считается вычислительно невыполнимой на обычном компьютере для больших целых чисел, если они являются произведением нескольких простых чисел (например, произведения двух 300-значных простых чисел). Для сравнения, квантовый компьютер мог бы эффективно решить эту проблему, используя алгоритм Шора для нахождения ее факторов. Эта способность позволила бы квантовому компьютеру взломать многие криптографические системы, используемые сегодня, в том смысле, что для решения проблемы был бы алгоритм с полиномиальным временем (по количеству цифр целого числа). В частности, большинство популярных шифров с открытым ключом основаны на сложности разложения целых чисел на множители или на задаче дискретного логарифмирования, обе из которых могут быть решены с помощью алгоритма Шора. В частности, могут быть нарушены алгоритмы RSA, Диффи-Хеллмана и алгоритмы Диффи-Хеллмана на эллиптических кривых. Они используются для защиты защищенных веб-страниц, зашифрованной электронной почты и многих других типов данных. Их взлом будет иметь серьезные последствия для электронной конфиденциальности и безопасности.
Идентификация криптографических систем, которые могут быть защищены от квантовых алгоритмов, является активно исследуемой темой в области постквантовой криптографии. Некоторые алгоритмы с открытым ключом основаны на проблемах, отличных от целочисленной факторизации и дискретного логарифмирования, к которым применяется алгоритм Шора, например, криптосистема МакЭлиса, основанная на проблеме теории кодирования. Также известно, что криптосистемы на основе решеток не могут быть взломаны квантовыми компьютерами, и поиск алгоритма с полиномиальным временем для решения проблемы двугранных скрытых подгрупп, который взломает многие криптосистемы на основе решеток, является хорошо изученной открытой проблемой. Было доказано, что применение алгоритма Гровера для взлома симметричного алгоритма (с секретным ключом) методом грубой силы требует времени, равного примерно 2n/2 вызовам базового криптографического алгоритма, по сравнению с примерно 2n в классическом случае, что означает, что длина симметричного ключа эффективно вдвое: AES-256 будет иметь такую же защиту от атаки с использованием алгоритма Гровера, что и AES-128 от классического поиска методом грубой силы (см. Размер ключа).
Квантовая криптография потенциально может выполнять некоторые функции криптографии с открытым ключом. Поэтому криптографические системы на основе квантов могут быть более защищены от квантового взлома, чем традиционные системы.
Проблемы с поиском
Наиболее известным примером задачи, допускающей полиномиальное квантовое ускорение, является неструктурированный поиск, нахождение отмеченного элемента из списка из n элементов в базе данных. Это может быть решено с помощью алгоритма Гровера с использованием O (sqrt (n)) запросов к базе данных, что квадратично меньше, чем запросы Omega (n), необходимые для классических алгоритмов. В этом случае преимущество не только доказуемо, но и оптимально: было показано, что алгоритм Гровера дает максимально возможную вероятность нахождения искомого элемента при любом числе обращений к оракулу.
Задачи, которые можно решить с помощью алгоритма Гровера, обладают следующими свойствами:
- В наборе возможных ответов нет поисковой структуры,
- Количество возможных ответов для проверки совпадает с количеством входов в алгоритм, и
- Существует логическая функция, которая оценивает каждый ввод и определяет, является ли он правильным ответом.
Для задач со всеми этими свойствами время работы алгоритма Гровера на квантовом компьютере масштабируется как квадратный корень из числа входных данных (или элементов в базе данных), в отличие от линейного масштабирования классических алгоритмов. Общий класс задач, к которым можно применить алгоритм Гровера, — это проблема булевой выполнимости, где база данных, через которую проходит алгоритм, представляет собой базу данных всех возможных ответов. Примером и (возможно) применением этого является взломщик паролей, который пытается угадать пароль. Симметричные шифры, такие как Triple DES и AES, особенно уязвимы для такого рода атак. [Править] Это применение квантовых вычислений представляет большой интерес для государственных учреждений.
Моделирование квантовых систем
Поскольку химия и нанотехнологии опираются на понимание квантовых систем, а такие системы невозможно эффективно смоделировать классическим способом, многие считают, что квантовое моделирование станет одним из наиболее важных приложений квантовых вычислений. Квантовое моделирование также можно использовать для моделирования поведения атомов и частиц в необычных условиях, таких как реакции внутри коллайдера. Квантовое моделирование может быть использовано для предсказания будущих траекторий движения частиц и протонов при суперпозиции в эксперименте с двумя щелями. промышленность удобрений, в то время как естественные организмы также производят аммиак. Квантовое моделирование может быть использовано для понимания этого процесса увеличения производства.
Квантовый отжиг и адиабатическая оптимизация
Квантовый отжиг или адиабатические квантовые вычисления основаны на адиабатической теореме для проведения вычислений. Система помещается в основное состояние для простого гамильтониана, который медленно эволюционирует в более сложный гамильтониан, основное состояние которого представляет собой решение рассматриваемой проблемы. Теорема адиабаты утверждает, что если эволюция достаточно медленная, система будет оставаться в своем основном состоянии все время на протяжении всего процесса.
Машинное обучение
Поскольку квантовые компьютеры могут производить выходные данные, которые классические компьютеры не могут эффективно производить, и поскольку квантовые вычисления в своей основе являются линейно-алгебраическими, некоторые выражают надежду на разработку квантовых алгоритмов, которые могут ускорить задачи машинного обучения. Например, считается, что квантовый алгоритм для линейных систем уравнений, или «алгоритм HHL», названный в честь его первооткрывателей Харроу, Хассидима и Ллойда, обеспечивает ускорение по сравнению с классическими аналогами. Некоторые исследовательские группы недавно изучили использование оборудования квантового отжига для обучения машин Больцмана и глубоких нейронных сетей.
Вычислительная биология
В области вычислительной биологии квантовые вычисления сыграли большую роль в решении многих биологических проблем. Одним из хорошо известных примеров может быть компьютерная геномика и то, как компьютеры резко сократили время секвенирования генома человека. Учитывая то, как вычислительная биология использует общее моделирование и хранение данных, ожидается, что ее приложения к вычислительной биологии также появятся.
Компьютерный дизайн лекарств и генеративная химия
Модели глубокой генеративной химии становятся мощными инструментами для ускорения разработки лекарств. Однако огромные размеры и сложность структурного пространства всех возможных лекарствоподобных молекул создают значительные препятствия, которые в будущем могут быть преодолены квантовыми компьютерами. Квантовые компьютеры, естественно, хороши для решения сложных квантовых задач многих тел и, таким образом, могут быть полезными в приложениях, связанных с квантовой химией. Следовательно, можно ожидать, что генеративные модели с квантовым усилением, включая квантовые GAN, в конечном итоге могут быть преобразованы в окончательные алгоритмы генеративной химии. Гибридные архитектуры, объединяющие квантовые компьютеры с глубокими классическими сетями, такими как квантовые вариационные автоэнкодеры, уже можно обучать на имеющихся в продаже отжигателях и использовать для создания новых молекулярных структур, подобных лекарствам.
Разработка физических квантовых компьютеров
Вызовы
При создании крупномасштабного квантового компьютера возникает ряд технических проблем. Физик Дэвид Ди Винченцо перечислил следующие требования к практическому квантовому компьютеру:
- Физически масштабируемая для увеличения количества кубитов,
- Кубиты, которые можно инициализировать произвольными значениями,
- Квантовые вентили, работающие быстрее, чем время декогеренции,
- Универсальный комплект ворот,
- Кубиты, которые можно легко прочитать.
Поиск деталей для квантовых компьютеров также очень сложен. Многим квантовым компьютерам, например созданным Google и IBM, нужен гелий-3, побочный продукт ядерных исследований, и специальные сверхпроводящие кабели, производимые только японской компанией Coax Co.
Управление многокубитными системами требует генерации и координации большого количества электрических сигналов с жестким и детерминированным временным разрешением. Это привело к разработке квантовых контроллеров, которые позволяют взаимодействовать с кубитами. Масштабирование этих систем для поддержки растущего числа кубитов является дополнительной проблемой.
Квантовая декогеренция
Одной из самых больших проблем, связанных с созданием квантовых компьютеров, является контроль или устранение квантовой декогеренции. Обычно это означает изоляцию системы от ее окружения, поскольку взаимодействие с внешним миром приводит к декогерентности системы. Однако существуют и другие источники декогеренции. Примеры включают квантовые вентили, колебания решетки и фоновое термоядерное вращение физической системы, используемой для реализации кубитов. Декогеренция необратима, поскольку она фактически неунитарна, и обычно ее следует строго контролировать, если не избегать. Время декогеренции для систем-кандидатов, в частности, время поперечной релаксации T2 (для технологий ЯМР и МРТ, также называемое временем дефазировки), обычно находится в диапазоне от наносекунд до секунд при низкой температуре. В настоящее время некоторые квантовые компьютеры требуют, чтобы их кубиты охлаждались до 20 милликельвинов (обычно с использованием рефрижератора растворения), чтобы предотвратить значительную декогерентность. В исследовании 2020 года утверждается, что ионизирующее излучение, такое как космические лучи, тем не менее может вызвать декогерентность определенных систем в течение миллисекунд.
В результате трудоемкие задачи могут сделать некоторые квантовые алгоритмы неработоспособными, так как поддержание состояния кубитов в течение достаточно длительного периода времени в конечном итоге приведет к повреждению суперпозиций.
Эти проблемы более сложны для оптических подходов, поскольку временные масштабы на порядки короче, и часто упоминаемый подход к их преодолению - это формирование оптического импульса. Частота ошибок обычно пропорциональна отношению времени работы ко времени декогеренции, поэтому любая операция должна быть завершена намного быстрее, чем время декогеренции.
Как описано в квантовой пороговой теореме, если частота ошибок достаточно мала, считается возможным использовать квантовую коррекцию ошибок для подавления ошибок и декогерентности. Это позволяет общему времени расчета быть больше, чем время декогеренции, если схема исправления ошибок может исправлять ошибки быстрее, чем их вносит декогерентность. Часто цитируемая цифра для требуемой частоты ошибок в каждом вентиле для отказоустойчивых вычислений составляет 10-3, если предположить, что шум является деполяризующим.
Выполнение этого условия масштабируемости возможно для широкого круга систем. Однако использование исправления ошибок влечет за собой стоимость значительного увеличения количества необходимых кубитов. Число, необходимое для факторизации целых чисел с использованием алгоритма Шора, по-прежнему является полиномиальным и считается находящимся между L и L2, где L — количество цифр в факторизуемом числе; алгоритмы исправления ошибок увеличили бы эту цифру на дополнительный коэффициент L. Для 1000-битного числа это подразумевает необходимость примерно 104 битов без исправления ошибок. С исправлением ошибок цифра увеличилась бы примерно до 107 бит. Время вычисления составляет около L2 или около 107 шагов и на частоте 1 МГц около 10 секунд.
Совершенно другой подход к проблеме стабильности-декогеренции заключается в создании топологического квантового компьютера с энионами, квазичастицами, используемыми в качестве нитей и опирающимся на теорию кос для формирования стабильных логических вентилей.
Квантовое превосходство
Квантовое превосходство — это термин, придуманный Джоном Прескиллом и относящийся к инженерному подвигу, демонстрирующему, что программируемое квантовое устройство может решить проблему, выходящую за рамки возможностей современных классических компьютеров. Проблема не обязательно должна быть полезной, поэтому некоторые рассматривают тест квантового превосходства только как потенциальный тест на будущее.
В октябре 2019 года Google AI Quantum с помощью НАСА стал первым, кто заявил о достижении квантового превосходства, выполнив вычисления на квантовом компьютере Sycamore более чем в 3,000,000 XNUMX XNUMX раз быстрее, чем они могли быть выполнены на Summit, который обычно считается самым быстрым в мире. компьютер. Впоследствии это утверждение было оспорено: IBM заявила, что Summit может выполнять выборку намного быстрее, чем заявлено, и с тех пор исследователи разработали более совершенные алгоритмы для задачи выборки, используемой для утверждения квантового превосходства, что дает существенное сокращение или сокращение разрыва между Sycamore и Sycamore. классические суперкомпьютеры.
В декабре 2020 года группа USTC осуществила выборку бозонов на 76 фотонах с помощью фотонного квантового компьютера Jiuzhang, чтобы продемонстрировать квантовое превосходство. Авторы утверждают, что классическому современному суперкомпьютеру потребуется вычислительное время в 600 миллионов лет, чтобы сгенерировать количество выборок, которое их квантовый процессор может сгенерировать за 20 секунд. 16 ноября 2021 года на саммите по квантовым вычислениям компания IBM представила 127-кубитный микропроцессор под названием IBM Eagle.
Физические реализации
Для физической реализации квантового компьютера преследуется множество различных кандидатов, среди которых (отличающихся физической системой, используемой для реализации кубитов):
- Сверхпроводящие квантовые вычисления (кубит, реализованный состоянием малых сверхпроводящих цепей, переходы Джозефсона)
- Квантовый компьютер с захваченными ионами (кубит реализован внутренним состоянием захваченных ионов)
- Нейтральные атомы в оптических решетках (кубит, реализованный внутренними состояниями нейтральных атомов, захваченных в оптической решетке)
- Компьютер с квантовыми точками, основанный на спине (например, квантовый компьютер Лосса-ДиВинченцо) (кубит определяется спиновыми состояниями захваченных электронов)
- Компьютер с квантовой точкой, пространственный (кубит, заданный положением электрона в двойной квантовой точке)
- Квантовые вычисления с использованием инженерных квантовых ям, которые в принципе могут позволить создавать квантовые компьютеры, работающие при комнатной температуре.
- Связанный квантовый провод (кубит реализован парой квантовых проводов, соединенных квантовым точечным контактом)
- Квантовый компьютер ядерного магнитного резонанса (NMRQC), реализованный с помощью ядерного магнитного резонанса молекул в растворе, где кубиты создаются ядерными спинами внутри растворенной молекулы и исследуются с помощью радиоволн.
- Твердотельные квантовые компьютеры ЯМР Кейна (кубит, реализованный состоянием ядерного спина доноров фосфора в кремнии)
- Квантовые компьютеры «электроны-на-гелии» (кубит — это спин электрона)
- Квантовая электродинамика полости (CQED) (кубит, обеспечиваемый внутренним состоянием захваченных атомов, связанных с полостями высокой точности)
- Молекулярный магнит (кубит определяется спиновыми состояниями)
- Квантовый компьютер ESR на основе фуллеренов (кубит, основанный на электронном вращении атомов или молекул, заключенных в фуллерены)
- Нелинейный оптический квантовый компьютер (кубиты, реализованные путем обработки состояний различных режимов света как линейными, так и нелинейными элементами)
- Линейный оптический квантовый компьютер (кубиты, реализованные путем обработки состояний различных режимов света с помощью линейных элементов, таких как зеркала, светоделители и фазовращатели)
- Квантовый компьютер на основе алмаза (кубит, реализованный электронным или ядерным вращением азотно-вакансионных центров в алмазе)
- Квантовый компьютер на основе конденсата Бозе-Эйнштейна
- Транзисторный квантовый компьютер - струнные квантовые компьютеры с захватом положительных дырок с помощью электростатической ловушки
- Квантовые компьютеры на основе неорганических кристаллов, легированных ионами редкоземельных металлов (кубит реализован внутренним электронным состоянием легирующих примесей в оптических волокнах)
- Квантовые компьютеры на основе металлоподобных углеродных наносфер
- Большое количество кандидатов демонстрирует, что квантовые вычисления, несмотря на быстрый прогресс, все еще находятся в зачаточном состоянии.
Существует ряд моделей квантовых вычислений, отличающихся базовыми элементами, на которые раскладываются вычисления. Для практической реализации используются четыре соответствующие модели вычислений:
- Массив квантовых вентилей (вычисления разложены на последовательность квантовых вентилей с несколькими кубитами)
- Односторонний квантовый компьютер (вычисления, разложенные на последовательность однокубитных измерений, применяемых к сильно запутанному начальному состоянию или состоянию кластера)
- Адиабатический квантовый компьютер, основанный на квантовом отжиге (вычисление разлагается на медленное непрерывное преобразование исходного гамильтониана в конечный гамильтониан, основные состояния которого содержат решение)
- Топологический квантовый компьютер (вычисления, разложенные на сплетение анионов в двумерной решетке)
Квантовая машина Тьюринга теоретически важна, но физическая реализация этой модели невозможна. Было показано, что все четыре модели вычислений эквивалентны; каждый может имитировать другой с не более чем полиномиальными накладными расходами.
Чтобы более подробно ознакомиться с учебным планом сертификации, вы можете расширить и проанализировать таблицу ниже.
Учебная программа сертификации основ квантовой информации EITC/QI/QIF ссылается на дидактические материалы с открытым доступом в виде видео. Процесс обучения разделен на пошаговую структуру (программы -> уроки -> темы), охватывающую соответствующие разделы учебного плана. Также предоставляются неограниченные консультации с экспертами в предметной области.
Подробнее о процедуре сертификации см. Как это работает.
Основные конспекты лекций
Конспект лекций У. Вазирани:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Поддерживающие конспекты лекций
Л. Якак и соавт. конспект лекций (с дополнительными материалами):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Основной вспомогательный учебник
Учебник по квантовым вычислениям и квантовой информации (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Дополнительные конспекты лекций
Конспекты лекций J. Preskill:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
Конспект лекций А. Чайлдса:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Конспекты лекций С. Ааронсона:
https://scottaaronson.blog/?p=3943
Конспекты лекций Р. де Вольфа:
https://arxiv.org/abs/1907.09415
Другие рекомендуемые учебники
Классические и квантовые вычисления (Китай, Шен, Вялый)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Квантовые вычисления со времен Демокрита (Ааронсон)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
Теория квантовой информации (Ватрус)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Квантовая теория информации (Уайльд)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Загрузите полные подготовительные материалы для самостоятельного обучения по программе EITC/QI/QIF «Основы квантовой информации» в формате PDF.
Подготовительные материалы EITC/QI/QIF – стандартная версия
Подготовительные материалы EITC/QI/QIF – расширенная версия с контрольными вопросами