Миф «перебирает всё сразу»
Урок 10 из 23 курса «Квантум: курс с нуля». Бесплатно, с анимациями и тестом.
Миф, который повторяют даже СМИ
Почти в каждой статье пишут: «Квантовый компьютер перебирает все варианты одновременно, поэтому он в миллиарды раз быстрее». Звучит логично после урока про суперпозицию, но это неправда. Если бы всё было так просто, квантовый компьютер мгновенно решал бы любую задачу. На деле он умеет хитро гасить неправильные ответы, и только для задач с особой математической структурой.
Почему «всё сразу» — ловушка
Физик Скотт Ааронсон много лет объясняет это так. Да, можно создать суперпозицию всех вариантов. Но если сразу её измерить, получишь один случайный вариант. А случайный вариант ты мог проверить и на обычном ноутбуке. Значит, нужен трюк: так устроить интерференцию, чтобы правильный ответ усилился, а остальные погасли. В 2016 году Ааронсон вместе с автором комиксов Заком Вейнерсмитом нарисовал об этом комикс SMBC «The Talk», его до сих пор кидают друг другу физики.
Гровер: честное ускорение
В 1996 году Лов Гровер придумал квантовый поиск. Представь неотсортированную базу на миллион записей, нужная одна. Обычный компьютер в худшем случае проверит все миллион, в среднем полмиллиона. Алгоритму Гровера хватит примерно 800 шагов. Это ускорение «корень из N»: в базе в сто раз больше шагов станет всего в десять раз больше. Сильно, но не мгновенно, и ни о каком «всё сразу» речи нет. Подробно разберём его в уровне про алгоритмы.
Где выигрыш огромный, а где нулевой
Экспоненциальный выигрыш, когда задача на годы превращается в задачу на часы, известен для узкого круга задач. Главные: разложение больших чисел на множители, на этом держится часть интернет-шифрования, и моделирование молекул и материалов. Умеренный выигрыш есть в поиске и части задач оптимизации. А для игр, видео, соцсетей и таблиц пользы нет: обычный чип делает это быстрее и дешевле. Нет и доказательств, что квантовый компьютер быстро решит любую сложную задачу.
Не замена, а ускоритель
Квантовый компьютер не заменит ноутбук и не появится в смартфоне. Правильнее думать о нём как о видеокарте: процессор делает всю обычную работу, видеокарта берёт графику и нейросети. Так и квантовый процессор, его называют QPU, получает от обычного компьютера только узкую подзадачу, например расчёт энергии молекулы, и возвращает ответ. Крупные игроки уже ставят QPU рядом с суперкомпьютерами и строят гибридные схемы.
Как не вестись на заголовки
В 2019 году Google заявила: её чип Sycamore за 200 секунд решил задачу, на которую суперкомпьютеру нужно 10 000 лет. IBM почти сразу ответила, что хватит примерно 2,5 дня, а в 2022 году китайские учёные решили ту же задачу примерно за 15 часов на 512 видеокартах. Задача при этом была специально придуманной и пользы не несла. Прежде чем восхищаться новостью, пройди пять вопросов чек-листа. Пять «да» встречаются редко, и это нормально: наука идёт шагами.
Проверь себя
- Что не так в заголовке «квантовый компьютер проверяет все пароли сразу»?
Правильный ответ: Измерение даёт один ответ; для перебора есть только ускорение «корень из N». «Всё сразу» — миф. Для подбора пароля работает Гровер, а он даёт ускорение «корень из N», не мгновенный взлом. - Стартап обещает «квантовый ускоритель для Excel». Как оценишь?
Правильный ответ: Скептически: для таблиц квантового выигрыша нет. Обычные вычисления в таблицах ноутбук делает быстрее и дешевле. Квантовый выигрыш есть только для узких задач. - Какой вопрос из чек-листа первым разоблачил бы рекорд Sycamore 2019?
Правильный ответ: Эта задача кому-то нужна?. Задача была придумана специально для демонстрации и практической пользы не имела. Плюс обычные методы быстро сократили отрыв.
← Интерференция: главный трюк Алгоритм Гровера: квантовый поиск →