Разрешимость / алгоритм проверки универсальности множества квантовых ворот

Учитывая конечный набор квантовых вентилей , можно ли решить (в теоретическом смысле вычисления), является ли универсальным набором ворот? С одной стороны, «почти все» наборы гейтов являются универсальными, с другой, неуниверсальные наборы гейтов все еще недостаточно понятны (в частности, конечно, неизвестно, является ли каждый неуниверсальный набор гейтов классически симулируемым), поэтому я представляю, что явный алгоритм проверки универсальности может быть нетривиальным. $\mathcal{G} = \{G_1, \dots, G_n\}$ $\mathcal{G}$

quantum-computing Марчин Котовски
источник

Вы можете уточнить вопрос? В ответе Джо предполагается, что у вас есть фиксированное количество кубитов, и все шлюзы действуют на них, но для универсальности мы часто предполагаем, что вентили могут действовать на любом подмножестве кубитов. Например, CNOT + все одно-кубитные вентили не являются универсальными, если одно-кубитные вентили могут действовать только на первый кубит, а CNOT - только с кубита 1 на кубит 2. В последнем случае нам может потребоваться экстраполировать на множество кубитов. чтобы получить универсальность. В этом случае я думаю, что ответ может быть неизвестен.

@DanielGottesman: я согласен с ограничениями моего ответа. В самом деле, я считаю, что в последнем случае это неразрешимо: возьмите клеточный автомат на бесконечной решетке кубитов и используйте его для кодирования проблемы остановки (назовите это обновление унитарным

). Затем возьмем вторую решетку с универсальным QCA (с обновлением унитарного

). Мы можем определить новый унитарный

, где индекс

U_{1}

$U_1$

U_{2}

$U_2$

C U_{2} = | 0 ⟩ ⟨ 0 |_{H} \otimes I + | 1 ⟩ ⟨ 1 | \otimes U_{2}

$CU_2 = |0\rangle\langle0|_H\otimes I + |1\rangle\langle1|\otimes U_2$

H

$H$ обозначает кубит, который установлен в

тогда и только тогда первые клеточные автоматы остановок.

| 1 ⟩

$|1\rangle$

Джо Фицсимонс

Таким образом, ворота

универсальны тогда и только тогда, когда первая машина Тьюринга останавливается, и, следовательно, неразрешимы.

C U_{2} \times U_{1}

$CU_2 \times U_1$

Джо Фицсимонс

Ответы:

Для случая гамильтонианов, а не Гейтса, ответ тривиален: да, вы просто перечисляете независимые элементы алгебры Ли. Поскольку алгебра Ли является векторным пространством с добавлением оператора скобки Ли. Поскольку пространство конечное, оно имеет конечный базис, и его легко проверить, является ли оно замкнутым или открытым при операции скобки Ли. Простая проверка скобки Ли всех пар ортогональных операторов может быть выполнена за многочлен времени от размерности пространства, а подходящий операторный базис может быть найден методом Грамма-Шмидта.

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

В любом случае, взятие журнала ворот, чтобы получить набор операторов, которые генерируют их при возведении в степень, и проверку, генерируют ли они полную алгебру Ли, обеспечит простой необходимый, но не достаточный критерий универсальности.

Джо Фитцсимонс
источник

Почему мы должны проверять только пары?

Алекс 'qubeat'

@AlexV: Поскольку скобка Lie принимает два входа. Каждый раз, когда вы создаете новый линейно независимый оператор, вы создаете ортогональный оператор и повторяете, пока не получите замыкание.

Джо Фицсимонс

[\dots [H_{k}, H_{j}], H_{l}], \dots]

$[\ldots[H_k,H_j],H_l],\ldots]$

@AlexV: Вам не нужно. Это векторное пространство, поэтому вектор ортогонален данному подпространству тогда и только тогда, когда он ортогонален любому базису для этого подпространства.

Джо Фицсимонс

Вероятно, мы говорим о разных вещах - о каком векторном пространстве вы говорите? Вы не знаете с самого начала подалгебру, сгенерированную вашими воротами - вам нужно построить ее из заданных гамильтонианов, чтобы проверить, является ли она целой алгеброй Ли.

Алексей 'qubeat'