# Problem definition

I'm implementing a quantum circuit in qiskit for a Szegedy quantum walk, (reference, Fig 21.). It uses two registers of dimension $$N$$ ($$N=3$$) each one. The challenges I'm facing are:

1. Multiple controlled gates (2 and 3 controls and targets like $$H$$, $$R_{y}$$).
2. Hermitian conjugate of an operator (Dagger).
3. Ancilla qubits, that increase the complexity of the circuit.

Here is a main part of the circuit:

For example, we have $$K_{b_{2}}$$ controlled by zero and one controls.

# Main questions

• How do I implement the controlled-dagger operator $$K^{\dagger}_{b_{2}}$$, of operator $$K_{b_2}$$? Does qiskit provide dagger operators of the principal gates? I have a little insight here. Should I apply tdg to all gates in $$K_{b_{2}}$$?

• For multiple-controlled qubits operations, I base the construction of the multiple-controlled gates in the Nielsen&Chuang book, as Toffoli gates. So, we must use ancilla qubits. For $$N$$ controls we use $$N-1$$ ancilla qubits.

• Is the following proposal correct?

# proposition

So, for $$K_{b_{2}}$$, I control individually all the gates as follows, is this approximation correct?

How do I control the $$R_{y}$$ gate? I could not find a Controlled rotation around Y-axis only for Z axis (crz).

# qiskit

I would define for each gate of the above figure, the "compute-copy-uncompute" method here.

def kb2(qw, q0, q1, anc):
qw.ccx(q0[0], q0[1], anc[0])
qw.cry(np.pi/2, anc[0], q1[0])
qw.ccx(q0[0], q0[1], anc[0])
qw.ccx(q0[0], q0[1], anc[0])
qw.ccx(anc[0], q1[0], anc[1])
qw.cry(np.pi/2, anc[1], q1[1])
qw.ccx(anc[0], q1[0], anc[1])
qw.ccx(q0[0], q0[1], anc[0])
qw.ccx(q0[0], q0[1], anc[0])
qw.ccx(anc[0], q1[0], anc[1])
qw.ch(anc[1], q1[1])
qw.ccx(anc[0], q1[0], anc[1])
qw.ccx(q0[0], q0[1], anc[0])

#... and so on

return kb2

q0 = QuantumRegister(3, 'q0')
q1 = QuantumRegister(3, 'q1')
anc = QuantumRegister(2, 'a')

qwcirc = QuantumCircuit(q0, q1, anc)

qwcirc.x(q0[1]) # for 0-control
kb2(qwcirc, q0, q1, anc)
qwcirc.x(q0[1]) #for 0-control

# Matplotlib Drawing
qwcirc.draw(output='mpl')


I think half of the Toffoli's gates may be avoided...but I really hope to start a conversation. Thanks in advance.

## 1 Answer

This is an interesting question here.

How do I implement the controlled-dagger operator $$K^{\dagger}_{b_{2}}$$, of operator $$K_{b_2}$$? Does qiskit provide dagger operators of the principal gates? I have a little insight here. Should I apply tdg to all gates in $$K_{b_{2}}$$?

The dagger operation is quite simple to implement and can be seen as a recursive operation.

The only requirement is that the dagger of each gate in your gateset is also in your gateset. This means that if $$U$$ is a gate in your gateset (i.e. a "primitive" gate), then $$U^\dagger$$ should also be present in your gateset.

If this requirement is checked (and it is checked for IBM gateset, which is the answer to your second question), then here is a pseudo-algorithm using Python syntax implementing a generic dagger operation:

def dagger(quantum_gate):
if quantum_gate in gateset:
return quantum_gate.dagger() # just returning a gate from the gateset.
# else, quantum_gate is a sequence of other quantum gates (primitive or not)
daggerized_gate = []
for gate in reversed(quantum_gate):
daggerized_gate.append(dagger(quantum_gate)) # recursive call
return daggerized_gate


This algorithm is fully-generic: it works for every gates, even for controlled ones, provided the requirement is checked.

For multiple-controlled qubits operations, I base the construction of the multiple-controlled gates in the Nielsen&Chuang book, as Toffoli gates. So, we must use ancilla qubits. For $$N$$ controls we use $$N-1$$ ancilla qubits.

There are several algorithms that implement a generic $$N$$-controlled (controlled by $$N$$ qubits) $$X$$ gate. As far as I know, there are 3 distinct classes:

1. The algorithms requiering $$N-1$$ ancilla qubits as you mention. These algorithms have the best gate-count and circuit-depth complexity.
2. The algorithms requiering only $$1$$ ancilla qubit, at the expense of a bigger gate-count and circuit-depth.
3. Hybrid algorithms between the 2 previous classes: they need more than one ancilla qubit but less than $$N-1$$ and also have a gate complexity between the 2 previous classes.

I don't have links right now, but will edit as soon as possible to provide you links to papers describing algorithms in the 3 previous classes.

Note: if someone has access to some papers, please edit my answer if possible or leave the link in comments.

Is the following proposal correct?

So, for $$K_{b_{2}}$$, I control individually all the gates as follows, is this approximation correct?

How do I control the $$R_{y}$$ gate? I could not find a Controlled rotation around Y-axis only for Z axis (crz).

This is not an approximation: it is 100% correct. Controlling a composed-quantum gate is equivalent to controlling all the gates composing it (may be used recursively).

About the implementation of the $$R_y$$ gate, you can implement it with the circuit given here.

For multiply-controlled $$R_y$$ gates, you can apply this definition recursively.

A quick observation: you can remove the 3rd control from the last 2 $$H$$ gates. If the first 2 controls are verified, the $$H$$ gate will be applied only once to the last qubit, independently of the value of third control-qubit.

• A great answer @sanchayan-dutta.. About the implementation of the controlled-$R_{y}$, I found a reference here implementing it with a cnot and a u3 rotation (y-rotation) is it that simple? How I make this controlled-gate a dagger gate. I think that this is the only gate that is needed daggerized (I see that the Hadamard $H=H^{\dagger}$ ). Jun 17 '19 at 6:11
• The answer you found seems valid. I will correct my answer once I verified it fully. Jun 17 '19 at 6:58
• About inverting the $R_y$ gate, you just have to invert the angle of rotation: if you want to invert an arbitrary rotation, then apply that same rotation but with the inverse angle (i.e. in the other direction). Jun 17 '19 at 7:27
• can you provide any resource for the recursive multiple-controlled $R_{y}$ gates? Jun 17 '19 at 23:54
• Also, any hints about using barriers, should I place a barrier after each controlled-operation? Jun 18 '19 at 0:44