Implementing these $N×N$ matrices on $\log N$ qubits - Quantum Computing Stack Exchange most recent 30 from quantumcomputing.stackexchange.com 2019-12-12T19:44:33Z https://quantumcomputing.stackexchange.com/feeds/question/5801 https://creativecommons.org/licenses/by-sa/4.0/rdf https://quantumcomputing.stackexchange.com/q/5801 2 Implementing these $N×N$ matrices on $\log N$ qubits as2457 https://quantumcomputing.stackexchange.com/users/6076 2019-03-29T12:44:46Z 2019-03-29T19:39:11Z <p>Consider <span class="math-container">$n$</span> qubits and the <span class="math-container">$N=2^n$</span> states that I label <span class="math-container">\begin{equation} |k \rangle = \sum_{i=0}^{n-1} 2^i q_i, \end{equation}</span> i.e. <span class="math-container">$|q_{n-1}\cdots q_0 \rangle \rightarrow |k\rangle$</span>, where <span class="math-container">$q_j \in \{0,1\}$</span>. That is I label the binary string of qubits by its decimal value.</p> <p>I then want to find quantum circuits implementing three <span class="math-container">$N\times N$</span> matrices: <span class="math-container">\begin{equation} \begin{aligned} H_0 &amp;= -\frac{1}{2} \sum_{k=0}^{N-1} |2j\rangle \langle 2j+1| - |2j+1\rangle\langle 2j|, \\ H_1 &amp;= -\frac{1}{2} \sum_{k=0}^{N-1} |2j+1\rangle \langle 2j+2| - |2j+2\rangle\langle 2j+1|,\\ H_2 &amp;= -\frac{1}{2} \sum_{k=0}^{N-1} |2j\rangle \langle 2j+3| - |2j+3\rangle\langle 2j|, \end{aligned} \end{equation}</span> where the values are all modulo <span class="math-container">$N$</span>. Pictorially this is: <a href="https://i.stack.imgur.com/Zh2Uh.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Zh2Uh.png" alt="Schematic of the action of the matrices, H0, H1, H2 for n=3."></a></p> <p>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.</p> <p>The first of these can be solved quite easily and is given by <span class="math-container">\begin{equation} H_0 = 1_{n-1} \otimes (iY_0), \end{equation}</span> where <span class="math-container">$1_{n-1}$</span> is the identity on qubits 1 to <span class="math-container">$n-1$</span> and <span class="math-container">$Y_0$</span> is the Y-Pauli operator on qubit 0.</p> <p>I can also find <span class="math-container">$H_1$</span> using the incrementer <a href="https://i.stack.imgur.com/9n3S5.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9n3S5.png" alt="H1 using incrementer"></a> 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.</p> <p>I currently have no idea how to tackle <span class="math-container">$H_2$</span>. Any solution for these matrices, and or tips, references etc. would be greatly appreciated!</p> https://quantumcomputing.stackexchange.com/questions/5801/implementing-these-n%c3%97n-matrices-on-log-n-qubits/5802#5802 2 Answer by Craig Gidney for Implementing these $N×N$ matrices on $\log N$ qubits Craig Gidney https://quantumcomputing.stackexchange.com/users/119 2019-03-29T14:04:33Z 2019-03-29T14:14:49Z <p>Basically your three operations are, for each even <span class="math-container">$k$</span>, do an interaction with <span class="math-container">$k+1+2j$</span> for some <span class="math-container">$j$</span>. For <span class="math-container">$H_0$</span> the value of <span class="math-container">$j$</span> is <span class="math-container">$0$</span>. For <span class="math-container">$H_1$</span> the value of <span class="math-container">$j$</span> is <span class="math-container">$-1$</span>. For <span class="math-container">$H_2$</span> the value of <span class="math-container">$j$</span> is <span class="math-container">$1$</span>. I'm going to define <span class="math-container">$G_{-1} = H_1$</span>, <span class="math-container">$G_0 = H_0$</span>, <span class="math-container">$G_1 = H_2$</span> so that the indices match the value of <span class="math-container">$j$</span>.</p> <p>The way to implement <span class="math-container">$G_k$</span> is by applying a <span class="math-container">$-k$</span> 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 <span class="math-container">$+k$</span> operation to all qubits except the least significant qubit.</p> <p>(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.)</p> <p>In other words, <span class="math-container">$H_2$</span> is implemented in the same way as <span class="math-container">$H_1$</span> except you decrement instead of incrementing.</p> <hr> <p>To optimize the circuit, you can use <a href="https://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html" rel="nofollow noreferrer">a more efficient linear-cost increment circuit</a> such as the one explained in <a href="https://arxiv.org/abs/1706.07884" rel="nofollow noreferrer">"Factoring with n+2 clean qubits and n-1 dirty qubits"</a>.</p> <p>Alternatively, you can use the fact that <span class="math-container">$+k \equiv \text{QFT} \cdot \text{GRAD}^k \cdot \text{QFT}^\dagger$</span> where <span class="math-container">$\text{QFT}$</span> is the quantum fourier Transform and <span class="math-container">$\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}$</span> is the phase gradient operation (see <a href="https://arxiv.org/abs/quant-ph/0008033" rel="nofollow noreferrer">"Addition on a Quantum Computer"</a>). This allows you to rework <span class="math-container">$H_1$</span> and <span class="math-container">$H_2$</span> into the <a href="https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22X%22%5D%2C%5B%22Z%22%2C%22QFT4%22%5D%2C%5B%22%E2%80%A2%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B1%2C%22Z%5E-%E2%85%9B%22%2C%22Z%5E-%C2%BC%22%2C%22Z%5E-%C2%BD%22%2C%22Z%22%5D%2C%5B1%2C%22QFT%E2%80%A04%22%5D%5D%7D" rel="nofollow noreferrer">following sort of form</a>:</p> <p><a href="https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22X%22%5D%2C%5B%22Z%22%2C%22QFT4%22%5D%2C%5B%22%E2%80%A2%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22Z%22%5D%2C%5B1%2C%22Z%5E-%E2%85%9B%22%2C%22Z%5E-%C2%BC%22%2C%22Z%5E-%C2%BD%22%2C%22Z%22%5D%2C%5B1%2C%22QFT%E2%80%A04%22%5D%5D%7D" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/eicKm.png" alt="Rewritten circuit"></a></p> <p>Which is equivalent to this:</p> <p><a href="https://i.stack.imgur.com/3gNWz.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/3gNWz.png" alt="Rewritten circuit"></a></p> <p>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.</p>