Алгоритм усложнит экзаменационные задачи для квантовых компьютеров

Алгоритм усложнит экзаменационные задачи для квантовых компьютеров

Физики из Мадридского университета Комплутенсе и Университета Южной Калифорнии разработали алгоритм, способный значительно усложнять задачи, необходимые для тестирования производительности квантовых вычислителей. Благодаря подобным системам ученые смогут количественно оценить преимущество квантовых компьютеров над классическими. По словам авторов, случайно сгенерированные задачи удалось усложнить более чем в сто раз. Исследование опубликовано в журнале Physical Review A (препринт), кратко о нем сообщает Physics.

Одна из причин интереса к квантовым компьютерам — возможность реализовать принципиально новые алгоритмы, недоступные для классических вычислителей. Это возможно благодаря квантовой природе битов этих компьютеров. Они могут находиться в суперпозиции состояний «ноль» и «единица», которые будут «выпадать» с некоторой вероятностью при измерениях. Теоретики предсказывают, что квантовые алгоритмы в ряде случаев оказываются эффективнее классических. Например, алгоритм Шора гораздо быстрее раскладывает число на простые множители, нежели существующие классические алгоритмы.

Еще один класс задач, легко поддающихся решению квантовыми алгоритмами, — задачи Изинга. В этих задачах рассматривается набор из нескольких частиц, каждая из которых может быть в состоянии «+1» или «-1». Энергия каждой частицы зависит от состояния других частиц, с которыми она связана. То, насколько сильны эти связи записано в «условии» задачи. В зависимости от того, положительна или отрицательна сила связи, частицам выгодно иметь одинаковые или разные знаки.

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

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

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

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

Владимир Королёв

N+1

Похожие новости:
Алгоритм определит правдивость твитов
Twitter остается интересной средой для практического применения математики. Не так давно мир увидел алгоритм, способный предсказывать тренды в этой соцсети. А на днях ученые представили программу, определяющую, содержится ли в твите достоверная информация. Необычный алгоритм использует для определения правдивости сообщения различные ..
2012-12-18 1124 0 Интернет, IT
0
Google и MIT разработали алгоритм удаления отражений при съемке через стекло
Компания Google и Массачусетский технологический институт (MIT) совместно разработали алгоритм, который позволяет удалять с фотографий отражение, возникающее при съемке через стекло. О задачах, поставленных перед командой исследователей, и принципах действия предложенной ими методики рассказывается в видеоролике, опубликованном ..
2015-08-13 2040 0 Интернет, IT
0
Для взлома шифров АНБ потребовался квантовый компьютер
Агентство национальной безопасности (АНБ) США пытается создать собственный квантовый компьютер, который смог бы взломать практически любую систему шифрования. Об этом пишет в пятницу, 3 января, газета The Washington Post со ссылкой на документы, обнародованные бывшим сотрудником ведомства Эдвардом ..
2014-01-03 1294 0 Интернет, IT
1
Google улучшает поиск и вводит новый алгоритм Hummingbi
В рамках празднования 15-летия Google компания объявила о переходе самого главного своего продукта — поисковика — на новый алгоритм под названием Hummingbird. На самом деле он начал действовать еще месяц назад, но рассказать о некоторых его достоинствах руководство корпорации решило ..
2013-10-1 1193 0 Интернет, IT
1
Алгоритм Google обыграл в го чемпиона Европы
Программа AlphaGo, разработанная компанией DeepMind (одна из дочерних компаний Google), выиграла у профессионального игрока пять игр подряд. Об этом сообщает Nature.Программа выиграла пять игр из пяти по турнирным правилам против Фаня Хуэя, чемпиона Европы по го. Кроме того, программа ..
2016-01-29 1435 0 Интернет, IT
0
Математики превратили геном в гомоморфную криптосистему
Криптологи компании Microsoft разработали алгоритм шифрования последовательностей ДНК, который позволяет анализировать их традиционными биоинформатическими методами и при этом не дает скомпрометировать обладателя генома. Технология была представлена на конференции Американского научного общества AAAS, кратко о ней пишет Science. Технология ..
2014-02-17 958 0 Интернет, IT
0
Панда нового поколения скоро увидит мир
Согласно данным, полученным с конференции SMS West, которая недавно проходила в Калифорнии, команда разработчиков интернет-корпорации Google занимается разработкой нового алгоритма, носящего название Панда «нового поколения». По словам Мэтта Каттса: «Этот алгоритм станет для представителей малого ..
2014-03-17 1054 0 Интернет, IT
0
Создан эффективный алгоритм распознавания пешеходов
Исследователи из Калифорнийского университета в Сан-Диего разработали алгоритм распознавания пешеходов в режиме реального времени, который в качестве исходных данных использует только изображение с камеры. Доклад был представлен на конференции ICCV 2015, которая прошла в декабре в Сантьяго. С кратким описанием ..
2016-02-10 1165 0 Интернет, IT
0
Разработчики создали игровой университет для искусственного интеллекта
Некоммерческая компания OpenAI выпустила платформу Universe, которая позволит системам искусственного интеллекта обучаться, играя в компьютерные игры и получая награду за успешно пройденные испытания. Как сообщает MIT Technology Review, в Universe собраны более тысячи «виртуальных миров». Новая ..
2016-12-08 3320 0 Интернет, IT
0
Google внедрила новый поисковый алгоритм
Компания Google приурочила к своему 15-летию объявление о запуске нового алгоритма поиска. Система, получившая кодовое имя Hummingbird ("Колибри"), работает уже как месяц. Она обрабатывает примерно 90% всех поисковых запросов. Поисковик, основанный в сентябре 1998 года, не стал вдаваться в подробности о том, ..
2013-09-28 1202 0 Интернет, IT
0
Создан алгоритм для наведения порядка в социальных связях
Ученые из Стенфордского университета создали алгоритм, который способен автоматически выделять в социальных связях пользователя "круги" коллег, членов семьи или знакомых. Препринт работы доступен в архиве Корнельского университета, краткое ее содержание пересказывает блог Technology Review. В основе ..
2012-11-5 1170 0 Интернет, IT
0
Алгоритм Baidu догнал людей в распознавании речи на английском и китайском
Лаборатория искусственного интеллекта (SVAIL) исследовательского подразделения китайской компании Baidu улучшила алгоритм распознавания речи под названием Deep Speech, при этом в некоторых случаях вторая версия программы распознает речь даже быстрее людей. Препринт статьи опубликован ..
2016-01-10 1274 0 Интернет, IT
0
Яндекс начал регистрацию на чемпионат по программированию Алгоритм
Российская интернет-компания "Яндекс" открыла регистрацию на международный чемпионат по спортивному программированию "Яндекс.Алгоритм", в котором могут участвовать все желающие, говорится в сообщении компании. "Яндекс.Алгоритм" — это индивидуальные соревнования, участие в которых не ограничено образованием, родом занятий и возрастом. Впервые конкурс проводился в 2011 ..
2014-04-09 1342 0 Интернет, IT
0
Искусственный интеллект научился дорисовывать изображения
Выпускники Имперского колледжа Лондона создали искусственный интеллект Magic Pony, способный анализировать и улучшать качество изображений и видео низкого разрешения из интернета. Об этом пишет MIT Technology Review.Технология использует принцип машинного обучения: разработчики загружают в искусственный интеллект ..
2016-04-16 1623 0 Интернет, IT
0
Новый голосовой поиск Google оказался в 7 раз быстрее старого
Новый голосовой алгоритм Google, работающий без подключения к интернету, в ходе испытаний оказался в 7 раз быстрее своей онлайн-версии. Об этом пишет 9to5Google.Приложение размером 20,3 мегабайта тестировалось на смартфоне Nexus 5 2014 года выпуска, оснащенном четырехъядерным процессором с частотой 2,26 ..
2016-03-15 1435 0 Интернет, IT
0