Соглашение | Публикация статей

Шторы - calon.by

Предпосылки создания квантовых компьютеров
Категория: Статьи

Уже сейчас существует множество систем, в работе которых кванто¬вые эффекты играют существен¬ную роль. Одним из наиболее из¬вестных примеров может служить лазер: поле его излучения поро¬ждается квантово-механическими событиями - спонтанным и ин¬дуцированным излучением света. Другим важным примером таких систем являются современные микросхемы - непрерывное ужесточение проектных норм приводит к тому, что квантовые эффекты начинают играть в их поведении существенную роль. В диодах Ганна возникают осцил¬ляции электронных токов, в полу¬проводниках образуются слои¬стые структуры: электроны или дырки в различных запертых состояниях могут хранить информа¬цию, а один или несколько элек¬тронов могут быть заперты в так называемых квантовых ямах.
Сейчас ведутся разработки нового класса квантовых устройств - кванто¬вых компьютеров. Идея кванто¬вого компьютера возникла так.
Все началось в 1982 году, когда Фейнман написал очень интерес¬ную статью [1], в которой рас¬смотрел два вопроса. Он подошел к процессу вычисления как фи¬зик: есть чисто логические огра¬ничения на то, что можно вычис¬лить (можно придумать задачу, для которой вообще нет алгорит¬ма, можно придумать задачу, для которой любой алгоритм будет долго работать). А есть ли ограни¬чения физические? Вот есть закон сохранения энергии - вечный двигатель невозможен; а есть ли какое-нибудь физическое огра¬ничение на функционирование компьютера, которое накладыва¬ет некие запреты на реализуемость алгоритмов? И Фейнман показал, что термодинамических ограни¬чений, типа второго начала тер¬модинамики, нет. Если мы будем уменьшать потери энергии, шумы, то мы можем сделать сколь угод¬но длинные вычисления со сколь угодно малыми затратами энер¬гии. Это означает, что вычисления можно сделать обратимым образом - потому что в необратимых про¬цессах энтропия возрастает. Соб¬ственно, Фейнмана это и заинте¬ресовало: ведь реальное вычис¬ление на реальном компьютере необратимо. И полученный им результат состоит в том, что мож¬но так переделать любое вычис¬ление - без особой потери эф¬фективности, - чтобы оно стало обратимым. Те вычисления, кото¬рые делаются «просто так», ко¬нечно, необратимы, но «рост нео¬братимости» пренебрежимо мал по сравнению, скажем, с шумами в современном компьютере. То есть необратимость - это тонкий эффект; тут вопрос не практичес¬кий а принципиальный: если представить себе, что технология дойдет до такого уровня, что этот эффект станет существенным, то можно так перестроить вычисле¬ния, чтобы добиться обратимости.
И в этой же работе Фейнман об¬ратил внимание на то, что если у нас имеется устройство квантовое, то есть подчиняющееся законам кван¬товой механики, то его вычисли¬тельные возможности совершенно не обязательно должны совпадать с возможностями обычного устрой¬ства. Возникают некоторые допол¬нительные возможности. Но пока непонятно, позволяют они полу¬чить какой-то выигрыш или нет. Фактически, он и поставил своей статьей такой вопрос.
Кстати, Ю.И. Манин в конце семидесятых годов написал две популярные книжки по логике - «Вычислимое и невычислимое» и «Доказуемое и недоказуемое», и в одной из них есть сюжет про кван¬товые автоматы, где он говорит о некоторых кардинальных отличи¬ях этих автоматов от классических [2].
В середине восьмидесятых годов появились работы Дойча (D. Deutsch), Бернстайна и Вазирани (Е. Bernstein, U. Vazirani), Яo (A. Уао). В них были построены формальные модели квантового компьютера - напри¬мер, квантовая машина Тьюринга [3-6].
Следующий этап - статья Шора (Р.W. Shor) 1994 года [7], вызвавшая лавинообразный рост числа публикаций о квантовых вы¬числениях. Шор построил кван¬товый (то есть реализуемый на квантовом компьютере) алгоритм факторизации (разложения це¬лых чисел на множители - ис¬пользуется в том числе для вскры¬тия зашифрованных сообщений). Все известные алгоритмы для обычного компьютера - экспо¬ненциальные (время их работы растет как экспонента от числа зна¬ков в записи факторизуемого чис¬ла). Факторизация 129-разряд¬ного числа потребовала 500 MIPS-лет, или восемь месяцев непре¬рывной работы системы из 1600 рабочих станций, объединенных через Интернет. А при числе раз¬рядов порядка 300 это время су¬щественно превзойдет возраст Вселенной - даже если работать одновременно на всех существующих в мире машинах. Считается (хотя это и не доказано!), что бы¬строго алгоритма решения этой задачи не существует. Более того, гарантией надежности большин¬ства существующих шифров яв¬ляется именно сложность реше¬ния задачи факторизации или од¬ной из родственных ей теорети¬ко-числовых задач, например - дискретного логарифма. И вдруг выясняется, что на квантовом ком¬пьютере эта задача имеет всего лишь кубическую сложность! Пе¬ред квантовым компьютером клас¬сические банковские, военные и другие шифры мгновенно теряют всякую ценность. Короче говоря, работа Шора показала, что вся эта изысканная академическая дея¬тельность непосредственно каса¬ется такой первобытной стихии, как деньги. После этого и началась настоящая популярность...
Впрочем, выясняется, что не толь¬ко классическая, но и квантовая криптография (наука о шифрова¬нии сообщений) часто не способна противостоять квантовой криптоаналитике (науке о расшифровке). Некоторые важные криптографи¬ческие протоколы, такие как «под¬брасывание монеты по телефону», рушатся при переходе к квантовым вычислениям. Точнее, гарантией их надежности является отныне не сложность тех или иных алгорит¬мов, а сложность задачи создания квантового компьютера.
Таким образом возникает новая отрасль вычислений – квантовые вычисления. Квантовые вычисления (КВ) - это, как можно догадаться, вычисле¬ния на квантовом компьютере. Квантовых компьютеров на свете пока нет. Более того, до сих пор неясно, когда появятся практиче¬ски полезные конструкции и поя¬вятся ли вообще. Тем не менее, квантовые вычисления - пред¬мет, чрезвычайно модный сейчас в математике и физике, как теоре¬тической, так и эксперименталь¬ной, и занимается им довольно много людей. Судя по всему, именно инте¬рес стимулировал первопроход¬цев - Ричарда Фейнмана, напи¬савшего пионерскую работу, в ко¬торой ставился вопрос о вычис¬лительных возможностях уст¬ройств на квантовых элементах; Дэвида Дойча, формализовавше¬го этот вопрос в рамках современ¬ной теории вычислений; и Питера Шора, придумавшего первый не¬тривиальный квантовый алгоритм.


Статьи по теме:

Критерий пользователя ЭС
Нарушение правил эксплуатации ЭВМ, системы ЭВМ или их сети
Основы работы в среде Microsoft Windows XP
SLOT MASK
Сигналы в системе UNIX
Как Выбрать Принтер?
Защита памяти в ЕС ЭВМ
Системные и локальные шины
Глобальная настройка параметров печати
Робот Tartalo Стучится В Вашу Дверь
Общая характеристика преступлений в сфере технологий
Конверт
Разработка Баз Данных На Msde 2000, Работа С Бесплатной Базой Данных Mssql
CRT мониторы
TCO '95
Компьютерные Технологии И Генеалогия
Классификация прикладных систем и классификация кабельных систем
Основы Работы С Virtualdub
Операционные системы которые могут управлять CompactPCI- компьютерами
Программные оболочки MS DOS, Norton Commander
Охранно-пожарные системы фирмы Satel теперь можно контролировать по телефону или Ethernet
Электронные вычислительные машины (ЭВМ)
Определение экспертных систем
СТАДИИ СОЗДАНИЯ САПР
Классификация ЭВМ
Видеопамять
LCD мониторы
Средство разработки приложений JAM (JYACC's Application Manager)
О Windows Vista
Общая структура СКС
Мой Выбор Система Monitor Crm Для Автоматизации Отдела Продаж
Базовая система классов Java
История открытия и развитие метода компьютерной томографии
Глобальный уровень
Самая популярная операционная система сегодня для CompactPCI систем
Трассировка процессов в UNIX
Установление лиц: совершивших неправомерный доступ к компьютерной информации
Анализ содержимого CMOS-памяти
Уголовно-правовой анализ ст? 273 гл? 28 УК РФ "Создание: распространение и использование вредоносных программ для ЭВМ"
Google о вредоносных программах Интернета
ВЫБОРКА ДАННЫХ
История развития компьютера
Коммутаторы NetGear
Расположение и размер корневого каталога
Бесплатный Интернет Или Как Стать Хакером
Стримеры
Элементарная теория процесса обучения нейросетей
Создание, использование и распространение вредоносных программ для ЭВМ (ст. 273 УК)
Правовые аспекты
Прокси-Сервер - Это Действенный Способ Защиты Информации, А Также Преграда Для Атак Хакеров
Прослушка И Антижучки - Гонка Технологий
Жадный шкаф создателей Spyware в тесте!!
HotMail своими руками, или Что может PH
Интерфейс, селекторный и мультиплексный каналы
Информационные технологии в управлении банком