# What is the best way to write a tridiagonal matrix as a linear combination of Pauli matrices?

I'm looking for an algorithm to write an arbitrarily sized tridiagonal matrix as a linear combination of Pauli matrices. The tridiagonal matrix has the form, for example,

$$\begin{pmatrix} 2 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 2 \end{pmatrix}$$

I've been able to do this for a 4X4 matrix (2 Qubit system), but nothing larger. I am building these from fundamental Identity and Pauli matrices.

Any help is appreciated!

• By "construct" do you mean you want a sequence of unitaries that multiply to result in a tridiagonal unitary matrix? Or just some way of expressing the tridiagonal matrix as a sum of Pauli matrices? Jan 7 at 15:58
• One starting point would be the constructions in sections $4.5.1$ and $4.5.2$ in Nielsen & Chuang which show how to obtain an arbitrary unitary using "two-level" unitaries and how to build "two-level" unitaries using CNOT and single-qubit gates, respectively. It's all part of a discussion of universality. Jan 7 at 18:16
• What does "tridiagonal" mean? And what do you mean by "construct" - do you want to generate all/general such matrices, or are you given such a matrix and want to express it using some elementary building blocks (and using what rules)? Jan 8 at 15:21
• @AdamZalcman I recently found that paper. Looking into it now. Thank you! Jan 8 at 16:23
• @forky40 Norbert ... Thanks for your replies .. by "construct" I mean create some general, arbitrary sized, tri-diagonal unitary matrix via a linear combination of Pauli matrices. Jan 8 at 16:26

Summary: There is a solution for expressing a tridiagonal matrix of the form you've provided for arbitrary $$n$$ in terms of Pauli operators using recursion. This procedure is given at the bottom of this answer.

## Expressing a tridiagonal matrix recursively

Writing an $$n$$-qubit tridiagonal matrix in terms of Pauli operators can be done recursively. Ignoring the diagonal component $$I_{2^n}$$ , suppose we have an expression for the off-diagonal elements in the $$n$$-qubit case, $$A_{n} = \sum_{i=0}^{2^{n}-2} \left( |i\rangle \langle i + 1| + |i +1\rangle \langle i | \right) \tag{1}$$

which gives us an expression like $$|0\rangle\langle 1| + |1\rangle \langle 2| + \cdots |2^{n}-2\rangle\langle 2^{n}-1| + h.c. \tag{2}$$ Note how the largest index is just short of $$2^{n}$$ and so modular addition isn't necessary. Now we write

\begin{align} I_2 \otimes A_{n} &= (|0\rangle \langle 0| + |1\rangle\langle 1|) \otimes A_{n}\tag{3} \\&=\sum_{i=0}^{2^{n}-2} \left(|i\rangle \langle i +1| + |i +1\rangle \langle i |\right) + \sum_{i=2^{n}}^{2^{n+1}-2} \left(|i\rangle \langle i +1| + |i+1\rangle \langle i |\right)\tag{4} \\&= A_{n+1} - \left(|2^{n} - 1\rangle \langle 2^n| + |2^n\rangle \langle 2^{n} - 1| \right)\tag{5} \end{align} and so $$$$A_{n+1} = I_2 \otimes A_n + \left(|2^{n} - 1\rangle \langle 2^n| + |2^n\rangle \langle 2^{n}-1|\right) \tag{6}$$$$

In Line $$(4)$$, tensoring $$|1\rangle\langle 1|$$ with the the second sum puts a "1" bit ahead of every bitstring which shifts every index in the summand by $$2^n$$. Then by comparison to $$(1)$$ we see that $$(4)$$ is just $$A_{n+1}$$ missing a single term connecting the two tri-diagonal block submatrices of $$I_2 \otimes A_n$$.

#### Recursion example for $$n=3$$

For example, you've probably already found that the off-diagonal solution for $$n=2$$ is given by \begin{align} A_2 = I\otimes X + \frac{1}{2} (X\otimes X + Y \otimes Y) \dot{=} \begin{pmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0\\ \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{pmatrix} \tag{7} \end{align}

and so its not hard to write out the following and verify Eq. $$(6)$$ \begin{align} A_3 &= \begin{pmatrix} A_2 & 0 \\ 0 & A_2\end{pmatrix} + (|011\rangle \langle 100| + |100\rangle \langle 011|) \tag{8} \end{align}

the second term is the element "left out" by combining the two sums in Eq. $$(4)$$.

### Implementing the recursion using GHZ states

Given the relationship in Eq. $$(6)$$ all we need is a way of writing $$\left(|2^{n}-1\rangle \langle 2^n| + |2^n\rangle \langle 2^{n}-1|\right)$$ on $$n+1$$ qubits. This turns out to be closely related to writing an $$n+1$$-qubit GHZ state in terms of Pauli operators! Intuitively, we know that for a GHZ state $$|\psi\rangle = |0\rangle^{\otimes (n+1)} + |1 \rangle^{\otimes (n+1)}$$, the operator $$|\psi \rangle \langle \psi|$$ has two off diagonal elements: One in the top bottom left and one in the top right of the corresponding matrix. Our strategy will be to permute those two elements towards the center of the matrix. More concretely, define the operator: \begin{align} B_{n+1} = |0\rangle \langle 2^{n+1} - 1| + |2^{n+1} - 1 \rangle \langle 0| = \left(|0\rangle \langle 1|\right)^{\otimes(n+1)} + \left(|1\rangle \langle 0|\right)^{\otimes(n+1 )} \tag{9} \end{align} and so \begin{align} (X \otimes I_{2^{n}})B_{n+1}(X \otimes I_{2^{n}}) &= (X \otimes I_{2^{n}})\left( (|0\rangle \langle 1|)^{\otimes(n+1)} + (|1\rangle \langle 0|)^{\otimes(n+1)}\right) (X \otimes I_{2^{n}}) \tag{10a-c} \\&= \left(|10\cdots 0\rangle \langle 01 \cdots 1| + |01\cdots 1\rangle \langle 10 \cdots 0| \right) \\&= |2^n\rangle \langle 2^{n}-1| + |2^{n}-1\rangle \langle 2^n| \end{align}

Now we can use a result from (Gühne, 2007) which I also derived in another answer: \begin{align} B_n = |0\rangle \langle 1|^{\otimes n} + |1\rangle \langle 0|^{\otimes n} &= \frac{1}{2^{n-1}}\sum_{t=0}^{\lfloor n/2\rfloor} (-1)^t \sum_\pi S_\pi\left(X^{\otimes (n-2t)}\otimes Y^{\otimes 2t}\right) \tag{11} \end{align}

here $$S_\pi$$ represents the operator that permutes $$n$$ subsystems according to a permutation $$\pi: \{1, \dots, n\} \rightarrow \{1, \dots, n\}$$ and the sum runs over all such unique permutations $$\pi$$ on size-$$n$$ sets (see my other answer for additional details). This formula with Eqs. $$(6)$$ and $$(10)$$ therefore allows us to find the complete Pauli decomposition analytically.

#### Complete example for $$n=3$$

In the same answer above I derived the following (from here forwards I'll sometimes use Pauli string notation where e.g. $$XYY = X \otimes Y \otimes Y$$): $$B_3 = \frac{1}{4}(XXX - XYY - YXY - YYX)\tag{12}$$

so we can easily compute \begin{align} (X \otimes I_4) B_3 (X\otimes I_4) = \frac{1}{4}(XXX - XYY + YXY + YYX) \tag{13} \end{align} which probably has a nice closed-form expression like the sum in Eq. $$(11)$$ that you might be able to find using $$XYX = -Y$$. And so the tridiagonal matrix you're looking for with 3 qubits is$$^1$$

\begin{align} 2I_8 - A_3 &=2 I_8 - \left[I_2 \otimes A_2 + (X \otimes I_4) B_3 (X\otimes I_4) \right]\tag{14a-b} \\&= 2 III - \left[IIX + \frac{1}{2}(IXX + IYY) + \frac{1}{4}(XXX - XYY + YXY + YYX)\right] \end{align}

## Summary for arbitrary $$n$$

Putting everything together, the procedure for an $$n$$-qubit matrix of this form is as follows: Using $$A_1 := X$$, you can build $$A_{n}$$ recursively as

$$$$A_n = I_2 \otimes A_{n-1} + (X \otimes I_{2^{n-1}})\left[\frac{1}{2^{n-1}}\sum_{t=0}^{\lfloor n/2\rfloor} (-1)^t \sum_\pi S_\pi\left(X^{\otimes (n-2t)}\otimes Y^{\otimes 2t}\right) \right](X \otimes I_{2^{n-1}})\tag{15}$$$$ and then your matrix is given as $$$$D_n = 2I_{2^n} - A_n \tag{16}$$$$

$$^1$$ The factors of $$2$$ and $$(-1)$$ feel almost right since it seems you're trying to construct a graph Laplacian with nearest neighbor connectivity. However the open boundary conditions make this slightly wrong for elements $$D_{00}$$ and $$D_{2^n-1,2^n-1}$$ which should both be $$1$$. But, it turns out the solution to that problem is also the $$n$$-qubit GHZ state! This time you would want to subtract the diagonal components of the GHZ state from $$D_n$$, which I provide in closed form similar to Eq. $$(11)$$ in my other answer.

• You are an absolute genius. This is exactly what I was looking for! Thank you so much! Jan 9 at 23:35
• No problem, glad you found it useful :) Jan 10 at 0:01
• I was working through your example, and I seem to be having contradictory results for the block coupling term. I was able to recover |011><100| + |100><011| = |3><4| + |4><3| But this is not equal to the RHS term given n=2 in Eq. 6. That term is |2><4| + |4><2| Am I missing something? I am using the convention of |000> = |0>, etc. Jan 10 at 22:07
• You're totally right, I somehow kept writing $2^{n-1}$ when I meant $2^n-1$. I've corrected this in a few places and things should work now. Jan 11 at 1:17
• I don't quite understand what you mean. But I am jumping between notation that labels basis states (for 3 qubits, e.g.) as $|0\rangle, |1\rangle, |2\rangle, \dots, |7\rangle$ and equivalently $|000\rangle, |001\rangle, |010\rangle, \dots, |111\rangle$. The notation $|a\rangle\langle b|^{\otimes 3} = |a\rangle \langle b| \otimes |a\rangle \langle b| \otimes |a\rangle \langle b| = |aaa\rangle \langle bbb|$ is also maybe a bit sloppy, so I'll make an edit to clarify Jan 13 at 17:53