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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 24.12.2012
Размер файла 213,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

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

Глава 1. Квантовые компьютеры

1.1 Квантовые и классические приборы

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

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

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

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

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

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

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

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

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

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

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

1.2 Алгоритмы: классы их сложности

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

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

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

В 1994 г. Шор построил алгоритм решения этой задачи на квантовом компьютере, который оказался полиномиальной сложности: необходимое число операций , где e - вероятность ошибочного результата вычислений. Результат Шора был сенсационным. Он опровергал так называемый тезис (эмпирический закон) Чёрча-Тьюринга: все компьютеры эквивалентны в том смысле, что переход от одного компьютера к другому не изменяет класса сложности задачи. Тезис был сформулирован для множества классических компьютеров. Тезис нарушается, если множество включает квантовые компьютеры.

Результат не оказался неожиданным для физиков. Информация не является только математическим понятием. Она имеет физического носителя: кодируется, хранится, обрабатывается, передается, записывается, стирается путем изменения состояния носителя информации. Информация физична (information is physical). Наличие глубокой связи между физикой и информацией обнаруживается при сопоставлении термодинамической энтропии в физике и информационной энтропии Шеннона в теории информации: они совпадают с точностью до постоянного множителя.

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

Глава 2. Квантовая информация в квантовой системе

2.1 Определение квантовой информации

Рассмотрим вектор состояния кубита

где , и ,

и определим, сколько информации содержится в таком состоянии.

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

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

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

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

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

2.2 Реализация квантового алгоритма

правление компьютером с n-кубитами реализуется преобразованием:

где и - векторы с компонентами. Очевидно что уже для n=3 вычисление даже на самом производительном компьютере станет проблемой. Еще сложнее физическая реализация

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

(1.1)

Матрица второго порядка преобразует вектор в состояние одного кубита следующим образом:

Таким образом, имеем, что каждая матрица из(1.1) описывает операцию на отдельном кубите. Матрица преобразует векторы пар кубитов:

(1.2)

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

Глава 3. Универсальные наборы элементарных операций

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

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

Среди двухкубитовых операций выделяют операцию «контролируемого НЕ» (Controlled NOT - CNOT). Пусть контролирующий кубит первый, а контролируемый - второй. Тогда операция CNOT характеризуется таблицей входных и выходных состояний:

Таблица 1

Входное состояние

Выходное состояние

Из таблицы видно, что второй кубит инвертируется:

Рис. 1 - Схема двухкубитовой операции CNOT

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

То с помощью таблицы операций легко вычислить

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

Тогда операция взаимодействия двух кубитов примет вид:

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

Фазового вентиля , и двухкубитового вентиля CNOT.

Физическая реализация квантовой операции всегда сопровождается некоторой погрешностью исполнения е. В связи с этим теория квантовой информации строится, как теория аппроксимаций.

Ошибка определяется как при выполнении операций:

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

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

Введем переменные .

Операторы имеют вид:

Очевидно, что

На сфере блоха значения a и b одного кубита будет иметь вид

Далее получим для оператора вращения матрицы Паули:

Покажем, что с точностью до постоянной :

Покажем, что с точностью до постоянной

Покажем, что с точностью до постоянной

Последовательное преобразование HTH и T будут представлять собой вращение сферы блоха на угол вокруг оси Ox, и вокруг оси Oz:

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

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

Теперь докажем, что именно с погрешностью

(2.1)

Для углов покажем, что

Так же нам известно, что возможно такое вращение вокруг вектора

Отсюда и следует, что

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

Согласно теореме Соловей-Китаева, чтобы достичь погрешности необходимо совершить операций.

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

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

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

квантовый информация квухкубитовый алгоритм

1. Валиев К.А. Квантовые компьютеры и квантовые вычисления. 2005. Стр. 6-15.

2. Nielsen M.A., Chuang I.L. Quantum computation and quantum information. Cambridge University Press 2000. Стр. 176-197.

3. Богданов Ю.И. Физико-статистические основы квантовой информатики. Учебное пособие. М.: МИЭТ, 2010 стр. 72-79.

Размещено на Allbest.ru


Подобные документы

  • Физическая реализация квантового компьютера. Вычислимые функции и разрешимые предикаты. Вероятностные алгоритмы, проверка простоты числа. Соотношение между классическим и квантовым вычислением. Базисы для квантовых схем. Универсальная квантовая схема.

    курсовая работа [3,8 M], добавлен 05.04.2013

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

    реферат [241,0 K], добавлен 07.05.2009

  • Сущность, понятие и назначение квантового комп’ютера; его использование для вычисления процессов квантовой природы. Физические системы, реализующие кубиты. Упрощённая схема вычисления на квантовом компьютере. Тезис Черча-Тьюринга. Алгоритм Deutsch-Josza.

    реферат [122,6 K], добавлен 10.11.2014

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

    курсовая работа [129,6 K], добавлен 17.02.2011

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

    курсовая работа [31,7 K], добавлен 07.01.2011

  • Способ представления графа в информатике. Алгоритмы поиска элементарных циклов в глубину в неориентированных графах. Описание среды wxDev-C++, последовательность создания проекта. Руководство пользователю программы поиска и вывода на экран простых циклов.

    курсовая работа [783,2 K], добавлен 18.02.2013

  • Процессор — транзисторная микросхема, главный вычислительный и управляющий элемент компьютера. Одноядерные и двуядерные процессоры; программная и аппаратная виртуализация, ее преимущества. Новые технологии: оптические, квантовые, молекулярные компьютеры.

    реферат [612,5 K], добавлен 28.02.2011

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

    реферат [1,8 M], добавлен 26.05.2012

  • Обзор алгоритмов решения задачи: точные методы, генетический и жадный алгоритмы. Характеристика жадного алгоритма: его описание, анализ точности приближения, вычислительной сложности. Программная реализация и проверка корректности и быстродействия.

    курсовая работа [228,7 K], добавлен 14.10.2017

  • Виды информации, с которыми работают современные компьютеры. Понятие "информация": в физике, в биологии, в кибернетике. Представление информации. Кодирование и каналы передачи информации. Локальные компьютерные сети. Хранение информации в файлах.

    контрольная работа [26,4 K], добавлен 13.01.2008

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.