Главная » Безопасность » Квантовый компьютер и квантовые вычисления. Квантовые компьютеры

Квантовый компьютер и квантовые вычисления. Квантовые компьютеры

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

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

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

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

По мере распространения компьютеров ученые, занимавшиеся квантовыми объектами, пришли к выводу о практической невозможности напрямую рассчитать состояние эволюционирующей системы, состоящей всего лишь из нескольких десятков взаимодействующих частиц, например молекулы метана СН 4 . Объясняется это тем, что для полного описания сложной системы необходимо держать в памяти компьютера экспоненциально большое (по числу частиц) количество переменных, так называемых квантовых амплитуд. Возникла парадоксальная ситуация: зная уравнение эволюции, зная с достаточной точностью все потенциалы взаимодействия частиц друг с другом и начальное состояние системы, практически невозможно вычислить ее будущее, даже если система состоит лишь из 30 электронов в потенциальной яме, а в распоряжении имеется суперкомпьютер с оперативной памятью, число битов которой равно числу атомов в видимой области Вселенной. В то же время, для исследования динамики такой системы можно просто поставить эксперимент с 30 электронами, поместив их в заданные потенциал и начальное состояние. На это, в частности, обратил внимание русский математик Ю. И. Манин, указавший в 1980 году на необходимость разработки теории квантовых вычислительных устройств. В 1980-е годы эту же проблему изучали американский физик П. Бенев, явно показавший, что квантовая система может производить вычисления, а также английский ученый Д. Дойч, теоретически разработавший универсальный квантовый компьютер, превосходящий классический аналог.

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

И все же долгое время оставалось неясным, можно ли использовать гипотетическую вычислительную мощь квантового компьютера для ускорения решения практических задач. В 1994 году американский математик П. Шор предложил квантовый алгоритм, позволяющий проводить быструю факторизацию больших чисел. По сравнению с лучшим из известных на сегодня классических методов квантовый алгоритм Шора дает многократное ускорение вычислений, причем, чем длиннее факторизуемое число, тем значительней выигрыш в скорости. В случае классического алгоритма увеличение факторизуемого числа приводит к экспоненциальному росту требуемых ресурсов. Например, для разложения на множители 500-значного числа нужно в 100 млн. раз больше итераций, чем для 250-значного числа. Для алгоритма Шора объём необходимых ресурсов растёт лишь полиномиально – 500-значное число требует всего в 8 раз больше шагов, чем 250-значное.

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

В 1997 году Л. Гровер предложил квантовый алгоритм быстрого поиска в неупорядоченной базе данных. (Пример такой базы данных - телефонная книга, в которой фамилии абонентов расположены не по алфавиту, а произвольным образом.) Задача поиска, выбора оптимального элемента среди многочисленных вариантов очень часто встречается в экономических, военных, инженерных задачах, в компьютерных играх. Алгоритм Гровера позволяет не только ускорить процесс поиска, но и увеличить примерно в два раза число параметров, учитываемых при выборе оптимума.

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

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

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

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

Создание универсального квантового компьютера - одна из сложнейших задач современной физики, решение которой в корне изменит представления человечества об интернете и методах передачи информации, кибербезопасности и криптографии, электронных валютах, системах искусственного интеллекта и машинного обучения, методах синтеза новых материалов и лекарств, подходах к моделированию сложных физических, квантовых и ультра больших (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 схем: эффективной связи кубитов и управляющих элементов, схемотехнические решения перепутывания кубитов, квантовой нелинейности взаимодействия элементов с малым количеством фотонов и т.п. Эти исследования направлены на формирование базы практических экспериментальных методов для создания многокубитных квантовых интегральных схем.

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

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

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

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

Что такое квантовые вычисления?

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

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

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

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

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

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

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

Пока не очень-то и понятно, в чём фишка. А фишка вот в чём. Суперпозиция одного кубита записывается как A|0> + B|1>, где A и B - некоторые комплексные числа, единственное ограничение на которые заключается в том, что сумма квадратов их модулей всегда должна равняться 1. А если рассмотреть два кубита? Два бита могут получать 4 возможных значения: 00, 01, 10 и 11. Резонно предположить, что два кубита представляют собой суперпозицию четырёх базовых значений: A|00> + B|01> + C|10> + D|11>. И так оно и есть. Три кубита представляют собой суперпозицию восьми базовых значений. Другими словами, квантовый регистр из N кубитов одновременно хранит в себе 2N комплексных чисел. Ну а с математической точки зрения это есть 2N -мерный вектор в комплекснозначном пространстве. Именно этим достигается экспоненциальная мощность модели квантовых вычислений.

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

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

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

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

То есть что получается? Имея N кубитов можно одновременно обработать 2N комплексных чисел. И в выходном векторе будут результаты обработки всех этих чисел одновременно. В этом мощь модели квантовых вычислений. Но получить можно только одно значение, и оно может быть каждый раз различное в зависимости от распределения вероятностей. В этом ограничение модели квантовых вычислений.

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

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

Алгоритм Дойча

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

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

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

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

Что получается? Как уже было сказано, при измерении мы не можем получить все значения функции. Но мы можем сделать определённые выводы о её свойствах. Задача Дойча как раз и спрашивает о свойстве функции. И это свойство очень простое. Ведь как выходит? Если функция константна, то сложение по модулю 2 всех её выходных значений всегда даёт 0. Если же функция сбалансирована, то сложение по модулю 2 всех её выходных значений всегда даёт 1. Именно этот результат мы и получили в результате выполнения алгоритма Дойча. Мы не знаем, какое именно значение вернула функция на равновероятностной суперпозиции всех входных значений. Мы знаем только, что это тоже суперпозиция результатов, и если теперь эту суперпозицию преобразовать специальным образом, то будут сделаны однозначные выводы о свойстве функции.

Вот как-то так.

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

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

Уже упоминалась некая фаза, которая может быть у квантового состояния в составе кубита. Как таковой фазы нет в классической модели, это что-то новенькое именно в рамках квантовых вычислений. Фазу можно понимать как знак у коэффициента при квантовом состоянии в суперпозиции. Алгоритм Гровера основан на том, что специально подготовленная функция меняет фазу у состояния |1>.

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

Алгоритм Гровера состоит из следующих шагов:

1. Инициализация начального состояния . Опять готовится равновероятностная суперпозиция всех входных кубитов.

2. Применение итерации Гровера . Данная итерация состоит из последовательного применения функции поиска (она определяет критерий поиска элемента) и специального гейта диффузии. Гейт диффузии меняет коэффициенты при квантовых состояниях, вращая их вокруг среднего. Тем самым производится амплификация, то есть увеличение амплитуды искомого значения. Фишка в том, что осуществить применение итерации необходимо определённое количество раз (√2n ), иначе алгоритм вернёт не те результаты.

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

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

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

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

Классические вычисления: AND, OR, NOT

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

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

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

Квантовые вычисления. Физическая основа

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

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

Кубиты

В квантовых вычислениях физические свойства квантовых объектов реализованы в так называемых кубитах (q-bit). Классический бит может находиться только в одном состоянии – 0 или 1. Кубит до измерения может находиться одновременно в обоих состояниях, поэтому его принято обозначать выражением a|0⟩ + b|1⟩, где A и B - комплексные числа, удовлетворяющие условию |A| 2 +|B| 2 =1. Измерение кубита мгновенно «схлопывает» его состояние в одно из базисных – 0 или 1. При этом «облако» коллапсирует в точку, первоначальное состояние разрушается, и вся информация о нем безвозвратно теряется.

Одно из применений этого свойства – кот Шредингера генератор истинно случайных чисел. Кубит вводится в такое состояние, при котором результатом измерения могут быть 1 или 0 с одинаковой вероятностью. Это состояние описывается так:

Квантовые и классические вычисления. Первый раунд

Начнем с основ. Имеется набор исходных данных для вычислений, представленный в двоичном формате векторами длиной N.

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

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

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

Рассмотрим реальную задачу. Нужно определить, эквивалентны ли два бита.

Если при классических вычислениях на выходе получаем единицу, значит эквивалентны, иначе нет:

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

В примере мы сравниваем значения первого и второго кубитов. Результат будет в нулевом кубите - кубите-флаге. Данный алгоритм применим только к базовым состояниям – 0 или 1. Вот порядок квантовых преобразований.

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

Следующий уровень. Квантовые однокубитные гейты Паули

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

В квантовых вычислениях обрабатываемая информация закодирована в квантовых битах – так называемых кубитах. В простейшем случае кубит, как и классический бит, может находиться в одном из двух базисных состояний: |0⟩ (краткое обозначение для вектора 1|0⟩ + 0|1⟩) и |1⟩ (для вектора 0|0⟩ + 1|1⟩). Квантовый регистр представляет собой тензорное произведение векторов кубит. В простейшем случае, когда каждый кубит находится в одном из базисных состояний, квантовый регистр эквивалентен классическому. Регистр из двух кубит, находящихся в состоянии |0>, можно расписать в таком виде:

(1|0⟩ + 0|1⟩)*(1|0⟩ + 0|1⟩) = 1|00⟩ + 0|01⟩ + 0|10⟩ + 0|11⟩ = |00⟩.

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

А вот пример применения гейта Not:

X * |0⟩ = X * (1|0⟩ + 0|1⟩) = 0|0⟩ + 1|1⟩ = |1⟩

Множители перед базисными состояниями называются амплитудами и являются комплексными числами. Модуль комплексного числа равен корню из суммы квадратов действительной и мнимой частей. Квадрат модуля амплитуды, стоящей перед базисным состоянием, равен вероятности получить это базисное состояние при измерении кубита, поэтому сумма квадратов модулей амплитуд всегда равна 1. Мы могли бы использовать произвольные матрицы для преобразований над кубитами, но из-за того, что норма (длина) вектора всегда должна быть равна 1 (сумма вероятностей всех исходов всегда равна 1), наше преобразование должно сохранять норму вектора. Значит преобразование должно быть унитарным и соответствующая ему матрица унитарной. Напомним, что унитарное преобразование обратимо и UU † =I.

Для более наглядной работы с кубитами их изображают векторами на сфере Блоха. В такой интерпретации однокубитные гейты представляют собой вращение вектора кубита вокруг одной из осей. Например гейт Not (X) поворачивает вектор кубита на Pi относительно оси X. Таким образом, состояние |0>, представляемое вектором, направленным строго вверх, переходит в состояние |1>, направленное строго вниз. Состояние кубита на сфере Блоха определяется формулой cos(θ/2)|0⟩+e iϕ sin(θ/2)|1⟩

Квантовые двухкубитные гейты

Для построения алгоритмов нам недостаточно только однокубитных гейтов. Необходимы гейты, которые осуществляют преобразования в зависимости от некоторых условий. Основным таким инструментом является двухкубитный гейт CNOT. Этот гейт применяется к двум кубитам и инвертирует второй кубит только в том случае, если первый кубит находится в состоянии |1⟩. Матрица гейта CNOT выглядит так:

А вот пример применения:

CNOT *|10⟩ = CNOT * (0|00⟩ + 0|01⟩ + 1|10⟩ + 0|11⟩) = 0|00⟩ + 0|01⟩ + 1|11⟩ + 0|10⟩ = |11⟩

Применение гейта CNOT эквивалентно выполнению классической операции XOR с записью результата во второй кубит. Действительно, если посмотреть на таблицу истинности оператора XOR и CNOT, то увидим соответствие:

XOR			CNOT
0	0	0	00	00
0	1	1	01	01
1	0	1	10	11
1	1	0	11	10

У гейта CNOT есть интересное свойство – после его применения кубиты запутываются или распутываются, в зависимости от исходного состояния. Это будет показано в следующей статье, в разделе про квантовый параллелизм.

Построение алгоритма - классическая и квантовая реализация

Имея полный арсенал квантовых гейтов, мы можем приступать к разработке квантовых алгоритмов. В графическом представлении кубиты представляются прямыми линиями – «струнами», на которые накладываются гейты. Однокубитные гейты Паули обозначаются обычными квадратами, внутри которых изображается ось вращения. Гейт CNOT выглядит немного сложнее:

Пример применения гейта CNOT:

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

Итак, попробуем построить классический и квантовый алгоритм, который прибавляет 3 к аргументу.

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

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

Arg = #задаем аргумент result = #инициализируем результат carry1 = arg & 0x1 #складываем с 0b11, так что перенос от младшего бита появится в том случае, если у агрумента младший бит = 1 result = arg ^ 0x1 #складываем младшие биты carry2 = carry1 | arg #складываем с 0b11, так что перенос от старшего бита появится в том случае, если у агрумента старший бит = 1 или был перенос с младшего бита result = arg ^ 0x1 #складываем старшие биты result ^= carry1 #применяем перенос с младшего бита result ^= carry2 #применяем перенос со старшего бита print(result)
Теперь попробуем разработать аналогичную программу для квантового вычислителя:

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

Первым шагом до барьера мы выставляем аргумент в то же состояние, как и в классическом случае – 0b11.
С помощью оператора CNOT вычисляем значение первого переноса – результат операции arg & 1 равен единице только тогда, когда arg равен 1, в этом случае мы инвертируем второй кубит.
Следующие 2 гейта реализуют сложение младших бит – мы переводим кубит 4 в состояние |1⟩ и результат XOR записываем в него же.
Большим прямоугольником обозначен гейт CCNOT – расширение гейта CNOT. В этом гейте два управляющих кубита и третий инвертируется только в том случае, если первые два находятся в состоянии |1. Комбинация из 2 гейт CNOT и одного CCNOT дает нам результат классической операции carry2 = carry1 | arg. Первые 2 гейта выставляют перенос в единицу в том случае, если один из них равен 1, а гейт CCNOT обрабатывает случай, когда они оба равны единице.
Складываем старшие кубиты и кубиты переноса.

Промежуточные выводы

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

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

По материалам

Историческая справка

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

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

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

Заметим, что воздействие на какой-либо кубит немедленно приводит к одновременному изменению всех 2” базовых состояний. Это свойство носит название «квантовый параллелизм ».

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

Под унитарной матрицей будем понимать квадратную матрицу ||aj|, произведение которой на комплексную сопряженную и транспонированную матрицу || aJI дает единичную матрицу. Числа a jk и a ki комплексные. Если числа a ik являются действительными числами, то унитарная матрица будет ортогональной. Некоторое число кубитов формирует квантовый регистр компьютера. В такой цепочке квантовых битов можно проводить одно- и двухбитовые логические операции подобно тому, как в классическом регистре проводятся операции НЕ, И-НЕ, 2 ИЛИ-HE и т.д. (рис. 5.49).

Определенное число N регистров формируют по существу квантовый компьютер. Работа квантового компьютера происходит в соответствии с разработанными алгоритмами вычислений.

Рис. 5.49.

NOT - булевское НЕ; CNOT - контролируемое НЕ

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

где p i - населенность или вероятность i- го состояния, так что р { + р 2 + р 3 + + Ра = 1-

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

Если два кубита сцеплены между собой, то они лишены индивидуальных квантовых состояний. Они зависят друг от друга так, что измерение для одного тина дает «О», а для другого - «1» и наоборот (рис. 5.50). В этом случае говорят, что максимально сцепленная пара несет один e-бит сцеплснности.

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

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

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

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

Алгоритм Дойна - Йожи позволяет «за одно вычисление» определить, является ли функция двоичной переменной /(/?) постоянной (f x {ri) = О, f 2 {ri) = 1 независимо от п) или «сбалансированной» (f 3 (0) = 0,/ 3 (1) = 1;/ 4 (0) = 1, / 4 (1) = 0).

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

Алгоритм Гровера позволяет найти решение уравнения f(x) = 1 для 0 х за время O(VN) и предназначен для поиска в базе данных. Квантовый алгоритм Гровера является заведомо более эффективным, чем любой алгоритм для неупорядоченного поиска на классическом компьютере.

Алгоритм факторизации Шора позволяет определить для простых множителей аиЬ заданное целое число М= a"Xb путем использования соответствующей квантовой схемы. Этот алгоритм позволяет находить сомножители А-значного целого числа. С его помощью можно оценить время вычислительного процесса. Одновременно алгоритм Шора можно интерпретировать как пример процедуры определения энергетических уровней квантовой вычислительной системы.

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

Алгоритм Саймона решает проблему «черного ящика» экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы.

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

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

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