Внедрение шлюза CCCNOT с использованием только ворот Toffoli

10

Вентиль CCCNOT - это четырехразрядный обратимый вентиль, который переворачивает свой четвертый бит, если и только если все первые три бита находятся в состоянии 1 .

Как мне реализовать ворота CCCNOT, используя ворота Toffoli? Предположим, что биты в рабочей области начинаются с определенного значения, 0 или 1, при условии, что вы возвращаете их этому значению.

chuster
источник
Использование только ворот Toffoli, или Toffoli и CNOT являются честной игрой?
user1271772
Разрешены только ворота Тоффоли.
Chuster
1
Какая часть этого вопроса является квантовой? Кажется, вы хотите разложить классические обратимые ворота (CCCNOT) на более мелкие классические обратимые ворота (CCNOT).
user1271772
1
Сам вопрос не относится к квантовым вычислениям, но ворота важны для квантовой схемы.
Chuster

Ответы:

8

Я думаю, что вы ищете следующую схему. Здесь, б1,б2,б3,б4{0,1} , и является сложение по модулю 2 .

введите описание изображения здесь

Здесь пятый кубит используется в качестве вспомогательного или вспомогательного кубита . Это начинается в |0 и заканчивается в |0 , когда применяется схема.

Позвольте мне подробнее рассказать о том, как работает эта схема. Идея состоит в том, чтобы прежде всего проверить, находятся ли первые два кубита в состоянии |1 . Это может быть сделано с использованием единственного гейта Тоффоли, и результат сохраняется во вспомогательном кубите. Теперь задача сводится к переключению кубита 4 , когда кубиты 3 и вспомогательный кубит находятся в |1 . Это также может быть достигнуто с помощью одного приложения ворот Тоффоли, а именно среднего в схеме, показанной выше. Наконец, последний вентиль Toffoli служит для вычисления временного результата, который мы сохранили во вспомогательном кубите, так что состояние этого кубита возвращается к |0 после того, как схема применяется.


В разделе комментариев возник вопрос, возможно ли реализовать такую ​​схему, используя только логики Тоффоли, без использования вспомогательных кубитов. На этот вопрос можно ответить отрицательно, как я покажу здесь.

Мы хотим реализовать СССNОT -gate, который действует на четыре кубита. Мы можем определить следующую матрицу (матрицу представление Паули Икс -gate):

Иксзнак равно[0110]
Кроме того, мы будем обозначать N - мерную матрицу идентичности яN . Теперь мы видим, что матричное представление СССNОT ворот, действующих на четыре кубита, задается следующей матрицей 16×16 :
СССNОTзнак равно[я1400Икс]
Следовательно, мы можем определить его определитель:
йе(СССNОT)знак равно-1
Теперь рассмотрим матричное представление ворот Тоффоли, действующих на первые три кубита4 система Его матричное представление записывается в виде (где мы использовали произведение матриц Кронекера):
TоееоLяя2знак равно[я600Икс]я2знак равно[я1200Икся2]знак равно[я120000я20я20]
Расчет его определяющих выходов:
йе(TоееоLяя2)знак равно1
Врата Тофоли, конечно же, могут действовать и на разные кубиты. Предположим, что мы позволяем воротам Тоффоли действовать на первом, втором и четвертом кубите, где четвертый кубит является целевым кубитом. Затем мы получаем новое матричное представление из представленного выше путем замены столбцов, соответствующих состояниям, которые отличаются только в третьем и четвертом кубите, т. Е. |0001 с |0010 , |0101 с |0110 и т.д. Важно отметить, что число перестановок столбцов четно, и , следовательно, определитель остается неизменным. Как мы можем записать каждую перестановку кубитов в виде последовательности последовательных перестановок просто2 кубита (т. Е.S4 генерируется транспозициями вS4 ), мы находим, что для всех тоффолио, примененных к любой комбинации контрольных и целевых кубитов, его матричное представление имеет определитель1 .

Последнее, что следует отметить, это то, что определитель коммутирует с умножением матриц, то есть йе(AВ)знак равнойе(A)йе(В) , для любых двух матриц A и В совместимых с умножением матриц. Следовательно, теперь становится очевидным, что применение нескольких последовательностей Toffoli никогда не создает схему, матричное представление которой имеет определитель, отличный от 1 , что, в частности, подразумевает, что СССNОT ворота не могут быть реализованы с использованием только элементов Toffoli для 4 кубитов.

Теперь очевидный вопрос: что меняется, когда мы разрешаем вспомогательный кубит? Мы находим ответ, когда записываем действие СССNОT ворот на 5 кубитную систему:

СССNОTя2знак равно[я1400Икс]я2знак равно[я280000я20я20]
Если мы вычислим этот определитель, мы найдем:
йе(СССNOTI2)=1
Следовательно, определительCCCNOT -грэта, действующего на5 кубитах, равен1 , а не1 . Вот почему предыдущий аргумент недействителен для5 кубитов, как мы уже знали из-за явно сконструированной схемы, запрошенной OP.

arriopolis
источник
1
источник или метод, используемый для получения схемы, был бы полезен!
GLS
1
Я не знаю источников, которые бы объясняли, как разрабатывать такие схемы всесторонне. Источниками, которые я использовал при изучении квантовых вычислений, были книга Нильсена и Чуанга, а также примечания к лекциям, которые можно найти здесь: homepages.cwi.nl/~rdewolf/qcnotes.pdf , но эти источники специально не фокусируются на дизайне квантовых цепей.
Артеополис
2
Я попытался немного подробнее рассказать о том, как работает схема. Надеюсь, что это помогает в разработке схем, подобных этой! :)
Артеополис
Возможно ли это без вспомогательных средств?
user1271772
1
+1СССNОT4-1СССNОT+1