# How to calculate a matrix difference in a quantum circuit in the form $A - BAB$

In quantum circuits, every gate is a unitary, and these gates get multiplied together. For example, a simple circuit that performs $$X$$ on the least significant qubit (i.e., $$I \otimes X$$), and $$CNOT$$ on both qubits after would look like this:

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}$$

But say I wanted to include, instead of the multiplication of CNOT and X, the difference between them. This is not possible without computing the difference beforehand.

But in my case, my difference takes the form of $$A - BAB$$, where $$A$$ is matrix 1, and $$B$$ is matrix 2. $$A$$ is diagonal, and $$B$$ is hermitian and $$1-sparse$$, meaning it has one entry per row and per column, and each entry is $$1$$.

Is there any way to implement my specific case?

I tried noting that $$BB = I$$, where $$I$$ is the identity matrix. So, $$A - BAB = ABB - BAB = (AB - BA)B$$. From this, we can go to $$(AB - BA)B = (A^TB^T - BA)B$$ as both $$A$$ and $$B$$ are hermitian. This equals $$((BA)^T - BA)B$$. But I can't seem to get anywhere else with this.

For the sake of clarity, let us first consider the simple example introduced at the start of the question, and then we shall discuss the actual problem that motivated this question.

We want to apply the operator $$C_{1}X_{0} - I_{1} \otimes X_{0}$$, where "0" ("1") labels the least (most) significant qubit. Notice that the matrix representation of this operator is not unitary:

$$C_{1}X_{0} - I_{1} \otimes X_{0} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} - \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & -1 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$.

Hence, it is not possible to directly implement this operation on quantum hardware. Nevertheless, this operator can be expressed as a linear combination $$U_1 - U_2$$ of two unitary operators $$U_1 \equiv C_{1}X_{0}$$ and $$U_2 \equiv I_{1} \otimes X_{0}$$. We can explore such decomposition to implement its action on a given input two-qubit state $$|\psi \rangle$$ in a probabilistic way as follows.

We introduce an ancillary qubit initialized in the fiducial state $$|0 \rangle$$. Then, we apply a Hadamard gate to such ancilla to obtain $$\frac{1}{\sqrt{2}}(|0 \rangle + |1 \rangle) \otimes |\psi \rangle$$. Then, we apply the controlled-$$U_1$$ triggered by the ancilla in state $$|0 \rangle$$ and the controlled-$$U_2$$ triggered by the ancilla in state $$|1 \rangle$$, which produces $$\frac{|0 \rangle}{\sqrt{2}} \otimes U_1 |\psi \rangle + \frac{|1 \rangle}{\sqrt{2}} \otimes U_2 |\psi \rangle$$. Then, we apply the Hadamard gate to the ancilla to obtain $$\frac{|0 \rangle}{2} \otimes (U_1 + U_2) |\psi \rangle + \frac{|1 \rangle}{2} \otimes (U_1 - U_2) |\psi \rangle$$. Hence, upon measuring the ancilla in the computational basis and retrieving the trials that yield the outcome $$|1 \rangle$$, we obtain the desired state (up to a normalization constant). For concreteness, the quantum circuit for the particular example considered here is the following.

This is the simplest example of the so-called Linear Combination of Unitaries (LCU) method, which was introduced by Andrew Childs and Nathan Wiebe within the context of the Hamiltonian simulation problem. A clear description of this method can be found in Section VIII of this paper.

We can also apply the LCU method to obtain $$(A - BAB) |\psi \rangle$$ provided that we express $$A - BAB$$ as a linear combination of unitaries. Given that $$A$$ is diagonal, assuming that its nonzero entries are all real-valued, then $$A$$ is Hermitian, like $$B$$. Hence, $$A - BAB$$ is itself Hermitian, in which case it can be expressed as a linear combination of Pauli operators. Of course, the LCU method is only efficient if the number of terms in the linear combination is not too large, so it could be that a decomposition in another basis is more efficient, as generally the Pauli basis can give rise to $$4^n$$ terms, where $$n$$ is the number of qubits.