dxdt.blog: занимательный интернет-журнал

Квантовая часть алгоритма Шора, если его вообще возможно реализовать, выглядит примерно следующим образом. Первому квантовому регистру назначается состояние, представляющее собой суперпозицию всех входных числовых значений. То есть, предположим, что это 1024 “битовых разряда”, тогда получается 2^1024 различных (числовых) значений и тому подобные штуки. Однако физические детали существенно отличаются, при этом основная идея вообще не касается выбранной реализации. То есть, традиционно, в качестве примера приводят отдельные “кубиты”, как некие “конструкты”, принимающие два состояния (“спин вверх/спин вниз” или что-то похожее, это довольно сложно представить) и совместимые с представлениями о суперпозиции. В квантовой суперпозиции и состоит смысл этих конструктов, так что реализация входного регистра не важна: он является лишь входом, через который основную схему предлагается “подключить”, если хотите, к квантовой ирреальности.

Регистр можно, конечно, представлять состоящим из многих кубитов, где каждый кубит базируется на отдельной частице, но можно и считать этот регистр просто единым интерфейсом, который подтянет нужное количество состояний в область реальности, обозримую при помощи моделей физических схем. В кубитах удобнее описывать алгоритмы, поэтому их и используют в мысленных экспериментах (отсюда – модели). При этом, несмотря на оригинальную бра- и кет-нотацию, речь, концептуально, идёт об управлении потоком вероятности: “квантовая вероятность” некоторым образом перетекает из одной конфигурации в другую, при этом схлопываются те части потока, которые коммутируют (опять же, можно не задумываться над значением этого “коммутируют”; схлопываются, интерферируют и – всё; главное, чтобы обратимо). “Квантовая вероятность” – она даже больше комбинаторная, чем вероятность обычная. Это и позволяет надеяться на конкретные числовые результаты: с одной стороны, применяемые тут квантовые эффекты полагаются достаточно случайными, чтобы использовать непрерывное представление для вероятности, с другой – эти же эффекты строго разбиваются на дискретные подмножества состояний (те самые “спин вверх/спин вниз”).

Итак, в случае входного регистра для схемы алгоритма Шора, подходящий поток вероятности должен спуститься через этот регистр в ту часть, которая реализует ключевую функцию всей загадочной машинерии – дискретную экспоненту. То есть, возведение целого числа в целую (даже натуральную) степень по модулю (арифметика остатков). Этот момент в популярных изложениях почему-то не всегда упоминают, а он один из главных: требуется какая-то весьма сложная схема из экзотических объектов, которые пропускали бы входящий поток вероятности и переводили его в результат “вычисления” экспоненты, разделив поток и схлопнув часть веток таким образом, чтобы сформировался периодический результат. “Вычисление” тут должно быть в кавычках.

Если вспомнить математическую часть алгоритма, то речь про вычисление y = A^x (mod M). Обратите внимание на значение A (натуральное число), которое задаёт конкретную схему аппарата для запуска алгоритма Шора! При последовательном вычислении y = A^x (mod M), если показатель x пробегает достаточное количество значений, результат (y) начнёт повторяться, это теоретико-числовая польза от алгоритма, потому что позволяет определить, при каком x A^x == 1 (mod M) и т.д., этому как раз соответствует период данной функции, который мы хотим определить квантовой машиной. Конечно, в случае квантовой машины, никаких подобных вычислений нет: такая машина – супераналоговый прибор, возможно, что ламповый, но скорее холодный, чем тёплый: выход в квантовую ирреальность почему-то требует низких температур. В общем, не предполагается, что происходят какие-то шаги, кто-то переключает реле и сигналы, а на вход “блока функций” поступают разные “иксы”, пусть даже и параллельно. Нет, напротив, подключается несколько миллионов (предположим) загадочных “гейтов”, объединённых в схему, задающую функцию для проверяемого значения A, и всё – предполагается, что в финальном измерении через схему пройдёт поток вероятности, который преобразуется нужным способом и выльется во второй регистр.

Второй регистр тоже можно представлять некоторым единым “бассейном” для входящего потока вероятности, нужного объёма. А можно представлять набором неких кубитов, которых должно быть достаточно много, чтобы получить нужную разрешающую способность. Дело в том, что модели на бумаге можно “записывать” в “действительных числах”, однако, даже если одно действительное число в дополнение к рациональным и влезает в квантовую ирреальность, достать его оттуда полностью точно и за конечное количество измерений – не получится. Это, понятно, не мешает использованию комплексных чисел даже в прикладном квантово-механическом аппарате. Поэтому для окончательного превращения результата в целое число потребуется дополнительно место в пространстве состояний.

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

Машина так устроена, что для этого второго регистра некоторый общий “базис” превращения потока вероятности, который был порядковым или индексным, заменяется на “частотный” – то, что традиционно называется преобразованием Фурье. На графиках это эквивалентно переходу из шаблона, где горизонтальная ось соответствует “времени” (“последовательность событий/состояний”), к шаблону, где горизонтальная ось соответствует частоте (“повторяемость событий/состояний”). Это как раз и есть второй ключевой момент: превращение из индексов в частоты. После этого можно измерять состояние, чтобы получить результат: предполагается, что в выходном регистре, с высокой вероятностью, получится измеренное состояние, которое, используя модель устройства квантовой машины, можно интерпретировать как некоторое значение, кратное периоду функции (детали, связанные с тем, что там должно быть обратное значение, которое ещё не ясно как прочитать и преобразовать, опять же пропускаем). Как это выходное значение будет, так сказать, выглядеть? Например, как набор величин измерений, полученных для каких-то частиц, из которых построен выходной интерфейс. Преобразования, начиная с результатов измерений, уже будут выполняться классическими компьютерами.

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

(См. также про алгоритм Шора и Вселенную кубиками.)

Вообще, эта история с встраиваемой в посторонние сайты браузером Firefox рекламы Mozilla VPN тоже имеет отношение к стремительно наступающему Новому Средневековью. Скорее всего, в этом конкретном случае, у пользователя всё ещё имеются возможности не подключать “промо” или “отписаться” (как минимум, сообщают, что можно выключить флаг в настройках браузера – что, конечно, само по себе показательно: флаг для отключения встроенной в браузер рекламы). Важно совсем другое. Ещё некоторое время назад разработчикам браузера могло бы показаться, что задача браузера состоит в отрисовывании веб-страницы максимально близко к некоторым спецификациям (“веб-стандартам” и пр.). Идея воспользоваться статусом браузера и модифицировать визуальное оформление страницы так, чтобы закрыть его собственной рекламой, должна была бы быть отброшена. Это не отменяет богатой истории подобных подмен, начиная с массового перенаправления “несуществующих доменных имён” с использованием положения провайдера авторитативных серверов DNS и вплоть до вмешательства в HTTP-трафик на стороне провайдера доступа или даже на транзите. Наоборот, такой исторический опыт и должен бы приводить к тому, что в приличном браузере подобные практики не могут рассматриваться. Но, конечно, не в условиях Нового Средневековья.

Так, в случае браузера, типичный пользователь может подумать, что реклама встроена в сам сайт. Возможно, расчёт делался на это. Сейчас обычна ситуация, когда для того, чтобы добраться до полезного (возможно – полезного) содержания веб-страницы на новостном, например, сайте, нужно сперва закрыть три или четыре всплывающих окна под общим названием “Мы используем куки!”, а потом ещё сдвинуть/перетащить разнообразные плашки, в половину экрана, объясняющие, что этот сайт нужно поддержать, что ему нужно разрешить уведомления и отключить “блокировщик рекламы”, подписавшись на рассылку. На рубеже веков это являлось предметом шуток, сейчас – уже без шуток, поэтому обычный пользователь Firefox, предположим, привык и просто не заметит ничего необычного, как и разработчики браузера (но задача по откручиванию рекламы собственного сервиса, который нуждается в новых регистрациях, – выполнена).

Пока что с Firefox это не сработало: пользователи всё поняли правильно и даже возмутились. Не факт, что это будет иметь долгий эффект: интернеты становятся “корпоративными”, в том числе, на стороне клиента. Нужно ли ожидать рекламных пауз в ядре Linux? Риторический вопрос.

Не самым хорошим образом развивается браузер Firefox, хоть и предсказуемо, к сожалению: теперь этот браузер принялся показывать блокирующую всплывающую рекламу Mozilla VPN на произвольных веб-страницах. Надо сказать, что если сравнивать с подобным внедрением рекламы, то остаётся не так уж и много вариантов поведения браузера, которые хуже. В VPN-сервис, можно предположить, там ещё больше встроено всякой подобной нагрузки. (Дополнение. Предположим ещё, что блокирующая реклама Mozilla VPN не показывалась тем пользователям, которые уже купили Mozilla VPN. Тогда получается простая и известная схема: чтобы убрать рекламу – нужно заплатить, а иначе – будете просматривать рекламный видеоролик перед тем, как страница сайта отобразится. Забавно.)

Google пишет, что с декабря 2023 года начнут удалять google-аккаунты, в которых не было “активности” в течение двух лет. Тут главное, чтобы не оказалось так, что после удаления кто-то ещё может зарегистрировать аккаунт с таким же именем, получив, предположим, авторизацию привязанных к имени внешних (относительно Google) ресурсов, “подхватив” какие-нибудь сервисы и регистрационную информацию (да, там уже есть в описании процесса оговорки о “совершённых покупках”, что будут исключения и пр., но это ничего ещё не гарантирует). Вариант, впрочем, известный, поэтому есть шанс, что в Google об этом всё же подумали (но не факт).

За несколько лет я написал некоторое количество полезных статей об интернет-технологиях на сайт ТЦИ, вот ссылки и краткие пояснения:

Certificate Transparency в современном Интернете
Статья о Certificate Transparency (CT). Это довольно техническая статья, которая, впрочем, рассказывает не столько о методах построения CT (про это и так много написано), сколько о не самых очевидных особенностях работы данной технологии на практике: полноте логов, реальному значению технологии в случае малого количества УЦ и т.д. (Отдельно рекомендую почитать, как весьма актуальную, и в стиле “на “Хабре” такого не пишут”.)

Сертификаты удостоверяющих центров TLS
Небольшая статья о том, какие и почему встречаются сертификаты УЦ.

Доступ к скрытым TLS-сервисам: Encrypted Client Hello
Encrypted Client Hello (способ сокрытия метаинформации в TLS) с примерами и описанием принципов построения, назначения, а также перспектив.

DNS в качестве инструмента публикации вспомогательной информации
Использование DNS-записей для публикации информации о настройках и свойствах других интернет-протоколов: типы DNS-записей, примеры и др. Речь про TXT для DKIM/DMARC, про SSHFP и подобные малоизвестные, но весьма полезные, записи.

DNSSEC: доверие по цепочке
Популярное описание DNSSEC, на которое можно ссылаться.

DNS-доступ под защитой: DoT и DoH
Принцип работы и способы применения технологий DNS-over-TLS и DNS-over-HTTPS, их место в общей “парадигме” инструментов защиты информации.

TLS 1.3 на веб-узлах Рунета
Количественная оценка распространённости узлов с корректно настроенным протоколом TLS версии 1.3 и валидным TLS-сертификатом в зонах .RU, .SU и .РФ. Данные актуальны на 2020 год.

Заголовки HTTP и их роль в обеспечении безопасности
Описание HTTP-заголовков, предназначенных для повышения безопасности доступа к сайтам. Content-Security-Policy и др.

ESNI как защита TLS от утечек метаинформации
Подробный рассказ про ESNI. Это 2019 год, с тех пор от ESNI отказались, но статья представляет исторический интерес.

Кстати, в продолжение долгоиграющего офтопика про цвет собак в “Илиаде” – соответствующий фрагмент (1.50, о том, что Аполлон сперва атаковал мулов и собак) из манускрипта Venetus A:

В современной “типографике”: οὐρῆας μὲν πρῶτον ἐπῴχετο καὶ κύνας ἀργούς. Обратите внимание, что подстрочная йота в ῴ написана справа от ω, а союз καί сокращён до значка, похожего на S. Сомнения может вызвать -ούς в конце предложения, но тут всё верно: это такой способ “оптимизированной” записи, в котором больше всего упростилась как раз буква ипсилон.

На исходном манускрипте немало комментариев (в частности, есть и комментарии между строк, буквально). А в комментариях пишут, в частности, что в цитированном выше фрагменте “неверно “быков/мулов” (οὐρῆας) полагать “охраной”, поскольку не совпадают они” (про охрану – это версия Аристотеля, довольно занятная). Есть и объяснение, что всякие лошаки слабые по своей природе, а среди собак – слабые белые, поэтому и те, и другие первыми пострадали от атаки Аполлона.

Между прочим, RSS остаётся одним из немногих полезных инструментов трансляции сообщений между сайтами и приложениями. Например, на dxdt.ru трансляция новых записок доступна по обычному и привычному адресу: https://dxdt.blog/feed/, что актуально во времена централизации по telegram-каналам (предположим) и разнообразным сервисам типа Facebook. Читать RSS можно разными способами. Я довольно давно использую удобное серверное решение – Tiny Tiny RSS. Уже писал про этот полезный пакет раньше, почти десять лет назад, но упомяну ещё раз, тем более, что он продолжает поддерживаться. Сейчас я использую вариант в docker-контейнере. TT-RSS работает без нареканий, есть даже отправка дайджеста почтой, а просматривать ленту сообщений можно браузером. Конечно, есть различные программы “стороны клиента”. Например, Akregator из KDE. Но серверное решение часто удобнее, на мой взгляд.

Пишут (правда, в несколько странной форме), что в Apple запрещают сотрудникам использовать ChatGPT и прочие “внешние ИИ” для рабочих задач. Якобы, из-за опасений, что возможна “утечка конфиденциальных данных”. Вообще, опасаться следовало бы не только и не столько утечек, сколько того, что подобный внешний инструмент, контролируемый другой компанией, начнёт целевым образом управлять деятельностью сотрудников, через подсказки этого самого ИИ. Как показывает практика целевого фишинга, ввести работника компании “Имярек” в заблуждение, или просто-напросто обмануть, – не так уж и сложно. Тем более, если вы управляете выдачей раскрученного в нужном направлении профильными СМИ инструмента, который называется “мощный современный ИИ”.

Попытаться построить квантовый компьютер на тысячи кубитов имеет смысл хотя бы для того, чтобы проверить, что имеющиеся модели работают для больших пространств состояний. Попытка факторизации 1024-битного числа на гипотетическом квантовом компьютере при помощи алгоритма Шора сталкивается с необходимостью как-то действовать в пространстве из 2^1024 состояний (ну, предположим). Влезет ли такое количество состояний во Вселенную? Насколько 2^1024 вообще большое?

Понятно, что какие-то прямые физические воплощения для такого числа придумать не получится, поскольку, например, 2^1024 несравнимо больше, чем масса Земли, подсчитанная в граммах. Но можно пойти на комбинаторные ухищрения. Нарежем пространство Вселенной на 2^80 небольших кубиков. 2^80 выглядит очень похожим на разные оценки “объёма Вселенной”, “количества частиц” и других сходных параметров. Перестановкой этих кубиков можно получать разные конфигурации Вселенной, которые, возможно, будут весьма сходными. Предположим, что количество конфигураций это (2^80)! (факториал, а не восклицание). “Реальный”, – что бы это ни значило, – показатель может быть другим: нужно учитывать возможности по сочетанию получившихся кубиков, их взаимное расположение. Однако для нашего примера это не важно.

Существенно ли (2^80)! превосходит 2^1024? Может показаться, что 2^1024 очень большое число. Однако провести сравнение нетрудно. Заметьте, что при вычислении факториала каждое чётное число повышает степень двойки (иногда – больше чем на единицу), поэтому 2^1024 вкладывается уже в 1026! (ну или примерно так; 1026 = 1024+2, проверьте; естественно, 171! больше 2^1024). Что уж говорить про (2^80)!! (Здесь второй восклицательный знак обозначает восклицание.) Теперь может показаться, что 2^1024 не такое уж и большое число, чтобы не вкладываться в качественно нарезанную Вселенную.

С другой стороны, а кто сказал, что разрешается разбирать объём Вселенной на кубики и переставлять их? Это было только предположение. Тем не менее, для реализации квантового алгоритма квантовым компьютером как раз нечто подобное и требуется, только детали различаются от интерпретации к интерпретации, поэтому иногда переставляются целые разные вселенные (ну, хорошо, не “переставляются”, а “интерферируют”). При этом комбинаторная часть здесь выносится за пределы реальности. То есть, можно предположить, что некая огромная “категория”, содержащая все возможные комбинации состояний и все процессы преобразования между состояниями, локализуется в конкретный результат измерений квантового компьютера, а этот результат помогает в факторизации больших чисел. Тут есть глубоко теоретический математический смысл.

Но, конечно, если Вселенная является симуляцией, то мощностей на 2^1024 состояний может и не хватить. А ведь не исключено, что получение нужной для 1024 битов разрешающей способности может потребовать во много раз больше кубитов, а элементов квантовой схемы – так вообще миллионы могут понадобиться. Впрочем, в симуляции факторизация скорее всего известна заранее: выписать на листке подобранное вручную 1024-битное простое число, удерживая его в области внимания, довольно трудно, а все остальные способы получения больших простых чисел, предположим, представляют собой результат спуска подготовленного значения из машины симуляции вселенных (из гипервизора, так сказать). Да что уж там – даже и выписывание числа может быть “наведённым”: ведь ещё предстоит проверить его простоту (спускается ли структура простых из машины симуляции в симуляцию?).

Так или иначе, но выходит, что реализация квантового алгоритма факторизации выдвигается во внешнюю область, которая не определяется окружающей “физической реальностью”, но объекты из этой области могут в “физическую реальность” проваливаться. Однако считается, что удерживать схему из кубитов там сложно, поэтому элементы достаточно быстро должны бы входить в зацепление с “реальностью”, теряя, тем самым, возможности для эффективной работы. В физике это называется декогеренцией, а для наших целей можно считать, что “категория”, стоящая за квантовым вычислением, “запутывается” (entanglement) с той действительностью, о которой смогли договориться наблюдатели – то есть, локализуется или схлопывается, теряя все полезные свойства. Иногда результатом локализации может быть “результат вычислений”. Хотя, вычисления ли это? Отдельный вопрос.

Сайт dxdt.ru сегодня (16/05/2023) несколько часов был полностью недоступен, к сожалению. Говорят, что “проблемы с сетевым оборудованием”. В итоге – всё же починили. Посмотрим, как будет дальше.

Чтобы придумать имя файла для архива, в котором будет сохранена резервная копия сайта, достаточно посмотреть в логи веб-сервера: /dxdt_ru.tar.gz, /dxdt-ru.tar.gz, /dxdtru.tar.gz, /dxdt.ru_backup.zip – и много других вариантов видны среди запросов ботов (впрочем, все получили ответ с кодом HTTP 404). Но, понятно, что насобирать такого по сайтам сейчас можно немало.