Implementing these $N×N$ matrices on $\log N$ qubits

Question

Consider $n$ qubits and the $N=2^n$ states that I label \begin{equation} |k \rangle = \sum_{i=0}^{n-1} 2^i q_i, \end{equation} i.e. $|q_{n-1}\cdots q_0 \rangle \rightarrow |k\rangle$, where $q_j \in \{0,1\}$. That is I label the binary string of qubits by its decimal value.

I then want to find quantum circuits implementing three $N\times N$ matrices: \begin{equation} \begin{aligned} H_0 &= -\frac{1}{2} \sum_{k=0}^{N-1} |2j\rangle \langle 2j+1| - |2j+1\rangle\langle 2j|, \\ H_1 &= -\frac{1}{2} \sum_{k=0}^{N-1} |2j+1\rangle \langle 2j+2| - |2j+2\rangle\langle 2j+1|,\\ H_2 &= -\frac{1}{2} \sum_{k=0}^{N-1} |2j\rangle \langle 2j+3| - |2j+3\rangle\langle 2j|, \end{aligned} \end{equation} where the values are all modulo $N$. Pictorially this is:

I want to find efficient implementations using only CNOTs and single qubit gates. By efficient I mean that I want the lowest CNOT gate count possible.

The first of these can be solved quite easily and is given by \begin{equation} H_0 = 1_{n-1} \otimes (iY_0), \end{equation} where $1_{n-1}$ is the identity on qubits 1 to $n-1$ and $Y_0$ is the Y-Pauli operator on qubit 0.

I can also find $H_1$ using the incrementer However, this uses gates with many controls. I am wondering, due to the symmetry, is it possible to significantly reduce the number of CNOTs to implement this circuit.

I currently have no idea how to tackle $H_2$. Any solution for these matrices, and or tips, references etc. would be greatly appreciated!

Answer 1

Basically your three operations are, for each even $k$, do an interaction with $k+1+2j$ for some $j$. For $H_0$ the value of $j$ is $0$. For $H_1$ the value of $j$ is $-1$. For $H_2$ the value of $j$ is $1$. I'm going to define $G_{-1} = H_1$, $G_0 = H_0$, $G_1 = H_2$ so that the indices match the value of $j$.

The way to implement $G_k$ is by applying a $-k$ operation to all qubits except the least significant qubit, but using the least significant qubit as a control, then applying your mixing operation to the least significant qubit, then uncomputing the offset by applying a $+k$ operation to all qubits except the least significant qubit.

(You incremented the whole register instead of performing a controlled increment of part of the register. This just happens to be equivalent, modulo that last NOT gate on the control, because of how the increment circuit is built.)

In other words, $H_2$ is implemented in the same way as $H_1$ except you decrement instead of incrementing.

---

To optimize the circuit, you can use a more efficient linear-cost increment circuit such as the one explained in "Factoring with n+2 clean qubits and n-1 dirty qubits".

Alternatively, you can use the fact that $+k \equiv \text{QFT} \cdot \text{GRAD}^k \cdot \text{QFT}^\dagger$ where $\text{QFT}$ is the quantum fourier Transform and $\text{GRAD}_n^k = \sum_{j=0}^{2^n-1} |j\rangle\langle j| e^{i j \pi / 2^n} = \otimes_{j=0}^{n-1} Z_j^{k/2^j}$ is the phase gradient operation (see "Addition on a Quantum Computer"). This allows you to rework $H_1$ and $H_2$ into the following sort of form:

Which is equivalent to this:

Which still has two increments, but they are slightly smaller. I suspect there is a way to merge these two increments into one single addition.