Физики из Канады нашли способ искать плотные подграфы с помощью бозонных, точнее, фотонных семплеров. Звучит как абзац из романа
Питера Уоттса? Сейчас попробуем расшифровать.
Читая текст ниже, держите в голове, что любое упрощение — это только часть правды )
Если вкратце, то с появлением первых прототипов квантовых компьютеров выяснилось несколько неприятных обстоятельств: во-первых, универсальные квантовые вычислители очень сложны и дороги, во-вторых, очень нестабильны — вычисления зачастую приходится выполнять много сотен раз для получения надёжных результатов.
Одним из решений проблемы (кроме, очевидно, залить недостатки деньгами) стало построение специализированных вычислительных узлов, которые умеют что-то одно, но хорошо, быстрее классических компьютеров. Так вот, фотонные семплеры – это и есть одно из семейств таких узлов.
Фотонный семплер – это, по большому Копенгагенскому счёту,
всего лишь линейный интерферометр, лазер и фотоэлемент. Путём некоторых преобразований эту несложную схему
можно использовать для вычисления некоторого класса комбинаторных задач, особенно преобразования функции распределения случайных величин в системах с очень большим числом комбинаций. В чём-то устройство похоже на доску Гальтона – на вход мы высыпаем кучу шариков, внутри происходит магия, на выходе мы получаем статистику распределения какой-то величины для нашей задачи.
Плотные подграфы – это группы вершин в графах с особенно высоким числом связей. Например, бывшие одноклассники в ВК – это плотные подграфы, там каждый дружит с каждым. Находить такие группы очень вычислительно сложно, но важно не только
для анализа социальных сеточек, но и вообще для поиска совпадений между наборами данных, например,
поиска нужного гена в геноме, или анализа спектрограмм при анализе взрывчатых веществ.
В общем, штука очень полезная и нужная, правда пока на этапе прототипа и модели. Хотя сейчас внедрение всякого хайтека идёт быстро, так что увидим мы квантовые семплеры в бою скорее всего довольно скоро, ещё в нашем поколении.
#физика #кванты #симуляция #квантовый_компьютер #квантовые_вычисления #вычисления #математика #графы
