Как построить мульти-кубит управляемый-Z из элементарных ворот?

Для реализации определенного квантового алгоритма мне нужно построить мультикубитный (в данном случае трехкубитный) управляемый вентиль Z из набора элементарных вентилей, как показано на рисунке ниже. ,

Ворота, которые я могу использовать,

• ворота Паули $\rm X, Y, Z$ и все их силы (то есть все вращения Паули с точностью до фазового фактора),
• ${\rm exp}(i\theta|11\rangle\langle11|)$ (вращение вокруг проектор),$|11\rangle\langle11|$
• $\rm H$ (Адамар),
• $\rm C_X$ (управляемый одним кубитом X или CNOT),
• $\rm C_Z$ ( управляемый-Z) и
• $\rm S$ (SWAP).

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

(РЕДАКТИРОВАТЬ: Улучшено до 14 CNOT.)

Это можно сделать с помощью 14 CNOT, плюс 15 однокубитных Z-поворотов и без вспомогательных кубитов.

Соответствующая схема

где $\fbox{$\pm$}$ ворота - это повороты

Вывод:

Используя процедуру, описанную в https://arxiv.org/abs/quant-ph/0303063 ¹ , любой диагональный вентиль - любой, таким образом, в частности вентиль CCCZ - можно разложить, например, на CNOT и однобитовые диагональные вентили, где CNOT могут быть оптимизированы самостоятельно, следуя классической процедуре оптимизации.

Ссылка предоставляет схему, использующую 16 CNOT для произвольных диагональных 4-кубитных элементов (рис. 4).

Это может быть улучшено, если произвольные пары кубитов могут быть связаны с 14 кубитами. Для ближайших соседей с периодическими (открытыми) граничными условиями это можно сделать с помощью 16 (18) CNOT. Соответствующие схемы можно найти в https://epub.uni-regensburg.de/1511/ ¹ , рис. 5.2, 5.4 и 5.5, и, например, их можно получить, используя методы для построения коротких последовательностей Грея.

Количество однобитных гейтов всегда 15.

Примечание. Хотя в принципе может существовать более простая схема (упомянутая схема была оптимизирована с учетом более ограниченной архитектуры схемы), она должна быть близка к оптимальной - схема должна создавать все состояния формы $\bigoplus_{i\in I}x_i$ для любого нетривиального подмножества $I\subset\{1,2,3,4\}$и есть 15 из них для 4 кубитов.

Отметим также, что эта конструкция ни в коем случае не должна быть оптимальной.

^{1 Примечание: я автор}

Вы можете реализовать $n$контролируемый $U$по схеме, приведенной в этом ответе . Просто замени$U$ по $Z$, Однако для этого нужны шлюзы CCNOT (Toffoli), и у вас есть несколько вариантов того, как реализовать CCNOT с использованием элементарных вентилей .

Вот конструкция CCCZ, которая использует 29 ворот :

Если вам разрешено использовать измерения и классическую прямую связь, количество гейтов может быть уменьшено до 25 :

(Ворота Адамара могут быть заменены квадратными корнями Y, если это необходимо для удовлетворения ограничения набора ворот.)

И если вы позволите мне выполнить вентили Controlled-S и Gateled Controlled-sqrt (X) и выполнить измерения X базисов, то я могу получить их до 10 шлюзов :

Я публикую здесь очередную декомпозицию CCCZ на тот случай, если она будет полезна всем, кто пытается скомпилировать CCCZ. Для этого требуется меньшее количество общих шлюзов и только 1 вспомогательный кубит вместо 2, но на пять шлюзов на 2 кубита больше, чем в «очевидном» ответе, что может фактически ухудшить реализацию на аппаратном уровне.

Это было предложено пользователем @Rob в этом комментарии: Автоматическая компиляция квантовых цепей , и происходит из этой статьи .

GMS5$(\chi)$ Ворота это:

с $n=5$ и все $\chi_{ij}=\chi$, что означает, что он включает в себя 10 двухкубитных ворот. Затем их нужно будет скомпилировать в набор вентилей, указанный в вопросе, поэтому эту декомпозицию следует использовать только в том случае, если вы пытаетесь сэкономить на количестве вспомогательных кубитов или если вы не возражаете против того, чтобы у вас было больше 2-кубитных вентилей, чтобы уменьшить глубину цепи немного.

Есть некоторые большие сбережения, которые могут быть сделаны на основе указанного набора шлюзов. Например, в типичной конструкции ccnot, если вы замените$T$ ворота с $Z^{1/4}$вам не нужна фазовая коррекция, которая составляет последние несколько ворот между двумя контрольными кубитами. Эта конструкция, которая подчиняется набору гейтов, указанному в вопросе, состоит из 21 вентиля, из которых 10 являются 2-кубитными (вам не нужны последние вентили в схеме ниже).

Чтобы было ясно (в ответ на несколько комментариев): обычно мы смотрим на Toffoli, и пытаемся сделать это, используя $T$Ворота. Если оба элемента управления$|1\rangle$то последовательность ворот на целевом кубите $HXTXT^\dagger XTXT^\dagger H$, Теперь, так как$XT^\dagger X=Te^{-i\pi/4}$то последовательность упрощается до $-iHT^4H=-iX$и необходимо добавить компенсирующий логический элемент-Управляемый-S на двух контрольных кубитах. Если вместо этого мы используем$Z^{1/4}$, тогда $XZ^{-1/4}X=Z^{1/4}$и ни одна из этих надоедливых фаз не входит в него, и это спасает вас от двух-кубитных ворот!

Кроме того, обратите внимание, что эти два входа Toffoli являются только Toffoli, потому что они нацелены на состояние 0. Как правило, вам понадобятся дополнительные два-кубитные ворота.

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

В то время как мой другой ответ является наиболее очевидным способом «учебника» (используя декомпозицию CCCZ Нильсена и Чанга в CCNOT , а затем другую декомпозицию учебника для компиляции CCNOT ), более творческий способ может позволить нам выполнить работу с меньшим количеством элементов.

Шаг 1:

Замените все CNOT в схеме Nielsen & Chuang следующим гаджетом:

Шаг 2:

Теперь у нас есть несколько CCZ вместо CCNOT, и их можно разложить следующим образом (любезно предоставлено в этой статье ):

Шаг 3:

Обратите внимание, что $H^2 = I$так что некоторые из этих Адамардов отменяют друг друга, и мы получаем еще большее сокращение :)