Квантовые вычисления против классических: зачем нам столько цифр. Кратчайшее введение в квантовые вычисления (гостевой пост Романа Душкина) Квантовые расчеты

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

Экспоненциальный рост размерности при попытке расчетов реальных систем или самых простых квантовых систем является непреодолимым препятствием для классических компьютеров. Однако в 1980 году Юрий Манин и Ричард Фейнман (в 1982 году, но более подробно) независимо выдвинули идею использования квантовых систем для вычислений. В отличие от классических современных компьютеров, в квантовых схемах при вычислениях используются кубиты (квантовые биты), которые по своей природе являются квантовыми двухуровневыми системами и обеспечивают возможность прямого использования феномена квантовой суперпозиции. Другими словами это означает, что кубит может одновременно находится в состояниях |0> и |1>, а два связанных между собой кубита - одновременно в состояниях |00>, |10>, |01> и |11>. Именно это свойство квантовых систем должно обеспечить экспоненциальный рост производительности параллельных вычислений, сделав квантовые компьютеры в миллионы раз быстрее самых мощных современных суперкомпьютеров.

В 1994 году Питером Шором предложен квантовый алгоритм разложения чисел на простые множители. Вопрос существования эффективного классического решения данной задачи является крайне важным и до сих пор открыт, при этом квантовый алгоритм Шора обеспечивает экспоненциальное ускорение относительно наилучшего классического аналога. Например, современный суперкомпьютер петафлопсного диапазона (10 15 операций/сек) позволяет разложить число с 500 десятичными знаками за 5 миллиардов лет, квантовый компьютер мегагерцового диапазона (10 6 операций/сек) решил бы ту же задачу за 18 секунд. Важно отметить, что сложность решения данной задачи является основой популярного алгоритма криптографической защиты RSA, который после создания квантового компьютера попросту потеряет актуальность.

В 1996 году Ловом Гровером предложен квантовый алгоритм решения задачи перебора (поиска) с квадратичным ускорением. Несмотря на то, что ускорение алгоритма Гровера заметно ниже алгоритма Шора, важным является его широкий спектр применения, и очевидная невозможность ускорения классического варианта перебора. Сегодня известно более 40 эффективных квантовых алгоритмов, большинство из которых основаны на идеях алгоритмов Шора и Гровера, реализация которых является важным шагом к созданию универсального квантового компьютера.

Реализация квантовых алгоритмов - одна из приоритетных задач НОЦ ФМН. Наши исследования в этой области направлены на разработку многокубитных сверхпроводящих квантовых интегральных схем для создания универсальных квантовых систем обработки информации и квантовых симуляторов. Базовым элементом таких схем являются джозефсоновские туннельные переходы, состоящие из двух сверхпроводников, разделенных тонким барьером - диэлектриком толщиной порядка 1 нм. Сверхпроводящие кубиты на основе джозефсоновских переходов при охлаждении в криостатах растворения практически до температуры абсолютного нуля (~20 мК) проявляют квантово-механические свойства, демонстрируя квантование электрического заряда (зарядовые кубиты), фазы или потока магнитного поля (потоковые кубиты) в зависимости от их конструкции. Для объединения кубитов в схемы используются емкостные или индуктивные соединительные элементы, а также сверхпроводящие копланарные резонаторы, а управление осуществляется микроволновыми импульсами с контролируемыми амплитудой и фазой. Сверхпроводящие схемы особенно привлекательны благодаря тому, что они могут быть изготовлены планарными массовыми технологиями, используемыми в полупроводниковой промышленности. В НОЦ ФМН мы используем оборудование (R&D класса) ведущих мировых производителей, специально спроектированное и созданное для нас с учетом особенностей технологических процессов изготовления сверхпроводящих квантовых интегральных схем.

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

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

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

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

В ФМН разработана алюминиевая технология формирования джозефсоновских переходов Al–AlOx–Al с минимальными размерами в диапазоне 100-500 нм и воспроизводимостью параметров переходов по критическому току не хуже 5%. Продолжающиеся технологические исследования направлены на поиск новых материалов, усовершенствование технологических операций формирования переходов, подходов по интеграции с новыми маршрутными технологическими процессами и повышение воспроизводимости изготовления переходов при увеличении их количества до десятков тысяч штук на кристалле.

Джозефсоновские кубиты (квантовая двухуровневая система или «искусственный атом») характеризуются типичным расщеплением энергии основного возбужденного состояния на уровни и управляются стандартными микроволновыми импульсами (внешняя подстройка расстояния между уровнями и собственных состояний) на частоте расщепления в гигагерцовом диапазоне. Все сверхпроводящие кубиты можно разделить на зарядовые (квантование электрического заряда) и потоковые кубиты (квантование магнитного поля или фазы), а основными критериями качества кубитов с точки зрения квантовых вычислений являются время релаксации (T1), время когерентности (T2, дефазировки) и время на выполнение одной операции. Первый зарядовый кубит был реализован в лаборатории компании NEC (Япония) научной группой под руководством Y. Nakamura и Ю. Пашкина (Nature 398, 786–788, 1999). За прошедшие 15 лет времена когерентности сверхпроводящих кубитов были улучшены ведущими научными группами почти на шесть порядков с наносекуд до сотен микросекунд, обеспечив возможность выполнения сотен двухкубитных операций и реализации алгоритмов коррекции ошибок.

В НОЦ ФМН мы разрабатываем, изготавливаем и тестируем зарядовые и потоковые кубиты различных конструкций (потоковые, флаксониумы, 2D/3D трансмоны, X-моны и т.п.) с алюминиевыми джозефсоновскими переходами, проводим исследования новых материалов и методов создания высококогерентных кубитов, направленные на улучшение основных параметров сверхпроводящих кубитов.

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

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

Научные группы из различных областей физики давно занимаются исследованием возможности когерентного взаимодействия (связи) квантовых двухуровневых систем с квантовыми гармоническими осцилляторами. До 2004 года такого взаимодействия удавалось добиться только в экспериментах атомной физики и квантовой оптики, где одиночный атом когерентно обменивается одиночным фотоном с одномодовым излучением. Эти эксперименты внесли большой вклад в понимание механизмов взаимодействия света с веществом, квантовой физики, физики когерентности и декогерентности, а также подтвердили теоретические основы концепции квантовых вычислений. Однако в 2004 году научной группой под руководством A. Wallraff (Nature 431, 162-167 (2004)) была впервые продемонстрирована возможность когерентной связи твердотельной квантовой схемы с одиночным фотоном микроволнового диапазона. Благодаря этим экспериментам и после решения ряда технологических проблем были разработаны принципы создания управляемых твердотельных двухуровневых квантовых систем, которые составили основу новой парадигмы схем квантовой электродинамики (QED схем) активно исследуемых в последние годы.

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

Основной целью исследований в данном направлении в ФМН является разработка технологии создания, метрологической, методической и алгоритмической базы для реализации алгоритмов Шора и Гровера с использованием многокубитных квантовых схем и демонстрации квантового ускорения по сравнению с классическими суперкомпьютерами. Эта крайне амбициозная научно-техническая задача требует решения колоссального количества теоретико-физических, технологических, схемотехнических, метрологических и алгоритмических проблем, над которыми в данный момент активно работаю ведущие научные группы и ИТ-компании.

Исследования и разработки в области квантовых вычислений проводятся в тесной кооперации с ведущими российскими научными коллективами ИФТТ РАН, МИСИС, МФТИ, НГТУ и РКЦ под управлением известных в мире российских ученых.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

Реферат

Квантовые вычисления

Введение

Глава I. Основные понятия квантовой механики

Глава II. Основные понятия и принципы квантовых вычислений

Глава III. Алгоритм Гровера

Заключение

Список литературы

Введение

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

Тогда вы думаете о квантовом компьютере.

Идея вычислительного устройства, основанного на квантовой механике, впервые рассматривалась еще в ранних 1970-х годах и ранних 1980-х физиками и компьютерными учеными, такими, например, как Чарльз Х. Беннет из IBM Thomas J. Watson Research Center, Пол А. Бениофф из Аргоннской национальной лаборатории в Иллинойсе, Дэвидом Дойчем из Оксфордского университета, и позднее Ричардом П. Фейнманом из из Калифрнийского технологического института (Калтех). Идея возникла тогда, когда ученые заинтересовались фундаментальными ограничениями вычислений. Они поняли, что если технология будет продолжать следовать постепенному уменьшению размеров вычислительных сетей упакованных в кремниевые ЧИПы, то это приведет к тому, что индивидуальные элементы станут не больше чем несколько атомов. Тогда возникла проблема, так как на атомном уровне действуют законы квантовой физики, а не классической. А это подняло вопрос, можно ли сконструировать компьютер, основанный на принципах квантовой физики.

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

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

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

Глава I . Основные понятия квантовой механики

В конце 19 века среди ученых было широко распространено мнение, что физика – наука «практически завершенная» и для полной её «завершенности» осталось совсем немного: объяснить структуру оптических спектров атомов и спектральное распределение теплового излучения . Оптические спектры атома получаются при испускании или поглощении света (электромагнитных волн) свободными или слабо связанными атомами; такими спектрами обладают, в частности, одноатомные газы и пары.

Тепловое излучение – это механизм переноса тепла между пространственно разделёнными частями тела за счет электромагнитного излучения.

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

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

При решении проблемы спектрального состава излучения немецким физиком Максом Планком в 1900 году было высказано предположение о том, что излучение и поглощение света веществом происходит конечными порциями, или квантами. При этом энергия фотона - кванта электромагнитного излучения (в узком смысле - света) определяется выражением

Где - частота излучаемого (или поглощаемого) света, а – универсальная постоянная, называемая теперь постоянной Планка.

Часто используется постоянная Дирака

Тогда энергия кванта выражается как , где

Круговая частота излучения.

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

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

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

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

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

Энергия, переданная в каком-либо месте пространства фотоном, всегда равна . Тем самым где - вероятность нахождения фотона в данной области, а - число фотонов.

В 1921 году опытом Штерна-Герлаха было подтверждено наличие у атомов спина и факт пространственного квантования направления их магнитных моментов (от англ. spin - вращаться, вертеться.). Спин -собственный момент количества движения элементарных частиц, имеющий квантовую природу и не связанный с перемещением частицы как целого. При введении понятия спина предполагалось, что электрон можно рассматривать как «вращающийся волчок», а его спин - как характеристику такого вращения. Спином называют также собственный момент импульса атомного ядра или атома; в этом случае спин определяется как векторная сумма (вычисленная по правилам сложения моментов в квантовой механике) спинов элементарных частиц, образующих систему, и орбитальных моментов этих частиц, обусловленных их движением внутри системы.

Спин измеряется в единицах (приведенных постоянных Планка, или постоянных Дирака) и равен , где J - характерное для каждого сорта частиц целое (в т. ч. нулевое) или полуцелое положительное число - спиновое квантовое число , которое обычно называют просто спином (одно из квантовых чисел). В связи с этим говорят о целом или полуцелом спине частицы. Однако не следует путать понятия спин и спиновое квантовое число. Спиновое квантовое число - это квантовое число, определяющее величину спина квантовой системы (атома, иона, атомного ядра, молекулы), т. е. её собственного (внутреннего) момента импульса. Проекция спина на любое фиксированное направление z в пространстве может принимать значения J , J-1, ..., -J. Т. о., частица со спином J может находиться в 2J + 1 спиновых состояниях (при J = 1 / 2 - в двух состояниях), что эквивалентно наличию у неё дополнительной внутренней степени свободы.

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

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

Система уравнений Максвелла инвариантна относительно преобразования Лоренца. Преобразованиями Лоренца в специальной теории относительности называются преобразования, которым подвергаются пространственно-временные координаты (x,y,z,t) каждого события при переходе от одной инерциальной системы отсчета к другой. По сути, эти преобразования представляют собой преобразования не только в пространстве, как преобразования Галилея, но и во времени.

Глава II . Основные понятия и принципы квантовых вычислений

Хотя компьютеры стали компактными и значительно быстрее, чем раньше, справляются со своей задачей, сама задача остается прежней: манипулировать последовательностью битов и интерпретировать эту последовательность как полезный вычислительный результат. Бит - это фундаментальная единица информации, обычно представляемая как 0 или 1 в вашем цифровом компьютере. Каждый классический бит физически реализуется макроскопической физической системой, такой как намагниченность на жестком диске или заряд конденсатора. Например, текст, составленный из n символов, и сохраненный на жестком диске типичного компьютера, описывается строкой из 8n нулей и единиц. Здесь и лежит фундаментальное отличие между вашим классическим компьютером и квантовым компьютером. В то время как классический компьютер подчиняется хорошо понятным законам классической физики, квантовый компьютер это устройство, которое использует квантово-механические явления (в особенности квантовую интерференцию ), чтобы осуществлять совершенно новый способ обработки информации.

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

Идеи о возможности построения квантового компьютера восходят к работам Р. Фейнмана 1982- 1986 гг. Рассматривая вопрос о вычислении эволюции квантовых систем на цифровом компьютере, Фейнман обнаружил "нерешаемость" этой задачи: оказывается, что ресурсы памяти и быстродействия классических машин недостаточны для решения квантовых задач. Например, система из n квантовых частиц с двумя состояниями (спины 1/2 ) имеет 2 n базисных состояний; для ее описания необходимо задать (и записать в память ЭВМ) 2 n амплитуд этих состояний. Отталкиваясь от этого негативного результата, Фейнман высказал предположение, что, вероятно, "квантовый компьютер" будет обладать свойствами, которые позволят решать на нем квантовые задачи.

"Классические" компьютеры построены на транзисторных схемах, обладающих нелинейными зависимостями между входными и выходными напряжениями. По существу, это бистабильные элементы; например, при низком входном напряжении (логический "0") входное напряжение высокое (логическая "1"), и наоборот. Такой бистабильной транзисторной схеме в квантовом мире можно сопоставить двухуровневую квантовую частицу: состоянию припишем значения логического , состоянию , - значение логической . Переходам в бистабильной транзисторной схеме здесь будут соответствовать переходы с уровня на уровень: . Однако квантовый бистабильный элемент, получивший название кубит, обладает новым, по сравнению с классическим, свойством суперпозиции состояний: он может быть в любом суперпозиционном состоянии , где - комплексные числа, . Состояния квантовой системы из п двухуровневых частиц имеют в общем случае вид суперпозиции 2 n базовых состоянии . В конечном счете квантовый принцип суперпозиции состояний позволяет придать квантовому компьютеру принципиально новые "способности".

Доказано, что квантовая ЭВМ может быть построена всего из двух элементов (вентилей): однокубитового элемента и двухкубитового элемента контролируемое НЕ (CNOT). Матрица 2x2 элемента имеет вид:

(1)

Вентиль описывает поворот вектора состояния кубита от оси z к полярной оси, заданной углами . Если - иррациональные числа, то многократным применением вектору состояния можно придать любую наперед заданную ориентацию. Именно в этом заключается "универсальность" однокубитового вентиля в форме (1). В частном случае получаем однокубитовый логический элемент НЕ (NOT): НЕ=, НЕ=. При физической реализации элемента НЕ необходимо воздействовать на квантовую частицу (кубит) импульсом извне, переводящим кубит из одного состояния в другое. Вентиль контролируемое НЕ исполняют, воздействуя на два взаимодействующих между собой кубита: при этом посредством взаимодействия один кубит контролирует эволюцию другого. Переходы под влиянием внешних импульсов хорошо известны в импульсной магниторезонансной спектроскопии. Вентиль НЕ соответствует перевороту спина под действием импульса (вращение намагниченности вокруг оси на угол ). Вентиль CNOT выполняется на двух спинах 1/2 с гамильтонианом (спин контролирует ). CNOT выполняется в три шага: импульс + свободная прецессия в течение времени - импульс . Если (контролирующий кубит в состоянии ), то при указанных воздействиях контролируемый кубит совершает переходы (или ). Если же (контролирующий кубит в состоянии ), то результат эволюции контролируемого кубита будет другим: (). Таким образом, спин , эволюционирует по-разному при : здесь в - состояние контролирующего кубита.

При рассмотрении вопроса о реализации квантового компьютера на тех или иных квантовых системах в первую очередь исследуют реализуемость и свойства элементарных вентилей НЕ и контролируемое НЕ.

Для дальнейшего полезно также ввести однокубитовое преобразование Адамара:

В технике магнитного резонанса эти вентили осуществляются импульсами :

Схема квантового компьютера представлена на рисунке. До начала работы компьютера все кубиты (квантовые частицы) должны быть приведены в состояние , т.е. в основное состояние. Это условие само по себе не тривиально.

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

В результате система перешла в состояние суперпозиции из 2 п базисных состояний с амплитудой 2 - n /2 . Каждое базисное состояние представляет собой двоичное число от до . Горизонтальные линии на рисунке обозначают оси времени.

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

Количество сомножителей в этом разложении определяет длительность (и сложность) вычислений . Все в (3) выполняются с применением операций NOT, CNOT, Н (или их разновидностей).

Замечательно, что линейный унитарный оператор действует одновременно на все члены суперпозиции

Результаты вычисления записываются в запасном регистре, который перед применением находился в состоянии . За один прогон вычислительного процесса мы получаем значения искомой функции f при всех значениях аргумента х = 0,..., 2 п - 1 . Этот феномен получил название квантового параллелизма.

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

(5)

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

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

Исследуются различные пути физической реализации квантовых компьютеров. Модельные эксперименты по квантовому компьютингу выполнены на импульсном ядерном магнитно-резонансном спектрометре. В этих моделях работало два или три спина (кубита), например два спина ядер 13 С и один спин протона в молекуле трихлорэтилена

Однако в этих опытах квантовый компьютер был "ансамблевым": выходные сигналы компьютера сложены большим числом молекул в жидком растворе (~ 10 20).

К настоящему времени высказаны предложения о реализации квантовых компьютеров на ионах и молекулах в ловушках в вакууме, на ядерных спинах в жидкостях (см. выше), на ядерных спинах атомов 31 Р в кристаллическом кремнии, на спинах электронов в квантовых точках, созданных в двумерном электронном газе в гетероструктурах GaAs, на переходах Джозеф-сона. Как видим, в принципе, квантовый компьютер можно построить на атомных частицах в вакууме, жидкости, кристаллах. При этом в каждом случае предстоит преодолеть те или иные препятствия, однако среди них можно выделить несколько общих, обусловленных принципами действия кубитов в квантовом компьютере. Поставим задачу создать полномасштабный квантовый компьютер, содержащий, скажем, 10 3 кубитов (хотя и при п = 100 квантовый компьютер может стать полезным инструментом).

1. Нужно найти способы "инициализации" кубитов компьютера в состояние . Для спиновых систем в кристаллах очевидно применение сверхнизких температур и сверхсильных магнитных полей. Применение поляризации спинов накачкой может оказаться полезным при одновременном применении охлаждения и больших магнитных полей.

Для ионов в вакуумных ловушках сверхнизкое охлаждение ионов (атомов) достигается лазерными методами. Очевидна также необходимость холодного и сверхвысокого вакуума.

2. Необходимо иметь технологию избирательного воздействия импульсами на любой выбранный кубит. В области радиочастот и спинового резонанса это означает, что каждый спин должен обладать своей резонансной частотой (в терминах спектроскопического разрешения). Различия резонансных частот для спинов в молекулах обусловлены химическими сдвигами для спинов одного изотопа и одного элемента; необходимые различия частот имеются для спинов ядер различных элементов. Однако здравый смысл подсказывает, что эти дарованные природой различия резонансных частот вряд ли достаточны, чтобы работать с 10 3 спинов.

Более перспективными представляются подходы, когда можно управлять извне резонансной частотой каждого кубита. В предложении о кремниевом квантовом компьютере кубитом служит ядерный спин примесного атома 31 Р. Частота резонанса определяется константой А сверхтонкого взаимодействия ядерного и электронного спинов атома 31 Р. Электрическое поле на наноэлектроде, находящемся над атомом 31 Р, поляризует атом и изменяет константу А (соответственно резонансную частоту ядерного спина). Таким образом, наличие электрода встраивает кубит в электронную схему и настраивает его резонансную частоту.

3. Для выполнения операции CNOT (контролируемое НЕ) необходимо взаимодействие между кубитами и вида . Такое взаимодействие возникает между спинами ядер в молекуле, если ядра и разделены одной химической связью. В принципе, необходимо иметь возможность выполнять операцию для любых пар кубитов . Иметь физическое взаимодействие кубитов одного масштаба величины и по принципу "все со всеми" в природной среде вряд ли возможно. Очевидна потребность в способе настройки среды между кубитами извне путем введения электродов с управляемым потенциалом. Таким путем можно создать, например, перекрытие волновых функций электронов в соседних квантовых точках и возникновение взаимодействия вида между спинами электронов [. Перекрытие волновых функций электронов соседних атомов 31 Р обусловливает возникновение взаимодействия вида между ядерными спинами.

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

4. В ходе выполнения унитарного преобразования, соответствующего избранному алгоритму, кубиты компьютера подвергаются воздействию со стороны среды; в результате амплитуды и фазы вектора состояния кубита испытывают случайные изменения - декогеренизацию . По существу, декогеренизация - это релаксация тех степеней свободы частицы, которые используются в кубите. Время декогеренизации равно времени релаксации. В ядерном магнитном резонансе в жидкостях времена и релаксации составляют 1-10 с. Для ионов в ловушках с оптическими переходами между уровнями Е 0 и Е 1 временем декогеренизации выступают время спонтанного излучения и время столкновений с остаточными атомами. Очевидно, что декогеренизация - это серьезное препятствие квантовому вычислению: начатый вычислительный процесс приобретает черты случайности по истечении времени декогеренизации. Однако можно достичь устойчивого квантового вычислительного процесса в течение сколь угодно долгого времени т > та, если систематически использовать методы квантового кодирования и коррекции ошибок (фазовых и амплитудных). Доказано, что при относительно невысоких требованиях к безошибочному выполнению элементарных операций типа NОТ и СNОТ (вероятность ошибки не более 10 -5) методы квантовой коррекции ошибок (QEC) обеспечивают устойчивую работу квантового компьютера.

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

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

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

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

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

В обычном компьютере информация кодируется последовательностью битов, и эти биты последовательно обрабатываются булевскими логическими элементами, чтобы получить нужный результат. Аналогично квантовый компьютер обрабатывает кубиты, выполняя последовательность операций квантовыми логическими элементами, каждый из которых представляет собой унитарное преобразование, действующее на единичный кубит или пару кубитов. Последовательно выполняя эти преобразования, квантовый компьютер может выполнить сложное унитарное преобразование над всем набором кубитов приготовленных в некотором начальном состоянии. После этого можно произвести измерение над кубитами, которое и даст конечный результат вычислений. Это сходство вычислений между квантовым и классическим компьютером позволяет считать, что, по крайней мере, в теории, классический компьютер может в точности воспроизводить работу квантового компьютера. Другими словами, классический компьютер может делать все то же самое, что и квантовый компьютер. Тогда зачем вся эта возня с квантовым компьютером? Дело в том, что, хотя теоретически классический компьютер может симулировать квантовый компьютер, это очень неэффективно, настолько неэффективно, что практически классический компьютер не в состоянии решать многие задачи, которые по плечу квантовому компьютеру. Симуляция квантового компьютера на классическом компьютере вычислительно сложная проблема, потому что корреляции между квантовыми битами качественно отличается от корреляций между классическими битами, как было впервые показано Джоном Беллом. Для примера можно взять систему только из нескольких сотен кубитов. Она существует в пространстве Гильберта размерностью ~10 90 , что потребует, при моделировании классическим компьютером, использования экспоненциально больших матриц (чтобы выполнить расчеты для каждого отдельного состояния, которое также описывается матрицей). Это означает, что классическому компьютеру понадобится экпоненциально больше времени по сравнению даже с примитивным квантовым компьютером.

Ричард Фейнман был среди первых, кто осознал потенциал, заложенный в явлении квантовой суперпозиции для решения таких задач гораздо быстрее. Например, система из 500 кубитов, которую практически невозможно промеделировать классически, представляет собой квантовую суперпозицию из 2 500 состояний. Каждое значение такой суперпозиции классически эквивалентно списку из 500 единиц и нулей. Любая квантовая операция над такой системой, например, настроенный определенным образом импульс радиоволн, который может выполнить операцию управляемое НЕ над, скажем, 100-м и 101-м кубитом, будет одновременно воздействовать на 2 500 состояний. Таким образом, за один тик компьютерных часов квантовая операция вычисляет не одно машинное состояние, как обычные компьютеры, а 2 500 состояний сразу! Однако, в конце концов, над системой кубитов производится измерение, и система коллапсирует в единственное квантовое состояние, соответствующее единственному решению задачи, единственному набору из 500 единиц и нулей, как это диктуется измерительной аксиомой квантовой механики. Это поистине волнующий результат, поскольку это решение, найденное колективным процессом квантовых параллельных вычислений, берущим свои истоки в суперпозиции, эквивалентно выполнению той же самой операции на классическом суперкомпьютере с ~10 150 отдельных процессоров (что, конечно, невозможно)!! Первые исследователи в этой области были, конечно, вдохновлены такими гигантскими возможностями, и поэтому вскоре началась настоящая охота за подходящими задачами для такой вычислительной мощи. Питер Шор, исследователь и компьютерный ученый из компании AT&T"s Bell Laboratories в Нью Джерси, предложил такую задачу, которую можно было бы решить именно на квантовом компьютере и при помощи квантового алгоритма. Алгоритм Шора использует мощь квантовой суперпозиции, чтобы раскладывать большие числа (порядка ~10 200 двоичных разрядов и больше) на множители за несколько секунд. Эта задча имеет важное практическое применение для шифрования, где общепринятый (и лучший) алгоритм шифрования, известный как RSA, основан как раз на сложности разложения больших составных чисел на простые множители. Компьютер, который с легкостью решает такую задачу, конечно, представляет большой интерес для множества правительственных организаций, использующих RSA, который до сих пор считался "невзламываемым", и для любого кто заинтересован в безопсаности своих данных.

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

Глава III . Алгоритм Гровера

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

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

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

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

т. е. бит в состоянии 0 превращается в суперпозицию двух состояний: (1/, 1/). Аналогично, бит в состоянии 1 трансформируется в (1/, -1/,), т. е. величина амплитуды для каждого состояния равна 1/, но фаза в состоянии 1 перевернута. Фаза не имеет аналога в классических вероятностных алгоритмах. Она возникает в квантовой механике, где амплитуда вероятности комплексна. В системе, в которой состояние описывается п битами (т. е. имеется N = 2 п возможных состояний), мы можем осуществить преобразование М на каждом бите независимо, последовательно изменяя состояние системы. В случае, когда начальная конфигурация представляла собой конфигурацию с п битами в первом состоянии, полученная конфигурация будет иметь равные амплитуды для каждого из состояний. Это и есть способ создания суперпозиции с той же самой амплитудой для всех состояний.

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

где j = и - произвольные действительные числа. Заметим, что в отличие от преобразования Адамара и других матриц преобразования состояний, вероятность каждого состояния остается той же, т. к. квадрат абсолютной величины амплитуды в каждом состоянии остается прежним.

Рассмотрим задачу в абстрактной форме.

Пусть система имеет N = 2 п состояний, которые обозначаются как ,..., . Эти 2 п состояния представляются как n-битные строки. Пусть существует единственное состояние, скажем , которое довлетворяет условию C() = 1, тогда как для всех других состояний S, С( ,) = 0 (предполагается, что для любого состояния S условие оценивается за единицу времени). Задача состоит в распознании состояния ,

Перейдем собственно к алгоритму

Шаги (1) и (2) являются последовательностью элементарных унитарных операций описаных ранее. Шаг (3) есть завершающее измерение, осуществляемое внешней системой.

(1) Приводим систему в состояние суперпозиции:

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

(2) Повторим следующую унитарную операцию О( ) раз:

a . Пусть система будет в каком-нибудь состоянии S:

В случае С( S ) = 1, повернуть фазу на радиан;

В случае С(S) = 0, оставить систему неизмененной.

b . Применить преобразование диффузии D которое определяется матрицей D следующим образом:, если ;" и . D может быть реализована как последовательное выполнение унитарных преобразований: , где W – матрица преобразований Адамара, R – матрица фазового поворота.

(3) Произвести измерение полученного состоянии. Это состояние будет состоянием С( )„ (т. е. искомым состоянием, удовлетворяющим условию (C() = 1) с вероятностью, по крайней мере, не меньшей, чем 0.5. Заметим, что шаг (2а) - это фазовое вращение. В его реализацию должна быть включена процедура распознания состояния и последующего определения осуществлять или нет поворот фазы. Она должна проводиться таким образом, чтобы не оставлять следа на состоянии системы, так, чтобы была уверенность, что пути, приводящие к тому же самому конечному состоянию, неразличимы и могут интерферировать. Заметим, что эта процедура не включает классического измерения.

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

Заключение

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

Список литературы

1. Квантовые вычисления: за и против. Под ред. В.А. Садовничего. – Ижевск: Издательский дом «Удмуртский университет», 1999. – 212 с.

2. Белонучкин В.E., Заикин Д.А., Ципенюк Ю.М., Основы физики. Курс общей физики: Учебн. В 2 т. Т. 2. Квантовая и статистическая физика. – М.: ФИЗМАТЛИТ, 2001. – 504 с.

3. Валиев К.А. «Квантовые компьютеры: можно ли их сделать «большими»?», Успехи физических наук, т. 169, № 6, 1999г.

4. Валиев К.А. «Квантовая информатика: компьютеры, связь и криптография», ВЕСТНИК РОССИЙСКОЙ АКАДЕМИИ НАУК, том 70, № 8, с. 688-695, 2000г.

5. Маслов. Д. «Квантовые вычисления и коммуникация: реальность и перспективы», Компьютерра, №46 , 2004г.

6. Халфин Л.А. «Квантовый эффект Зенона», Успехи физических наук, т. 160, № 10, 1990г.

7. Холево А. «Квантовая информатика: прошлое, настоящее, будущее»,

В МИРЕ НАУКИ, №7, 2008г.

8. Centre for Quantum Technologies, National University of Singapore www.quantumlah.org

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

Под квантовой запутанностью, которую называют также «квантовой суперпозицией» , обычно понимается следующее: "Вообразите атом, который мог бы подвергнуться радиоактивному распаду в определенный промежуток времени. Или не мог бы. Мы можем ожидать, что у этого атома есть только два возможных состояния: «распад» и «не распад», /…/ но в квантовой механике у атома может быть некое объединенное состояние - «распада - не распада», то есть ни то, ни другое, а как бы между. Вот это состояние и называется «суперпозицией» .

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

Теория

Кубиты

Идея квантовых вычислений, впервые высказанная Ю. И. Маниным и Р. Фейнманом состоит в том, что квантовая система из L двухуровневых квантовых элементов (кубитов) имеет 2 L линейно независимых состояний, а значит, вследствие принципа квантовой суперпозиции, 2 L -мерное гильбертово пространство состояний. Операция в квантовых вычислениях соответствует повороту в этом пространстве. Таким образом, квантовое вычислительное устройство размером L кубит может выполнять параллельно 2 L операций.

Предположим, что имеется один кубит. В таком случае после измерения, в так называемой классической форме, результат будет 0 или 1. В действительности кубит - квантовый объект и поэтому, вследствие принципа неопределённости, может быть и 0, и 1 с определенной вероятностью. Если кубит равен 0 (или 1) со стопроцентной вероятностью, его состояние обозначается с помощью символа |0> (или |1>) - в обозначениях Дирака . |0> и |1> - это базовые состояния. В общем случае квантовое состояние кубита находится между базовыми и записывается, в виде , где |a |² и |b |² - вероятности измерить 0 или 1 соответственно; ; |a |² + |b |² = 1. Более того, сразу после измерения кубит переходит в базовое квантовое состояние, аналогичное классическому результату.

Имеется кубит в квантовом состоянии В этом случае, вероятность получить при измерении В данном случае, при измерении мы получили 0 с 64 % вероятностью. Тогда кубит перескакивает в новое квантовое состояние 1*|0>+0*|1>=|0>, то есть, при следующем измерении этого кубита мы получим 0 со стопроцентной вероятностью. Это обусловлено тем, что дираковский вектор состояния не зависит от времени, то есть раскладывается в сумму векторов базисных состояний с независящими от времени коэффициентами.

Приведем для объяснения два примера из квантовой механики: 1) фотон находится в состоянии суперпозиции двух поляризаций; измерение раз и навсегда коллапсирует состояние фотона в таковое с определенной поляризацией; 2) радиоактивный атом имеет определенный период полураспада; измерение может выявить то, что он еще не распался, но это не значит, что он никогда не распадется.

Перейдем к системе из двух кубитов. Измерение каждого из них может дать 0 или 1. Поэтому у системы 4 классических состояния: 00, 01, 10 и 11. Аналогичные им базовые квантовые состояния: |00>, |01>, |10> и |11>. И наконец, общее квантовое состояние системы имеет вид . Теперь |a |² - вероятность измерить 00 и т. д. Отметим, что |a |²+|b |²+|c |²+|d |²=1 как полная вероятность.

В общем случае, системы из L кубитов у неё 2 L классических состояний (00000…(L-нулей), …00001(L-цифр), … , 11111…(L-единиц)), каждое из которых может быть измерено с вероятностями 0-100 %.

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

Вычисление

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

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

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

Чем же квантовый компьютер лучше классического? Большая часть современных ЭВМ работают по такой же схеме: n бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае система из n кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2 n базовых состояний одновременно. Теоретически новая схема может работать намного (в экспоненциальное число раз) быстрее классической. Практически (квантовый) алгоритм Гровера поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов. Пока в природе их не существует.

Алгоритмы

Было показано, что не для всякого алгоритма возможно «квантовое ускорение».

Квантовая телепортация

Алгоритм телепортации реализует точный перенос состояния одного кубита (или системы) на другой. В простейшей схеме используются 4 кубита: источник, приёмник и два вспомогательных. Отметим, что в результате работы алгоритма первоначальное состояние источника разрушится - это пример действия общего принципа невозможности клонирования - невозможно создать точную копию квантового состояния, не разрушив оригинал. На самом деле, довольно легко создать одинаковые состояния на кубитах. К примеру, измерив 3 кубита, мы переведем каждый из них в базовые состояния (0 или 1) и хотя бы на двух из них они совпадут. Не получится скопировать произвольное состояние, и телепортация - замена этой операции.

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

Применение квантовых компьютеров

Специфика применения

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

Основные проблемы, связанные с созданием и применением квантовых компьютеров:

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

Приложения к криптографии

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

Реализации

Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 кубит (устройство получило название Orion). Однако информация об этом устройстве не отвечала строгим требованиям точного научного сообщения; новость не получила научного признания. Более того, дальнейшие планы компании (создать уже в ближайшем будущем 1024-кубитный компьютер) вызвали скепсис у членов экспертного сообщества .

В ноябре 2007 года та же компания D-Wave продемонстрировала работу образца 28-кубитного компьютера онлайн на конференции, посвященной суперкомпьютерам . Данная демонстрация также вызвала определенного рода скепсис.

В декабре 2008 года компания организовала проект Распределенных вычислений AQUA@home(A diabatic QU antum A lgorithms) , в котором тестируются алгоритмы, оптимизирующие вычисления на адиабатических сверхпроводящих квантовых компьютерах D-Wave.

См. также

Примечания

Литература

• Kilin S.Ya. Quanta and information / Progress in optics. - 2001. - Vol. 42. - P. 1-90.
• Килин С. Я. Квантовая информация / Успехи Физических Наук. - 1999. - Т. 169. - C. 507-527.
• Квантовые вычисления за и против. Под ред. Садовничего В. А.
• Квантовый компьютер и квантовые вычисления. Под ред. Садовничего В. А.
• Валиев К. А., Кокин А. А. Квантовые компьютеры: надежды и реальность. Москва, Ижевск: Регулярная и хаотическая динамика, 2004. 320 с. ISBN 5-93972-024-2

Ссылки

• Квантовый компьютер и его полупроводниковая элементарная база
• Китаев,А., Шень, А., Вялый, М. Классические и квантовые вычисления
• QWiki (англ.) и Quantiki (англ.) - Wiki-ресурсы по квантовой информатике
• Язык программирования QCL для квантовых компьютеров (англ.)
• Курс «Современные задачи теоретической информатики » (лекции по квантовым вычислениям: введение, суперплотное кодирование, квантовая телепортация, алгоритмы Саймона и Шора)
• InFuture.ru: Будущее квантовых компьютеров - в троичных вычислениях
• Валиев К. А. «Квантовые компьютеры и квантовые вычисления» УФН 175 3 (2005)

Wikimedia Foundation . 2010 .

• Квантоворазмерный эффект
• Квантовые размерные эффекты

Смотреть что такое "Квантовые вычисления" в других словарях:

Квантовые компьютеры - 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер гипотетическое вычислительное устройство, которое путем выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как… … Википедия

ТОПОЛОГИЧЕСКИЕ КВАНТОВЫЕ ТЕОРИИ ПОЛЯ - квантовомеханич. или квантовополевые теории, все корреляционные функции в к рых не зависят от выбора координат и метрики как в пространстве времени, так и в др. пространствах, участвующих в определении теории. Это позволяет использовать… … Физическая энциклопедия

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

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

У человека любознательного такие заявления вызывают вопросы. Что такое квантовые вычисления (рисунок 1)? Это реально? Если да, то как это работает? И как это связано с криптографией? Затем появляются более личные вопросы. Могут ли квантовые вычисления изменить мои методы проектирования? Должен ли я изучить этот материал?

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

Рисунок 1 – Визуализация квантовых вычислительных элементов

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

Второй жанр совершенно другой, но столь же «полезный», написанный экспертами, для того, чтобы произвести впечатление на других экспертов. Эта жанр характеризуется употреблением таких терминов как машина Тьюринга, имя Ричарда Фейнмана, Гильбертово пространство и преобразование Адамара, все вышеупомянутое и еще примерно 75 слов, за которыми следует путаница уравнений с незнакомой и необъяснимой терминологией. Конечно же, вы все хорошо помните, что означает |0>!

Три параллельные вселенные

Одной из причин, почему эта тема настолько сложна, является то, что квантовые вычисления охватывают три дисциплины с очень разной терминологией и интересами. Все началось с физиков-теоретиков. Еще в 1980 году физик Пол Бениофф (Paul Benioff ) из Национальной Аргоннской лаборатории описал, как некоторые квантовомеханические эффекты могут быть использованы для реализации машины Тьюринга. Два года спустя известный физик Ричард Фейнман также поднял вопрос о компьютере с использованием квантового поведения.

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

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

Некоторые пояснения

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

Вместо этого, квантовые компьютеры – это машины, основанные на уникальном поведении, описываемом квантовой механикой, и совершенно отличающимся от поведения классических систем. Одно из таких отличий – способность частицы или группы частиц в некотором отношении находиться только в двух дискретных квантовых базовых состояниях – назовем их 0 и 1. Мы обойдемся здесь без забавных скобок (обозначений принятых в квантовой теории – добавлено переводчиком) Примерами такого рода могут быть спин электрона, поляризация фотона или заряд квантовой точки.

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

Рисунок 2 – Сфера Блоха – один из способов визуализации квантовой суперпозиции в кубите

Это (свойство суперпозиции – добавлено переводчиком) важно, потому что позволяет кубиту быть в обоих состояниях 0 и 1 одновременно. Следовательно, регистр, состоящий из n кубит, может одновременно «содержать» все возможные двоичные числа n бит длиной. Это позволяет квантовому компьютеру выполнять одну операцию не только с одним n-разрядным целым числом, но и со всеми возможными n-разрядными целыми числами сразу – очень существенный параллелизм по мере увеличения n.

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

Компьютер на бумаге

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

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

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

Компьютерные специалисты выяснили, что для эмуляции машины Тьюринга достаточно очень небольшого набора квантовых вентилей – всего лишь набор одновходовых квантовых вентилей и один двухвходовой квантовый вентиль. Наиболее часто используемым примером двухвходового квантового вентиля является «контролируемое НЕ» (Сontrolled NOT – CNOT). Эта обратимая функция либо переворачивает векторное состояние кубита, либо оставляет его неизменным, в зависимости от состояния второго кубита. Это скорее похоже на квантовую аналогию с «исключающим ИЛИ».

Возможные преимущества

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

Приведем пример. В 1994 году математик Питер Шор, в Bell Labs, разработал алгоритм факторизации (разложения на простые сомножители – добавлено переводчиком) очень больших чисел с использованием квантовых подпрограмм. Такая факторизация является жизненно важной проблемой в прикладной математике, потому что не существует аналитического решения: единственный способ – метод проб и ошибок, и вы можете всего лишь сделать алгоритм быстрее, выбрав более искусным образом соответствующие пробные числа. Соответственно, когда вы делаете входное число очень большим, количество проб и ошибок становится огромным. Не случайно это является основой алгоритмов криптографии, подобных RSA. RSA и шифры на основе эллиптических кривых трудно взломать, особенно потому, что так трудно факторизовать огромные числа.

Алгоритм Шора объединил некоторые традиционные вычисления с двумя квантовыми функциями, которые непосредственно ускоряют алгоритм в части метода проб и ошибок, по сути, перебирая все возможные числа в одно и то же время, демонстрация работы алгоритма приведена на рисунке 3. Одна из этих квантовых функций выполняет модульное возведение в степень, а другая осуществляет квантовую версию быстрого преобразования Фурье (БПФ). По причинам, которые мог бы полюбить только математик, если бы мы ввели набор из n кубитов, подготовленных так, что вместе они представляют все возможные двоичные числа до длины n, то в квантовых вентилях различные состояния в суперпозиции взаимно компенсируют друг друга – подобно интерференции двух когерентных световых лучей – и мы остаемся с определенной структурой состояний в выходном регистре.

Рисунок 3 – Алгоритм Шора зависит от квантовых подпрограмм для модульного возведения в степень и операций БПФ. (рисунок предоставлен Tyson Williams)

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

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

Алгоритм Шора являет собой яркий образец квантовых вычислений, потому что он одновременно не похож на обычные вычисления и потенциально чрезвычайно важен. Но он не одинок. Национальный институт стандартов и технологий США (NIST) поддерживает большую библиотеку алгоритмов квантовых вычислений в своем Зоопарке Квантовых Алгоритмов, по адресу math.nist.gov/quantum/zoo/ .

Являются ли эти алгоритмы просто математическими упражнениями? Пока еще слишком рано это утверждать. Но на практике исследователи действительно создали лабораторные квантовые калькуляторы с несколькими рабочими кубитами. Эти машины успешно разложили на простые множители число 15 (впервые это было сделано в IBM в 2001 году), вполне ожидаемо получив в результате 3 и 5, а текущий мировой рекорд составляет число 21 (сделано объединенной командой из нескольких институтов в 2012 году). Так что для небольших чисел идея работает. Пригодность такого подхода для больших чисел можно будет проверить только в будущем на машинах с большим количеством кубитов. И это переносит вопрос в практическую плоскость.

Путь к реализации

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

К сожалению, проблемы связаны не столько с новизной проблем, сколько с законами квантовой механики и классической физики. Возможно, самая главная и наименее знакомая из них, называется декогеренцией. Роль кубит состоит в том, чтобы удерживать физический объект – например, ион, пакет фотонов или электрон — на месте, чтобы мы могли воздействовать на него и в конечном итоге измерять квантованную величину, такую как заряд или спин. Чтобы эта величина вела себя квантовым, а не классическим образом, мы должны иметь возможность ограничить ее состояние суперпозицией двух чистых базовых состояний, которые мы называли 0 и 1.

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

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

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

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

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

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

Сомнения

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

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

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

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

Стоит ли оно того? Вот один факт. Шор подсчитал, что скромный гибридный, то есть квантовый плюс обычный, компьютер может взломать мощный алгоритм шифрования RSA быстрее, чем обычный компьютер может его зашифровать. Были получены аналогичные результаты для таких задач, как сортировка и распутывание других аналогичных сложных математических задач. Итак, в этой области присутствует достаточно перспектив, чтобы исследователи не теряли энтузиазм. Но было бы неплохо увидеть все это еще при жизни.

Хотя компьютеры стали компактными и значительно быстрее, чем раньше, справляются со своей задачей, сама задача остается прежней: манипулировать последовательностью битов и интерпретировать эту последовательность как полезный вычислительный результат. Бит - это фундаментальная единица информации, обычно представляемая как 0 или 1 в вашем цифровом компьютере. Каждый классический бит физически реализуется макроскопической физической системой, такой как намагниченность на жестком диске или заряд конденсатора. Например, текст, составленный из n символов, и сохраненный на жестком диске типичного компьютера, описывается строкой из 8n нулей и единиц. Здесь и лежит фундаментальное отличие между вашим классическим компьютером и квантовым компьютером. В то время как классический компьютер подчиняется хорошо понятным законам классической физики, квантовый компьютер это устройство, которое использует квантово-механические явления (в особенности квантовую интерференцию ), чтобы осуществлять совершенно новый способ обработки информации. Квантовые вычисления: за и против. Под ред. В.А. Садовничего. - Ижевск: Издательский дом «Удмуртский университет», 1999. - 212 с.

В квантовом компьютере фундаментальная единица информации (называемая квантовый бит или кубит ), не двоична, а скорее четверична по своей природе. Это свойство кубита проистекает как прямое следствие его подчиненности законам квантовой механики, которые радикально отличаются от законов классической физики. Кубит может существовать не только в состоянии, соответствующем логическим 0 или 1, как классический бит, но также в состояниях, соответствующих смесли или суперпозиции этих классических состояний. Другими словами, кубит может существовать как ноль, как единица, и как одновременно 0 и 1. При этом можно указать некоторый численный коэффициент, представляющий вероятность оказаться в каждом состоянии. . Белонучкин В.E., Заикин Д.А., Ципенюк Ю.М., Основы физики.

Идеи о возможности построения квантового компьютера восходят к работам Р. Фейнмана 1982- 1986 гг. Рассматривая вопрос о вычислении эволюции квантовых систем на цифровом компьютере, Фейнман обнаружил "нерешаемость" этой задачи: оказывается, что ресурсы памяти и быстродействия классических машин недостаточны для решения квантовых задач. Например, система из n квантовых частиц с двумя состояниями (спины 1/2 ) имеет 2 n базисных состояний; для ее описания необходимо задать (и записать в память ЭВМ) 2 n амплитуд этих состояний. Отталкиваясь от этого негативного результата, Фейнман высказал предположение, что, вероятно, "квантовый компьютер" будет обладать свойствами, которые позволят решать на нем квантовые задачи. Валиев К.А. «Квантовые компьютеры: можно ли их сделать «большими»?», Успехи физических наук, т. 169, № 6, 1999г.

"Классические" компьютеры построены на транзисторных схемах, обладающих нелинейными зависимостями между входными и выходными напряжениями. По существу, это бистабильные элементы; например, при низком входном напряжении (логический "0") входное напряжение высокое (логическая "1"), и наоборот. Такой бистабильной транзисторной схеме в квантовом мире можно сопоставить двухуровневую квантовую частицу: состоянию припишем значения логического, состоянию, - значение логической. Переходам в бистабильной транзисторной схеме здесь будут соответствовать переходы с уровня на уровень: . Однако квантовый бистабильный элемент, получивший название кубит, обладает новым, по сравнению с классическим, свойством суперпозиции состояний: он может быть в любом суперпозиционном состоянии, где -- комплексные числа, . Состояния квантовой системы из п двухуровневых частиц имеют в общем случае вид суперпозиции 2 n базовых состоянии. В конечном счете квантовый принцип суперпозиции состояний позволяет придать квантовому компьютеру принципиально новые "способности".

Доказано, что квантовая ЭВМ может быть построена всего из двух элементов (вентилей): однокубитового элемента и двухкубитового элемента контролируемое НЕ (CNOT). Матрица 2x2 элемента имеет вид:

Вентиль описывает поворот вектора состояния кубита от оси z к полярной оси, заданной углами . Если -- иррациональные числа, то многократным применением вектору состояния можно придать любую наперед заданную ориентацию. Именно в этом заключается "универсальность" однокубитового вентиля в форме (1). В частном случае получаем однокубитовый логический элемент НЕ (NOT): НЕ=, НЕ=. При физической реализации элемента НЕ необходимо воздействовать на квантовую частицу (кубит) импульсом извне, переводящим кубит из одного состояния в другое. Вентиль контролируемое НЕ исполняют, воздействуя на два взаимодействующих между собой кубита: при этом посредством взаимодействия один кубит контролирует эволюцию другого. Переходы под влиянием внешних импульсов хорошо известны в импульсной магниторезонансной спектроскопии. Вентиль НЕ соответствует перевороту спина под действием импульса (вращение намагниченности вокруг оси на угол). Вентиль CNOT выполняется на двух спинах 1/2 с гамильтонианом (спин контролирует). CNOT выполняется в три шага: импульс + свободная прецессия в течение времени - импульс. Если (контролирующий кубит в состоянии), то при указанных воздействиях контролируемый кубит совершает переходы (или). Если же (контролирующий кубит в состоянии), то результат эволюции контролируемого кубита будет другим: (). Таким образом, спин, эволюционирует по-разному при: здесь в - состояние контролирующего кубита. Валиев К.А. «Квантовая информатика: компьютеры, связь и криптография», ВЕСТНИК РОССИЙСКОЙ АКАДЕМИИ НАУК, том 70, № 8, с. 688-695, 2000г.

При рассмотрении вопроса о реализации квантового компьютера на тех или иных квантовых системах в первую очередь исследуют реализуемость и свойства элементарных вентилей НЕ и контролируемое НЕ.

Для дальнейшего полезно также ввести однокубитовое преобразование Адамара:

В технике магнитного резонанса эти вентили осуществляются импульсами:

Схема квантового компьютера представлена на рисунке. До начала работы компьютера все кубиты (квантовые частицы) должны быть приведены в состояние, т.е. в основное состояние. Это условие само по себе не тривиально.

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

В результате система перешла в состояние суперпозиции из 2 п базисных состояний с амплитудой 2 -n/2 . Каждое базисное состояние представляет собой двоичное число от до. Горизонтальные линии на рисунке обозначают оси времени.

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

Количество сомножителей в этом разложении определяет длительность (и сложность) вычислений. Все в (3) выполняются с применением операций NOT, CNOT, Н (или их разновидностей).

Замечательно, что линейный унитарный оператор действует одновременно на все члены суперпозиции

Результаты вычисления записываются в запасном регистре, который перед применением находился в состоянии. За один прогон вычислительного процесса мы получаем значения искомой функции f при всех значениях аргумента х = 0,..., 2 п -- 1 . Этот феномен получил название квантового параллелизма.

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

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

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

Исследуются различные пути физической реализации квантовых компьютеров. Модельные эксперименты по квантовому компьютингу выполнены на импульсном ядерном магнитно-резонансном спектрометре. В этих моделях работало два или три спина (кубита), например два спина ядер 13 С и один спин протона в молекуле трихлорэтилена

Однако в этих опытах квантовый компьютер был "ансамблевым": выходные сигналы компьютера сложены большим числом молекул в жидком растворе (~ 1020).

К настоящему времени высказаны предложения о реализации квантовых компьютеров на ионах и молекулах в ловушках в вакууме, на ядерных спинах в жидкостях (см. выше), на ядерных спинах атомов 31 Р в кристаллическом кремнии, на спинах электронов в квантовых точках, созданных в двумерном электронном газе в гетероструктурах GaAs, на переходах Джозеф-сона. Как видим, в принципе, квантовый компьютер можно построить на атомных частицах в вакууме, жидкости, кристаллах. При этом в каждом случае предстоит преодолеть те или иные препятствия, однако среди них можно выделить несколько общих, обусловленных принципами действия кубитов в квантовом компьютере. Поставим задачу создать полномасштабный квантовый компьютер, содержащий, скажем, 10 3 кубитов (хотя и при п = 100 квантовый компьютер может стать полезным инструментом).

1. Нужно найти способы "инициализации" кубитов компьютера в состояние. Для спиновых систем в кристаллах очевидно применение сверхнизких температур и сверхсильных магнитных полей. Применение поляризации спинов накачкой может оказаться полезным при одновременном применении охлаждения и больших магнитных полей.

Для ионов в вакуумных ловушках сверхнизкое охлаждение ионов (атомов) достигается лазерными методами. Очевидна также необходимость холодного и сверхвысокого вакуума.

2. Необходимо иметь технологию избирательного воздействия импульсами на любой выбранный кубит. В области радиочастот и спинового резонанса это означает, что каждый спин должен обладать своей резонансной частотой (в терминах спектроскопического разрешения). Различия резонансных частот для спинов в молекулах обусловлены химическими сдвигами для спинов одного изотопа и одного элемента; необходимые различия частот имеются для спинов ядер различных элементов. Однако здравый смысл подсказывает, что эти дарованные природой различия резонансных частот вряд ли достаточны, чтобы работать с 103 спинов.

Более перспективными представляются подходы, когда можно управлять извне резонансной частотой каждого кубита. В предложении о кремниевом квантовом компьютере кубитом служит ядерный спин примесного атома 31 Р. Частота резонанса определяется константой А сверхтонкого взаимодействия ядерного и электронного спинов атома 31 Р. Электрическое поле на наноэлектроде, находящемся над атомом 31 Р, поляризует атом и изменяет константу А (соответственно резонансную частоту ядерного спина). Таким образом, наличие электрода встраивает кубит в электронную схему и настраивает его резонансную частоту.

3. Для выполнения операции CNOT (контролируемое НЕ) необходимо взаимодействие между кубитами и вида. Такое взаимодействие возникает между спинами ядер в молекуле, если ядра и разделены одной химической связью. В принципе, необходимо иметь возможность выполнять операцию для любых пар кубитов. Иметь физическое взаимодействие кубитов одного масштаба величины и по принципу "все со всеми" в природной среде вряд ли возможно. Очевидна потребность в способе настройки среды между кубитами извне путем введения электродов с управляемым потенциалом. Таким путем можно создать, например, перекрытие волновых функций электронов в соседних квантовых точках и возникновение взаимодействия вида между спинами электронов [. Перекрытие волновых функций электронов соседних атомов 31Р обусловливает возникновение взаимодействия вида между ядерными спинами.

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

4. В ходе выполнения унитарного преобразования, соответствующего избранному алгоритму, кубиты компьютера подвергаются воздействию со стороны среды; в результате амплитуды и фазы вектора состояния кубита испытывают случайные изменения -- декогеренизацию. По существу, декогеренизация -- это релаксация тех степеней свободы частицы, которые используются в кубите. Время декогеренизации равно времени релаксации. В ядерном магнитном резонансе в жидкостях времена и релаксации составляют 1-10 с. Для ионов в ловушках с оптическими переходами между уровнями Е0 и Е1 временем декогеренизации выступают время спонтанного излучения и время столкновений с остаточными атомами. Очевидно, что декогеренизация -- это серьезное препятствие квантовому вычислению: начатый вычислительный процесс приобретает черты случайности по истечении времени декогеренизации. Однако можно достичь устойчивого квантового вычислительного процесса в течение сколь угодно долгого времени т > та, если систематически использовать методы квантового кодирования и коррекции ошибок (фазовых и амплитудных). Доказано, что при относительно невысоких требованиях к безошибочному выполнению элементарных операций типа NОТ и СNОТ (вероятность ошибки не более 10-5) методы квантовой коррекции ошибок (QEC) обеспечивают устойчивую работу квантового компьютера.

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

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

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

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

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

В обычном компьютере информация кодируется последовательностью битов, и эти биты последовательно обрабатываются булевскими логическими элементами, чтобы получить нужный результат. Аналогично квантовый компьютер обрабатывает кубиты, выполняя последовательность операций квантовыми логическими элементами, каждый из которых представляет собой унитарное преобразование, действующее на единичный кубит или пару кубитов. Последовательно выполняя эти преобразования, квантовый компьютер может выполнить сложное унитарное преобразование над всем набором кубитов приготовленных в некотором начальном состоянии. После этого можно произвести измерение над кубитами, которое и даст конечный результат вычислений. Это сходство вычислений между квантовым и классическим компьютером позволяет считать, что, по крайней мере, в теории, классический компьютер может в точности воспроизводить работу квантового компьютера. Другими словами, классический компьютер может делать все то же самое, что и квантовый компьютер. Тогда зачем вся эта возня с квантовым компьютером? Дело в том, что, хотя теоретически классический компьютер может симулировать квантовый компьютер, это очень неэффективно, настолько неэффективно, что практически классический компьютер не в состоянии решать многие задачи, которые по плечу квантовому компьютеру. Симуляция квантового компьютера на классическом компьютере вычислительно сложная проблема, потому что корреляции между квантовыми битами качественно отличается от корреляций между классическими битами, как было впервые показано Джоном Беллом. Для примера можно взять систему только из нескольких сотен кубитов. Она существует в пространстве Гильберта размерностью ~10 90 , что потребует, при моделировании классическим компьютером, использования экспоненциально больших матриц (чтобы выполнить расчеты для каждого отдельного состояния, которое также описывается матрицей). Это означает, что классическому компьютеру понадобится экпоненциально больше времени по сравнению даже с примитивным квантовым компьютером.

Ричард Фейнман был среди первых, кто осознал потенциал, заложенный в явлении квантовой суперпозиции для решения таких задач гораздо быстрее. Например, система из 500 кубитов, которую практически невозможно промеделировать классически, представляет собой квантовую суперпозицию из 2 500 состояний. Каждое значение такой суперпозиции классически эквивалентно списку из 500 единиц и нулей. Любая квантовая операция над такой системой, например, настроенный определенным образом импульс радиоволн, который может выполнить операцию управляемое НЕ над, скажем, 100-м и 101-м кубитом, будет одновременно воздействовать на 2 500 состояний. Таким образом, за один тик компьютерных часов квантовая операция вычисляет не одно машинное состояние, как обычные компьютеры, а 2 500 состояний сразу! Однако, в конце концов, над системой кубитов производится измерение, и система коллапсирует в единственное квантовое состояние, соответствующее единственному решению задачи, единственному набору из 500 единиц и нулей, как это диктуется измерительной аксиомой квантовой механики. Это поистине волнующий результат, поскольку это решение, найденное колективным процессом квантовых параллельных вычислений, берущим свои истоки в суперпозиции, эквивалентно выполнению той же самой операции на классическом суперкомпьютере с ~10 150 отдельных процессоров (что, конечно, невозможно)!! Первые исследователи в этой области были, конечно, вдохновлены такими гигантскими возможностями, и поэтому вскоре началась настоящая охота за подходящими задачами для такой вычислительной мощи. Питер Шор, исследователь и компьютерный ученый из компании AT&T"s Bell Laboratories в Нью Джерси, предложил такую задачу, которую можно было бы решить именно на квантовом компьютере и при помощи квантового алгоритма. Алгоритм Шора использует мощь квантовой суперпозиции, чтобы раскладывать большие числа (порядка ~10 200 двоичных разрядов и больше) на множители за несколько секунд. Эта задча имеет важное практическое применение для шифрования, где общепринятый (и лучший) алгоритм шифрования, известный как RSA, основан как раз на сложности разложения больших составных чисел на простые множители. Компьютер, который с легкостью решает такую задачу, конечно, представляет большой интерес для множества правительственных организаций, использующих RSA, который до сих пор считался "невзламываемым", и для любого кто заинтересован в безопсаности своих данных.

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