Перманент матрицы: алгебраический двойник определителя и проблема #P-полноты

Свойства перманента: отсутствие инвариантности

Хотя формула перманента (Perm A) визуально неотличима от формулы определителя (Det A) за исключением знака, их алгебраические свойства отличаются катастрофически. Определитель — это антисимметричный тензор: если мы поменяем местами две строки матрицы, определитель изменит знак на противоположный. Если в матрице две одинаковые строки, определитель строго равен нулю (геометрически это схлопывание объема). Перманент же симметричен: перестановка строк или столбцов вообще не меняет его значения. Более того, для перманента не работает самое главное свойство определителя — мультипликативность: перманент произведения матриц не равен произведению их перманентов (Perm(AB) != Perm(A)*Perm(B)). Именно из-за отсутствия этих элегантных свойств перманент не используется для решения СЛАУ или поиска обратных матриц.

Комбинаторный смысл и паросочетания

Если перманент так неудобен в алгебре, зачем он нужен? Ответ лежит в теории графов. Рассмотрим двудольный граф (например, n рабочих и n задач, где ребро означает, что рабочий может выполнить задачу). Эту ситуацию можно описать бинарной матрицей смежности. Значение перманента такой матрицы в точности равно количеству идеальных паросочетаний в графе (то есть количеству уникальных способов распределить всех рабочих по задачам так, чтобы никто не остался без дела). В статистической механике перманент используется в модели димеров для подсчета способов укладки домино на шахматной доске. Для матриц, состоящих из единиц, перманент равен факториалу (n!), так как это просто подсчет всех возможных перестановок.

Теорема Вэлианта и вычислительный кошмар

Определитель матрицы n на n состоит из n! (факториала) слагаемых. Прямое вычисление заняло бы миллиарды лет, но благодаря методу Гаусса компьютер находит определитель за доли секунды (за O(n^3) операций). Казалось бы, перманент тоже можно вычислить быстро. Однако в 1979 году Лесли Вэлиант доказал шокирующую теорему: вычисление перманента даже для матриц, состоящих только из нулей и единиц, является #P-полной задачей (Sharp-P-complete). Это означает, что для вычисления перманента принципиально не существует быстрых алгоритмов (типа метода Гаусса), которые работали бы за полиномиальное время. Никакие алгебраические трюки не могут упростить сумму без минусов. Для матрицы 50x50 вычисление перманента на самом мощном суперкомпьютере займет больше времени, чем возраст Вселенной.

Формула Райзера и квантовое превосходство

Самый быстрый из известных на сегодня точных классических алгоритмов для перманента — это формула Райзера. Она использует принцип включений-исключений и сокращает сложность с O(n!) до O(n^2 * 2^n). Это все еще экспоненциальная сложность, но она позволяет считать матрицы размера 30x30. Удивительно, но перманент стал центральной фигурой в гонке за создание квантовых компьютеров. Задача «бозонного сэмплинга» (Boson Sampling) заключается в моделировании прохождения фотонов через систему оптических интерферометров. Квантовая механика гласит, что амплитуда вероятности распределения фотонов (которые являются бозонами и имеют симметричные волновые функции) на выходе в точности пропорциональна перманенту унитарной матрицы интерферометра. В 2020 году квантовый компьютер Jiuzhang за 200 секунд решил задачу, которая потребовала бы вычисления гигантских перманентов, доказав квантовое превосходство над классическими алгоритмами.