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

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.

• Should your 4th register have a Z instead of a black circle? Aug 23 '18 at 23:35
• @user1271772 Both are okay. Since controlled-Z gates are symmetric in the used qubits (i.e. one can swap two qubits and the effect of the gate will remain the same), an orderless notation, like the one with black dots, has been considered more appropriate in recent literature. Aug 24 '18 at 0:18

(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/03030631 , 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/1, 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

• And would using Rx (or Ry) gates instead of Rz gates make this a multi-qubit controlled-X (or controlled-Y) gate? Oct 22 '18 at 15:49
• @Sierox You just need to Hadamard-transform everything on the bottom qubit, i.e. the corresponding CNOTs will become CZs, and the rotations on the bottom qubit will become X rotations. Oct 22 '18 at 16:54
• How does this generalize for n qubits? Does the rotation angle change? And for e.g. a fifth qubit I should add 16 Rz + 16 CNOTs on the bottom, right? Oct 22 '20 at 15:21

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.

• That gives a circuit with potentially excessive depth. Maybe the OP wants a shallower circuit with that gate set. One can do an automatic procedure to moderately reduce circuit sizes. Aug 23 '18 at 23:38
• @AHusain: What is the automatic procedure? Aug 23 '18 at 23:43
• It uses results from the theory of automatic groups, so that was a pun. Explanation would go somewhere else; not a short comment. Aug 24 '18 at 14:42
• Okay @AHusain, I'm going to ask a question catered just for you! Aug 24 '18 at 17:24 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: • But you are using a measurement + conditional controlled gate at the end. I would say that's outside the "normal" rules of the game. (E.g., if you would replace this by a controlled-gate and postpone the measurement, you would still use a Toffoli.) Aug 25 '18 at 12:50
• @NorbertSchuch That's why I preface the second diagram with "if you're allowed to use measurement and classical feedforward". Notice that the first diagram doesn't use those things. Aug 25 '18 at 19:30
• Ups. Sorry. Mea culpa. I shouldn't have just looked at the pictures, and scrolled a bit :-| Aug 25 '18 at 23:04
• At the end of the first circuit, the fifth qubit is discarded. How would I have to treat that qubit if I needed multiple CCCZs in sequence? Aug 27 '18 at 18:03
• You would feed it into the next CCCZ, but drop the first two operations in the the second CCCZ's circuit. Those operations are preparing it into a T state, which is what the final state of the discarded qubit is. So the second CCCZ would have 2 fewer operations. Aug 27 '18 at 18:13

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.

• The GMS5 gate is a pretty global gate - hard to compare this to a conventional gate count. And it's quite likely that even in scenarios where this gate can be implemented, you won't be able to choose $\chi_{ij}$. Why not just take the logarithm of the CCCZ gate? Aug 25 '18 at 12:52
• @NorbertSchuch: the question asks for CCCZ not log(CCCZ). If we were to do log(CCCZ), which you presumably suggest since GMS5 is an exponential of elementary gates and the logarithm of it would possibly be simpler to implement, would it be easy to get the output of CCCZ from the answer to log(CCCZ)? Aug 25 '18 at 19:06
• I have no clue what you are talking about. Sums of products or Paulis are NOT easy to implement. They are not even unitary. --- But logarithms of unitaries are Hamiltonians, so if you can time-evolve with log(CCCZ) through some smart experimental setup, you will get CCCZ with "one gate" in this counting. Aug 25 '18 at 23:03
• @NorbertSchuch: Your comment "exp(-iHt) is hardly adiabatic" is semantically null and doesn't make any sense. Why did you ask me "why not just take the logarithm of the CCCZ gate?" ? Aug 26 '18 at 5:47
• @user1271772 just to add to what (I believe) Norbert is saying in the comments: the problem of trying to find time-independent Hamiltonians directly generating nontrivial gates (CCX and others are considered in the paper) has been studied in arxiv.org/abs/1803.07119. The problem in this setting is that of finding Hamiltonians that contain only feasible interactions and still generate the target gate. The resource thus become what Hamiltonian interactions are allowed, rather than what elementary gates are allowed
– glS
Aug 28 '18 at 11:13

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.

• Feels like you are not uncomputing sth. in the lower half of the circuit -- but I didn't think very hard about it ;) Aug 25 '18 at 12:48
• I uncomputed the ancilla, apart from an irrelevant single qubit rotation on it. That’s what the last Toffoli does. I suppose Toffoli should be in inverted commas since it is missing that 1 gate at the end. Aug 25 '18 at 17:09
• Are you sure the first block is a Toffoli -- or is it just a Toffoli on the ancilla? (I remember the best one could do for Toffoli was about 8 CNOTs). Aug 25 '18 at 23:02
• I think you're missing a CS phase correction on the top two qubits in the middle block. You should be able to drop the leftmost CZ from each of the side blocks. Aug 26 '18 at 3:43
• I’ll check carefully on Tuesday. I thought this formulation avoided the cS. Aug 26 '18 at 5:19

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 :)

• What's the gate count? Aug 25 '18 at 12:51