Почему квантовый компьютер спотыкается о решётку
Алгоритм Шора съедает RSA одним ходом. Та же машина почти ничего не может сделать с сеткой точек, к которой добавили немного шума. Один ползунок показывает разницу.
Этап Шор
- 0
- 1
- 2
- 3
- 4
Нажмите на участок схемы, чтобы открыть этап.
Что на самом деле изменилось
RSA спрятал секрет в вопросе, который квантовый компьютер, как выяснилось, умеет задавать. Решётки прячут его в вопросе, который остаётся экспоненциальным для обеих машин, — а владелец короткого базиса этот вопрос просто обходит.
Что внутри
- 1 Разложение на множители перестаёт быть трудным — С математикой ничего не случилось. Просто трудность жила не в том месте.
- 2 Вместо чисел — точки — Сама решётка открыта. Точки видят все.
- 3 Сообщение — это точка, которую потом толкнули — Шум достаточно мал, чтобы его можно было снять, и достаточно велик, чтобы спрятать исходную точку.
- 4 Найти ближайшую точку — и есть вся задача — Известные квантовые алгоритмы сбивают показатель степени в этой задаче. Убрать его они не могут.
- 5 С правильным базисом это одно округление — Секрет — не решётка. Секрет — хорошее описание решётки.
Интерактивные статьи
- Как лекарство проносят через гематоэнцефалический барьер Мозг не пускает внутрь почти ни одну молекулу лекарства — и правильно делает. Один ползунок показывает приём, который сейчас пробуют в лабораториях: упаковать молекулу в пузырёк, который стенка и так умеет переносить.
- Как робот рисует карту комнаты, которую видит впервые Лидар выдаёт несколько сотен точек за оборот и ни малейшего понятия, где он находится. Один ползунок проходит путь от этого облака до плана помещения, где робот стоит в правильном месте.
- Как двое печатают в одной строке и не теряют ни одной буквы Два курсора, одна строка и никакого сервера, который держит ручку. Один ползунок разбирает слияние по индексам и собирает его заново на адресах, которые живут между буквами.
- Охлаждение здания через окно в космос Покрытие, которое под прямым солнцем остаётся холоднее окружающего воздуха и не потребляет ни ватта. Один ползунок ведёт тепло от солнца до другой стороны атмосферы.
- Как робот предсказывает следующую секунду Текстовая модель угадывает следующее слово. Модель мира угадывает следующий кадр — вместе с массой, скоростью и гравитацией. Один ползунок проходит весь цикл: от камеры до перехвата.
- Доказательство без раскрытия: пещера Али-Бабы Один ползунок ведёт по этапам, второй добавляет раунды. Посмотрите, как уверенность растёт почти до полной, а секрет так и остаётся секретом.
- Литий из рассола: пруды против прямой добычи Проведите ползунок через пять этапов и сравните два способа достать один и тот же металл из одной и той же солёной воды.
- Как работает персональная мРНК-вакцина от рака Проведите ползунок через пять этапов и посмотрите, как собственные мутации опухоли превращаются в инструкцию, по которой иммунитет учится её находить.
- Граница приложения Всё, что приходит снаружи, недоверенное. Ломайте по одному звену и смотрите, где останавливается цепочка и что при этом показывает экран.
- Как работает поиск по своим документам Подвигайте ползунки и посмотрите, как поисковый конвейер решает, что модели вообще будет видно — и что бывает, когда ей подсунули не тот кусок.
- Повтор запроса и долгий ответ Сеть рвётся посреди операции. Нажмите кнопку дважды и посмотрите, что окажется в базе — с ключом идемпотентности и без него.
- Как языковая модель пишет текст Веса заморожены, ничего не запоминается. Потяните ползунки и посмотрите, как модель раз за разом выбирает следующий кусок текста.
- Как обучается языковая модель Потяните один ползунок и посмотрите, как груда случайных чисел за тысячу шагов превращается в предсказание.
- Откуда берётся электричество Потяните один ползунок и проследите путь энергии от реки до насоса, который поднимает воду обратно наверх.