Коллектив Авторов - Цифровой журнал «Компьютерра» № 169

• Название: Цифровой журнал «Компьютерра» № 169
• Автор: Коллектив Авторов
• Жанр: Прочая околокомпьтерная литература

ОглавлениеКолонка

Парадокс Уоллеса, или Почему мы обладаем столь крупным мозгом Автор: Дмитрий Шабанов

О пользе фиктивных кандидатов наук вкупе с докторами Автор: Василий Щепетнёв

За холмами человеческих отношений и разума: шедевр Кристиана Мунджиу Автор: Сергей Голубицкий

Самый доходный бизнес, или Кое-что о фейке Автор: Сергей Голубицкий

Эзоп и Ксанф: О том, как действительно разумные системы будут взаимодействовать со своими простодушными повелителями Автор: Михаил Ваннах

Как публиковать статьи, не прилагая к тому особых усилий Автор: Дмитрий Вибе

Ненадёжные инстинкты, или Почему среди людей встречаются плохие матери Автор: Дмитрий Шабанов

50 на 50, сверчки на своих шестках и подсказка Ильича Автор: Сергей Голубицкий

«Ждите вечно!» — маркетинговый прорыв шаньджая или китайский ответ мировым брэндам Автор: Сергей Голубицкий

IT-рынок

Две волны: Как можно, хотя бы приблизительно, разложить драматические процессы в ИТ-отрасли Автор: Михаил Ваннах

Bethesda Softworks начинает работу над новым игровым проектом. Каким — неизвестно Автор: Юрий Ильин

Промзона

Обзор наиболее интересных финалистов конкурса If Concept Design Award 2013 Автор: Николай Маслухин

Охлаждающие панели для кондиционера, позволяющие снизить энергопотребление до нуля Автор: Николай Маслухин

Посмотрите на проект ресторана с автоматической подачей блюд Автор: Николай Маслухин

Светодиодный датчик давления в шинах Автор: Николай Маслухин

4D по-сыктывкарски: специально нанятый пугальщик доведет кинозрителей до инфаркта Автор: Николай Маслухин

Mobile

Запрещённые приложения: вредит ли пользователям цензура Apple в App Store и нужно ли с ней бороться Автор: Олег Парамонов

Терралаб

Выбираем сетевой медиаплеер: платформы и возможности Автор: Олег Нечай

Технологии

Как построить свой личный ботнет и сколько это стоит Автор: Олег Нечай

Сотовая связь в условиях терактов и чрезвычайных ситуаций Автор: Андрей Васильков

Очки Google в руках простых пользователей: первые впечатления, первые вопросы, первые проблемы Автор: Евгений Золотов

Рождение и смерть мини-диска Автор: Олег Нечай

Невозможная машина, которая знает ответы наперёд: чем замечательны квантовые компьютеры Автор: Олег Парамонов

Как взломать самолёт с помощью смартфона — и почему это вообще стало возможным? Автор: Евгений Золотов

Приватность наоборот: как отдать жизнь в чужие руки Автор: Андрей Письменный

«Метро» и вода: как создавались визуальные эффекты для нового фильма-катастрофы Автор: Юрий Ильин

Сто тысяч за биткойн: какая она — справедливая цена криптовалюты? Автор: Евгений Золотов

Инновации

Дмитрий Филатов, основатель TopFace: Я за то, чтобы стартаперы не попадали в кабалу к инвесторам Автор: Елена Краузова

Дизайн в Hi-tech: «звезда» против команды Автор: Максим Каманин, основатель Displair

Антон Малышев,Lactocore: молодых ученых из России на Западе ждут сильнее, чем стартаперов Автор: Елена Краузова

Гас Робертсон, новый CEO Nginx: Мы хотим разделить наши инновации с пользователями Автор: Елена Краузова

Гид

Это приложение поможет узнать, насколько вы близки к инцесту (если вы исландец) Автор: Михаил Карпов

---

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

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

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

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

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

Квантовый компьютер позволяет факторизовать число, состоящее из N разрядов, за N2 операций. Это означает, что появление достаточно мощных квантовых компьютеров сделает непригодными для использования многие популярные криптоалгоритмы.

Другой интересный пример — алгоритм Гровера, позволяющий найти нужный элемент в неотсортированном списке из N элементов, выполнив лишь N1/2 сравнений. На обычном компьютере для решения той же задачи потребовалось бы N сравнений.

Для наглядности предположим, что в списке миллион элементов. Обычному компьютеру, чтобы отыскать один из них, необходимо выполнить миллион сравнений. Квантовый компьютер, использующий алгоритм Гровера, обойдётся тысячью. Это не экспоненциальное ускорение, как в случае алгоритма Шора, но прибавка всё равно ощутима.

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

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

Слово «компьютер» обманчиво. Капризные и дорогостоящие квантовые установки, которые строят в лабораториях, не имеют с компьютерами ничего общего. Это не программируемые вычислительные машины. Слово «машина» едва ли подходит для их обозначения — по крайней мере, на этой стадии развития.

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

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

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

Ренегаты и шарлатаны

В 2007 году канадский стартап D-Wave объявил о намерении выпустить первый коммерческий квантовый компьютер. Намерение подкрепили демонстрацией машины, которая, по уверениям разработчиков, насчитывала шестнадцать кубит.

На глазах у зрителей она решила головоломку судоку, вычислила идеальную комбинацию гостей на гипотетической свадьбе и обработала SQL-запрос в специальной версии MySQL. С этими задачами прекрасно справился бы и обычный компьютер, но презентация и не должна была потрясать воображение.

Воображение потрясало другое: наполеоновские планы D-Wave. К концу года компания намеревалась довести число кубит до 32, а к середине 2008 года впустить квантовый компьютер с 1024 кубитами.

Обещания D-Wave отличались от суровой реальности, хорошо знакомой всем, кто занимался исследованиями в области квантовых вычислений, как небо и земля. Скачок таких масштабов был бы чудом, а чудес, как известно, не бывает.

Скептицизм специалистов столкнулся с полным нежеланием D-Wave рассказывать, каким образом были достигнуты такие успехи. Напрашивается вопрос: а был ли мальчик? Действительно ли устройство, которым хвасталась компания, — это квантовый компьютер? Никаких доказательств этому не было. Развеять сомнения могли бы публикации разработчиков D-Wave в академических журналах, но их не было.

К D-Wave приклеился ярлык «шарлатаны», но компания продолжала работать. Чересчур оптимистичный план пришлось скорректировать. Машина, использующая, если верить D-Wave, 128 кубитов, появилась не в 2008, а лишь в 2011 году. Несколько месяцев назад разрядность довели до 512.

В 2009 году D-Wave и Google провели совместную презентацию. Хартмут Невен, видный специалист в области распознавания лиц, работающий в Google, рассказал об испытании самообучающегося алгоритма для выделения автомобилей на снимках Street View. По утверждению Невена, квантовое устройство D-Wave справилось с задачей лучше, чем традиционные компьютеры в дата-центрах Google.

Такое развитие событий немного озадачило скептиков. Результаты, которые обнародовал Невен, не доказывали, что в D-Wave построили настоящий квантовый компьютер, однако отмести их тоже было нельзя. Если D-Wave — это мошенники, то как же им удалось переманить на свою сторону совсем не глупых людей из Google?

В 2011 году корпорация Lockheed Martin, гигант военно-промышленного комплекса США, объявила о приобретении 128-кубитной машины D-Wave за 10 миллионов долларов. Можно было бы предположить, что покупка совершена из любопытства, однако история на этом не закончилась.

В марте 2013 года в Lockheed Martin решили купить следующую модель квантового компьютера D-Wave. Первая покупка не просто удовлетворила интерес компании — она доказала свою полезность. Получается, в обещаниях D-Wave всё же есть доля правды?

Правда D-Wave

В D-Wave в итоге пошли на попятную и опубликовали пару научных работ о своей машине. Попутно стало ясно, что это, во-первых, не квантовый компьютер в самом распространённом понимании этого слова, а во-вторых, кубиты, о которых идёт речь в рекламе компании, строго говоря, не вполне кубиты.

В основе машины D-Wave лежит охлаждённая до -273 градусов по Цельсию микросхема с решёткой, построенной из сверхпроводящих квантовых интерферометров. Именно их в компании называют кубитами. Значение кубитов D-Wave, как и значение кубитов в настоящем квантовом компьютере, может быть неопределённым, однако они не связаны между собой с помощью квантовой запутанности.

Машина D-Wave не годится для алгоритмов, которые используют квантовые вентили. Ни алгоритм Шора, ни алгоритм Гровера на ней не пойдут. Вместо этого она использует для работы совершенно иной принцип — так называемые адиабатические квантовые вычисления. Это значительно ограничивает её возможности, но позволяет не беспокоиться о декогеренции и других проблемах, сопровождающих обычные квантовые вычислители.

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

Эта оптимизационная задача имеет на удивление много реальных применений. В D-Wave использовали своё устройство для фолдинга белков, в Google учили его распознавать образы, а в Lockheed Martin приспособили машину для верификации критически важного программного обеспечения.