In the quantum circuit model of quantum computing, we represent a quantum program as a sequence of gates, where each gate is an operation that changes the state of the system.
Although easy to visualize and interpret, this representation of a circuit as a sequence of gates is not unique. Some gates within the sequence can be swapped without changing the operation of the circuit as a whole. Both circuits, before and after the swap, result in the same unitary matrix.
In this post we will find out when that is the case.
Motivation
In mathematical terms, quantum gates commute, at least sometimes. Let’s refer to this as partial-commutativity.
The task of determining whether two quantum circuits are equivalent becomes relevant for example in the context of circuit simplification. If two sequences of quantum gates represent the same unitary operation but one sequence requires fewer gates, the total gate count of a circuit can be reduced by replacing the longer sequence with the shorter one.
If we want to determine whether two circuits are equivalent based on their gates alone, computing the unitary for every possible sequence of gates is costly! We have to take into account that some gates can be swapped.
Some gates commute, others don’t.
Revisiting Commutativity
In high school math, commutativity is usually introduced using addition or multiplication. When adding two numbers, the order of the operands does not matter.
\(a + b = b + a\)This is not the case for all operations, though:
\(a / b ≠ b / a\)In quantum computing, every gate corresponds to a unitary matrix. The operation a circuit as a whole performs can be determined by multiplying the unitary matrices of each of its gates, one after the other.
The question of whether or not two quantum gates commute can therefore be rephrased as under which circumstances do two unitary matrices result in the same product regardless of their order? In other words, when does \(A \times B = B \times A\)?
To answer this question, let’s briefly revisit what a matrix actually does.
Revisiting Matrices
Every matrix is a linear transformation. It maps a point from one vector space to a new point in a different vector space.
The basis of a matrix is a set of vectors that when combined can reach every point in the space spanned by the matrix. Every point within the vector space can be expressed by summing scaled versions of those basis vectors.
What’s special about unitary matrices is that they are guaranteed to possess an eigenbasis. Every point in the space spanned by a unitary matrix can be described as a combination of the eigenvectors of the matrix.
The eigenvectors of a matrix are those vectors that maintain their direction when transformed by a matrix. Aside from a scaling factor \(\lambda\), they remain the same.
\(A\vec{v} = \lambda \vec{v}\)The corresponding scaling factors \(\lambda\) are called the eigenvalues of the matrix.
See Eigenvectors and eigenvalues (3blue1brown) for more details.
Eigendecomposition of a Matrix
Every matrix with an eigenbasis can be rewritten as \(A = T^{-1}DT\), where the T-matrix rewrites/translates an incoming vector into the eigenbasis of the matrix A.
Think of it as a redefinition of what the dimensions within a vector represent.
Usually, we think of a vector \(b = (2, 7)\) in terms of \(2 * (1, 0) + 7 * (0, 1)\), but that does not have to be the case. The basis vectors, here \((1, 0)\) and \((0, 1)\) could just as well be \((1, 1)\) and \((1, -1)\). All we have to do to transform a vector from one basis to another is to determine which its new coefficients.
If we wanted to translate the vector \(b = (2, 7)\) from the “standard”-basis to our new basis of \((1, 1)\) and \((1, -1)\), the new vector would be \(b^*=(4.5, -2.5)\).
A vector expressed in the eigenbasis of a matrix, does not change its direction anymore when multiplied by that matrix. Any eigenvector only gets scaled when applied to the corresponding matrix.
In our case, once the transformation T has been applied, every dimension within our vector corresponds to an eigenvector of A. The individual dimensions within the vector get scaled by the eigenvalue of the eigenvector representing that dimension.
In our representation from above, \(A = T^{-1}DT\), this scaling step takes the form of the diagonal matrix D, a matrix that contains the eigenvalues of the eigenbasis vectors in its diagonal. All other cells in the matrix are 0.
Because we do not want to remain in the eigenbasis of A, in the end, we have to transform our vector back into its original basis. In our decomposition, this step is done by applying the inverse \(T^{-1}\) of our original basis change.
So far, so good. But why should you (or anyone for that manner) care? What does all of that have to do with the question of whether or not two quantum gates commute?
Putting it all together
Each quantum gate corresponds to a unitary matrix. The simulation of a circuit amounts to the matrix multiplication of the matrices of each of its gates. Let A and B be the unitary matrices of two consecutive gates within a circuit.
According to our decomposition from above, the matrix product \(A * B\) can be rewritten as \(T_A^{-1} D_A T_A * T_B^{-1} D_B T_B\). If A and B share an eigenbasis, in other words, \(T_A = T_B = T\), the product of A and B can be further rewritten as \(A * B = T^{-1} D_A T * T^{-1} D_B T\). Because the product of a matrix with its inverse results in the identity matrix, this expression can further be simplified to \(A * B = T^{-1} D_A * D_B T\).
What does this simplified expression represent?
At first, it transforms an incoming vector into the shared eigenbasis of both matrices. Then, we scale each of its dimensions by the corresponding eigenvalues of the matrix B using the diagonal matrix \(D_B\). Afterwards, we perform the same scaling for matrix A using \(D_A\). Finally, we transform the resulting vector back into its original basis using the transformation \(T^{-1}\). The only aspect of this expression that is specific to the matrices A and B are the diagonal matrices \(D_A\) and \(D_B\).
Now the interesting part: All diagonal matrices commute!
Therefore, as long as A and B share a common eigenbasis*, the following equality holds:
\(A * B\) \(= T_A^{-1} D_A T_A * T_B^{-1} D_B T_B\) \(= T^{-1} D_A T * T^{-1} D_B T\) \(= T^{-1} D_A D_B T\) \(= T^{-1} D_B D_A T\) \(= T^{-1} D_B T * T^{-1} D_A T\) \(= T_B^{-1} D_B T_B * T_A^{-1} D_A T_A\) \(= B * A\)As long as two unitary matrices share a common eigenbasis, they commute. In consequence, as long as the unitary matrices of two quantum gates share a common eigenbasis, the gates commute and can be swapped without altering the behavior of the sequence.
Quod erat demonstrandum.
* I chose the wording “share a common eigenbasis”, because a matrix can have more than one eigenbasis. The most important example is the identity matrix. For the identity matrix, any (complete) set of orthogonal vectors can serve as an eigenbasis. Therefore, the identity matrix commutes with all gates.