Информатика и программирование

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 4
1 ОБЗОР ПОИСКОВЫХ СИСТЕМ В ИНТЕРНЕТЕ 6
2 ПОЯВЛЕНИЕ КВАНТОВЫХ ВЫЧИСЛЕНИЙ 9
2.1 История возникновения идеи о квантовых вычислениях 9
2.2 Основные понятия квантовых вычислений 11
2.3 Квантовые алгоритмы 14
2.3.1 Алгоритм Шора 14
2.3.2 Алгоритм Гровера 15
3 РЕАЛИЗАЦИЯ КВАНТОВОГО КОМПЬЮТЕРА 17
3.1 Основные принципы работы и реализации квантовых
компьютеров 17
3.2 Виды квантовых компьютеров 21
ЗАКЛЮЧЕНИЕ 24
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 25

Введение

В данный момент, квантовые компьютеры и теория квантовой информации находится в начальной стадии. Преодолеваются препятствия, что обеспечит знания, необходимые для продвижения квантовых компьютеров на их законное место самых быстрых вычислительных устройств на свете. Коррекция ошибок осуществила многообещающий прогресс на сегодняшний день, приближаясь к точке, когда у нас появятся все необходимые инструменты, необходимые для постройки компьютера, способного достаточно устойчиво противостоять эффектам декогеренции.
Квантовое аппаратное обеспечение, с другой стороны, остаётся отсталой областью, но совершённая на данный день работа предполагает, что это лишь вопрос времени, прежде чем мы построим достаточно большие устройства для тестирования алгоритма Шора и других квантовых алгоритмов. В связи с этим, квантовые компьютеры предстанут в качестве превосходных вычислительных устройств, и возможно однажды сделают современные компьютеры устаревшими. Квантовые вычисления имеет корни в узко специализированных областях теоретической физики, но их будущее без сомнений лежит в огромном эффекте, которые они окажут на жизнь всего человечества.
Уже сейчас существует множество систем, в работе которых квантовые эффекты играют существенную роль. Одним из наиболее известных примеров может служить лазер: поле его излучения порождается квантомеханическими событиями - спонтанным и индуцированным излучением света. Другим важным примером таких систем являются современные микросхемы - непрерывное ужесточение проектных норм приводит к тому, что квантовые эффекты начинают играть в их поведении существенную роль. В диодах Ганна возникают осцилляции электронных токов, в полупроводниках образуются слоистые структуры: электроны или дырки в различных запертых состояниях могут хранить информацию, а один или несколько электронов могут быть заперты в так называемых квантовых ямах.
Прототипы квантовых компьютеров существуют уже сегодня. Правда, пока что экспериментально удается собирать лишь небольшие регистры, состоящие всего из нескольких квантовых битов. Так, недавно группа, возглавляемая американским физиком И. Чангом (IBM), объявила о сборке 5-битового квантового компьютера. Несомненно, это большой успех. К сожалению, существующие квантовые системы еще не способны обеспечить надежные вычисления, так как они либо недостаточно управляемы, либо очень подвержены влиянию шумов. Однако физических запретов на построение эффективного квантового компьютера нет, необходимо лишь преодолеть технологические трудности.
Следовательно, тема изучения квантовых компьютеров актуальна и на сегодняшний день.
Обзор поисковых систем в ИнтернетеПоисковая система – это программно-аппаратный комплекс, предназначенный для осуществления поиска в сети Интернет и реагирующий на запрос пользователя, задаваемый в виде текстовой фразы (поискового запроса), выдачей списка ссылок на источники информации, в порядке релевантности (в соответствии запросу).
Рассмотрим подробнее понятие поискового запроса на примере поисковой системы «Яндекс». Поисковый запрос должен быть сформулирован пользователем в соответствии с тем, что он хочет найти, максимально кратко и просто. Допустим, мы хотим найти информацию в «Яндексе» о том, как выбрать автомобиль. Для этого, открываем главную страницу «Яндекса», и вводим текст поискового запроса «как выбрать автомобиль». Далее, наша задача сводится к тому, чтобы открыть предоставленные по нашему запросу ссылки на источники информации в Интернет. Однако, вполне можно и не найти нужную нам информацию. Если таковое произошло, то либо нужно перефразировать свой запрос, либо в базе поисковой системе действительно нет никакой актуальной информации по нашему запросу (такое может быть при задании очень «узких» запросов, как, например «как выбрать автомобиль в Архангельске»)
Первоочередная задача любой поисковой системы – доставлять людям именно ту информацию, которую они ищут. А научить пользователей делать «правильные» запросы к системе, т.е. запросы, соответствующие принципам работы поисковых систем, невозможно. Поэтому разработчики создают такие алгоритмы и принципы работы поисковых систем, которые бы позволяли находить пользователям искомую ими информацию.
В начальный период развития Интернет, число его пользователей было невелико, а объем доступной информации сравнительно небольшим. В большинстве своем, доступ к сети Интернет имели лишь сотрудники научно-исследовательской сферы. В это время задача поиска информации в Интернете не была столь актуальной, как в настоящее время.
Одним из первых способов организации доступа к информационным ресурсам сети стало создание открытых каталогов сайтов, ссылки на ресурсы в которых группировались согласно тематике. Первым таким проектом стал сайт Yahoo.com, открывшийся весной 1994 года. После того, как количество сайтов в каталоге Yahoo значительно увеличилось, была добавлена возможность поиска нужной информации по каталогу. В полном смысле это еще не было поисковой системой, так как поисковая область была ограничена только ресурсами, присутствующими в каталоге, а не всеми Интернет ресурсами.
Каталоги ссылок широко использовались ранее, однако практически полностью утратили свою популярность в настоящее время. Так как даже современные, огромные по своему объему каталоги, содержат информацию лишь о ничтожно малой части сети Интернет. Самый большой каталог сети DMOZ (его еще называют Open Directory Project) содержит информацию о 5 миллионах ресурсов, тогда как база поисковой системы Google состоит из более чем 8 миллиардов документов.
Первой полноценной поисковой системой стал проект WebCrawler, вышедший в свет в 1994 году.
В 1995 году появились поисковые системы Lycos и AltaVista. Последняя долгие годы была лидером в области поиска информации в сети Интернет.
В 1997 году Сергей Брин и Ларри Пейдж создали поисковую машину Google в рамках исследовательского проекта в Стэндфордском университете. В настоящий момент Google - самая популярная поисковая система в мире!
В сентябре 1997 года была официально анонсирована поисковая система Yandex, являющаяся самой популярной в русскоязычном Интернете.
В настоящее время существуют три основные поисковые системы (международные) – Google, Yahoo и MSN, имеющие собственные базы и алгоритмы поиска. Большинство остальных поисковых систем (коих насчитывается большое количество) использует в том или ином виде результаты трех перечисленных. Например, поиск AOL (search.aol.com) использует базу Google, а AltaVista, Lycos и AllTheWeb – базу Yahoo.
Наиболее крупные международные поисковые системы: «Google», «Yahoo», «MSN». В русском Интернете это – «Яндекс», «Рамблер», «Апорт».
В России основной поисковой системой является «Яндекс», далее - Rambler.ru, Google.ru, Aport.ru, Mail.ru. Информация представлена на рисунке REF Risunok1 \h 1. Причем, на данный момент, Mail.ru использует механизм и базу поиска «Яндекса».
Рисунок SEQ Рисунок \* ARABIC 1- Диаграмма использования поисковых систем за декабрь 2018
Практически все крупные поисковые системы имеют свою собственную структуру, отличную от других. Однако можно выделить общие для всех поисковых машин основные компоненты. Различия в структуре могут быть лишь в виде реализации механизмов взаимодействия этих компонентов.
Появление Квантовых вычисленийИстория возникновения идеи о квантовых вычисленияхВсе началось в 1982 году, когда Фейнман написал очень интересную статью, в которой рассмотрел два вопроса. Он подошёл к процессу вычисления как физик: есть чисто логические ограничения на то, что можно вычислить (можно придумать задачу, для которой вообще нет алгоритма, можно придумать задачу, для которой любой алгоритм будет долго работать). А есть ли ограничения физические? Вот есть закон сохранения энергии - вечный двигатель невозможен; а есть ли какое-нибудь физическое ограничение на функционирование компьютера, которое накладывает некие запреты на реализуемость алгоритмов? И Фейнман показал, что термодинамических ограничений, типа второго начала термодинамики, нет. Если мы будем уменьшать потери энергии, шумы, то мы можем сделать сколь угодно длинные вычисления со сколь угодно малыми затратами энергии. Это означает, что вычисления можно сделать обратимым образом - потому что в необратимых процессах энтропия возрастает.
Собственно, Фейнмана это и заинтересовало: ведь реальное вычисление на реальном компьютере необратимо. И полученный им результат состоит в том, что можно так переделать любое вычисление - без особой потери эффективности, - чтобы оно стало обратимым. Те вычисления, которые делаются «просто так», конечно, необратимы, но «рост необратимости» пренебрежимо мал по сравнению, с шумами в современном компьютере. То есть необратимость - это тонкий эффект; тут вопрос не практический а принципиальный: если представить себе, что технология дойдет до такого уровня, что этот эффект станет существенным, то можно так перестроить вычисления, чтобы добиться обратимости.
И в этой же работе Фейнман обратил внимание на то, что если у нас имеется устройство квантовое, то есть подчиняющееся законам квантовой механики, то его вычисли-тельные возможности совершенно не обязательно должны совпадать с возможностями обычного устройства. Возникают некоторые дополнительные возможности. Но пока непонятно, позволяют они получить какой-то выигрыш или нет. Фактически, он и поставил своей статьей такой вопрос.[5]
Ю.И. Манин в конце семидесятых годов написал две популярные книжки по логике - «Вычислимое и невычислимое» и «Доказуемое и недоказуемое», и в одной из них есть сюжет про квантовые автоматы, где он говорит о некоторых кардинальных отличиях этих автоматов от классических.
В середине восьмидесятых годов появились работы Дойча (D. Deutsch), Бернстайна и Вазирани (Е. Bernstein, U. Vazirani), Яo (A. Уао). В них были построены формальные модели квантового компьютера - например, квантовая машина Тьюринга.
Следующий этап - статья Шора (Р.W. Shor) 1994 года, вызвавшая лавинообразный рост числа публикаций о квантовых вычислениях. Шор построил квантовый (то есть реализуемый на квантовом компьютере) алгоритм факторизации (разложения целых чисел на множители - используется в том числе для вскрытия зашифрованных сообщений). Все известные алгоритмы для обычного компьютера - экспоненциальные (время их работы растет как экспонента от числа знаков в записи факторизуемого числа).
Факторизация 129-разрядного числа потребовала 500 MIPS-лет, или восемь месяцев непрерывной работы системы из 1600 рабочих станций, объединенных через Интернет. А при числе разрядов порядка 300 это время существенно превзойдет возраст Вселенной - даже если работать одновременно на всех существующих в мире машинах.
Считается (хотя это и не доказано!), что быстрого алгоритма решения этой задачи не существует. Более того, гарантией надежности большинства существующих шифров является именно сложность решения задачи факторизации или одной из родственных ей теоретико-числовых задач, например - дискретного логарифма. И вдруг выясняется, что на квантовом компьютере эта задача имеет всего лишь кубическую сложность! Перед квантовым компьютером классические банковские, военные и другие шифры мгновенно теряют всякую ценность. Короче говоря, работа Шора показала, что вся эта изысканная академическая деятельность непосредственно касается такой первобытной стихии, как деньги. После этого и началась настоящая популярность...[1]
Впрочем, выясняется, что не только классическая, но и квантовая криптография (наука о шифровании сообщений) часто не способна противостоять квантовой криптоаналитике (науке о расшифровке). Некоторые важные криптографические протоколы, такие как «подбрасывание монеты по телефону», рушатся при переходе к квантовым вычислениям. Точнее, гарантией их надежности является отныне не сложность тех или иных алгоритмов, а сложность задачи создания квантового компьютера.
Таким образом, возникает новая отрасль вычислений - квантовые вычисления. Квантовые вычисления (КВ) - это, как можно догадаться, вычисления на квантовом компьютере. Квантовых компьютеров на свете пока нет. Более того, до сих пор неясно, когда появятся практически полезные конструкции и появятся ли вообще. Тем не менее, квантовые вычисления - предмет, чрезвычайно модный сейчас в математике и физике, как теоретической, так и экспериментальной, и занимается им довольно много людей. Судя по всему, именно интерес стимулировал первопроходцев - Ричарда Фейнмана, написавшего пионерскую работу, в которой ставился вопрос о вычислительных возможностях устройств на квантовых элементах; Дэвида Дойча, формализовавшего этот вопрос в рамках современной теории вычислений; и Питера Шора, придумавшего первый нетривиальный квантовый алгоритм.
Основные понятия квантовых вычисленийКлассический компьютер состоит из некоторого числа битов, с которыми можно выполнять арифметические операции. Основным элементом квантового компьютера (КК) являются квантовые биты, или кубиты (от Quantum Bit, qubit). Обычный бит - это классическая система, у которой есть только два возможных состояния. Можно сказать, что пространство состояний бита - это множество из двух элементов, например, из нуля и единицы. Кубит же - это квантовая система с двумя возможными состояниями. Имеется ряд примеров таких квантовых систем: электрон, у которого спин может быть равен либо +1/2 либо -1/2, атомы в кристаллической решетке при некоторых условиях. Но, поскольку система квантовая, ее пространство состояний будет несравненно богаче. Математически кубит - это двумерное комплексное пространство.
В такой системе можно выполнять унитарные преобразования пространства состояний системы. С точки зрения геометрии такие преобразования - прямой аналог вращении и симметрий обычного трехмерного пространства. Согласно принципу суперпозиции вы можете складывать состояния, вычитать их, умножать на комплексные числа. Эти состояния образуют фазовые пространства. При объединении двух систем полученное фазовое пространство будет их тензорным произведением. Эволюция системы в фазовом пространстве описывается унитарными преобразованиями фазового пространства.
Так вот, в квантовом компьютере аналогичная ситуация. Он тоже работает с нулями и единицами. Но его функциональные элементы реализуют действия прямо в фазовом пространстве некоторой квантовой системы - при помощи унитарных преобразований этого пространства.
Конечно, унитарные преобразования не могут быть произвольными - они должны удовлетворять некоторым естественным ограничениям. Например, в случае обычной логики достаточно иметь три операции: конъюнкция, дизъюнкция, отрицание. Все можно реализовать, используя только эти три операции. Точно так же и в квантовом случае есть некоторый набор операторов, действующих только на три бита, с помощью которых можно все реализовать. Там есть даже более тонкие результаты: можно ограничиться классическими операторами на нескольких битах, а квантовые операторы будут действовать только на один бит. То есть классический набор операций {конъюнкция, дизъюнкция, отрицание} можно заменить на такой: {конъюнкция, дизъюнкция, квантовое отрицание}, где квантовое отрицание - это произвольное унитарное преобразование одного кубита.Фазовое пространство КК есть тензорное произведение кубитов. Если в каждом кубите фиксирован базис (он будет состоять из двух векторов), то фазовое пространство - это комплексное линейное пространство, базис которого индексирован словами из нулей и единиц. Таким способом двоичное слово на входе определяет базисный вектор.
Итак, вход - двоичное слово, определяющее один из базисных векторов. Сам же алгоритм - предписанная последовательность элементарных операторов. Применяем эту последовательность к вектору на входе, в результате получаем некоторый вектор на выходе.
Так вот, согласно квантовой механике (КМ), пока система эволюционирует под действием наших унитарных операторов, мы не можем сказать, в каком именно классическом состоянии она находится. То есть она находится в каком-то квантовом состоянии, но измеряем-то мы, когда общаемся с системой, все равно какие-то классические значения. Как это понимается в КМ? В фазовом пространстве фиксируется некоторый базис, и вектор состояния разлагается по этому базису. Это математическая формализация процедуры измерения в КМ. То есть если мы имеем дело с ситемой, у которой «то ли спин влево, то ли спин вправо», и если мы все-таки посмотрим, какой спин, то мы получим одно из двух в любом случае. А вот вероятности того, что мы получим тот или другой результат, - это как раз квадраты модуля коэффициентов разложения. КМ утверждает, что точно предсказать ре-зультат измерения нельзя, но вероятности возможных результатов вычислить можно.
Вероятность возникает в процессе измерения. А пока система живет, для нас существенно, что там есть сам этот вектор.
Другими словами, существенно, что система «находится одновременно во всех возможных состояниях». Как пишут многие авторы популярных введений в KB, возникает совершенно чудовищный параллелизм вычислении: к примеру, в случае нашей системы из двух кубитов мы как бы оперируем одновременно со всеми возможными ее состояниями: 00, 01, 11, 10.
Чтобы интерпретировать ответ, надо заранее условиться, что какой-то бит - допустим, первый - это бит ответа. Пусть алгоритм проработал, у нас получился какой-то вектор, не обязательно базисный. Тогда мы можем сказать, что первый бит с некоторой вероятностью равен 1. И требование к алгоритму такое: если ответ «да», то вероятность того, что первый бит равен 1, должна быть больше двух третей. А если ответ «нет», вероятность того, что будет ноль, должна быть тоже больше двух третей.
Квантовые алгоритмыАлгоритм ШораВ 1994 году Питер Шор, вдохновленный работой Даниеля Саймона, открыл ограниченно — вероятностный алгоритм разложения на множители n-разрядных чисел за полиномиальное время на квантовом компьютере. Начиная с семидесятых, люди ищут эффективные алгоритмы для разложения целых чисел. Наиболее эффективным классическим алгоритмом, известным на сегодняшний день, является алгоритм Ленстра, который экспоненциален по размеру входа. Люди были настолько уверены в том, что эффективного алгоритма разложения не существует, что были созданы криптографические системы, например, RSA, которые опираются на сложность этой проблемы. Результат Шора был ошеломляющим для большинства учёных и побудил их к широкомасштабным исследованиям в области квантовых вычислений.
В большинстве алгоритмов, включая алгоритм Шора, используется стандартный способ сведения задачи разложения к задаче поиска периода функции. Шор использует квантовый параллелизм для получения суперпозиции всех значений функции за один шаг. Затем он производит квантовое преобразование Фурье, результатом которого, как для классического преобразовании Фурье, является функция, аргумент которой кратен величине, обратной периоду. С высокой вероятностью измерение состояния возвращает период, который в свою очередь, служит для разложения целого числа М.
Все, что было сказано выше, раскрывает суть квантового алгоритма, но в очень упрощённом виде. Наибольшая трудность заключается в том, что квантовое преобразование Фурье основано на быстром преобразовании Фурье и, таким образом, дает только приблизительный результат в большинстве случаев.
Алгоритм ГровераБольшой класс задач можно определять как задачи поиска вроде «найти из множества возможных решений, такое, что утверждение — истинно». Диапазон подобных задач широк: от поиска информации в базе данных до закраски графа. Например, задачу закраски графа можно рассматривать как поиск такого обозначения цветов вершин, что утверждение «все примыкающие вершины имеют разные цвета» является верным. Аналогично задача сортировки может быть рассмотрена, как поиск перестановки, для которой утверждение «перестановка переводит первоначальное состояние сортировки в желаемое» являлось бы верным.
В задаче неупорядоченного поиска ничего не известно о структуре пространства решений и об утверждении . Например, определение не дает никакой информации о возможном значении для . В задаче упорядоченного поиска можно использовать информацию о пространстве поиска и об утверждении .
Например, поиск по алфавитному списку является задачей упорядоченного поиска, и алфавитный порядок используется для построения алгоритма. В других случаях, скажем, в задачах, где нужно найти хотя бы одно решение, структуру задачи можно использовать для построения эвристических алгоритмов, которые быстро дают решения для некоторых отдельных случаев. Но в общем случае, когда мы имеем задачу неупорядоченного поиска, лучшее, что можно сделать классическим путем — это последовательно проверять истинность каждого утверждения . Для поискового пространства из элементов обычная задача неупорядоченного поиска требует проверок . На квантовом же компьютере, как показал Гровер, задачу неупорядоченного поиска можно решить с большой вероятностью производя около проверок. Таким образом, квантовый алгоритм Гровера является заведомо более эффективным, чем любой алгоритм для неупорядоченного поиска, выполняемый на классическом компьютере.
Гровер также показал, что некоторые поисковые задачи, которые на классических компьютерах выполняются за могут быть решены за на квантовом компьютере. Поиск Гровера можно использовать в других квантовых вычислениях в качестве подпрограммы. Байрон показал, что алгоритм Гровера можно применять для произвольного начального распределения амплитуд, и что при этом сохраняется сложность порядка .
Реализация квантового компьютераОсновные принципы работы и реализации квантовых компьютеровКвантовые методы выполнения вычислительных операций, а также передачи и обработки информации, уже начинают воплощаться в реально функционирующих экспериментальных устройствах, что стимулирует усилия по реализации квантовых компьютеров - этого нового направления в вычислительной технике.
Количество публикаций по квантовой теории информации и квантовым вычислениям приобрело в последнее время лавинообразный характер, появились и экспериментальные работы.
Принципиальная схема работы любого квантового компьютера может быть представлена на рисунке REF Risunok2 \h 2.
Рисунок SEQ Рисунок \* ARABIC 2 - Схематическая структура квантового компьютера
Основной его частью является квантовый регистр - совокупность некоторого числа L кубитов. До ввода информации в компьютер все кубиты регистра должны быть приведены в основные базисные (булевы) состояния, то есть в состояние . Эта операция называется подготовкой начального состояния или инициализацией. Далее каждый кубит подвергается селективному воздействию, например, с помощью импульсов внешнего электромагнитного поля, управляемых классическим компьютером, которое переведет основные базисные состояния определенных кубитов в неосновное состояния . При этом состояние всего регистра перейдет в суперпозицию базисных состояний вида , где , задающую бинарное представление числа имеющего вид
n=i=1Lni2i ( SEQ Формула \* ARABIC 1)
Вычисления производятся по формуле ( REF Formula \h 1).
При вводе информации в квантовый компьютер состояние входного регистра, с помощью соответствующих импульсных воздействий преобразуется в соответствующую когерентную суперпозицию базисных ортогональных состояний . В таком виде информация далее подвергается воздействию квантового процессора, выполняющего последовательность квантовых логических операций, определяемую унитарным преобразованием , действующим на состояние всего регистра. К некоторому моменту времени t в результате преобразований исходное квантовое состояние становится новой суперпозицией вида , которая и определяет результат преобразования информации на выходе компьютера.
Совокупность всех возможных операций на входе данного компьютера, формирующих исходные состояния, а также осуществляющих унитарные локальные преобразования, соответствующие алгоритму вычисления, способы подавления потери когерентности - так называемой декогерентизации (decoherence) квантовых состояний и исправления случайных ошибок, играют здесь ту же роль, что и "программное обеспечение" (software) в классическом компьютере.
Теперь обратимся к аппаратной части квантового компьютера. При выборе конкретной схемы любого квантового компьютера необходимо решить три вопроса: во-первых, выбрать физическую систему, представляющую требуемую систему кубитов, во-вторых, определить физический механизм, определяющий взаимодействие между кубитами, необходимое для выполнения двухкубитовых операций, в-третьих, определить способы селективного управления кубитами и измерения их состояния на выходе. Все это вместе взятое аналогично "аппаратному обеспечению" (hardware) классического компьютера.
Принципиальное отличие квантового компьютера в подходе к процессу вычисления.
В обычном процессоре все вычисления строятся на основе битов, бывающих в двух состояний 1 либо 0. То есть, вся работа сводится к анализу огромного количества данных на предмет соответствия заданным условиям. В основу квантового компьютера положены кубиты (квантовые биты). Их особенностью является возможность быть в состоянии 1, 0, а также одновременно 1 и 0.
Возможности квантового компьютера значительно возрастают, так как нет необходимости искать нужный ответ среди множества. В этом случае ответ выбирается из уже имеющихся вариантов с определенной долей вероятности соответствия.
Сравнение компьютеров приведено в таблице REF Tablisa1 \h 1.
Таблица SEQ Таблица \* ARABIC 1 – Сравнение классического и квантового компьютера
Классический компьютер Квантовый компьютер
Бит КубитРазное намагничивание Разные энергетические состояния
Только «0» и «1» Любые сочетания процентных долей «0» и «1»
Считается, что для реализации полномасштабного квантового компьютера, превосходящего по производительности любой классический компьютер, на каких бы физических принципах он не работал, следует обеспечить выполнение следующих пяти основных требований:
Физическая система, представляющая полномасштабный квантовый компьютер, должна содержать достаточно большое число хорошо различаемых кубитов для выполнения соответствующих квантовых операций.
Необходимо обеспечить условия для приготовления входного регистра в исходном основном базисном состоянии , то есть возможность процесса инициализации.
Необходимо обеспечить максимальное подавление эффектов декогерентизации квантовых состояний, обусловленное взаимодействием системы кубитов с окружающей средой, что приводит к разрушению суперпозиций квантовых состояний и может сделать невозможной выполнение квантовых алгоритмов. Время декогерентизации должно по крайней мере в раз превышать время выполнения основных квантовых операций (времени такта). Для этого система кубитов должна быть достаточно слабо связана с окружением.
Необходимо обеспечить за время такта выполнение требуемой совокупности квантовых логических операций, определяющей унитарное преобразование . Эта совокупность должна содержать определенный набор только двухкубитовых операций, типа контролируемого НЕ (аналог исключающего ИЛИ в классических компьютерах), осуществляющих операции поворота вектора состояния двух взаимодействующих кубитов в четырехмерном гильбертовом пространстве, и однокубитовых операций, осуществляющих поворот вектора состояния кубита в двухмерном гильбертовом пространстве, таких как операции НЕ, Адамара и некоторые другие.
Необходимо обеспечить с достаточно высокой надежностью измерение состояния квантовой системы на выходе. Проблема измерения конечного квантового состояния является одной из основных проблем квантовых вычислений. Это связано ещё и с тем, что измерения квантового состояния системы изменяют её.
Виды квантовых компьютеровТеоретических моделей квантового компьютера множество. Проблема, скорее, в том, чтобы найти разумные пути создания реального прибора. Существует несколько перспективных подходов к осуществлению идеи такого устройства.
Использование в качестве кубитов атомов с ядерными спинами с , принадлежащих молекулам органических жидкостей с косвенным скалярным взаимодействием между ними и методов ядерного магнитного резонанса (ЯМР) для управления кубитами.
Первые предложения были сформулированы в 1997 году в США и в Оксфорде в Великобритании. В этом же году были выполнены первые эксперименты на ядерных спинах двух атомов водорода в молекулах 2,3-дибромотиофена и на трех ядерных спинах - одном в атоме водорода и двух в изотопах углерода в молекулах трихлорэтилена . Важным здесь является то, что для селективного воздействия на ядерные спины молекулы необходимо, чтобы они достаточно различались по резонансным частотам. Позднее были осуществлены квантовые операции также в цитозине, хлороформе, аланине и других жидкостях с числом спинов-кубитов .
Главным преимуществом такого компьютера является то, что огромное число практически независимых молекул-компьютеров жидкости действует, обеспечивая тем самым возможность управления ими с помощью хорошо известных в технике ядерного магнитного резонанса (ЯМР) операций над макроскопическим объемом жидкости. Последовательности радиочастотных импульсов, выполняющие в этом случае роль определенных квантовых логических вентилей, осуществляют глобальные унитарные преобразования состояний соответствующих ядерных спинов для всех молекул-компьютеров. Индивидуальное обращение к отдельным кубитам заменяется одновременным обращением к соответствующим кубитам во всех молекулах большого ансамбля. Компьютер такого рода получил название ансамблевого ЯМР квантового компьютера. Замечательно, что он может в принципе работать при комнатной температуре. Время декогерентизации квантовых состояний ядерных спинов в жидкости достаточно велико. Оно может составлять несколько секунд.
В области ЯМР квантовых компьютеров на органических жидкостях к настоящему времени достигнуты наибольшие успехи. Они связаны в основном с хорошо развитой импульсной техникой ЯМР-спектроскопии, обеспечивающей выполнение различных операций над когерентными суперпозициями состояний ядерных спинов и с возможностью использования для этого стандартных ЯМР-спектрометров, работающих при комнатных температурах.
Экспериментально на ЯМР квантовых компьютерах были осуществлены алгоритм Гровера поиска данных, квантовое фурье-преобразование, квантовая коррекция ошибок, квантовая телепортация, квантовое моделирование и другие операции.
Основными ограничениями для этого направления являются:
Смешанный характер исходного состояния кубитов, что требует использования определенных неунитарных операций для приготовления начального состояния.
Измеряемый на выходе сигнал экспоненциально убывает с ростом числа кубитов L.
Число ядерных спинов-кубитов в отдельной молекуле с достаточно различающимися резонансными частотами L ограничено.
Однокубитовые и двукубитовые квантовые операции являются относительно медленными.
Эти ограничения приводят к тому, что ЯМР квантовые компьютеры на молекулах органической жидкости не смогут иметь число кубитов, значительно больше десяти. Их следует рассматривать лишь как прототипы будущих квантовых компьютеров, полезные для отработки принципов квантовых вычислений и проверки квантовых алгоритмов.
Использование для модельной реализации квантовых компьютеров в качестве кубитов уровней энергии ионов, захваченных ионными ловушками, создаваемыми в вакууме определенной конфигурацией электрического поля в условиях лазерного охлаждения их до микрокельвиновых температур.
Взаимодействие между заряженными ионами в одномерной цепочке этих ловушек осуществляется посредством возбуждения их коллективного движения, а индивидуальное управление ими с помощью лазеров инфракрасного диапазона. Первый прототип квантового компьютера на этих принципах был предложен австрийскими физиками И. Цираком и П. Цоллером в 1995 году. В настоящее время интенсивные экспериментальные работы ведутся в National Institute of Standards and Technology в США. Преимущество такого подхода состоит в сравнительно простом индивидуальном управлении отдельными кубитами. Основными недостатками этого типа квантовых компьютеров являются необходимость создания сверхнизких температур, обеспечение устойчивости состояний ионов в цепочке и ограниченность возможного числа кубитов значением .
Заключение

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

Бетеров И.И. Квантовые компьютеры на «Холодных атомах» // Наука из первых рук. 2014. №3-4 (57-58).
Валиев К.А. Кокин А.А. Квантовые компьютеры: надежды и реальность. — Ижевск: «Регулярная и хаотическая динамика», 2001.
Вахний Т.В., Гуц А.К. Физические основы и проблемы технической реализации квантового компьютера // МСиМ. 2011. №1 (22). С.38-47.
Манин Ю.И. Вычислимое и невычислимое. — М.: «Советское Радио», 1980.Риффель Э. Полак В. Основы квантовых вычислений. Научный журнал «Квантовый компьютер и квантовые вычисления» №1. – 2000.
Соловьев В.М. Квантовые компьютеры и квантовые алгоритмы часть 2. Квантовые алгоритмы // Изв. Сарат. ун-та Нов. сер. Сер. Математика. Механика. Информатика; 2016. №1. с.104-112.
Соловьев В.М. Квантовые компьютеры и квантовые алгоритмы. Часть 1. Квантовые компьютеры // Изв. Сарат. ун-та Нов. сер. Сер. Математика. Механика. Информатика; 2015. №4. С.45-53.
Фейнман Р. Квантомеханические компьютеры. Сборник «Квантовый компьютер и квантовые вычисления» Выпуск 2. — Ижевск: «Регулярная и хаотическая динамика», 1999.
Фейнман Р. Моделирование физики на компьютерах. Сборник «Квантовый компьютер и квантовые вычисления» Выпуск 2. — Ижевск: «Регулярная и хаотическая динамика», 1999.