Учи Кванты! → Курс → Плотный подграф через GBS

Свет предлагает, классика проверяет

Прошлый урок закончился вопросом: выборки семплера дают нам некоторые плотные группы, но выборка это ещё не ответ. В этом уроке мы попробуем достроить недостающее звено. Соберём гибридный алгоритм, в котором квантовая часть работает вместе с классической, и посмотрим, что получится. Возьмём каждую выборку семплера как основу, доведём её до готового кандидата классическим «жадным поиском» и посмотрим, как всё это работает вместе.

Выборка это черновик

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

Нажмите кнопку конвейера. Сначала двести выборок приедут с семплера, каждая пройдёт дожимание «жадным поиском», и справа появится сводка: сколько черновиков превратились в идеальную пятёрку и сколько правок на это ушло.

Это платный урок курса. Дальше — интерактив: виджеты, схемы и контрольные вопросы. Продолжение — в полном курсе «Учи Кванты!»: открыть полный курс.