Квантовый параллелизм: Естественный параллелизм квантовых компьютеров и нейровычислителей Текст научной статьи по специальности «Физика»

Квантовый компьютинг|ИТММ ННГУ

Кафедра прикладной математики

Специальность: Прикладная математика и информатика и Прикладная математика и информатика

Преподаватель: Денисов С..

Предметом рассмотрения настоящего курса являются математические основы квантовых вычислений. Цель курса состоит в изучении основных понятий, методов и подходов квантовых вычислений – физических процессов в квантовых системах, которые могут быть использованы для кодирования и обработки информации, решения сложных вычислительных задач.

Задачей дисциплины является теоретическое и практическое освоение следующих разделов теории квантовых вычислений:

• Квантовая информация
• Элементы теории вычислений
• Квантовые вычисления

В результате освоения дисциплины обучающийся должен:

Знать:

– базовые понятия и методы квантовых вычислений, условия их применимости.

Уметь:

– определять и профессионально применять необходимые для решения прикладных задач квантовых вычислений математические методы, анализировать полученные результат;

– профессионально разрабатывать и использовать программное обеспечение для решения прикладных задач квантовых вычислений;

— проводить процедуры корректности работы реализуемых алгоритмов;

– давать физическую интерпретацию результатам вычислительного эксперимента.

Владеть:

– математическими методами квантовых вычислений;

– современными инструментальными вычислительными средствами.

Содержание

Тема 1. Квантовая информация.

Тема 2. Элементы теории вычислений.

Тема 3. Квантовые вычисления.

Выполнение практических заданий на следующие темы

1. Классическая информация. Кубиты. Однобитовые вентили. Двухбитовые состояния и вентили. Управление U-вентилями, теорема о запрете клонирования и квантовая телепортация. Е-бит, классические вычисления в квантовых цепях. Квантовый параллелизм, алгоритмы Дойча и Дойча-Йожи, преобразование Фурье в квантовых цепях. Основные понятия квантовой механики. Измеряющий оператор. Матрица плотности. Разложение Шмидта. Неравенство Белла. Локальный реализм.
2. Элементы теории вычислений. Машины и цепи Тьюринга. Классы сложности. Обратимые вычисления.
3. Квантовые вычисления. Универсальные квантовые вентили. Аппроксимация унитарности одного кубита универсальным набором вентилей. Пропагация квантовых систем на квантовых компьютерах (декомпозиция Троттера). Квантовое преобразование Фурье. Фазовый эстиматор, алгоритм Гровера. Квантовый поиск как квантовые вычисления. Квантовые операции и каналы.

Литература

а) основная литература:

1. Кайданов Л. З. Генетика популяций. Москва. Изд-во «Высшая школа», 1996. 320 с.
2. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр: Учеб. пособие для ун-тов. — М.: Высш. шк., Книжный дом «Университет», 1998. — С. 304
3. Грень Е. Статистические игры и их применение. — М.: Статистика, 1975.-176с.
4. Ли Ч. Введение в популяционную генетику. – М.: Мир, 1978. — 556 с.

б) дополнительная литература:

5. Эбелинг В., Энгель А., Файстель Р. Физика процессов эволюции. – М.: Эдиториал УРСС, 2001.
6. Стронгин Р.Г. Исследование операций. Модели экономического поведения: Учебник. — Нижний Новгород: Издательство Нижегородского госуниверситета им. Н.И.Лобачевского, 2002. — 244с.
7. Малинецкий Г.Г., Потапов А.Б. Современные проблемы нелинейной динамики. – М.: УРСС, 2000.
8. Оуэн Г. Теория игр. — М.: Наука, 2008.-273с.

в) программное обеспечение и Интернет-ресурсы

9. Стронгин Р.Г. Исследование операций. Модели экономического поведения. Электр. ресурс. Режим доступа свободный, http://www.intuit.ru/department/algorithms/opres.

 

Отчетность

Квантовая информатика — Математическая составляющая

Квантовая информатика Поделиться    

Александр Семёнович Холево

Классическая теория информации — сравнительно молодая ветвь математики. Но порождённый ею мир мобильных телефонов, персональных компьютеров, цифровых фотокамер и других электронных устройств уже успел кардинально изменить нашу жизнь.

Исторический момент, предопределивший принципиальный переход к «цифре», можно указать точно: в 1948 году были совершены два революционных открытия. Первое — изобретение транзистора, проложившее путь к миниатюризации электронных устройств. Второе — возникновение математической теории информации, обосновавшей переход к цифровому представлению данных и предложившей универсальные методы обработки цифровых данных. Именно в 1948 году был опубликован основополагающий труд американского инженера‐математика К. Шеннона, хотя некоторые его идеи были предвосхищены в работах по основам помехоустойчивой связи нашего учёного В. А. Котельникова.

Одна из целей теории информации — совершенствовать методы передачи информации и её хранения (можно считать, что это тоже передача, только во времени). Здесь есть два особо важных аспекта: скорость и качество (точность воспроизведения) передачи данных. Между этими двумя характеристиками имеется обратная зависимость: повышение точности достигается добавлением избыточной информации, что замедляет передачу. Максимально возможная скорость передачи данных, при которой обеспечивается исправление ошибок, вызванных помехами, называется пропускной способностью канала.

Это важное понятие было введено К. Шенноном, им же была доказана теорема, определяющая верхний предел пропускной способности в рамках классической теории.

Сильной (и в то же время слабой) стороной классической теории информации, обусловившей её универсальность, является перевод информации в «цифру»: абстрагирование от содержания и природы передаваемых данных.

Но «информация — физична»: фундаментальным носителем информации является электромагнитное поле, например, в форме видимого света либо радиосигнала. Не учитывать физическую природу иногда просто невозможно: канал передачи информации по сути является квантовым, пределы скорости и точности передачи информации в нём — квантово‐механические.

Квантовая информатика — это новое научное направление, синтез математических идей теории информации и физических законов микромира (квантовой механики). Информация представляется не числами, а состояниями поля, являющегося её носителем.

Два фундаментальных отличия квантового мира от классического — это дополнительность и сцепленность. Дополнительность означает, что у объекта (явления) квантового мира есть свойства, которые в принципе невозможно одновременно точно измерить. В частности, измерение одного свойства меняет другое. Сцепленность — характеристика составных квантовых систем. Две части такой системы находятся в сцепленном состоянии, если между ними установлена квантовая связь, действующая даже при их значительном удалении друг от друга. Для сцепленных объектов измерение одного приводит к изменениям в другом, причём моментально (при этом моментальная передача информации исключена). Оба свойства не имеют классических аналогов и даже контринтуитивны, но они подтверждены экспериментально.

Дополнительность и сцепленность позволяют создавать квантовые каналы связи и криптографические протоколы, защищённые самой природой — несанкционированное вмешательство будет сразу заметно. Эти свойства определяют и демонстрируют вероятностный по сути характер физики микромира. Умение извлечь эту «чистую» вероятность, не связанную с неполнотой наших знаний, уже воплощено в квантовых датчиках подлинно случайных чисел.

Квантовая информатика предлагает эффективные алгоритмы для решения сложнейших задач, которые недоступны никаким «классическим» суперкомпьютерам. Эти возможности потенциально можно реализовать в квантовом компьютере, элементы которого, кубиты, находятся в сцепленном состоянии, обеспечивающем особый «квантовый параллелизм» операций.

Теоретические достижения квантовой информатики опираются на методы и результаты как классических, так и современных, быстро развивающихся разделов математики — теории гильбертовых пространств, матричного и операторного анализа, некоммутативной теории вероятностей и статистики. Эти достижения открывают человечеству возможность совершить технологический прорыв, пройти путь от экспериментальных установок до создания действующих устройств.

С другой стороны, квантовая информатика даёт ключ к пониманию некоторых фундаментальных закономерностей природы: проясняются основания физики микромира, её соотношение с реальностью. Может оказаться и так (вспомните дополнительность!), что результаты на этом пути обозначат границы возможного.

Литература

Бор Н.

Атомная физика и человеческое познание. — М.: ИЛ, 1961.

Online Courses | quant-opt

Для кого этот курс?

Целевой аудиторией курса являются научные работники в области математики и физики, а также сотрудники инженерно-физических и физико-технических вузов.

​

Кратко о курсе

Сегодня каждый наверняка что-то слышал про квантовые вычисления. Это новое направление науки возникло совсем недавно, но благодаря стремительному развитию технологий, к настоящему моменту уже был пройден путь от чисто теоретических идей Юрия Манина и Ричарда Фейнмана до реальных физических устройств, в которых эти идеи были реализованы. Однако до сих пор многие вопросы здесь остаются нерешенными и открытыми. В частности, до сих пор не ясно, возможно ли создание так называемого квантового компьютера, то есть специального устройства, которое будет способно выполнять особый набор алгоритмов, основанных на применении квантово-механических эффектов, которые позволят добиться существенно большей производительности в сравнении с существующими классическими алгоритмами.

​

Настоящий курс посвящен физическим явлениям, лежащим в основе квантовых вычислений.  В частности, большое внимание в нем уделено понятию сепарабельности квантовых систем и квантовой запутанности. Показано, как квантовую запутанность можно использовать для передачи информации на примерах протоколов сверхплотного кодирования и телепортации. Объяснены такие явления, как квантовый параллелизм и квантовая интерференция, на основе которых базируется большинство известных квантовых алгоритмов, а также приведены примеры таких алгоритмов. Кроме того, в курсе рассмотрены основы квантовой теории коррекции ошибок, без которой невозможно создание масштабируемых, то есть состоящих из большого числа логических операций, квантовых вычислений.
 

Что надо знать, чтобы в полной мере овладеть курсом?
Пререквизитами к курсу являются знания основ линейной алгебры и математического анализа. Также понадобятся знания из некоторых разделов оптики, электричества и магнетизма,  основ квантовой механики, и – самое главное – ваш интерес к предмету!

 

Что в итоге?

При прохождении курса обучающийся:

• освоит фундаментальные понятия квантовой механики и теории квантовой информации на понятных и информативных примерах; 

• получит необходимые навыки для работы с классическими и квантовыми схемами коммутации с учетом их квантовых физических особенностей;

• познакомитьсяс теорией коррекции ошибок и связанных с ней информационных протоколов;

• поймет работу важнейших квантовых алгоритмов на основе физических явлений, лежащих в их основе;

• научиться решать задачи по квантовой теории информации и квантовым алгоритмам.

 

Про онлайн формат, как построен курс

К несомненным преимуществам курса можно отнести онлайн-формат обучения, позволяющий осваивать дисциплину в удобное для слушателя время и в выбранном темпе. В то же время интерактивный форум, реализованный на платформе, позволяет задавать вопросы преподавателям в процессе обучения.

В каждом уроке слушателю предлагается посмотреть 1 или 2 видеоролика средней длительностью 12 минут, а также пройти проверочные задания, целью которых является закрепление пройденного материала. В конце каждой из семи представленных тем слушателю предлагается контрольный тест, который поможет проверить свой уровень знаний, а преподавателю – следить за освоением материала. Время, отведенное на прохождение контрольных тестов, неограниченно. 

После успешного прохождения всех тестов слушатель сдает итоговый очный экзамен, который проводится на физическом факультете СПбГУ в форме собеседования с преподавателем по прослушанным материалам курса. В случае невозможности проведения экзамена в очной форме, при необходимости экзамен может быть организован дистанционно. 

В конце обучения, после сдачи итогового экзамена, слушатель получает сертификат Удостоверение о повышении квалификации установленного образца СПбГУ (государственного образца).

Курс реализуется в онлайн-формате на платформе «Открытое образование». Объем обучения составляет 74 часа.

 

Перечень рассматриваемых тем

1. Основные понятия квантовой механики и теории квантовой информации (8 уроков):

квантово-механическое описание физических систем; вектор состояния; линейные операторы; спектральное уравнение; динамические переменные и наблюдаемые; кубит, физические реализации кубита; кубит как квантовая единица информации; сфера Блоха.

 

2. Статистические аспекты квантовой механики (4 урока):

чистые и смешанные состояния; матрица плотности; несепарабельность квантовых систем; редуцированная матрица плотности.

 

3. Несепарабельность квантовых систем (4 урока):

разложение Шмидта; состояния Белла; концепция скрытых переменных;ЭПР-парадокс; неравенства Белла; эксперименты по проверке неравенств Белла.

 

4. Классические и квантовые логические операции (7 уроков):

общие принципы классических вычислений; простейшие классические вычисления; принцип Ландауэра; обратимые вентили; полусумматоры и сумматоры;  матрицы Паули; однокубитовые логические вентили; контролируемые квантовые логические вентили; оптическая реализация квантовых логических вентилей.

 

5. Особенности квантовых вычислений (4 урока):

теорема о запрете клонирования; сверхплотное кодирование; квантовый параллелизм; квантовая телепортация; эффект Хонга-У-Манделя; генерация ЭПР-пар; эксперимент по квантовой телепортации кубита.

 

6. Квантовые алгоритмы (5 урока):

алгоритм Дойча; алгоритм Дойча-Джозы; квантовое преобразование Фурье; алгоритм определения собственного числа; алгоритм поиска порядка; алгоритм факторизации Шора.

 

7. Основы теории коррекции ошибок (4 урока):

особенности классической теории коррекции ошибок; классический трехбитовый код; синдром ошибки;

особенности квантовой теории коррекции ошибок; логический кубит; трехкубитовый код; код Шора.

​

Еще раз об итогах — что будет знать и уметь делать прилежный слушатель курса

По результатам обучения обучающийся будет знать:

• фундаментальные понятия квантовой механики и теории квантовой информации; 

• важнейшие протоколы передачи и обработки квантовой информации;

• важнейшие квантовые логические алгоритмы; 

• основные протоколы классической и квантовой теории ошибок.

​

По результатам обучения обучающийся будет уметь:
• работать с классическими и квантовыми схемами коммутации;

• решать задачи по квантовой теории информации.

​

По результатам обучения обучающийся будет обладать навыками математического аппарата квантовой механики, применяемом в теории квантовой информации.

 

Об авторах

Курс создан Лабораторией квантовой оптики СПбГУ в рамках работы Консорциума Центра Компетенций Национальной Технологической Инициативы (НТИ) по направлению «Квантовые технологии». Столь серьезная сертификация программы гарантирует слушателям качественное изложение материала и его интерпретацию в русле современных научных трактовок.

 

Руководитель программы: Голубева Татьяна Юрьевна, д.ф.-м.н., профессор СПбГУ.

​

Исследовательские интересы проф. Т.Ю. Голубевой сосредоточены на явлениях квантовой оптики и квантовых вычислений. Она занимается изучением генерации многомодовых квантовых полей с неклассическими особенностями: их использованием в качестве информационного ресурса, проблемами их передачи и хранения, и однонаправленными квантовыми вычислениями. Т.Ю. Голубева к настоящему моменту опубликовала более 100 научных работ. Она занимается научным руководством аспирантов и студентов СПбГУ, ведёт экспертную научную деятельность.

 

Преподаватель: Тихонов Кирилл Сергеевич, к.ф.-м.н., старший преподаватель СПбГУ.

​

К.С. Тихонов защитил кандидатскую диссертационную работу «Модовый анализ квантовой памяти на холодных и теплых атомных ансамблях» под руководством профессора Т.Ю. Голубевой в 2015 г. Основная область его текущих исследовательских интересов связана с созданием квантовых атомно-полевых интерфейсов, квантовой памяти и реализации квантовых симуляторов на основе массивов нейтральных атомов. Он также работает в сотрудничестве с профессором Клеменсом Хаммерером из Ганноверского университета им. Лейбница над теоретическими вопросами, связанными с исследованием явления сверхизлучения и других кооперативных эффектов в спин-поляризованных атомных ансамблях.

 

Что нужно сделать, чтобы начать обучение?

Для начала обучения по данной дисциплине слушателю необходимо обратиться в Центр дополнительных образовательных программ СПбГУ по направлениям химия, физика, математика, механика, процессы управления к Ольге Николаевне Якушевой

e-mail: 

тел. :   +7 (812) 324-12-52,    +7 (812) 324-12-54

После оформления договора на обучение между слушателем и СПбГУ и оплате квитанции слушатель получит ссылку на онлайн-ресурс. 

 

 

​

Ученые придумали нанохолодильник для квантового компьютера — Наука

МОСКВА, 18 декабря. /ТАСС/. Ученые из Московского физико-технического института (МФТИ) совместно с коллегами из США и Швейцарии описали первое в своем роде устройство, которое точечно охлаждает кубиты — наименьшие элементы для хранения информации в квантовом компьютере — и может найти применение при создании микроскопических холодильников и для охлаждения квантовых компьютеров. Об этом во вторник сообщила пресс-служба МФТИ.

«Ученые из МФТИ с коллегами из США и Швейцарии описали пространственно-разнесенного квантового демона Максвелла — устройство, локально нарушающее второе начало термодинамики [согласно которому энтропия, то есть неупорядоченность, энергетически изолированной системы не может самопроизвольно уменьшаться]. Устройство может найти применение в квантовых компьютерах и микроскопических холодильниках точечного действия», — говорится в сообщении

Ученые провели эксперимент, целью которого было перевести кубит, который может пребывать в двух состояниях с одинаковой энергией — смешанном и чистом — в чистое, для которого характерна большая упорядоченность. Роль кубита в исследовании выполнял сверхпроводящий искусственный атом — микроскопическое устройство из тонких пленок алюминия, нанесенных на кремниевый чип. Ценность чистого состояния кубита в том, что его можно относительно легко перевести в основное состояние при помощи электромагнитного поля. При этом кубит охладится.

Демон — такой же кубит, он присоединяется к рабочему кубиту волноводом — особым кабелем, после чего кубиты меняются состояниями. «Наш демон делает так, что устройство, которое называется кубитом, переходит из менее упорядоченного состояния в более упорядоченное. Важно, что кубит при этом не изменяет свою энергию — это первое устройство такого рода с макроскопическим радиусом действия», — сказал ведущий автор статьи, сотрудник МФТИ и ETH Zurich Андрей Лебедев. Отмечается, что кубит находится от демона на расстоянии 1-5 м.

При этом демон нарушает закон термодинамики, согласно которому энтропия, то есть неупорядоченность, энергетически изолированной системы не может самопроизвольно уменьшаться. Однако, как отмечают авторы статьи, речь идет лишь о локальном нарушении закона физики. Дело в том, что демона нужно особым образом готовить перед каждым взаимодействием с кубитом, а на это уходит энергия, поэтому систему «кубит — демон» нельзя считать энергетически изолированной.

«Обычный холодильник воздействует на весь свой объем, а такой кубитный нанохолодильник будет охлаждать конкретную точку. Это может быть полезно, например, для алгоритмического охлаждения квантового компьютера: можно в коде основной «квантовой» программы написать подпрограмму, которая будет прицельно охлаждать самые горячие кубиты», — сказал заведующий лабораторией физики квантовых информационных технологий МФТИ Гордей Лесовик.

О квантовом компьютере

Квантовый компьютер — одна из самых обсуждаемых тем в науке и технологии за последние годы, это гипотетическое устройство на стыке информационных технологий и квантовой физики. В современных компьютерах единицей информации является бит, который может находиться в одном из двух возможных положений — ноль или единица. Единица информации в квантовом компьютере — кубит — в свою очередь может находиться в так называемом состоянии суперпозиции, то есть быть и нулем, и единицей одновременно. Это позволяет выполнять операции над большим количеством чисел одновременно (квантовый параллелизм), значительно ускорить вычисления, решать задачи, которые требуют астрономически большого времени даже на современных суперкомпьютерах.

Почему квантовые вычисления превосходят классические — Реальное время

Лекция математика из КФУ о будущем шифрования и о том, как хакер может выдать себя

Вопросы хранения информатизации в наш век выходят на первый план. Сберечь данные от хакеров способна квантовая криптография. О важности криптографии, квантовом компьютере и обеспечении конфиденциальности в лекции рассказал заместитель директора по научной деятельности Института вычислительной математики и информационных технологий КФУ Александр Васильев. «Реальное время» приводит пересказ лекции в рамках проекта «Открытый лекторий».

Классическая криптография

Криптография как наука способна обеспечить конфиденциальность передачи данных, проверку целостности аутентификации пользователей. В качестве развлекательного примера ученый предложил рассмотреть протокол аутентификации.

Он задал аудитории вопрос, какой выбрать способ, чтобы узнать легален ли пользователь, ведь в мире компьютеров пароль можно вводить многократно. Даже при ограниченном числе попыток, пользователь может прийти повторно с другого IP-адреса или представиться иным именем, попытаться взломать пароль путем многократных подборов.

Когда сервисы говорят, что пароль ненадежен, это неслучайно. Короткий шифр легко набирается путем перебора, поэтому рекомендуется создавать длинные пароли и использовать символы.

Насколько устойчив ваш пароль?

Выделяют две группы протоколов. Первая — протоколы симметричной криптографии, когда у двух участников есть секретный ключ и с его помощью они могут шифровать или дешифровать передаваемые сообщения. Это надежная техника. Единственная проблема: ключ надо распределить каким-то образом, то есть обеспечить секретность ключа у участников обмена, говорит Александр Васильев.

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

— Функции, лежащие в основе асимметричной криптографии, — это односторонние функции, которые легко вычислить и сложно обратить. Строго доказать существование односторонних функций пока не удается. Мы предполагаем, что они сложные, так как неизвестны эффективные способы их вычисления. Стойкость таких протоколов становится условной. Либо мы верим, что такие алгоритмы не существуют, либо понимаем, что у атакующего не хватает вычислительных ресурсов, чтобы взломать протокол. Здесь уместно перейти к квантовой криптографии и квантовым вычислениям. Именно они могут взломать подобные протоколы.

Квантовый параллелизм

Переходя к разговору о квантовой криптографии ученый отметил, что единицу квантовой информации называют кубит. Если классический бит информации может находится в двух состояниях: 0 и 1, то в противоположность ему квантовые биты одновременно находятся в суперпозиции своих состояний. Они могут одновременно быть и 0, и 1 с некоторыми амплитудами альфа и бета. Они могут задаваться в произвольной точке, которая интерпретирует состояние квантового бита, и находится на сфере Блоха.

Александр Васильев сравнил кубит с летящей в воздухе монетой:

— Монета летит в воздухе и крутится, и вы не знаете, как она упадет — орлом или решкой. Но как только вы поймаете ее, она окажется в одном из двух состояний.

Александр Васильев сравнил кубит с летящей в воздухе монетой: «Монета летит в воздухе и крутится, и вы не знаете, как она упадет — орлом или решкой. Но как только вы поймаете ее, она окажется в одном из двух состояний»

Похожая ситуация и с квантовым битом. Пока кубит участвует в процессе преобразований, вычислениях, он находится в произвольной позиции, точнее, одновременно в одном из базовых своих состояний: 0 или 1. Как только его измерят, то спроецируют на одно из базовых состояний. Такова особенность квантовой формации.

Благодаря тому, что квантовый бит может быть и 0, и 1, появляется понятие квантового параллелизма. Вычисляя некоторую функцию, аргумент которой задается квантовыми битами, аргументы одновременно принимают все свои возможные значения. И вычисляя эту функцию на аргументах, вычисляются все аргументы сразу. Это и есть квантовый параллелизм, который во многих случаях обеспечивает преимущества квантовых вычислений.

Квантовый компьютер за 15 млн долларов

Классический пример и простая иллюстрация квантовых вычислений — это алгоритм Дойча-Йожи. Интерпретировать этот алгоритм Александр Васильев предлагает следующим образом:

— Как узнать, фальшивая монета или настоящая? Как это можно проверить? Мы смотрим на монету с одной стороны, переворачиваем на другую и видим, что она фальшивая или настоящая. В квантовом случае мы можем создать суперпозицию состояния монеты, посмотреть на нее один раз и сразу узнать, фальшивая она или нет.

Настоящий значимый пример превосходства квантовых вычислений перед классическими обнаружили в 1994 году. В этот год Питер Шор предложил эффективный алгоритм разложения числа на множители. Это стало бы возможным, если бы был создан квантовый компьютер и тогда можно было бы взламывать соответствующие протоколы.

В 1994 году Питер Шор предложил эффективный алгоритм разложения числа на множители. Кадр: Physics World / YouTube

По словам Александра Васильева, все не так плохо, поскольку квантовых компьютеров еще нет, а как только появился алгоритм Питера Шора, криптография шагнула еще дальше и возникла постквантовая криптография. Подобная криптография работает в предположении, что квантовые компьютеры уже есть. Строятся протоколы устойчивые к квантовым компьютерам. Область квантовой криптографии сама представляет протоколы о защите информации.

Впрочем, не стоит лукавить, квантовые компьютеры есть. Правда, стоят они 15 млн долларов, покупают такие машины для исследовательских целей Google, NASA. И все же это не самый универсальный квантовый компьютер, на котором можно рассчитать алгоритм Шора. По словам Александра Васильева, компьютер настроен на вычисление оптимизационных задач и работает по принципу имитации квантового отжига.

В квантовой информации есть ряд особенностей, которые вызывают большой интерес у ученых. Их интересует процесс измерения квантовой информации. Считывание классической информации не составляет труда.

— Если же квантовый бит находится в суперпозиции квантовых состояний, то процесс детектирования измерений схлопывает его в одно из базовых состояний с соответствующими вероятностями. Самое главное то, что суперпозиция разрушается при воздействии измерения. Как только мы пытаемся читать информацию, она пропадает. И важно правильно ее считать. Квантовая информация может быть телепортирована, но не может быть клонирована, — утверждает Александр Васильев.

Квантовые компьютеры есть. Правда стоят они 15 млн долларов, покупают такие машины для исследовательских целей Google, NASA. Фото dwavesys.com

Квантовую информацию нельзя клонировать

Протокол квантовой телепортации существует, когда при помощи некоторых дополнительных преобразований обеспечивается появление состояния на другой стороне без передачи физического носителя. Между тем, клонировать квантовую информацию в отличие от классической нельзя.

— Если у вас есть квантовый бит в неизвестном состоянии, то нет возможности создать копию этого неизвестного квантового состояния. Если вы его не знаете, то не сможете клонировать, — замечает ученый.

Такие особенности подходят для создания криптографических протоколов. Например, известный протокол распределения ключа появился еще в 1984 году и с тех пор неоднократно модифицировался и совершенствовался. Протокол обеспечивает появление секретного ключа у двух получателей. В процессе его формирования один из участников передает квантовые состояния, переворачивая их различным образом. От того, в каком базисе будет производиться измерение будет зависеть, что будет получать второй участник.

Хакер, решивший перехватить передающиеся квантовые состояния, то есть попытавшийся их измерить, выдаст себя. Он разрушит состояние, которое ему передавали. И появится возможность детектировать его вмешательство в канал. Есть еще ряд криптографических протоколов, которые появлялись в этой области. Они демонстрируются экспериментально. В 2016 году на базе Казанского квантового центра запустили четырехузловую сеть для распределения ключа. Такие сети запускают по всему миру, а протокол внедряется в практику.

В 2016 году на базе Казанского квантового центра запустили четырехузловую сеть для распределения ключа. Фото kai.ru

Стойкость квантовой криптографии

Александр Васильев рассказал о таком протоколе, как квантовая цифровая подпись, являющимся аналогом рукописной подписи. Квантовый аналог использует квантовые биты вместо классических и протокол также демонстрируется экспериментально. Запускать его в массовое использование или в широкое применение пока не приходится.

Следы квантовых вычислений — тоже интересный протокол, который также демонстрируется экспериментально. На базе крупной лаборатории квантового вычислителя простейшие клиенты могут создавать кубиты и отправлять их на сервер. Протокол обеспечивает неосведомленность сервера о том, что он делал, с какими данными и что получил на выходе. Для него это становится шумом, что обеспечивается средствами квантовых вычислений.

— Я намерено не вдаюсь в подробности, потому что протоколы квантовых вычислений и квантовой криптографии содержат много математики, и абстрактной алгебры, и теории вероятности, и математическую статистику. Многие разделы математики привлекаются для обоснования протоколов. Я уже говорил вначале, когда мы говорим о стойкости протокола в классической криптографии, то предполагаем, что вычислительные возможности злоумышленника или атакующего ограничены. Это является необходимым условием стойкости наших протоколов. Если они не ограниченны, то протокол взламывается. Стойкость квантовой криптографии обеспечивает постулат: законы природы выполняются.

Записала Екатерина Гумарова

ОбществоТехнологииIT

Электроника НТБ — научно-технический журнал — Электроника НТБ

ПРИНЦИП СУПЕРПОЗИЦИИ В КВАНТОВОМ МИРЕ
На рубеже 19–20 веков возникла великая физическая теория – квантовая механика. За четверть века Планк, Бор, Шредингер, Гейзенберг и др. создали новый математический аппарат и решили основные задачи квантового описания объектов микромира.
Один из важнейших принципов квантовой механики – принцип суперпозиции состояний: если квантовая система может существовать в состояниях |Y1с и |Y2с, то она может столь же «законно» пребывать в состояниях, являющихся их суперпозицией: а|Y1с+b|Y2с, a, b – комплексные «амплитуды», |a|2+|b|2=1, |Yс — вектор состояния системы. Математически принцип суперпозиции – это следствие линейности уравнения Шредингера, основного уравнения квантовой механики. Принцип суперпозиции противоречит представлениям человека, сложившимся при наблюдении “классических” явлений в макромире, т.е. он контринтуитивен. Это хорошо иллюстрирует пример парадоксального кота Шредингера: если кот может пребывать в состояниях |жив с и |мертвс, то согласно принципу суперпозиции, он способен существовать и в состоянии |Yс =а|живс +b|мертвс, т.е. быть одновременно и живым, и мертвым. Отметим, что контринтуитивны и такие свойства квантовых частиц, как корпускулярно-волновой дуализм, коллапс волновой функции при измерении и др. Важнейший вопрос в квантовой механике – измерение параметров квантовой частицы. Суперпозиционное состояние |Yс =а|живс +b|мертвс математически можно рассматривать как вектор в Гильбертовом пространстве, где базисные векторы |живс и |мертвс суть орты осей координат, a и b – проекции вектора |Yс на эти координатные оси. При измерении аппаратура так воздействует на частицу, что вектор состояния проецируется на ось |живс или на ось |мертвс. При этом проекции вектора a и b – амплитуды вероятности обнаружить частицу в том или ином состоянии: Ржив=|a|2, Рмертв=|b|2. Числовые значения вероятностей Р находят статистически, путем многократных измерений идентичных систем.

КУБИТ – КВАНТОВЫЙ БИТ
На основании принципа суперпозиции все приборы можно разделить на «квантовые» и «классические». Состояния квантового прибора подчиняются принципу суперпозиции, а классического – нет. Эволюция состояний квантового прибора происходит согласно квантовому уравнению Шредингера. С этой точки зрения все квантовые системы являются квантовыми приборами. Если с различными состояниями квантового прибора связать информационные понятия и символы, его можно использовать для представления информационного процесса. В результате из квантовых приборов формируется квантовая элементная база квантовых информационных систем. Наибольший интерес представляют квантовые системы с двумя состояниями, позволяющие строить информационные системы с двоичным исчислением.
Квантовую систему с двумя состояниями, способную нести один бит информации, называют кубит (qubit) [1]. Если эти состояния |Y0с и |Y1с связаны с двумя уровнями энергии Е0<Е1, то говорят о двухуровневой системе. В других случаях состояния системы могут различаться поляризацией (фотона) или фазой (сверхпроводника). Квантовая система может быть макроскопической (сверхпроводники, сверхтекучие жидкости, бозе-газ), отдельной атомной частицей или колебательной модой. Все они применимы для образования кубита.
Простейшим является спиновый кубит, построенный на двух состояниях (уровнях энергии) спина …

ЭЛЕМЕНТАРНЫЕ ОПЕРАЦИИ НАД КУБИТАМИ В КВАНТОВОМ КОМПЬЮТЕРЕ
Доказано, что любой квантовый алгоритм можно разложить на последовательность элементарных преобразований состояний отдельных кубитов и пар кубитов (одно- и двухкубитовые преобразования, или «вентили»). Пусть начальное состояние кубита – суперпозиция |Y(0)с=а(0)|0с+b(0)|1с. После преобразования, совершенного за время t, состояние кубита будет |Y(t)с=а(t)|0с+b(t)|1с. Такое преобразование называют «поворотом» вектора |Y(0)с к |Y(t)с. Чтобы построить квантовый компьютер, нужно научиться совершать преобразования двух типов: любые повороты вектора |Y(0)с любого заданного кубита и поворот одного кубита под контролем другого [3].
Повороты кубита выполняются под воздействием внешнего резонансного поля. Квантовая эволюция состояния кубита |Y(t)с описывается уравнением Шредингера
где – энергия взаимодействия дипольного момента m кубита и внешнего резонансного электрического поля (например, лазера). Приведенное уравнение легко решается, его результат:
…
Пусть в начальный момент кубит находился в состоянии |0с (т.е. a(0)=1, b(0)=0). Тогда a(t)=cos(q/2), b(t)=-ieijsin(q/2), а вероятности найти кубит в момент t в состояниях |0с и |1с равны
…
Кубит с частотой W (частота Раби) переходит из состояния |0с в состояние |1с, а в промежуточные моменты времени находится в состоянии |Y(t)с=a(t)|0с+b(t)|1с. Контролируя длительность и фазу внешнего воздействия, можно перевести кубит в состояние, описываемое любой суперпозицией. При Wt=p/2 получаем преобразование Адамара Н:
а при Wt=p – операцию отрицания НЕ:
В двухкубитовом преобразовании поворот V(q,j) контролируемого кубита совершается только когда состояние контролирующего кубита – |1с . Для такого преобразования необходимо физическое взаимодействие между контролирующим и контролируемым кубитами хотя бы во время выполнения операции. Специалисты предлагают как использовать природное взаимодействие кубитов (например, контактное спин-спиновое взаимодействие ядер в молекулах), так и включать его внешним воздействием (напряжениями на электродах). Если V(q,j)=НЕ, реализуется операция Контролируемое …, где Е – знак сложения по модулю 2. Подробно преобразования состояний кубитов описаны в [4–7].

КВАНТОВЫЙ КОМПЬЮТЕР
Структура квантового компьютера представлена на рис. 2. Его квантовую часть составляют n кубитов. К каждому из них может быть приложено селективное воздействие резонансными импульсами внешнего переменного поля. Генераторами полей и адресацией их излучения управляет классический компьютер. Перед началом вычислительного процесса все n кубитов необходимо инициализировать – привести в состояние |0 с . Это не тривиальная операция. Если в качестве кубитов используются спины ядер, для их инициализации потребуется охлаждение до температур порядка 1mK или поляризация спинов накачкой. Посредством одно- и двухкубитовых вентилей вводятся данные и исполняется алгоритм. Результат вычисления записывается в конечном квантовом состоянии кубитов. Чтобы его считать, эти состояния необходимо измерить.
Важнейшее свойство квантового компьютера – квантовый параллелизм. Составим квантовый алгоритм Uf вычисления функции f(x). Инициализируем все кубиты компьютера в состояние |0 с . Над каждым из n используемых в вычислениях кубитов произведем преобразование Адамара Результатом будет суперпозиция … базисных состояний системы из n кубитов с одинаковыми вероятностями 2-n/2. Базисные состояния |хс представляют собой двоичные числа от 0 до 2n-1. Произведем над |хс преобразование Uf, соответствующее вычислению функции f(х). В результате за один прогон алгоритма Uf получим суперпозицию, содержащую значения функции f от огромного числа значений аргумента x (от 0 до 2n-1). В этом и заключается феномен квантового параллелизма. Число значений аргумента x определяется только количеством n задействованных в вычислительном процессе кубитов.
Однако при измерении конечного состояния компьютера суперпозиция состояний его кубитов разрушается. Возникает вопрос: в чем польза от квантового параллелизма, если в результате можно получить (в данном случае – с вероятностью 2-n) только одно из значений f(xў)? Для вычисления функции при другом аргументе xўў инициализацию, вычисление, измерение придется повторять сначала. Тем не менее, квантовый параллелизм находит практическое применение. Дело в том, что нас может интересовать какое-то одно из значений функции f(xў). Если как-либо увеличить вероятность интересующего состояния |f(xў)с до значений, близких к 1, то нужное нам значение f(xў) было бы найдено при первом же измерении с вероятностью ~1.
Состояние системы кубитов Y1 в более общем виде выглядит как
где Сх – комплексные числа, Cx=|Cx|exp(ij). В алгоритм вычисления можно включить операции над векторами |xс, изменяющие фазу: |xс®exp(ijx)|xс. Тогда
Вычислительный процесс носит характер интерференции – комплексные амплитуды базисных состояний образуются при сложении комплексных чисел. Изменяя фазы амплитуд, можно добиться, чтобы амплитуды интересующих состояний складывались конструктивно, а других – деструктивно. Так построен знаменитый алгоритм Гровера поиска в неструктурированной базе данных [8]. Некоторые авторы вообще рассматривают квантовый компьютер как сложное интерференционное устройство, усматривая его вычислительную мощь именно в интерференции векторов состояний [6].

ПУТИ СОЗДАНИЯ КВАНТОВЫХ КОМПЬЮТЕРОВ
Наиболее впечатляющие результаты получены в экспериментах по квантовым вычислениям методом импульсного ядерного магнитного резонанса (ЯМР) в молекулярных жидкостях (ансамблевый квантовый компьютер) [9, 10]. Предлагается также использовать ионы в ловушках в вакууме [11], ядерные спины атомов 31Р в монокристаллическом кремнии [12], спины одиночных электронов в квантовых точках в двумерном газе в полупроводниковых гетероструктурах [13], атомы в резонаторах электромагнитного поля [14]. Возможно создание кубитов на состояниях сверхпроводников, разделенных переходами Джозефсона и различающихся числом зарядов [15–17] или фазой сверхпроводников [18]. Одно из достоинств применения сверхпроводников – использование структур с наноразмерами, технология которых в значительной мере разработана. Интересно, что модели квантовых компьютеров могут быть построены на линейных оптических элементах (делители пучка, поляризаторы, фазовращатели, интерферометры). В последнем случае одиночный фотон проходит через оптическую систему. Его волновая функция охватывает всю оптическую систему, интерферируя на выходных интерферометрах. Обнаружение фотона в том или ином интерферометре есть измерение результата вычисления. Таким образом, оптическая модель квантового компьютера весьма наглядно демонстрирует интерференционную природу квантового вычислительного процесса [19].
В ансамблевом ядерном магнитнорезонансном квантовом компьютере кубитами выступают спины I=1/2 ядер водорода (протоны) и углерода 13С в молекулах жидкости. Так, в молекуле трихлорэтилена (рис. 3) спины ядер двух атомов 13С и одного протона образуют три кубита. Два атома 13С химически неэквивалентны, поэтому частоты их ЯМР wA и wB будут различны во внешнем постоянном магнитном поле В0. Протон имеет третью резонансную частоту wC. Подавая импульсы переменного магнитного поля на частотах wA, wB, wC, можно селективно управлять квантовой эволюцией любого из этих спинов (выполнять однокубитовые вентили). Между спинами ядер, разделенных одной химической связью 1Н – 13С и 13С – 13С, имеется магнитное контактное взаимодействие, энергия которого HI=2JABIZAIZB+2JBCIZBIZC.
Взаимодействия IA « IB и IB « IC позволяют строить двухкубитовые вентили CNOTAB, CNOTBA, CNOTBC, CNOTCB (первый индекс обозначает контролирующий, второй – контролируемый кубит). Операции CNOTAC и CNOTCA основываются на процессах обмена состояниями соседних спинов.
Поскольку молекул в пробирке импульсного ЯМР-спектрометра достаточно много (~1020), можно говорить об ансамбле параллельно работающих квантовых компьютеров. Это позволяет решить сложные проблемы инициализации и измерения состояния кубитов по завершении процесса вычислений. Состояния |0с и |1с кубита в конечном состоянии определяются по знаку (фазе) линии резонансного поглощения: при |0с наблюдается, например, линия поглощения, а при |1с – излучения.
На спиновых двух- и трехкубитовых квантовых компьютерах уже реализованы модельный квантовый алгоритм Дойча-Иозса по определению типа дискретной функции от дискретного аргумента [20], алгоритм Гровера поиска в базе данных [21], алгоритм с квантовой коррекцией ошибок [22]. Эти результаты произвели большое впечатление на научное сообщество. Однако построить квантовый компьютер данного типа с числом кубитов порядка 103 вряд ли возможно, так как трудно представить столько ядер с различимыми частотами магнитного резонанса.
Интересна идея построения квантового компьютера на ловушках в вакууме. Ионы или атомы размещают в области минимума потенциала, создаваемого системой электродов и электромагнитных полей. Тепловое движение атомов замораживают методом лазерного охлаждения. Изначально данную технологию развивали для создания квантовых стандартов частоты. Но сегодня большой интерес к ней связан с квантовыми компьютерами. Эксперименты в этом направлении ведут в Лос-Аламосе и Национальном институте стандартов США [1, 23]. “Подвешенные” в вакууме ионы и атомы являются максимально изолированными от окружающего мира квантовыми частицами. Внешняя связь сохраняется только для их удержания в ловушке (посредством электродов с напряжениями) и управления квантовой эволюцией (сфокусированные лазерные пучки).
Энергетическая диаграмма кубита на основе ионов Ca+ приведена на рис. 4. Уровни 2S1/2 (основной) и 2D5/2 (метастабильный) выбраны как логические |0с и |1с. Сфокусированные на ионе импульсы лазерного излучения с длиной волны 729 нм выполняют однокубитовые эволюции. Другие переходы используются для доплеровского лазерного охлаждения (2S1/2®2P1/2, 397 нм; 2D3/2®2P1/2, 866 нм), лазерного охлаждения колебаний ионов в ловушке (рамановское рассеяние на переходе 2S1/2®2D3/2), а также при считывании информации.
Однако в квантовом компьютере на основе ионных ловушек сложно реализовать двухкубитовые вентили CNOT. Расстояние между ионами в ловушке (10–20 мкм) достаточно велико по сравнению с атомными размерами, поэтому прямое взаимодействие между внутренними кубитами ионов практически отсутствует. Но поскольку эти ионы участвуют в колебательном движении, можно ввести дополнительный кубит. Его логический |0с соответствует колебательному движению (одной из мод) в основном состоянии, логическая |1с – колебательному состоянию с одним фононом. В результате внутренние кубиты отдаленных ионов взаимодействуют через колебательное движение системы ионов. Однако достаточно сложно организовать преобразования, включающие переходы между уровнями энергии электронов внутри атомов и переходы между колебательными состояниями цепочки ионов,. Неудивительно, что в опытах по созданию квантового компьютера на ионах в ловушке пока не наблюдается быстрого прогресса.
Большой интерес вызывают проекты твердотельной реализации элементов квантовых компьютеров, поскольку можно использовать накопленный опыт микроэлектронной технологии. При этом сами компьютеры имели бы сходство с чипами микросхем. В [12] в качестве кубитов предлагается использовать спины I=1/2 ядер фосфора 31Р в монокристаллическом кремнии (рис. 5). Частотой магнитного резонанса можно управлять, подавая на наноэлектрод над атомом электрическое напряжение V – оно поляризует электронную оболочку атома и изменяет константу А так называемого сверхтонкого взаимодействия электронного S и ядерного I спинов атома (энергия взаимодействия h2=A(V)·I·S). Так достигается селективный доступ внешнего резонансного магнитного поля к спину атомного ядра. Структура с единичным атомом, встроенным в заданную точку под электродом, отдаленно напоминает полевой транзистор. Если в последнем затвор управляет движением электронов проводимости в канале, в случае кубита напряжения на затворе воздействуют на движение электрона внутри атома, поляризуя атом и изменяя резонансную частоту кубита.
Однако на этом пути немало проблем. Так, необходимо организовать производство бесспиновых монокристаллических слоев кремния (без спинового изотопа 29Si), разместить единичные атомы 31Р в заданных точках кремния, вырастить бездефектный барьерный слой, создать систему управляющих электродов с наноразмерами. Нужна низкотемпературная электроника, управляющая напряжениями на электродах. Кристалл следует охладить до температур ~1 мК, чтобы все спины ядер 31Р оказались в основном состоянии ( |0с ). Достаточно сложная проблема – измерение конечных состояний ядерных спинов (одним из вариантов ее решения могла бы стать реализация идеи ансамблевого квантового компьютера).
До создания полномасштабного (103–104 кубитов) квантового компьютера предстоит пройти большой путь. Пока неясно, какой вариант окажется предпочтительнее. Широкомасштабные поиски идут по всему фронту физики, постоянно возникают новые идеи и предложения. Оптимисты полагают, что среди них могут найтись «прорывные», которые приблизят долгожданный момент. По-видимому, одной из таких идей можно считать метод квантовой коррекции ошибок.

КВАНТОВАЯ КОРРЕКЦИЯ ОШИБОК
У квантового компьютера есть грозный противник. Имя ему – декогерентизация. Кубиты нельзя полностью изолировать от внешнего мира, они подвержены шумовому воздействию среды. Флуктуации напряжений на электродах, шумовые токи, неточности выполнения самих импульсных воздействий на кубиты – все это вносит неконтролируемые ошибки в фазы и амплитуды состояний кубитов при вычислительном процессе. По истечении времени декогерентизации квантовых состояний системы кубитов контролируемый вычислительный процесс прекратится. А время декогерентизации, как правило, меньше, чем нужно для выполнения сложного алгоритма, состоящего из многих (~109) вентилей.
Ситуация казалась тупиковой. Однако выход был найден в квантовой коррекции ошибок [24]. В теории обычных компьютеров хорошо известны методы кодирования |0с и |1с большим числом битов. При возникновении ошибки анализ кодовых комбинаций позволяет ее найти и исправить. Такой подход удалось разработать в квантовом варианте, где ошибки могут быть фазовыми и амплитудными. Выяснилось, что если вероятность ошибки при выполнении одной элементарной операции ниже некоторого порога, вычислительный процесс может длиться сколь угодно долго – операции квантовой коррекции исправляют больше ошибок, чем вносят. Этот вывод очень важен – по существу он имеет силу теоремы существования полномасштабного квантового компьютера.

ТЕХНОЛОГИЯ АТОМНЫХ РАЗМЕРОВ
Технологии с атомным разрешением уже довольно зрелы, работа с отдельными атомами является экспериментальной реальностью. Можно утверждать, что на рубеже 2020–2030 годов начнется изготовление микросхем, работающих на квантовых принципах. Три сегодняшних технологии могут оказаться базовыми: молекулярная эпитаксия, нанолитография и зондовая микроскопия. Молекулярная эпитаксия позволяет создавать совершенные моноатомные слои кристаллов, т.е. атомный размер достигается по толщине. Велико значение и электронно-лучевой нанолитографии с разрешением 1–10 нм. Методы зондовой микроскопии позволяют наблюдать поверхность тел с атомным разрешением. В то же время зонды используют как атомные манипуляторы – они позволяют перемещать, доставлять, снимать атомы с поверхности. Зонды могут служить и катализаторами локальных поверхностных химических реакций (окисление, травление, осаждение материала), доставляя энергию локального возбуждения (химической активации) в форме электрического тока, напряжения, фотонов, механической энергии (деформации). Наконец, зондовые методы применимы для измерения состояния атомных частиц.

РОЛЬ КВАНТОВЫХ КОМПЬЮТЕРОВ
Для квантовых компьютеров пока разработано небольшое число алгоритмов, но уже получены ошеломляющие результаты. В 1994 году Шор создал алгоритм факторизации – определения простых множителей больших чисел [25]. На классическом компьютере для этого требуется экспоненциально большое число операций. На невозможности решить данную задачу за приемлемое время на современных компьютерах основан алгоритм кодирования секретной информации RSA. Шор показал, что квантовый компьютер способен решить задачу факторизации за n3 операций, где n – разрядность числа. Коэффициент ускорения решения при больших n может быть весьма велик. Такое же ускорение имеет место для ряда задач квантовой физики [26]. В то же время установлено, что многие алгоритмы, неплохо выполняемые на классических компьютерах, не ускоряются на квантовом [27].
Таким образом, квантовые компьютеры не могут полностью заменить существующий компьютерный мир, а лишь дополняют его. В алгоритме Шора, по-видимому, впервые обнаружен феномен, когда класс сложности задачи коренным образом изменяется в зависимости от того, на каких физических принципах основан вычислительный процесс. Свое слово должны сказать математики – им предстоит разработать квантовые алгоритмы и определить, для каких задач достигается ускорение и каким оно будет.
В заключение отметим, что в ходе разработки идей квантовой информатики углубляются знания и о самой квантовой физике, уясняются ее основные понятия и принципы. Кроме того, квантовые методы позволяют создать квантовый канал связи и передавать по нему информацию. Но об этом сюжете квантовой информатики мы расскажем в будущем.

Литература
1. Schumacher B.W. – Phys. Rev. A51 (1995), p. 2738–2747.
2. Hughes R.J. et al. – Fortschr. Phys. 46 (1998) 45, p. 329–361.
3. Barenco A. et al. – Phys. Rev. A52 (1995), p. 3457.
4. Steane A. Quantum Computing. – Quant-ph/9708033, v.2, 1997, Sept. 24.
5. Rieffel. E., Polak W. An Introduction to Quantum Computing for non-physicists. – Quant-ph/9809016, 1998, Sept. 24.
6. Aharonov D. Quantum Computation. – Quant-ph/9812037, 1998, Dec.15.
7. Preskill J. Lecture Notes for Physics 229/ – Quantum Information and Computation, 1998, Sept.
8. Grover L.K. Proceedings of the Twenty Eight Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, 1996. p. 212–219.
9. Cory D.G., Fahmy A.F., Havel T.F. Proc. of the 4th Workshop on Physics and Computation (Complex Systems Institute, Boston, New England), 1996.
10. Gershenfeld N.A., Chuang I.L. – Science, 1997, p. 275, 350–356.
11. Cirak J.I., Zoller P. – Phys. Rev. Lett. 74, 1995, р.4091–4094.
12. Kane B.E. – Nature 393, 1998, May 14.
13. Loss D., Vincenzo D.P. – Phys. Rev., A57, №1, p. 120–126.
14. Cirac J.I. et al. – Phys. Rev. Lett. 78, 1997, p. 3221.
15. Shnirman A., Schцn G., Hermon Z. – Phys. Rev. Lett. 79, 1997, p. 2371–2374.
16. Schцn G., Shnirman A., Makhlin Y. – Cond-mat/9811029, 1998, Nov., 3.
17. Averin. D.V. – Solid State Comm. 105, 1998, p. 659–664.
18. Ioffe L.B. et al. – Cond-mat/9809116, 1999, v.2.
19. Adami C., Cert N.J. – Quant-ph/9806048, 1998, June 14.
20. Chuang I.L. et al. – Nature 393, 1998, p. 143–146.
21 Jones J.A., Mosca M., Hansen R.S. – Nature, 393, 1998, р. 344–346.
22. Cory D.G. et al. – Quant-ph/9802018, 1998, Feb 6.
23. Wineland D.J. et al. – J. Res. Natl. Inst. Stand. Tech. 103, 1998, p. 259.
24. Steane A. – Proc. Roy. Soc. of London A, 452, 1996, p. 2551–2577.
25. Shor P.W. – SIAMJ. Comp., 26, 1997, № 5, p. 1484–1509.
26. Zalka C. – Proc. Roy. Soc. Lond. A 454, 1998, p. 313–322.
27. Ozhigov Y. – Quant-ph/9712051.

Квантовые компьютеры и проблема энергопотребления

Деятельность научно-исследовательских работников можно сравнить с лотереей: бывает так, что работаешь, как вол, и топчешься месяцами, а то и годами, на месте, и бывает так, что один-единственный удачный эксперимент или теоретическое предсказание продвигает фронт научного знания на километры вперед за считанные дни.

Квантовые компьютеры — как раз тот случай, когда даже работая максимально интенсивно, нельзя гарантировать успех в короткие сроки. По крайней мере, на нынешнем уровне экспериментальной культуры. И, как часто бывает в научном сообществе, хотя квантовым компьютерам уже пророчили скорое появление, уже звучат предостережения, что их появление может оказаться совсем не таким скорым, как ожидается.

В частности, профессор физики Университета Арканзаса Хулио Джи-Банаклош (Julio Gea-Banacloche), считает, что составители оптимистичных прогнозов не учли выделение дополнительной тепловой энергии в процессе работы механизмов коррекции ошибок, которую квантовые компьютеры будут не в состоянии рассеять. В то же время, не использовать механизмы коррекции нельзя, поскольку разрабатываемые в настоящее время квантовые устройства имеют слишком малое время декорегентизации.

Если не вдаваться в подробности, то время декогерентизации можно описать как промежуток времени, в течение которого волновая функция кубита (квантового бита) сохраняет свою форму, соответствующую логической 1 или 0. При этом, если процитировать Джона Арчибальда Уилера: «квантовый эффект является квантовым эффектом лишь в том случае, если это — измеренный эффект», то есть состояние кубита фиксируется только в момент измерения и все вычисления сводятся к операции измерения состояния кубита и определения его волновой функции. Имея на вооружении большое время декогерентизации и умея приготавливать квантовые состояния квантовой системы, мы можем организовать хранение данных в своеобразной ячейке памяти, которую и назовем кубитом (qubit — квантовый бит). Прелесть квантовых вычислений заключается в том, что при измерении состояний, представимых в виде суперпозиции чистых состояний, квантовые вычисления производятся как бы одновременно над всеми составляющими (это явление носит название квантового параллелизма).Квантовый параллелизм — главная трудность квантовых вычислений

Помимо чисто практической выгоды — распараллеливания вычислений, квантовый параллелизм является и причиной уязвимости квантовой системы к внешним воздействиям. Так как состояние системы может быть результатом суперпозиции нескольких состояний, важно, чтобы оно было изолировано от паразитного внешнего воздействия, приводящего к изменению результирующего состояния и, соответственно, искажающего результат квантовых измерений или, если будет угодно, вычислений.

Таким образом, очень важно сохранить когерентность состояний кубита. Когерентные состояния очень чувствительны к внешним воздействиям, будь то измерение или случайное воздействие, например, шальной квант электромагнитного поля. От последних, кстати, изолироваться практически невозможно, так как всегда существуют так называемые нулевые флуктуации поля, проявляющиеся, в частности, в эффекте Казимира (эффект возникновения силы притяжения между зеркалами резонатора, вызванный разницей в спектрах нулевых колебаний поля вне и внутри резонатора).

Для решения этой проблемы еще в 1995 году были придуманы способы коррекции ошибок, а в 1998 была осуществлена первая их практическая реализация. Основной идеей предложенного метода коррекции ошибок было разложение смешанного состояния кубита на составляющие (своего рода спектр) для сравнения состояний до вычисления и после. Зная спектр состояний кубита возможно приготовление аналогичного состояния в любой момент, пока, конечно, нам не понадобится что-то с кубитом сделать. Этот процесс — разложение состояния кубита на спектр составляющих и восстановление когерентного состояния, аналогичен процессу обновления содержимого динамической памяти в компьютере. На данный момент время декогерентизации в прототипах кватовых чипов не превышает 1 мкс, следовательно, для поддержания состояния кубита его необходимо обновлять миллион раз в секунду, что требует немалых затрат. По мнению профессора Джи-Банаклоша, для квантовых вычислений требуется время не меньшее 1 мс, то есть на три порядка больше, чем то, что достигнуто сейчас.

На графике приведена зависимость потребляемой энергии от времени декогерентизации для теоретического квантового чипа, используемого для взлома криптографического кода AES с 1024-разрядным ключом. Из расчетов профессора Университета Арканзаса следует, что даже чипы с временем декогерентизации порядка 10 мкс будут рассеивать более 100 МВт. В то же время, по его расчетам, при времени декогерентизации 1 мс такой квантовый чип будет потреблять около 1 Вт.

Профессор Джи-Банаклош утверждает, что проанализировал все схемы, предлагаемые для реализации квантовых компьютеров и выдвинул тезис, который по своей фундаментальности похож на содержание теоремы Карно о коэффициенте полезного действия идеальной тепловой машины. Он утверждает, что количество энергии, затрачиваемой на коррекцию ошибок, обратно пропорционально времени декогерентизации.

Покритиковав существующие подходы, Джи-Банаклош предлагает и возможные выходы из ситуации: в первом предлагается использовать спин электрона, с которым ученые умеют работать достаточно хорошо, но связав его со сверхпроводящим квантово-интерференционным устройством (SQUID, устройство с джозефсоновским контактом), в котором возможно достижение достаточно большого времени декогерентизации. Второй подход, который считается более перспективным, заключается в использовании атомов с хорошо изолированным энергетическими уровнями, характеризующимися большими временами жизни.

Помимо времени декогерентизации, есть еще и сами алгоритмы коррекции ошибок, которые далеки от идеала, а значит, не исключено, что ограничение по затратам энергии можно обойти, используя улучшенные алгоритмы коррекции и, возможно, когда-нибудь можно будет построить квантовый чип, используя время декогерентизации порядка 1 мкс.

квантовый параллелизм

квантовый параллелизм
Далее: Эффективность Up: Квантовый компьютер Предыдущая: Вероятностная интерпретация Содержание

Учитывая, что наш регистр квантовой памяти отличается от классического регистром что он может хранить суперпозицию базовых состояний регистра, можно задаться вопросом, что это означает относительно эффективности квантовой вычисления. Изучение квантовых вычислений относительно новое, большинство отдать должное Ричарду Фейнману за то, что он первым предположил, что были задачи, которые квантовый компьютер мог выполнять экспоненциально лучше классического компьютера.Фейнман заметил, что классический компьютер не может моделировать квантово-механическую систему без страдает от экспоненциального замедления. При этом он намекнул, что возможно, используя устройство, поведение которого было по своей природе квантовым в природы можно было бы смоделировать такую ​​систему без этого экспоненциального замедлять. (Фейнман)

Некоторые квантовые алгоритмы основаны на так называемом квантовом параллелизм. Квантовый параллелизм возникает из способности квантового регистр памяти существует в суперпозиции базовых состояний.Квант регистр памяти может существовать в суперпозиции состояний, каждый компонент этой суперпозиции можно рассматривать как единственный аргумент в пользу функция. Функция, выполняемая над регистром в суперпозиции состояний, таким образом, выполняется на каждом из компонентов суперпозиция, но эта функция применяется только один раз. Поскольку количество возможных состояний — 2 ⁿ , где n — количество кубитов в квантовом регистре вы можете выполнить одну операцию над квантовым компьютер, что потребовало бы экспоненциального количества операций на классический компьютер.Это фантастика, но более наложенные состояния которые существуют в вашей регистрации, тем меньше вероятность того, что вы измерять какой-то конкретный станет.

В качестве примера предположим, что вы используете квантовый компьютер для вычислить функцию ( x ) = 2 * x мод 7, для x целые числа от 0 до 7 включительно. Вы можете подготовить квант регистр, который находился в равновзвешенной суперпозиции состояний 0-7. Тогда вы могли бы выполнить 2 * x mod 7 операция один раз, а регистр будет содержать равновзвешенную суперпозицию 1,2,4,6,1,3,5,0 состояния, это выходы функции 2 * x mod 7 для входов 0-7.При измерении квантового регистра вы будет иметь 2/8 шанса измерения 1 и 1/8 шанса измерение любых других выходов. Казалось бы, такого рода параллелизм бесполезен, так как чем больше мы получаем от параллелизма, тем менее вероятно, что мы сможем измерить значение функции для конкретного Вход. Было разработано несколько умных алгоритмов, в первую очередь Питером. Шору и Л. К. Гроверу, которым удалось использовать квантовый параллелизм на функция, в которой их интересует какое-то свойство всех входов, не только конкретный.

---

Далее: Эффективность Up: Квантовый компьютер Предыдущая: Вероятностная интерпретация Содержание

Мэтью Хейворд — Репозиторий GitHub по квантовым вычислениям и алгоритмам Шора

Квантовый параллелизм — где квантовые компьютеры получают свое преимущество от

Как квантовые компьютеры используют квантовую суперпозицию для одновременного выполнения множества вычислительных путей.

Изображение MonikaP с сайта Pixabay

Квантовые компьютеры были предложены в 1980-х годах.С тех пор физики кропотливо работали над тем, чтобы использовать силу природы для удовлетворения потребностей вычислений. Не существует единственно лучшего метода физической реализации квантового компьютера; поле разделено на несколько конкурирующих подходов, таких как ионные ловушки, оптические решетки, квантовые биты фотонов, ядерный магнитный резонанс и т. д. Но все эти разные подходы работают в направлении реализации одной и той же модели квантовых вычислений в аппаратных средствах. Пока мы работаем с моделью правильно, нам не нужно беспокоиться о том, как она реализована на оборудовании.Честно говоря, существует более одной модели квантовых вычислений, но в этой статье мы рассмотрим только стандартную модель квантовой схемы.

Мы разбиваем эту статью на четыре части. В первой части мы разберемся, что такое отдельный кубит. Затем мы увидим, как можно представить несколько кубитов. В третьей части мы вводим преобразования, действующие на кубиты. И, наконец, мы собрали все это вместе, чтобы объяснить, как квантовые компьютеры могут параллельно выполнять несколько вычислительных путей.

Классические компьютеры работают с битами, где каждый бит может находиться в состоянии 0 или 1. Квантовые компьютеры работают с квантовыми битами или кубитами. Кубит существует не как 0 или 1, а как суперпозиция двух (вспомните кот Шредингера, который одновременно мертв и жив?).

Давайте представим это математически. Состояние кубита ψ можно записать как:

Приведенное выше обозначение называется обозначением скобки, но мы не будем его здесь рассматривать. Этот кубит существует как 0, так и 1, но если его измерить, мы получим либо 0, либо 1, но не оба сразу.Вероятность того, что мы получим 0, определяется как | α | ², а вероятность того, что мы получим 1, определяется как | β | ². После выполнения измерения кубит теряет свою суперпозицию и продолжает существовать в наблюдаемом состоянии как 0 или 1. Обозначение в скобках весьма полезно по многим причинам, но те же уравнения также можно удобно записать с использованием матриц и векторов как:

Заявление об отказе от ответственности: В статье используются свободные обозначения, что не является технически полностью правильным. Например, указанные выше состояния 0 и 1 должны быть записаны как базисные векторы | 0> и | 1>.Причиной использования нечетких обозначений является тот досадный факт, что среда не позволяет использовать математические символы в тексте, а преобразование каждого экземпляра в изображение делает статью неудобной для чтения.

Состояние двух незапутанных кубитов может быть представлено как тензорное произведение их индивидуальных состояний. Если первый кубит имеет амплитуды a и b , а второй кубит имеет амплитуды c и d, их комбинированное состояние может быть записано как:

Некоторые двухкубитовые состояния не могут быть разложены на тензорные произведения два отдельных кубита.Такие кубиты называются запутанными кубитами. Запутанность играет центральную роль во многих квантовых алгоритмах, особенно в области квантовой криптографии. В классической физике нет аналогов квантовой запутанности. Мы не будем рассматривать запутанность в этой статье.

Нет ничего интересного, если мы ничего не можем сделать с кубитами. Но можем — с помощью преобразований. Классические компьютеры оперируют битами с помощью логических вентилей, таких как NOT, AND, OR, NAND, NOR, XOR и т. Д.Точно так же квантовые компьютеры работают с кубитами, используя квантовые вентили. В соответствии с положениями квантовой механики все операции, выполняемые над кубитами, должны быть линейными и обратимыми. Следовательно, все квантовые вентили должны быть линейными и обратимыми.

Вентиль НЕ — самый простой из них. Он просто инвертирует 0 и 1.

Один вентиль, который пронизывает квантовые вычисления, — это вентиль Адамара. Он преобразует кубит, существующий только как 0, в равную суперпозицию 0 и 1, т.е. если мы измерим кубит, мы получим 0 с вероятностью 50%, и мы получим 1 с вероятностью 50%.Это, как мы увидим, служит отличной отправной точкой для многих квантовых алгоритмов.

Теперь, вооружившись вышеуказанными знаниями, давайте разберемся, как квантовые компьютеры творит чудеса. Мы сделаем это на простом примере работы с двумя битами. Предположим, вам дана классическая функция f , которая принимает два бита на входе и возвращает один бит на выходе.

Чтобы оценить f на всех четырех перестановках двух битов, нам нужно будет вызвать f четыре раза: f (0,0), f (0,1), f (1, 0), f (1,1).Использование квантового параллелизма позволяет нам оценить все четыре входа за один вызов f. Обратите внимание, однако, что наша функция f необратима, и все операции с кубитами должны быть обратимыми. Итак, сначала мы определяем обратимую версию f следующим образом:

Знак плюс с кружком вокруг него обозначает операцию XOR. Квантовый оракул U принимает два входа x и y и выводит два значения. Первый — это собственно x .Второй — это значение: y XOR f (x) . Легко видеть, что когда y = 0, , второй выход равен f (x) .

Мы устанавливаем вход ϕ как равную суперпозицию четырех двухбитовых входов 00, 01, 10, 11. Для этого мы инициализируем два кубита как 0 и применяем вентиль Адамара к обоим из них. Это представлено как:

Затем мы применим нашу квантовую функцию U к этому состоянию, установив y = 0 . Это дает нам:

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

Более подробное, но все же мягкое введение в квантовые вычисления можно найти в обзорной статье по адресу https://arxiv.org/abs/2006.12025

Квантовый параллелизм составляет основу многих квантовых алгоритмов. Однако есть некоторые важные предостережения, которые необходимо учитывать. Хотя вывод содержит наложение интересующих нас результатов, мы не можем напрямую их прочитать.Любая прямая форма измерения даст нам один результат, а остальные три будут потеряны. Следовательно, необходимо использовать хитрые уловки, чтобы прочитать окончательный ответ, который нас интересует, и эти уловки могут быть нетривиальными с вычислительной точки зрения. Во-вторых, для нашего примера подготовка состояния ввода была простой, но это может не относиться к другим проблемам. Приведет ли использование квантового параллелизма к ускорению работы над классическими альтернативами, зависит от этих предостережений.

Квантовые компьютеры уже здесь, и пора нам начать серьезно относиться к квантам.Чем больше людей из разных сфер примут его, тем быстрее он станет реальностью.

Квантовый параллелизм — обзор

КВАНТОВЫЕ ВЫЧИСЛЕНИЯ / ИНФОРМАЦИЯ

Наше обсуждение здесь будет кратким из-за ограничений пространства и времени, а также из-за того, что концепции квантовых вычислений и информации все еще в некоторой степени умозрительны. Позвольте мне воспользоваться случаем, чтобы порекомендовать читателю отличную книгу по этой теме, Джулиана Брауна [2001]. Хотя это «популярная» книга, она чрезвычайно информативна как по деталям, так и по истории квантовых вычислений и включает предисловие одного из первых сторонников квантовых вычислений Дэвида Дойча.Вклад Дойча восходит к 1983 году, и ему предшествовало предложение Ричарда Фейнмана в 1979 году об использовании квантового компьютера для моделирования квантовой механики.

В классической модели компьютера самый фундаментальный строительный блок, бит, может существовать только в одном из двух различных состояний: «0» или «1». Мы уже указали, что в спинтронике биты могут быть представлены, скажем, как ускорение или замедление вращения электрона. Это предполагает большие преимущества в миниатюризации и, следовательно, в скорости, и это само по себе имеет большой практический потенциал.Гордон Мур, соучредитель Intel, предположил, что вычислительная мощность (на самом деле буквально количество транзисторов в интегральной схеме определенной области) удваивается примерно каждые два года, и это стало широко известно как «закон Мура». Было предсказано, что закон Мура истечет примерно через десять лет, потому что к тому времени транзисторы на кристалле должны будут опуститься до молекулярного уровня. Но спинтроника обещает пройти дальше этого уровня и опуститься на атомный уровень. Но перспективы квантовых вычислений гораздо более фундаментальны, чем расширение закона Мура на несколько десятилетий, как бы важно это ни было.

«Квантовый бит» (кубит) может находиться в классических состояниях «0» и «1», но он также может находиться в суперпозиции (когерентном состоянии) как «0», так и «1». Это связано с хорошо известной концепцией «суперпозиции», в которой, скажем, электрон может одновременно находиться в обоих состояниях «спин вверх» и «спин вниз» до тех пор, пока не будет измерен, когда он затем «декогерируется» в одно из состояний. эти государства. ¹³ Некоторые примеры кубитов включают в себя состояние поляризации фотона (т. Е. Параллельную или перпендикулярно поляризованную к заданной оси), двухуровневую атомную систему (например.например, атом водорода, с электроном в основном и первом возбужденном состоянии) и, конечно же, бедная «кошка Шредингера» (которая одновременно мертва и жива до тех пор, пока не будет проведено измерение, глядя на кошку, чтобы определить, действительно ли радиоактивный атом распался).

Рассмотрим регистр из 3 классических битов: можно было бы использовать этот регистр для представления любого из чисел от 0 до 7 одновременно. В регистре из 3 кубитов регистр может отображать все числа от 0 до 7 одновременно!

Процессор, который может использовать регистры кубитов, фактически сможет выполнять вычисления, используя все возможные значения входных регистров одновременно.Это явление иногда называют квантовым параллелизмом. Таким образом, очевидно, что квантовые вычисления имеют больше преимуществ, чем просто миниатюризация, которую дает спинтроника. В принципе, квантовые вычисления могут включать совершенно новые алгоритмы на кубитах, использующие феномен квантового параллелизма. Возможно, наиболее известным из них является «алгоритм Шора», созданный Питером Шором из лабораторий AT&T Bell. Этот алгоритм учитывает большое количество простых множителей. Эта задача в классическом смысле настолько сложна, что составляет основу шифрования с открытым ключом RSA, стандартного метода шифрования с открытым ключом, используемого сегодня. ¹⁴ Это сильно поднимает вопросы квантовой теории сложности и может ли она отличаться от классической теории сложности, и, возможно, даже то, что квантовый компьютер мог бы решить по крайней мере некоторые проблемы NP за полиномиальное время. Но вопрос о том, является ли факторинг классической проблемой NP, остается открытым.

Еще одним важным квантовым алгоритмом, хотя и не столь впечатляющим с точки зрения кажущегося преимущества в скорости, является «алгоритм Гровера», который может выполнять поиск в несортированном списке длиной n в среднем во времени в порядке √ n в отличие от обычного n. /2 для классического алгоритма линейного поиска, который проверяет каждый элемент списка до тех пор, пока не будет найдено совпадение.Алгоритм Гровера начинается с установки квантового регистра для суперпозиции всех возможных элементов в пространстве поиска. Алгоритм Гровера включает в себя последовательность простых квантовых операций над состоянием регистра. Гровер описывает их в терминах волновой механики: «Все пути, ведущие к желаемым результатам, конструктивно интерферируют, а другие мешают деструктивно и нейтрализуют друг друга».

В некоторых интерпретациях квантового параллелизма использовалась «интерпретация множества миров» (MWI) квантовой механики, впервые предложенная Хью Эвереттом [1957] и «популяризированная» Брайсом Селигманом Де Виттом [1970], который фактически дал ей захватывающий ярлык. «Много миров.«Множество вселенных» на самом деле лучше терминологии, чем «множество миров», а термин «мультивселенная» иногда используется для обозначения «сверхвселенной» из всех возможных вселенных.

Основная идея MWI, знакомая философам из дебатов о «модальном реализме» в семантике возможных миров для модальной логики, заключается в том, что существует множество возможных миров, а мы находимся только в одном. В дело вступает квантовая механика: каждый раз, когда квантовый эксперимент проводится с разными возможными результатами, каждый из этих результатов существует в другом возможном мире.Все они реальны, даже если «я» будет осознавать только то, что содержит результат, который я видел. Я заключил «я» в кавычки, потому что, очевидно, каждому результату соответствует «я». Это, конечно, исключает квантовое убийство или самоубийство, когда я фактически являюсь котом Шредингера и был убит как один из результатов.

Дэвид Дойч, которого я уже упоминал как основоположника квантовых вычислений, верит в интерпретацию множества миров. В Deutsch [1985] он предположил, что квантовые вычисления могут происходить одновременно во многих возможных мирах, давая своего рода параллелизм, который даст «метод, с помощью которого универсальный квантовый компьютер может выполнять определенные вероятностные задачи быстрее, чем при любом его классическом ограничении. .

Согласно Дойчу, картина интерференции одиночных фотонов, наблюдаемая в эксперименте с двойной щелью, может быть объяснена интерференцией фотонов во множественных вселенных. С этой точки зрения эксперимент по однофотонной интерференции неотличим от эксперимента по многофотонной интерференции.

Интересно, что в отношении возможности квантовых вычислений взломать шифрование RSA можно «сделать лимонад из лимонов», используя определенные устройства квантового шифрования, которые на самом деле, похоже, достигают более быстрых практических успехов, чем создание квантовых компьютеров. уже несколько компаний предлагают коммерческую квантовую криптографию.Что квант забирает, квант возвращает.

Как отмечалось выше, классическая криптография с открытым ключом основана на вычислительной сложности определенных математических задач, например, факторизации. Однако квантовая криптография опирается на одну из двух особенностей квантовой механики, либо на неопределенность квантовой запутанности Гейзенберга. Чтобы передать хотя бы ограниченное представление о том, как задействованы эти особенности, мы должны сделать небольшое отступление и кратко поговорить о криптографии.

Ключ к криптографии, конечно же, «ключ», т.е.е., механизм для генерации зашифрованного текста из обычного текста и / или наоборот. Вероятно, все мы знакомы с детства с клавишей «алфавитный сдвиг», когда простой текст зашифрован, где «a» становится «b», «b» становится «c» и т. Д., А «z» становится «a». Шифрованный текст, конечно, расшифровывается обратным способом. На самом деле ключ можно рассматривать как положительное целое число, например, в данном случае 1 (для «сдвига 1», в отличие от 2 для «сдвига 2»). Это так называемый «секретный ключ» или «симметричная» криптография, потому что по существу один и тот же ключ может использоваться для кодирования (сдвиг на 1 влево) или декодирования (сдвиг на 1 вправо).«Открытый ключ» или «асимметричная» криптография использует пару ключей: открытый ключ, известный в принципе всем, и закрытый ключ, известный только получателю сообщения. Когда Алиса отправляет сообщение Бобу, она использует широко распространенный открытый ключ Боба, а затем он декодирует его, используя свой закрытый ключ.

При криптографии с секретным ключом ключ должен передаваться тайно, либо лично, либо путем передачи (в прежние времена курьером). Наилучший способ сделать это — это так называемая проблема распределения ключей.Сложность того, чтобы сделать это лично, состоит в том, что это требует больших усилий, а проблема с передачами состоит в том, что их можно перехватить. Основная проблема криптографии с секретным ключом, которая усугубляет проблему распространения ключей, — это необходимость часто отправлять ключи. Лучшая гарантия того, что ключ не может быть взломана путем поиска шаблонов, — это использовать каждый раз другой ключ, убедившись, что он длиннее, чем отправляемое сообщение. Большим преимуществом криптографии с открытым ключом является то, что ваш закрытый ключ никогда не нужно передавать (вы можете просто случайным образом сгенерировать его), и тем не менее открытый ключ может передаваться открыто и широко.Но соответствующая трудность состоит в том, что тогда она может быть нарушена, скажем, путем разложения на простые множители. ¹⁵ Разве не было бы неплохо, если бы у вас был способ распространения секретного ключа, который относительно прост и не может быть взломан без вашего обнаружения? Это обещание квантовой криптографии.

Квантовая криптография возникла у Стивена Визнера [1983] (он фактически написал статью примерно в 1970 году), где он показал, как передавать ключ, используя дополнительные наблюдаемые.Наиболее известные дополнительные наблюдаемые — это положение и импульс частицы, ставшие известными благодаря многочисленным обсуждениям принципа неопределенности Гейзенберга. Но перпендикулярные фотонные поляризационные состояния света также являются дополнительными наблюдаемыми объектами, например прямолинейная (вертикальная и горизонтальная), а также диагональная поляризация (45 ° и 135 °). Точно так же, как невозможно точно определить как положение, так и импульс частицы (поскольку измерения сосредоточены на одном, они размываются на другом), также невозможно одновременно измерить как вертикальную, так и горизонтальную поляризацию света.Чарльз Беннетт и Джайлс Брассард [1984] разработали протокол (названный BB84), использующий состояния поляризации фотонов для передачи криптографического ключа. Мы не будем вдаваться в подробный протокол BB84, а просто отметим функцию, которая защищает от компрометации. Измерение значения одной дополнительной наблюдаемой подразумевает неопределенность в отношении другой. В частности, это означает, что получение некоторой информации о неизвестной квантовой системе обычно вызывает нарушение квантового состояния этой системы.Безопасность квантовой криптографии зависит от этого компромисса.

Второй метод квантовой криптографии, использующий запутанные пары фотонов, был разработан Артуром Экертом [1991]. Мы представим его в виде мысленного эксперимента «выдавать желаемое за действительное». Предположим, что у Алисы и Боба есть по одной из пары «запутанных монет». Под «запутанным» понимается то, что если в данной последовательности монета Алисы выпадает решкой, монета Боба выпадает решкой, когда он ее подбрасывает, и наоборот, и это произойдет мгновенно даже на больших расстояниях.Теперь, если Алиса хочет передать Бобу случайный ключ, она подбрасывает свою монету определенное количество раз, отмечая каждый бросок. Затем она отправляет Бобу незакодированное сообщение, скажем, по телефону, и просит его сделать то же самое. Если Алиса подбрасывает HTT…, то Боб подбрасывает THH…, и с предварительным пониманием того, что H = 1, T = 0, они знают, что ключ 100…

Звучит слишком хорошо, чтобы быть правдой? Ну пока это просто волшебство. Но теперь давайте введем квантовую запутанность. Квантовая запутанность — это когда состояния двух объектов не могут быть описаны отдельно, и, следовательно, между наблюдаемыми свойствами существуют корреляции.Например, можно приготовить две частицы в одном квантовом состоянии так, что, когда одна будет иметь спин вверх, у другой всегда будет наблюдаться вращение вниз, и наоборот. Есть две важные особенности квантовой запутанности: во-первых, квантовая запутанность может сохраняться, даже если два объекта сильно разделены пространством, и, во-вторых, квантовая запутанность может существовать, даже если невозможно предсказать, какие свойства будут наблюдаться.

Итак, давайте теперь заменим последовательность запутанных пар частиц двумя последовательностями подбрасывания монеты, и пусть Алиса измеряет первую частицу в каждой паре, а Боб измеряет вторую частицу.Тогда у нас по сути то же самое, что и у волшебных монет, но теперь это не магия, это квантовая механика! ¹⁶

Как передаются частицы? Между Алисой и Бобом может быть секретная встреча, на которой последовательности частиц распределяются между ними, но также возможно, что частицы могут быть распределены, скажем, через оптоволоконный кабель, если они являются фотонами, или даже через свободное пространство. Подслушиватель (всегда называемый «Ева») на этом кабеле должен был бы наблюдать фотон, чтобы прочитать сигнал, и это измерение можно было бы обнаружить, применив нечто, называемое теоремой Белла.

Возвращаясь к квантовым вычислениям, один философский вопрос, который, как мне кажется, еще недостаточно изучен, — это связь между квантовыми вычислениями и квантовой логикой. Последний был первоначально введен Биркгофом и фон Нейманом [1936], но имел очень разные мотивы, и понятие «кубит» не было введено явно. Данн, Хагге, Мосс и Ван [2004] — это начало.

Другой интересный с философской точки зрения аспект квантовых вычислений состоит в том, что они обратимы.Никакая информация не теряется! Это также может произойти в классической закрытой системе или может быть запрограммировано с большими накладными расходами в вычисления на классическом компьютере (нужно каким-то образом сохранить все предыдущие шаги). Но замечательный факт о квантовых вычислениях заключается в том, что обратимость предоставляется бесплатно, без особого внимания.

Является ли мир в конечном итоге цифровым благодаря квантовой механике? Ответ да, и нет. Да, когда это измеряется, нет, когда это не так. Квантовые вычисления — это своего рода гибрид цифровых и аналоговых вычислений.Возможно, это лучшее из обоих?

Вместо того, чтобы закончить на этой высокой ноте, честность заставляет меня упомянуть огромную практическую трудность построения квантового компьютера из-за того факта, что когерентные состояния легко разрушаются небольшими изменениями в их среде. По этой причине важно развивать отказоустойчивые квантовые вычисления. Одно из многообещающих направлений — «топологические квантовые вычисления», где кубиты хранятся в виде «квантовых узлов». Как известно всем, кто пытался распутать узел на своей обуви, узлы очень устойчивы даже к большим изменениям в окружающей среде.Впервые это было предложено Фридманом, Китаевым и Вангом [2000], где «узлы» представляют собой косы в двумерной квазичастице, называемой «аньоном». Серьезная проблема реализации заключается в том, действительно ли можно найти подходящие анонимы в природе. Отличная общая статья со ссылками — Collins [2006]. Эта парадигма квантовых вычислений реализуется Microsoft Station Q в Санта-Барбаре. http://stationq.ucsb.edu/research.html (по состоянию на 23 июля 2007 г.).

Первые квантовые компьютеры были независимо построены в 1998 году в Оксфордском университете и в исследовательском центре IBM в Алмадене. ¹⁷ Они были основаны на ядерном магнитном резонансе (ЯМР) и имели 2 кубита. Затем были продемонстрированы 5, 6, 7 кубитные компьютеры, кульминацией которых стала 12-кубитная модель NRM в 2006 году. D-Wave Systems, Inc. продемонстрировала в феврале 2007 года рабочий прототип коммерчески доступного 16-кубитного «адиабатического» квантового компьютера.

Квантовый параллелизм — обзор

КВАНТОВЫЕ ВЫЧИСЛЕНИЯ / ИНФОРМАЦИЯ

Наше обсуждение здесь будет кратким из-за ограничений пространства и времени, а также из-за того, что концепции квантовых вычислений и информации все еще в некоторой степени умозрительны.Позвольте мне воспользоваться случаем, чтобы порекомендовать читателю отличную книгу по этой теме, Джулиана Брауна [2001]. Хотя это «популярная» книга, она чрезвычайно информативна как по деталям, так и по истории квантовых вычислений и включает предисловие одного из первых сторонников квантовых вычислений Дэвида Дойча. Вклад Дойча восходит к 1983 году, и ему предшествовало предложение Ричарда Фейнмана в 1979 году об использовании квантового компьютера для моделирования квантовой механики.

В классической модели компьютера самый фундаментальный строительный блок, бит, может существовать только в одном из двух различных состояний: «0» или «1».Мы уже указали, что в спинтронике биты могут быть представлены как, скажем, ускорение или замедление вращения электрона. Это предполагает большие преимущества в миниатюризации и, следовательно, в скорости, и это само по себе имеет большой практический потенциал. Гордон Мур, соучредитель Intel, предположил, что вычислительная мощность (на самом деле буквально количество транзисторов в интегральной схеме определенной области) удваивается примерно каждые два года, и это стало широко известно как «закон Мура». Было предсказано, что закон Мура истечет примерно через десять лет, потому что к тому времени транзисторы на кристалле должны будут опуститься до молекулярного уровня.Но спинтроника обещает пройти дальше этого уровня и опуститься на атомный уровень. Но перспективы квантовых вычислений гораздо более фундаментальны, чем расширение закона Мура на несколько десятилетий, как бы важно это ни было.

«Квантовый бит» (кубит) может находиться в классических состояниях «0» и «1», но он также может находиться в суперпозиции (когерентном состоянии) как «0», так и «1». Это связано с хорошо известной концепцией «суперпозиции», в которой, скажем, электрон может одновременно находиться в обоих состояниях «спин вверх» и «спин вниз» до тех пор, пока не будет измерен, когда он затем «декогерируется» в одно из состояний. эти государства. ¹³ Некоторые примеры кубитов включают состояние поляризации фотона (т. Е. Параллельную или перпендикулярно поляризованную к заданной оси), атомную двухуровневую систему (например, атом водорода, с электроном в основном состоянии и первое возбужденное состояние. ) и, конечно же, бедная «кошка Шредингера» (которая одновременно мертва и жива, пока не будет проведено измерение, глядя на кошку, чтобы определить, распался ли радиоактивный атом).

Рассмотрим регистр из 3 классических битов: можно было бы использовать этот регистр для представления любого из чисел от 0 до 7 одновременно.В регистре из 3 кубитов регистр может отображать все числа от 0 до 7 одновременно!

Процессор, который может использовать регистры кубитов, фактически сможет выполнять вычисления, используя все возможные значения входных регистров одновременно. Это явление иногда называют квантовым параллелизмом. Таким образом, очевидно, что квантовые вычисления имеют больше преимуществ, чем просто миниатюризация, которую дает спинтроника. В принципе, квантовые вычисления могут включать совершенно новые алгоритмы на кубитах, использующие феномен квантового параллелизма.Возможно, наиболее известным из них является «алгоритм Шора», созданный Питером Шором из лабораторий AT&T Bell. Этот алгоритм учитывает большое количество простых множителей. Эта задача в классическом смысле настолько сложна, что составляет основу шифрования с открытым ключом RSA, стандартного метода шифрования с открытым ключом, используемого сегодня. ¹⁴ Это сильно поднимает вопросы квантовой теории сложности и может ли она отличаться от классической теории сложности, и, возможно, даже то, что квантовый компьютер мог бы решить по крайней мере некоторые проблемы NP за полиномиальное время.Но вопрос о том, является ли факторинг классической проблемой NP, остается открытым.

Еще одним важным квантовым алгоритмом, хотя и не столь впечатляющим с точки зрения кажущегося преимущества в скорости, является «алгоритм Гровера», который может выполнять поиск в несортированном списке длиной n в среднем во времени в порядке √ n в отличие от обычного n. /2 для классического алгоритма линейного поиска, который проверяет каждый элемент списка до тех пор, пока не будет найдено совпадение. Алгоритм Гровера начинается с установки квантового регистра для суперпозиции всех возможных элементов в пространстве поиска.Алгоритм Гровера включает в себя последовательность простых квантовых операций над состоянием регистра. Гровер описывает их в терминах волновой механики: «Все пути, ведущие к желаемым результатам, конструктивно интерферируют, а другие мешают деструктивно и нейтрализуют друг друга».

В некоторых интерпретациях квантового параллелизма использовалась «интерпретация множества миров» (MWI) квантовой механики, впервые предложенная Хью Эвереттом [1957] и «популяризированная» Брайсом Селигманом Де Виттом [1970], который фактически дал ей захватывающий ярлык. «Много миров.«Множество вселенных» на самом деле лучше терминологии, чем «множество миров», а термин «мультивселенная» иногда используется для обозначения «сверхвселенной» из всех возможных вселенных.

Основная идея MWI, знакомая философам из дебатов о «модальном реализме» в семантике возможных миров для модальной логики, заключается в том, что существует множество возможных миров, а мы находимся только в одном. В дело вступает квантовая механика: каждый раз, когда квантовый эксперимент проводится с разными возможными результатами, каждый из этих результатов существует в другом возможном мире.Все они реальны, даже если «я» будет осознавать только то, что содержит результат, который я видел. Я заключил «я» в кавычки, потому что, очевидно, каждому результату соответствует «я». Это, конечно, исключает квантовое убийство или самоубийство, когда я фактически являюсь котом Шредингера и был убит как один из результатов.

Дэвид Дойч, которого я уже упоминал как основоположника квантовых вычислений, верит в интерпретацию множества миров. В Deutsch [1985] он предположил, что квантовые вычисления могут происходить одновременно во многих возможных мирах, давая своего рода параллелизм, который даст «метод, с помощью которого универсальный квантовый компьютер может выполнять определенные вероятностные задачи быстрее, чем при любом его классическом ограничении. .

Согласно Дойчу, картина интерференции одиночных фотонов, наблюдаемая в эксперименте с двойной щелью, может быть объяснена интерференцией фотонов во множественных вселенных. С этой точки зрения эксперимент по однофотонной интерференции неотличим от эксперимента по многофотонной интерференции.

Интересно, что в отношении возможности квантовых вычислений взломать шифрование RSA можно «сделать лимонад из лимонов», используя определенные устройства квантового шифрования, которые на самом деле, похоже, достигают более быстрых практических успехов, чем создание квантовых компьютеров. уже несколько компаний предлагают коммерческую квантовую криптографию.Что квант забирает, квант возвращает.

Как отмечалось выше, классическая криптография с открытым ключом основана на вычислительной сложности определенных математических задач, например, факторизации. Однако квантовая криптография опирается на одну из двух особенностей квантовой механики, либо на неопределенность квантовой запутанности Гейзенберга. Чтобы передать хотя бы ограниченное представление о том, как задействованы эти особенности, мы должны сделать небольшое отступление и кратко поговорить о криптографии.

Ключ к криптографии, конечно же, «ключ», т.е.е., механизм для генерации зашифрованного текста из обычного текста и / или наоборот. Вероятно, все мы знакомы с детства с клавишей «алфавитный сдвиг», когда простой текст зашифрован, где «a» становится «b», «b» становится «c» и т. Д., А «z» становится «a». Шифрованный текст, конечно, расшифровывается обратным способом. На самом деле ключ можно рассматривать как положительное целое число, например, в данном случае 1 (для «сдвига 1», в отличие от 2 для «сдвига 2»). Это так называемый «секретный ключ» или «симметричная» криптография, потому что по существу один и тот же ключ может использоваться для кодирования (сдвиг на 1 влево) или декодирования (сдвиг на 1 вправо).«Открытый ключ» или «асимметричная» криптография использует пару ключей: открытый ключ, известный в принципе всем, и закрытый ключ, известный только получателю сообщения. Когда Алиса отправляет сообщение Бобу, она использует широко распространенный открытый ключ Боба, а затем он декодирует его, используя свой закрытый ключ.

При криптографии с секретным ключом ключ должен передаваться тайно, либо лично, либо путем передачи (в прежние времена курьером). Наилучший способ сделать это — это так называемая проблема распределения ключей.Сложность того, чтобы сделать это лично, состоит в том, что это требует больших усилий, а проблема с передачами состоит в том, что их можно перехватить. Основная проблема криптографии с секретным ключом, которая усугубляет проблему распространения ключей, — это необходимость часто отправлять ключи. Лучшая гарантия того, что ключ не может быть взломана путем поиска шаблонов, — это использовать каждый раз другой ключ, убедившись, что он длиннее, чем отправляемое сообщение. Большим преимуществом криптографии с открытым ключом является то, что ваш закрытый ключ никогда не нужно передавать (вы можете просто случайным образом сгенерировать его), и тем не менее открытый ключ может передаваться открыто и широко.Но соответствующая трудность состоит в том, что тогда она может быть нарушена, скажем, путем разложения на простые множители. ¹⁵ Разве не было бы неплохо, если бы у вас был способ распространения секретного ключа, который относительно прост и не может быть взломан без вашего обнаружения? Это обещание квантовой криптографии.

Квантовая криптография возникла у Стивена Визнера [1983] (он фактически написал статью примерно в 1970 году), где он показал, как передавать ключ, используя дополнительные наблюдаемые.Наиболее известные дополнительные наблюдаемые — это положение и импульс частицы, ставшие известными благодаря многочисленным обсуждениям принципа неопределенности Гейзенберга. Но перпендикулярные фотонные поляризационные состояния света также являются дополнительными наблюдаемыми объектами, например прямолинейная (вертикальная и горизонтальная), а также диагональная поляризация (45 ° и 135 °). Точно так же, как невозможно точно определить как положение, так и импульс частицы (поскольку измерения сосредоточены на одном, они размываются на другом), также невозможно одновременно измерить как вертикальную, так и горизонтальную поляризацию света.Чарльз Беннетт и Джайлс Брассард [1984] разработали протокол (названный BB84), использующий состояния поляризации фотонов для передачи криптографического ключа. Мы не будем вдаваться в подробный протокол BB84, а просто отметим функцию, которая защищает от компрометации. Измерение значения одной дополнительной наблюдаемой подразумевает неопределенность в отношении другой. В частности, это означает, что получение некоторой информации о неизвестной квантовой системе обычно вызывает нарушение квантового состояния этой системы.Безопасность квантовой криптографии зависит от этого компромисса.

Второй метод квантовой криптографии, использующий запутанные пары фотонов, был разработан Артуром Экертом [1991]. Мы представим его в виде мысленного эксперимента «выдавать желаемое за действительное». Предположим, что у Алисы и Боба есть по одной из пары «запутанных монет». Под «запутанным» понимается то, что если в данной последовательности монета Алисы выпадает решкой, монета Боба выпадает решкой, когда он ее подбрасывает, и наоборот, и это произойдет мгновенно даже на больших расстояниях.Теперь, если Алиса хочет передать Бобу случайный ключ, она подбрасывает свою монету определенное количество раз, отмечая каждый бросок. Затем она отправляет Бобу незакодированное сообщение, скажем, по телефону, и просит его сделать то же самое. Если Алиса подбрасывает HTT…, то Боб подбрасывает THH…, и с предварительным пониманием того, что H = 1, T = 0, они знают, что ключ 100…

Звучит слишком хорошо, чтобы быть правдой? Ну пока это просто волшебство. Но теперь давайте введем квантовую запутанность. Квантовая запутанность — это когда состояния двух объектов не могут быть описаны отдельно, и, следовательно, между наблюдаемыми свойствами существуют корреляции.Например, можно приготовить две частицы в одном квантовом состоянии так, что, когда одна будет иметь спин вверх, у другой всегда будет наблюдаться вращение вниз, и наоборот. Есть две важные особенности квантовой запутанности: во-первых, квантовая запутанность может сохраняться, даже если два объекта сильно разделены пространством, и, во-вторых, квантовая запутанность может существовать, даже если невозможно предсказать, какие свойства будут наблюдаться.

Итак, давайте теперь заменим последовательность запутанных пар частиц двумя последовательностями подбрасывания монеты, и пусть Алиса измеряет первую частицу в каждой паре, а Боб измеряет вторую частицу.Тогда у нас по сути то же самое, что и у волшебных монет, но теперь это не магия, это квантовая механика! ¹⁶

Как передаются частицы? Между Алисой и Бобом может быть секретная встреча, на которой последовательности частиц распределяются между ними, но также возможно, что частицы могут быть распределены, скажем, через оптоволоконный кабель, если они являются фотонами, или даже через свободное пространство. Подслушиватель (всегда называемый «Ева») на этом кабеле должен был бы наблюдать фотон, чтобы прочитать сигнал, и это измерение можно было бы обнаружить, применив нечто, называемое теоремой Белла.

Возвращаясь к квантовым вычислениям, один философский вопрос, который, как мне кажется, еще недостаточно изучен, — это связь между квантовыми вычислениями и квантовой логикой. Последний был первоначально введен Биркгофом и фон Нейманом [1936], но имел очень разные мотивы, и понятие «кубит» не было введено явно. Данн, Хагге, Мосс и Ван [2004] — это начало.

Другой интересный с философской точки зрения аспект квантовых вычислений состоит в том, что они обратимы.Никакая информация не теряется! Это также может произойти в классической закрытой системе или может быть запрограммировано с большими накладными расходами в вычисления на классическом компьютере (нужно каким-то образом сохранить все предыдущие шаги). Но замечательный факт о квантовых вычислениях заключается в том, что обратимость предоставляется бесплатно, без особого внимания.

Является ли мир в конечном итоге цифровым благодаря квантовой механике? Ответ да, и нет. Да, когда это измеряется, нет, когда это не так. Квантовые вычисления — это своего рода гибрид цифровых и аналоговых вычислений.Возможно, это лучшее из обоих?

Вместо того, чтобы закончить на этой высокой ноте, честность заставляет меня упомянуть огромную практическую трудность построения квантового компьютера из-за того факта, что когерентные состояния легко разрушаются небольшими изменениями в их среде. По этой причине важно развивать отказоустойчивые квантовые вычисления. Одно из многообещающих направлений — «топологические квантовые вычисления», где кубиты хранятся в виде «квантовых узлов». Как известно всем, кто пытался распутать узел на своей обуви, узлы очень устойчивы даже к большим изменениям в окружающей среде.Впервые это было предложено Фридманом, Китаевым и Вангом [2000], где «узлы» представляют собой косы в двумерной квазичастице, называемой «аньоном». Серьезная проблема реализации заключается в том, действительно ли можно найти подходящие анонимы в природе. Отличная общая статья со ссылками — Collins [2006]. Эта парадигма квантовых вычислений реализуется Microsoft Station Q в Санта-Барбаре. http://stationq.ucsb.edu/research.html (по состоянию на 23 июля 2007 г.).

Первые квантовые компьютеры были независимо построены в 1998 году в Оксфордском университете и в исследовательском центре IBM в Алмадене. ¹⁷ Они были основаны на ядерном магнитном резонансе (ЯМР) и имели 2 кубита. n состояний, представляющих разные входные строки.n различных проблем одновременно ». Однако разработчики лекарств, или радиотерапевты, или те, кому они собираются продавать свои квантовые компьютеры и программное обеспечение, по-видимому, захотят знать ответы на проблемы . Но вы не может считать из квантового компьютера, который выполнил такое «квантовое параллельное» вычисление, ответ на все эти проблемы (значение функции на всех входах). Фактически, вы можете прочитать ответ на только одна проблем (значение F (x) F на конкретном входе x).Если вы выполнили суперпозицию и измеряете регистр, в который алгоритм записывает значение F (x), вы получите ответ на случайно выбранном входе (знаменитая случайность квантовой теории), и если вы измерите часть компьютер, на котором была сохранена входная строка, вы также получите значение указанного случайно нарисованного ввода. Здесь нет абсолютно никакого преимущества перед простым запуском классического алгоритма на случайно выбранном входе.

Что правильно с квантовым параллелизмом

Так чем же может быть полезен этот квантовый параллелизм? Причина этого, по сути, заключается в существовании множества взаимно несовместимых наблюдаемых в квантовой теории (положение и импульс являются наиболее известным примером пары несовместимых наблюдаемых, хотя они не являются теми, которые обычно используются в предложениях для квантовых вычислений).В частности, квантовая теория позволяет эффективно (и часто эффективно) измерять такое состояние суперпозиции способами , отличными от , считывая значение F и вход, который его породил — способами, несовместимыми с этим считыванием. Это может сказать нам некоторые вещи о функции F , отличные от , ее значения на определенных входах, и эти вещи могут даже зависеть от ее значений на экспоненциально многих входах . Несовместимость этих измерений с тем, которое считывает входные данные и значение функции, означает, что после получения глобальной информации информация о входах и значениях функций больше не доступна — пример хорошо известного факта, что «измерение нарушает состояние» квантовой системы.

Почему нас это волнует?

Многие проблемы, представляющие практический интерес, принимают такую ​​форму: у нас есть программа (скажем, классическая схема — из которой мы всегда можем построить квантовую схему) для вычисления функции F, но мы хотим знать кое-что о функции, которую мы не знаю, как просто считывать информацию, которую мы использовали для построения схемы. Например, если F принимает значения в упорядоченном наборе (например, действительные числа, с некоторой точностью), мы можем захотеть узнать его максимальное значение и, вероятно, также вход, на котором он принимает этот максимум.(Это приложение, «оптимизация», упоминается в статье.) Или мы можем знать из-за способа построения схемы для вычисления функции, что она является периодической (нам нужно, чтобы набор входных данных имел некоторую структуру это позволяет нам определять периодичность, конечно — может быть, они интерпретируются как двоичная запись для целых чисел, например), но мы можем не знать — и, возможно, захотим узнать — период. Чтобы немного упростить, решение этой проблемы является ключевым ингредиентом в алгоритме Шора для разложения больших целых чисел с использованием квантовых вычислений — того, который нарушает используемые в настоящее время протоколы криптографии с открытым ключом.n вычислений функции. Повторюсь, факт, что квантовые вычисления позволяют эффективно измерять такое состояние суперпозиции другими способами, кроме считывания значения F, тем не менее дает нам потенциальный доступ после всего лишь одной оценки функции к определенному количеству информации о «глобальные» аспекты функции, такие как ее период, зависят от многих значений. Мы по-прежнему очень ограничены в том, сколько информации мы можем получить о функции за один прогон «квантово-параллельной» оценки функции — конечно, это только полиномиально, а не экспоненциально много, которое можно было бы получить, прочитав ее значение. на всех входах.Но в некоторых случаях мы можем получить важную информацию о некоторых глобальных аспектах функции, которая нас волнует, с помощью ряда квантово-параллельных вычислений функций, которые, если бы они были простыми вычислениями классических функций, оставили бы нам возможность далеко продвинуться. меньше информации или даже никакой информации об этом глобальном аспекте функции. Насколько существенно это ускорение, может зависеть от того, какую глобальную информацию мы хотим знать о функции и что мы знаем о ней заранее.Если мы знаем, что он периодический, то в хороших случаях мы можем использовать полиномиально много вычислений, чтобы получить период в ситуациях, когда, как считается, нам понадобится экспоненциально много классических вычислений. Это — основа «почти экспоненциального» ускорения факторизации алгоритмом Шора (оно не совсем экспоненциально, по-видимому, потому, что лучший классический алгоритм — это не просто попытка найти период, найденный в квантовом алгоритме, методом грубой силы, но более изощренно). Для относительно неструктурированных задач оптимизации квантовые алгоритмы обычно используют алгоритм Гровера, который, опять же, действительно использует квантовый параллелизм и может найти оптимальную или высокую точность примерно с * квадратным корнем * из числа вычислений функций, необходимых классически.{n / 2} — по-прежнему экспоненциальный, хотя и с половинным показателем; преимущество, которое все еще может быть полезным, если большой фактор постоянной стоимости, возникающий при выполнении квантовых операций вместо классических, не заглушает его.

Квантовые алгоритмы за пределами квантового параллелизма

Конечно, существуют и другие сценарии, в которых квантовые вычисления могут быть полезны, которые не очень хорошо описываются как «обнаружение неизвестных свойств функции путем запуска схемы для нее» — особенно те, где сама проблема исходит из квантовой физики, или имеет математическую структуру, аналогичную квантовой физике.Обычно они обладают тем свойством, что все еще «выясняют неизвестные свойства квантовой схемы путем ее запуска», но схема не обязательно является квантовой версией классической оценки функции, а скорее представляет некоторую математическую структуру или физическую эволюцию. , что хорошо описывается квантовой схемой. Самый очевидный пример — это, конечно, эволюция некой квантовой физической системы! Некоторые из этих проблем — например, приложения квантовой химии — относятся к числу потенциально относящихся к приложениям здравоохранения, которые являются темой статьи BNP.

Квантовый параллелизм: Период последовательности:

Квантовый параллелизм: Период последовательности:

---

Далее: Факторинговые числа: Up: Квантовые вычисления: учебное пособие Предыдущая: Модель квантового компьютера

---

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

Рассмотрим последовательность

где ; мы воспользуемся квантовым параллелизмом, чтобы найти его период. Начнем с набора частиц со спином вниз, которые мы группируем. на два набора (два квантовых регистра или квантовые переменные):

первый набор имеет k бит; следующий, имеющий достаточно для наших нужд. (На самом деле требуются другие регистры, но, применив решение Беннета к управлению пространством они могут быть исключены в нашем обсуждении здесь.) Для каждого бита первого регистра мы выполняем однобитную операция, в результате чего получается суперпозиция всех возможных битовых строк длина к в этом регистре:

Следующим этапом является разбивка вычислений, соответствующих функция на набор однобитовых и двухбитовых унитарных операций. Последовательность операций предназначена для отображения состояния в состояние для любого входа и . Теперь мы видим что количество битов, необходимых для этого второго регистра, должно быть по крайней мере достаточным, чтобы сохранить самый длинный результат для любое из этих вычислений.Однако когда такая последовательность операций применяется к нашей экспоненциально большой суперпозиции вместо одиночный ввод, получаем

Был выполнен экспоненциально большой объем вычислений. по сути бесплатно.

Последний вычислительный шаг, как и первый, снова является чисто квантовым. механический. Рассмотрим дискретное « квантовое » преобразование Фурье на первая регистрация

Легко видеть, что это обратимо с помощью обратного преобразования и действительно, его унитарность легко проверяется.Далее эффективный способ вычисления этого преобразования с помощью одно- и двухбитового ворота были описаны Копперсмитом (рис. 10) [23,24,6].

Рис.10 Схема квантового преобразования Фурье переменной используя быструю Подход с преобразованием Фурье [23,24,6]. Двухбитовый вентиль сам может быть разложен на различные однобитовые и XOR вентили [14].

Когда это квантовое преобразование Фурье применяется к нашей суперпозиции, мы получаем

Вычисление завершено, и мы получаем результат из квантовый компьютер, измерив состояние всех спинов в первом регистр (первые k бит).Действительно, если преобразование Фурье был выполнен, второй регистр может быть даже отброшен [27].

Как будет выглядеть результат? Допустим, период r так . Сумма более даст конструктивный помехи от коэффициентов только тогда, когда кратно обратному периоду [25]. Все другие значения вызовут деструктивную интерференцию в большей степени. или в меньшей степени. Таким образом, распределение вероятностей нахождения Первый регистр с различными значениями схематично показан на рис.11.

Рис.11 График вероятности каждого результата против . Конструктивная интерференция дает узкие пики, кратные обратному периоду последовательности.

Один полный запуск квантового компьютера дает случайный значение под одним из пиков вероятности каждого результат . То есть мы получаем случайное кратное обратному периоду. Чтобы извлечь сам период, нам нужно только повторить это квантовое вычисление. примерно раз, чтобы иметь высокий вероятность того, что хотя бы одно из кратных будет относительно простое с периодом r — однозначно его определяющее [1].Таким образом, этот алгоритм дает только вероятностный результат. К счастью, мы можем сделать эту вероятность сколь угодно высокой.

Вся вышеперечисленная работа может показаться немного противоречивой. Мы ушли к большим трудностям разработать квантовый компьютер, чтобы найти период последовательности. Дело, однако, в том, что последовательность вычисляется параллельно и экспоненциально длинный — даже для небольшого значения, скажем, k = 140 бит в первом регистре, вычисленном квантовым компьютером. и хранит больше результатов, чем частиц во Вселенной.Мы теперь опишите простую структуру, которая существует в математической проблема факторинга, которая позволяет нам применить вышеупомянутый квантовый компьютер алгоритм.

---

Далее: Факторинговые числа: Up: Квантовые вычисления: учебное пособие Предыдущая: Модель квантового компьютера

---

---

Сэмюэл Л. ~ Браунштейн
Ср, 23 августа 11:54:31 IDT 1995

Квантовый параллелизм в квантовой обработке информации

Ааронов Д.(1998). в Ежегодных обзорах вычислительной физики , Vol. VI. Д. Штауфер, изд., World Scientific, Сингапур.

Google Scholar

Араки, Х. и Янасэ, М. М. (1960). Физический анализ 120 , 622.

Google Scholar

d’Espagnat, B. (1971). Концептуальные основы квантовой механики , Benjamin, Reading, MA.

Google Scholar

Ди Винченцо, Д. П. и Шор, П. В. (1996). Письма о физических проверках 77 , 3260.

Google Scholar

Дугич, М. (1996). Physica Scripta 53 , 9.

Google Scholar

Дугич, М. (1997). PhysicaScripta 56 , 560.

Google Scholar

Дугич, М. (2000). Квантовые компьютеры и вычисления 1 , 102.

Google Scholar

Ekert, A. и Macchiavello, C. (1996). Письма о физических проверках 77 , 2585.

Google Scholar

Гровер, Л. К. (1997). Письма о физических проверках 79 , 325.

Google Scholar

Китаев А.Ю., Шень А.Х., Вялый М.Н. (1999). Классические и квантовые вычисления , МЦНМО, Черо, Москва. (на русском).

Google Scholar

Краус К. (1983). Состояния, эффекты и операции , Springer-Verlag, Берлин.

Google Scholar

Ллойд, С.(1989). Физический обзор A 39 , 5378.

Google Scholar

Шор, П. У. (1995). Физический обзор A 52 , 2943.

Google Scholar

Шор П. У. (1997). Журнал SIAM по вычислениям 26 , 1484.

Google Scholar

Стейн, А.М. (1996). Письма о физических проверках 77 , 793.

Google Scholar

Ульман, А. (1976). Rep. Prog. Математика. Физика 9 , 273.

Google Scholar

Виола, Л. и Ллойд, С. (1998). Физический обзор A 58 , 2733.

Google Scholar

фон Нейман, Дж.(1955). Математические основы квантовой механики , Princeton University Press, Princeton.

Google Scholar

Вигнер, Э. П. (1952). Zeitschrift f ü r Physik 133 , 101.