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

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

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

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

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

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

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

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

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

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

Год без лета Год без лета

Извержение вулкана Тамбора в 1815 году стало самым мощным в истории человечества

Вокруг света
Как вор Стефан Брайтвизер обокрал мировые музеи на $2 млрд и стал любимцем публики Как вор Стефан Брайтвизер обокрал мировые музеи на $2 млрд и стал любимцем публики

Как вор Стефан Братвизер стал героем книги журналиста Майкла Финкеля

Forbes
Дальше ехать некуда Дальше ехать некуда

На противоположной стороне планеты живут 45 человек и птица уэка

Вокруг света
Намагниченный взгляд Намагниченный взгляд

«Куда бегут собаки»: ошибки в электросхематической картине мира

Weekend
Вопрос / ответ Вопрос / ответ

Что ели русские крестьяне, кто изобрел алфавит и другие вопросы и ответы

Вокруг света
Почти убивший жизнь: благодаря или вопреки кислороду развились древнейшие животные Почти убивший жизнь: благодаря или вопреки кислороду развились древнейшие животные

Когда-то кислород убил почти все живое на планете

Forbes
Могила неизвестного Павлика Могила неизвестного Павлика

История Павлика Морозова

Дилетант
Как называют полицейских в разных странах и что это значит Как называют полицейских в разных странах и что это значит

Изучаем жаргонные названия полицейских в разных странах

Maxim
Ирина Хакамада: «Полезно нырнуть на самую глубину отчаяния» Ирина Хакамада: «Полезно нырнуть на самую глубину отчаяния»

Хакамада меняется в каждом отрезке времени. Сейчас у нее очень непростой период

Psychologies
История одной песни: «Barbie Girl», Aqua, 1997 История одной песни: «Barbie Girl», Aqua, 1997

Мифическую песню и клип, на который извели розовой краски больше, чем на Барби

Maxim
«Муж на первом месте»: Михаил Галустян объяснил, почему запретил работать русской жене «Муж на первом месте»: Михаил Галустян объяснил, почему запретил работать русской жене

Михаил Галустян объяснил, почему его супруга не должна работать

VOICE
Василий Ливанов: «Если бы отец увидел этого русского, он был бы счастлив», — сказала дочь Конан Дойля, посмотрев моего Шерлока Холмса Василий Ливанов: «Если бы отец увидел этого русского, он был бы счастлив», — сказала дочь Конан Дойля, посмотрев моего Шерлока Холмса

Камбербэтч и я — нормальные Холмсы. Но лучший Шерлок Холмс в истории — русский

Коллекция. Караван историй
С миру по нитке: как топ-спортсменам приходится просить на Олимпиаду деньги у фанатов С миру по нитке: как топ-спортсменам приходится просить на Олимпиаду деньги у фанатов

Вспоминаем истории, когда на Олимпиаду спортсменам собирали всем миром

Forbes
DRACO в космосе: зачем в NASA создают ядерный двигатель DRACO в космосе: зачем в NASA создают ядерный двигатель

Полмиллиарда долларов на создание космического корабля с ядерным двигателем

Forbes
Круглые, миндаль или щелки: как подобрать эффектный макияж по форме глаз — лайфхаки от эксперта Круглые, миндаль или щелки: как подобрать эффектный макияж по форме глаз — лайфхаки от эксперта

Форма глаз — аспект, на который стоит обращать внимание при выборе макияжа

VOICE
Король рок-н-ролла и стиля: 5 знаковых образов Элвиса Пресли Король рок-н-ролла и стиля: 5 знаковых образов Элвиса Пресли

Кружева, золото, кожа и блестки — вспоминаем, что носил Элвис Пресли

Правила жизни
Почему лучше покупать кондиционер с функцией обогрева Почему лучше покупать кондиционер с функцией обогрева

Жителей квартир эта функция здорово выручит в межсезонье

CHIP
Сон для красоты: 5 секретов от голливудских сомнологов Сон для красоты: 5 секретов от голливудских сомнологов

Как отправиться в объятия Морфея с максимальной пользой для своей внешности

VOICE
Женщина стала пауэрлифтером в 71 год! Счастливая история преображения Женщина стала пауэрлифтером в 71 год! Счастливая история преображения

Она недавно овдовела, чувствовала себя «действительно не в форме»...

ТехИнсайдер
Пауки-улобориды убили жертв пищеварительным соком Пауки-улобориды убили жертв пищеварительным соком

Отсутствие ядовитых желез на головогруди не помешало охоте пауков-улоборидов

N+1
Идеальный рацион: 3 заповеди здорового питания — советы диетолога Идеальный рацион: 3 заповеди здорового питания — советы диетолога

Как превратить диету в здоровый и полезный рацион? Рассказывает диетолог

Psychologies
Инженеры сделали трехколесный трехсредный трикоптер Инженеры сделали трехколесный трехсредный трикоптер

Трикоптер плавает со скоростью 2 м/с, а скорость на суше составляет 0,5 м/с

N+1
Волшебная нить, которую придумал дантист: удивительная история создания сахарной ваты Волшебная нить, которую придумал дантист: удивительная история создания сахарной ваты

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

ТехИнсайдер
На что похожа жизнь свободного человека и каким бывает детство в Репино На что похожа жизнь свободного человека и каким бывает детство в Репино

Сююмбике Давлет-Кильдеева — о радостях жизни на Финском заливе

РБК
Как расти в Дубае: правда и мифы о бизнесе в Эмиратах Как расти в Дубае: правда и мифы о бизнесе в Эмиратах

Какие представления о бизнесе в Дубае оказываются правдой, а какие мифом

Правила жизни
13 самых популярных вопросов про кондиционеры: проверьте свои знания 13 самых популярных вопросов про кондиционеры: проверьте свои знания

Кондиционеры: все, о чем вы не знали, у кого спросить

CHIP
Гора идолов Гора идолов

Одно из чудес России – столбы Маньпупунёр

Лиза
Самая молодая последовательница Мэнсона выходит из тюрьмы: кто такая Лесли Ван Хутен Самая молодая последовательница Мэнсона выходит из тюрьмы: кто такая Лесли Ван Хутен

Рассказываем историю Ван Хутен, Мэнсона и коммуны «Семья»

Forbes
Дипфейки, репетиторы и запрещенные слова: как Китай планирует регулировать ИИ Дипфейки, репетиторы и запрещенные слова: как Китай планирует регулировать ИИ

Китай одним из первых вводит ограничения для развития ИИ

Forbes
В ранней Вселенной наблюдаемое время протекает в 5 раз медленнее В ранней Вселенной наблюдаемое время протекает в 5 раз медленнее

Астрономы впервые наблюдали эффект, предсказанный Эйнштейном более века назад

ТехИнсайдер
Открыть в приложении