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

Наука и жизньНаука

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

Кандидат физико-математических наук Л. Федичкин (Физико-технологический институт Российской академии наук)

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

Введение, или немного о защите информации

Как вы думаете, на какую программу в мире продано наибольшее количество лицензий? Не рискну настаивать, что знаю правильный ответ, но мне точно известен один неверный: это не какая-либо из версий Microsoft Windows. Самую распространённую операционную систему опережает скромный продукт фирмы RSA Data Security, Inc. — программа, реализующая алгоритм шифрования с открытым ключом RSA, названный так в честь его авторов — американских математиков Ривеста, Шамира и Адельмана.

Дело в том, что алгоритм RSA встроен в большинство продаваемых операционных систем, а также во множество других приложений, используемых в различных устройствах — от смарт-карт до сотовых телефонов. В частности, имеется он и в Microsoft Windows, а значит, распространён заведомо шире этой популярной операционной системы. Чтобы обнаружить следы RSA, к примеру, в браузере Internet Explorer (программе для просмотра www-страниц в сети Интернет), достаточно открыть меню «Справка» (Help), войти в подменю «О программе» (About Internet Explorer) и просмотреть список используемых продуктов других фирм. Ещё один распространённый браузер Netscape Navigator тоже использует алгоритм RSA. Вообще, трудно найти известную фирму, работающую в области высоких технологий, которая не купила бы лицензию на эту программу. На сегодняшний день фирма RSA Data Security, Inc. продала уже более 450 миллионов (!) лицензий.

Почему же алгоритм RSA оказался так важен?

Представьте, что вам необходимо быстро обменяться сообщением с человеком, находящимся далеко. Благодаря развитию Интернета такой обмен стал доступен сегодня большинству людей — надо только иметь компьютер с модемом или сетевой картой. Естественно, что, обмениваясь информацией по сети, вы бы хотели сохранить свои сообщения втайне от посторонних. Однако полностью защитить протяжённую линию связи от прослушивания невозможно. Значит, при посылке сообщений их необходимо зашифровать, а при получении — расшифровать. Но как вам и вашему собеседнику договориться о том, каким ключом вы будете пользоваться? Если послать ключ к шифру по той же линии, то подслушивающий злоумышленник легко его перехватит. Можно, конечно, передать ключ по какой-нибудь другой линии связи, например отправить его телеграммой. Но такой метод обычно неудобен и к тому же не всегда надёжен: другую линию тоже могут прослушивать. Хорошо, если вы и ваш адресат заранее знали, что будете обмениваться шифровками, и потому заблаговременно передали друг другу ключи. А как быть, например, если вы хотите послать конфиденциальное коммерческое предложение возможному деловому партнёру или купить по кредитной карточке понравившийся товар в новом Интернет-магазине?

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

Как раз такая криптографическая схема и применяется в алгоритме RSA — самом распространённом методе шифрования с открытым ключом. Причём для создания пары открытого и закрытого ключей используется следующая важная гипотеза. Если имеются два больших (требующих более сотни десятичных цифр для своей записи) простых числа M и K, то найти их произведение N = MK не составит большого труда (для этого даже не обязательно иметь компьютер: достаточно аккуратный и терпеливый человек сможет перемножить такие числа с помощью ручки и бумаги). А вот решить обратную задачу, то есть, зная большое число N, разложить его на простые множители M и K (так называемая задача факторизации) — практически невозможно! Именно с этой проблемой столкнётся злоумышленник, решивший «взломать» алгоритм RSA и прочитать зашифрованную с его помощью информацию: чтобы узнать закрытый ключ, зная открытый, придётся вычислить M или K.

Для проверки справедливости гипотезы о практической сложности разложения на множители больших чисел проводились и до сих пор ещё проводятся специальные конкурсы. Рекордом считается разложение всего лишь 155-значного (512-битного) числа. Вычисления велись параллельно на многих компьютерах в течение семи месяцев 1999 года. Если бы эта задача выполнялась на одном современном персональном компьютере, потребовалось бы примерно 35 лет машинного времени! Расчёты показывают, что с использованием даже тысячи современных рабочих станций и лучшего из известных на сегодня вычислительных алгоритмов одно 250-значное число может быть разложено на множители примерно за 800 тысяч лет, а 1000-значное — за 1025 (!) лет. (Для сравнения возраст Вселенной равен ~1010 лет.)

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

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

Как всё начиналось?

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

Американский математик и физик венгерского происхождения Иоганн фон Нейман (1903—1957), автор трудов по функциональному анализу, квантовой механике, логике, метеорологии. Внёс большой вклад в создание первых ЭВМ и разработку методов их применения. Его теория игр сыграла важную роль в экономике.

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

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Используй ложку и телефон: 20 способов доставить себе удовольствие Используй ложку и телефон: 20 способов доставить себе удовольствие

Двадцать разных способов мастурбации на любой вкус и цвет

Cosmopolitan
Тибетские выдры пристрастились к выпускаемой буддистами рыбе Тибетские выдры пристрастились к выпускаемой буддистами рыбе

Тибетские выдры явно предпочитают охотиться на чужеродные виды рыб

N+1
20 вещей, которые могут тебе пригодиться в постели 20 вещей, которые могут тебе пригодиться в постели

Объекты и явления, при помощи которых твой секс будет еще великолепнее

Maxim
«Отсюда выхода нет»: кто делает из наркоблогеров рок-звезд и почему людям интересно смотреть, как другие умирают? «Отсюда выхода нет»: кто делает из наркоблогеров рок-звезд и почему людям интересно смотреть, как другие умирают?

Кто такие наркоблогеры и насколько опасен их контент?

Psychologies
На пороге квантового превосходства На пороге квантового превосходства

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

Наука и жизнь
Сетевой маркетинг: как спортсмены NCAA зарабатывают миллионы, оставаясь любителями Сетевой маркетинг: как спортсмены NCAA зарабатывают миллионы, оставаясь любителями

Как студенты-спортсмены зарабатывают миллионы

Forbes
Семь загадок питьевого спирта Семь загадок питьевого спирта

Пьют ли где-нибудь, кроме России, этиловый спирт?

Maxim
Как преодолеть стереотипы общества и позволить себе быть просто женщиной Как преодолеть стереотипы общества и позволить себе быть просто женщиной

Как стереотипы заставляют женщину быть кем-то другим?

Psychologies
Анна Плетнева Анна Плетнева

Певица уверяет, что она заколдованная и выигрывает всегда у всех мужчин!

Playboy
Босиком по росе Босиком по росе

Бегать босиком полезно или вредно?

Здоровье
От итальянских рабочих до суперзвезд и инфлюенсеров: история белой майки От итальянских рабочих до суперзвезд и инфлюенсеров: история белой майки

Откуда вообще взялась белая майка и при чем тут алкоголики и расизм

Правила жизни
Физики нашли в замещенном апатите свинца комнатную сверхпроводимость при атмосферном давлении Физики нашли в замещенном апатите свинца комнатную сверхпроводимость при атмосферном давлении

Ученые нашли у апатита свинца сверхпроводящие свойства при комнатной температуре

N+1
Я всего лишь хотел нормального Рождества: 5 причин, почему «Крепкий орешек» — идеальный боевик Я всего лишь хотел нормального Рождества: 5 причин, почему «Крепкий орешек» — идеальный боевик

Почему мы готовы пересматривать «Крепкий орешек» из года в год?

Правила жизни
Удивят, отвратят, напугают, просветят: 7 необычных книг для интеллектуалов Удивят, отвратят, напугают, просветят: 7 необычных книг для интеллектуалов

Тру-стори о лондонском приюте, мрачный артхаус о любви и притчи из Вавилона

ТехИнсайдер
«Хаббл» увидел неравномерную потерю атмосферы горячим нептуном «Хаббл» увидел неравномерную потерю атмосферы горячим нептуном

Переменность потери нейтрального водорода атмосферой горячего нептуна

N+1
У микобактерии лепры нашли новый антиген в клеточной стенке У микобактерии лепры нашли новый антиген в клеточной стенке

Ученые обнаружили в клеточной стенке микобактерии лепры фенольный гликолипид-II

N+1
Музыкальный ритм помог детям сделать меньше грамматических ошибок Музыкальный ритм помог детям сделать меньше грамматических ошибок

Музыкальные ритмы помогли франкоговорящим детям повторить услышанные фразы

N+1
Большой Дракон: как Брюс Ли изменил голливудский экшен-фильм Большой Дракон: как Брюс Ли изменил голливудский экшен-фильм

Как Брюс Ли взбодрил и обновил голливудский менстрим

Правила жизни
Самоуверенный алгоритм: какие риски внедрения ИИ пока недооцениваются Самоуверенный алгоритм: какие риски внедрения ИИ пока недооцениваются

ИИ обладают предсказательной способностью, но не могут заглянуть на шаг вперед

Forbes
«Мы были выше бога, который сотворил нас». Отрывок из книги об Адаме и Еве «Мы были выше бога, который сотворил нас». Отрывок из книги об Адаме и Еве

«Взлет и падение Адама и Евы»: отрывок из книги Стивена Гринблатта

СНОБ
Звезда родилась: лучшие байопики о музыкантах Звезда родилась: лучшие байопики о музыкантах

Музыкальные байопики, на которые стоит потратить время

Правила жизни
«Плюшевый пузырь»: как фильм о создателе мягких игрушек критикует американскую мечту «Плюшевый пузырь»: как фильм о создателе мягких игрушек критикует американскую мечту

Разбираем драмеди «Плюшевый пузырь» — историю предпринимателя Тая Уорнера

Forbes
Через призму кино: как Алексей Ган стал одним из создателей русского конструктивизма Через призму кино: как Алексей Ган стал одним из создателей русского конструктивизма

Глава из монографии о художнике Алексее Гане

Forbes
На пьяном корабле. Кто такой Артюр Рембо На пьяном корабле. Кто такой Артюр Рембо

Как жил и писал Артюр Рембо

СНОБ
Как решить, куда двигаться дальше: 5 советов коуча — попробуйте, если вы «сканер» Как решить, куда двигаться дальше: 5 советов коуча — попробуйте, если вы «сканер»

Не можете решить, в каком направлении идти дальше, и это вызывает у вас стресс?

Psychologies
Сергей Кемпо: «Я — счастливчик!» Сергей Кемпо: «Я — счастливчик!»

«Родители для меня желали какой угодно профессии, но только не актерской»

Караван историй
История о приемных детях и важной миссии для подростка История о приемных детях и важной миссии для подростка

Как примирить подростка с присутствием в семье приемного ребенка с особенностями

СНОБ
8 идей, как повторно использовать старые контейнеры для контактных линз – всем путешественникам на заметку! 8 идей, как повторно использовать старые контейнеры для контактных линз – всем путешественникам на заметку!

Контейнеры для линз — незаменимая вещь для путешественника

ТехИнсайдер
Головная боль всех кошатников: как отучить питомца царапать мебель Головная боль всех кошатников: как отучить питомца царапать мебель

Почему кота больше привлекает не когтеточка, а ваш диван?

ТехИнсайдер
Цистит Цистит

Почему многих цистит настигает именно летом?

Здоровье
Открыть в приложении