Какова вычислительная сложность оптимизации различных функций над унитарной группой ?
Типичная задача, возникающая часто в квантовой теории информации, было бы максимизировать количество типа (или выше многочленов порядка в ) по всем унитарные матрицы . Является ли этот тип оптимизации эффективным (возможно, приблизительно) вычислимым или NP-сложным? (возможно, это хорошо известно, но я не смог найти каких-либо общих ссылок)
cc.complexity-theory
reference-request
optimization
quantum-information
Марчин Котовски
источник
источник
Ответы:
Извините я опоздал! В теории квантовых вычислений существует множество примеров задач оптимизации для унитарной группы, которые, на удивление (по крайней мере для меня), разрешимы за (классическое) полиномиальное время путем сокращения до полуопределенного программирования.
Вот ранний пример: решение моей проблемы 2000 года, в 2003 году Барнум, Сакс и Сегеди показали, что Q (f), сложность квантового запроса для булевой функции f: {0,1} n → {0,1 }, может быть вычислено по полиному времени от 2 n (т. е. размер таблицы истинности f). Я думал об этом, но не мог понять, как это сделать, поскольку нужно оптимизировать вероятность успеха по всем возможным алгоритмам квантовых запросов, каждый из которых имеет свой собственный набор (возможно, 2 n- мерных) унитарных матриц. Барнум и др. сводится к SDP путем использования "двойственности" между унитарными матрицами и положительными полуопределенными матрицами, так называемый изоморфизм Чой-Ямиолковского, Более свежую и более простую характеристику SDP, характеризующую Q (f), см. В статье Райхардта 2010 года, показывающей, что метод противоборства с отрицательным весом является оптимальным.
Еще один важный случай, когда этот трюк использовался в квантовых интерактивных системах доказательства. Хотя это не является интуитивно очевидным, в 2000 году Китаев и Ватроус доказали, что QIP ⊆ EXP. сводя задачу оптимизации по унитарным матрицам экспоненциального размера, возникающим в квантовой интерактивной системе доказательств с тремя раундами, к решению SDP с единичным экспоненциальным размером (опять же, я думаю, используя изоморфизм Чой-Ямиолковского между смешанными состояниями и унитарные матрицы). Недавний прорыв QIP = PSPACE пришел к выводу о том, что этот конкретный SDP может быть приблизительно лучше решен в NC (т. Е. С помощью схем глубины регистрации).
Итак, какой бы ни была ваша конкретная проблема оптимизации с участием унитарной группы, я предполагаю, что она может быть решена быстрее, чем вы думаете - если не каким-то еще более простым способом, то путем сокращения до SDP!
источник
Определение того, эквивалентны ли две матрицы Адамара, является полной проблемой изоморфизма графов (GI). У Брендона Маккея есть статья на эту тему. См. Б.Д. Маккей, Эквивалентность Адамара через изоморфизм графов, Дискретная математика, 27 (1979) 213-216.
источник