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: Schematic of the action of the matrices, H0, H1, H2 for n=3.

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 H1 using 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!


1 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:

Rewritten circuit

Which is equivalent to this:

Rewritten circuit

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.

  • $\begingroup$ Thanks a lot for your answer! Yes I now see that $H_2$ is not so difficult given $H_1$. I have since found some papers that show that this can be achieved in O(n^2) gates, however, I think the prefactors are pretty large. Once I have worked this out properly I will add an answer (with references) but will be happy to accept yours. $\endgroup$
    – as2457
    Apr 2, 2019 at 20:17
  • $\begingroup$ @as2457 The incrementer from the factoring paper I mentioned only need O(n) gates, even with no workspace. You definitely don't need O(n^2) gates. $\endgroup$ Apr 2, 2019 at 22:26
  • $\begingroup$ It seems that the post that you gave a link to still requires ancilla bits. I should have specified that I don't want to use any. It appears they show how to implement an increment in O(n) with a single ancilla and how to implement a $C_n(X)$ with O(n) and no ancilla. $\endgroup$
    – as2457
    Apr 4, 2019 at 12:47
  • $\begingroup$ @as2457 Read the next post in that series, or read the paper. $\endgroup$ Apr 4, 2019 at 14:04
  • $\begingroup$ Thanks a lot for your help! I now realise that one way to solve it is to decompose the increment on $n$ qubits as a single $C_n(X)$ and an increment on $n-1$ qubits. I can then use the O(n) solution for the first, and the O(n)+ancilla solution for the second. $\endgroup$
    – as2457
    Apr 5, 2019 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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