Implementing a complex circuit for a Szegedy quantum walk in qiskit

Question

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.

Answer 1

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.