частичная трассировка с разреженными матрицами

Позволять р А Б С Д быть разреженной матрицей из 4 систем, каждая из которых д -мерное гильбертово пространство.

Для д < 7 за разумное время (несколько секунд) я могу выполнить частичную трассировку р А Д используя код, предложенный в http://www3.imperial.ac.uk/people/m.tame/research . Мне нужен эффективный алгоритм для вычисления р А Д где д ≥ 7 . Алгоритм сайта выше не использует никаких свойств матрицы и требует множества перестановок и перестановок.

Знаете ли вы эффективный алгоритм вычисления частичного следа qudit, который использует тот факт, что матрица разрежена? Также было бы интересно, если бы алгоритм мог использовать преимущества параллельных вычислений.

Заранее большое спасибо за ваши ответы.

С уважением,

Сильвио

Строго говоря, надеяться можно только на полиномиальное масштабирование с размерностью системы д (Я бы не назвал это эффективным с точки зрения вычислительной сложности, если только вы не установили d как константу). Было бы полезно знать, насколько разреженной является ваша матрица плотности: как максимальное количество коэффициентов на строки и столбцы асимптотически масштабируется с размером системы д ?
В общем, частичный след разреженной матрицы не дает разреженной матрицы, поэтому вы получите лишь ограниченное улучшение, используя тот факт, что матрица является разреженной (возможно, с коэффициентом d/s).

Ответы (1)

Если вы хотите что-то конкретное для Mathematica, то я не знаю, но в целом:

Позволять о "=" р А Д "=" Тр Б С ( р ) . р является оператором четырех подсистем, поэтому он имеет четыре входа и четыре выхода, что делает его тензором 8-го ранга. Позволять я , я ′ – индексы, соответствующие входу и выходу р на подсистеме А , позволять Дж , Дж ′ соответствовать Б и т.д. Компоненты о тогда о я я ′ л л ′ "=" ∑ Дж к р я я ′ Дж Дж к к л л ′ .

Если р является разреженным, вам нужно только суммировать записи, которые не равны нулю. Если р тогда эрмитов о будет эрмитовым, и достаточно вычислить только верхний треугольник (тогда нижний треугольник является его сопряженным). Я не верю, что есть какие-либо другие доступные оптимизации, если вы не знаете о дальнейшей структуре на р . Сумма тривиально распараллеливается - каждая комбинация я я ′ л л ′ полностью независим от других.

Эффективность этого метода сильно зависит от того, насколько затратно перечисление коэффициентов разреженных, которые отличны от нуля. Было бы хорошо, если бы ОП прояснил этот момент.
Большое спасибо за ваш ответ. Используя ваше предложение и более внимательно изучив алгоритм, предложенный в Mathematica (ссылка в вопросе), я смог распараллелить алгоритм, и теперь я могу прийти до тех пор, пока д ≤ 9 . Что касается дальнейших структур или асимптотического масштабирования ненулевых элементов, у меня нет такого глубокого анализа, потому что это не нужно для моей задачи. Я действительно считаю, что нет никакого интересного свойства, которое можно использовать для частичной трассировки, потому что я применяю единицу к некоторым состояниям и вижу, что есть «много» нулей. Большое спасибо еще раз.
частичная трассировка с разреженными матрицами
СпросиСетьПолитика конфиденциальности1y, 0v