3
$\begingroup$

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:

circuit

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

This is the K_{b_{2} without dagger}

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?

K_{b_{2}}

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.

$\endgroup$
2
$\begingroup$

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?

K_{b_{2}}

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.

Implementation of the controlled-Ry gate

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.

$\endgroup$
  • $\begingroup$ 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}$ ). $\endgroup$ – German Alamilla Jun 17 at 6:11
  • $\begingroup$ The answer you found seems valid. I will correct my answer once I verified it fully. $\endgroup$ – Nelimee Jun 17 at 6:58
  • 1
    $\begingroup$ 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). $\endgroup$ – Nelimee Jun 17 at 7:27
  • $\begingroup$ can you provide any resource for the recursive multiple-controlled $R_{y}$ gates? $\endgroup$ – German Alamilla Jun 17 at 23:54
  • $\begingroup$ Also, any hints about using barriers, should I place a barrier after each controlled-operation? $\endgroup$ – German Alamilla Jun 18 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.