How to construct a multi-qubit controlled-Z from elementary gates?

Question

For the implementation of a certain quantum algorithm, I need to construct a multi-qubit (in this case, a three-qubit) controlled-Z gate from a set of elementary gates, as shown in the figure below. .

The gates that I can use are

• the Pauli gates $\rm X, Y, Z$ and all their powers (i.e. all Pauli rotations up to a phase factor),
• ${\rm exp}(i\theta|11\rangle\langle11|)$ (rotation about $|11\rangle\langle11|$ projector),
• $\rm H$ (Hadamard),
• $\rm C_X$ (single-qubit controlled-X or CNOT),
• $\rm C_Z$ (single-qubit controlled-Z), and
• $\rm S$ (SWAP).

How can I go about building this three-qubit controlled-Z from these gates? I have read several papers on circuit decompositions, but none of them could give me a clear and concise answer.

Answer 1

(EDIT: Improved to 14 CNOTs.)

It can be done with 14 CNOTs, plus 15 single-qubit Z rotations, and no auxiliary qubits.

The corresponding circuit is

where the $\fbox{$\pm$}$ gates are rotations $$ R_z(\pm\pi/16)\propto \left(\begin{matrix}1\\&e^{\pm i\pi/8} \end{matrix}\right) $$

---

Derivation:

Using the procedure described in https://arxiv.org/abs/quant-ph/0303063¹ , any diagonal gate - any thus in particular the CCCZ gate -- can be decomposed in terms of e.g. CNOTs and one-qubit diagonal gates, where the CNOTs can be optimized on their own following a classical optimization procedure.

The reference provides a circuit using 16 CNOTs for arbitrary diagonal 4-qubit gates (Fig. 4).

This can be improved if arbitrary pairs of qubits can be coupled to 14 qubits. For nearest neighbors with periodic (open) boundary conditions, this can be done with 16 (18) CNOTs. The corresponding circuits can be found in https://epub.uni-regensburg.de/1511/¹, Fig. 5.2, 5.4, and 5.5, and can e.g. be obtained using methods to construct short Gray sequences.

The number of one-qubit gates is always 15.

---

Remark: While there might in principle be a simpler circuit (said circuit has been optimized with a more constrained circuit architecture in mind), it should be close to optimal -- the circuit needs to create all states of the form $\bigoplus_{i\in I}x_i$ for any non-trivial subset $I\subset\{1,2,3,4\}$, and there are 15 of those for 4 qubits.

Note also that this construction by no means needs to be optimal.

---

^{1 Note: I'm an author}

Answer 2

Here is a CCCZ construction that uses 29 gates:

If you're allowed to use measurement and classical feedforward, the gate count can be reduced to 25:

(The Hadamard gates can be replaced with square roots of Y if needed to meet the gate set constraint.)

And if you allow me to perform Controlled-S gates and Controlled-sqrt(X) gates and perform X basis measurements, then I can get it down to 10 gates total:

Answer 3

You can implement an $n$-qubit controlled $U$ by the circuit given in this answer. Just replace $U$ by $Z$. However this requires CCNOT (Toffoli) gates, and you have some options for how to implement CCNOT using elementary gates.

Answer 4

I'm posting another decomposition of CCCZ here just in case it is useful for anyone else trying to compile CCCZ. It requires a smaller number of total gates, and only 1 auxiliary qubit instead of 2, but five more 2-qubit gates than the "obvious" answer, so may actually be worse for implementation on Hardware.

It was suggested by user @Rob in this comment: Automatic compilation of quantum circuits, and comes from this paper.

The GMS5$(\chi)$ gate is this:

with $n=5$ and all $\chi_{ij}=\chi$, which means it involves 10 two-qubit gates. These will then have to be compiled into the gate set given in the question, so this decomposition should only be used if you are trying to save on the number auxiliary qubits or if you don't mind having more 2-qubit gates in order to reduce the circuit depth by a bit.

Answer 5

There are some large savings that can be made based on the specified gate set. For example, in the typical ccnot construction, if you replace the $T$ gate with $Z^{1/4}$, you don't need that phase correction that constitutes the last few gates between the two control qubits. This construction, which obeys the gate set specified in the question, consists of 21 gates, of which 10 are 2-qubit (you don’t need the last gate in the circuit below).

To be clear (in response to several comments): usually we look at Toffoli, and try to make it using the $T$ gate. If both controls are $|1\rangle$, then the gate sequence on the target qubit is $HXTXT^\dagger XTXT^\dagger H$. Now, since $XT^\dagger X=Te^{-i\pi/4}$, then the sequence simplifies to $-iHT^4H=-iX$, and one has to add a compensating controlled-S gate on the two control qubits. If, instead, we use $Z^{1/4}$, then $XZ^{-1/4}X=Z^{1/4}$, and none of those pesky phases come into it, and it saves you some two-qubit gates!

Also, note that the two Toffoli gates are only Toffoli because they target the 0 state. Typically you would need an extra two-qubit gate.

I've not found as efficient a construction in existing literature, although this paper claims a construction using only 11 2-qubit gates, but I haven’t done a complete gate count once it’s converted into the question’s restricted gate set.

Answer 6

While my other answer is the most obvious "textbook" way (using Nielsen & Chaung's CCCZ decomposition into CCNOTs, then another textbook decomposition to compile the CCNOTs), a more creative way might allow us to get the job done with fewer gates.

Step 1:

Replace all the CNOTs in Nielsen & Chuang's circuit with this gadget:

Step 2:

Now we have a bunch of CCZs instead of CCNOTs, and they can be decomposed like this (courtesy of this paper):

Step 3:

Note that $H^2 = I$, so some of these Hadamards cancel each other out and we get even more of a reduction :)