How to make circuit for n-control Z gate( i.e $C^3Z$ )?

Question

I am trying to make circuit for $C^3Z$ gate I have seen a circuit for $C^2Z$ or $CCZ$ gate made by using $CCX$ gate so is there any way to make circuit for $C^3Z$ in this similar manner( i.e by using $CCX$ gate) or i have to do something different then this method Fig. is below for $CCZ$ gate

Answer 1

The circuit you showed above for the double-controlled $Z$ gate can be extended to a triple-controlled $Z$ by adding an extra Toffoli and ancilla:

Qiskit offers such circuits readily in the circuit library, where you have many different possibilities to implement your multi-controlled Z gate.

Using the MCMT (multi-controlled multi-target circuit) is one option. You can either use the v-chain version with ancillas, which produces the same circuit as above:

from qiskit.circuit.library import MCMTVChain
c3z = MCMTVChain('z', num_ctrl_qubits=3, num_target_qubits=1)
c3z.draw(output='mpl')

Or you can use an ancilla-free version:

from qiskit.circuit.library import MCMT
c3z = MCMT('z', num_ctrl_qubits=3, num_target_qubits=1)
c3z.decompose().decompose().draw(output='mpl')

In principle you there's always a tradeoff in the number of ancilla qubits you can use and the depth of the circuit. More ancillas usually allows to use less gates, but more ancillas are costly or may not be available at all!

Excursion to multi-controlled $X$ gates

Since you know that $Z = HXH$ another possibility would be to use the multi-controlled $X$ gate from Qiskit. Since there are different methods on how the multi-controlled $X$ can be implemented you can choose the mode you want as either of 'noancilla' 'recursion' 'v-chain' 'v-chain-dirty-ancilla':

from qiskit import QuantumCircuit

noancilla = QuantumCircuit(4)
noancilla.h(3)  # H on target qubit
noancilla.mcx([0, 1, 2], 3, mode='noancilla')
noancilla.h(3)  # again H on target qubit
noancilla.draw()


q_0: ───────■───────
            │       
q_1: ───────■───────
            │       
q_2: ───────■───────
     ┌───┐┌─┴─┐┌───┐
q_3: ┤ H ├┤ X ├┤ H ├
     └───┘└───┘└───┘

The recursion mode uses only one ancilla and recursively splits the number of controls until we have a 3 or 4 controls for which the controlled-X is hardcoded. Here, since you only have 3 controls, it does not need an ancilla (since Qiskit knows a concrete 3-controlled X implementation). But if you have more than 4 qubits you need an ancilla.

n = 5  # number of controls
recursion = QuantumCircuit(n + 1 + 1)  # one for target, one as ancilla
recursion.h(n)  # H on target qubit
recursion.mcx(list(range(n)), n, ancilla_qubits=[n + 1], mode='recursion')
recursion.h(n)  # again H on target qubit
recursion.decompose().draw()

q_0: ──────────────■─────────■───────────────────
                   │         │                   
q_1: ──────────────■─────────■───────────────────
                   │         │                   
q_2: ──────────────■─────────■───────────────────
                   │         │                   
q_3: ──────────────┼────■────┼────■──────────────
                   │    │    │    │              
q_4: ──────────────┼────■────┼────■──────────────
     ┌──────────┐  │  ┌─┴─┐  │  ┌─┴─┐┌──────────┐
q_5: ┤ U2(0,pi) ├──┼──┤ X ├──┼──┤ X ├┤ U2(0,pi) ├
     └──────────┘┌─┴─┐└─┬─┘┌─┴─┐└─┬─┘└──────────┘
q_6: ────────────┤ X ├──■──┤ X ├──■──────────────
                 └───┘     └───┘                 

The v-chain implementation is similar to the $Z$ gate implementations with the Toffolis. Here you need $n - 2$ ancillas, if $n$ is the number of controls.

vchain = QuantumCircuit(n + 1 + n - 2)  # needs n - 2 ancillas
vchain.h(n)  # H on target qubit
vchain.mcx(list(range(n)), n, ancilla_qubits=list(range(n+1, 2*n-1)), mode='v-chain')
vchain.h(n)  # again H on target qubit


q_0: ───────■────────
            │        
q_1: ───────■────────
            │        
q_2: ───────■────────
     ┌───┐┌─┴──┐┌───┐
q_3: ┤ H ├┤0   ├┤ H ├  # if you decompose this you'll see
     └───┘│  X │└───┘  # the exact implementation, try
q_4: ─────┤1   ├─────  # vchain.decompose().decompose().draw()
          └────┘