В Бернштейн и Вазираньте в основополагающей работе «Квантовая теория сложности», они показывают , что - мерное унитарное преобразование может быть эффективно аппроксимировать продукт того , что они называют «рядом с тривиальными севооборотами» и «почти тривиальные фазовыми сдвиги».
«Почти тривиальные вращения» представляют собой одномерные матрицы которые действуют как единое целое во всех измерениях, кроме двух, но действуют как вращение в плоскости, охватываемой этими двумя измерениями (то есть имеет подматрицу 2x2 в форме:
для некоторых ).
«Почти тривиальные фазовые сдвиги» - это одномерные унитарные мерные матрицы, которые действуют как тождество во всех измерениях, кроме 1, но применяют коэффициент для некоторого к этому одному измерению.
Кроме того, они показывают, что необходим только один угол поворота (как для унитарного поворота, так и для сдвига фазы), учитывая, что угол кратен (BV устанавливает угол .
В последующих работах по квантовой теории сложности (например, Adleman et al. Или Fortnow and Rogers) утверждается, что результат BV подразумевает, что универсальные квантовые вычисления могут быть выполнены с помощью унитарных операторов, чьи записи находятся в .
Как это следует? Я могу понять, что произведение почти тривиальных матриц вращения даст вам унитарную матрицу с действительными элементами, но как насчет матриц фазового сдвига?
То есть: если вы можете выполнять только почти тривиальные повороты и матрицы фазового сдвига, где элементы матрицы равны , можем ли мы эффективно аппроксимировать все другие матрицы фазового сдвига?
Я подозреваю, что это подразумевается не сразу, и правильное доказательство для него будет напоминать доказательство универсальности Тойфоли-подобных ворот Дойча - или я упускаю что-то очень очевидное?
В дополнение к статье, на которую указал Мартин, была более ранняя статья Терри Рудольфа и Лов Гровер, показывающая, что двухбитный вентиль универсален для квантовых вычислений (см. Quant-ph / 0210187 ). В воротах есть все реальные входы, и в случае, если вы не знаете, ребиты - это кубиты, где амплитуды ограничены действительными числами. Это может быть источником претензии. Затвор, о котором идет речь, описан в статье и представляет собой управляемое вращение Y.
источник