Realizing a swap gate using a commutator sequence and an auxiliary qudit

Question

Say I have two qudits $1$ and $2$, each of which has Hilbert space of dimension $m$. Is it possible to introduce an auxiliary qudit $a$ (of any dimension $d_a\in \mathbb{Z}_{\geq 2}$) and find quantum gates $U,V$ such that the following quantum circuit equation holds $$ U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}=\Pi_{12} I_a$$ where $U,U^{-1}$ act on qudits $1,a$ while $V, V^{-1}$ act on qudits $2,a$, $\Pi_{12}$ is the swap gate on $1,2$ and $I_a$ is the identity operator on $a$. Note that $U^{-1}=U^\dagger, V^{-1}=V^\dagger$ (unitarity). The quantum circuit diagram looks like this:

I feel the answer is no (for any $m>1$), but can't prove it.

---

Update: I initially tried to prove that this is impossible by proving a stronger statement (see here for details): whenever we have $ U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}=S_{12} I_a$, we must have $S_{12}$ proportional to identity. But this conjecture is wrong--a counterexample has been constructed where $m=d_a=2$, $U,V,S$ are CNOT gates (suitably rotated, see here). So a CNOT gate can be represented as a commutator like this. Whether this is possible for SWAP gate remains open.

Answer 1

TL;DR: Desired $U$ and $V$ do not exist. We exploit the fact that $\Pi_{12}I_a$ sends product states to product states to show that $U$ and $V$ send the input qudit states into two subsystems in a subspace of the Hilbert space of the ancilla. We call them the exchange subsystem and the backup subsystem. Next, we show that $U$ and $V$ act as even permutations on the four-fold product states of the two qudits and the two ancilla subsystems. This leads to a contradiction with the fact that $\Pi_{12}I_a$ acts as an odd permutation on such states.

Independence

First note that the two middle gates $V_{2a}^{-1}U_{1a}$ perform the portion of the desired swap operation that sends the state of the first qudit to the second qudit. More precisely, $V_{2a}^{-1}U_{1a}$ sends any state of the form $|\psi_1\rangle|\phi_{2a}\rangle$ to a state of the form $|\chi_{1a}\rangle|\psi_2\rangle$ where Greek letters identify the states and subscripts identify subsystems.

Moreover, $|\chi\rangle$ is independent of $|\psi\rangle$. To see this, assume the contrary, i.e. $$ V_{2a}^{-1}U_{1a}|\psi_1\rangle|\phi_{2a}\rangle=|\chi(\psi)_{1a}\rangle|\psi_2\rangle\tag1 $$ where we use parenthesis to signify dependence of $|\chi\rangle$ on $|\psi\rangle$. If we apply $V_{2a}^{-1}U_{1a}$ to a product state where the first qudit is in superposition $(|\psi_1\rangle+|\psi'_1\rangle)|\phi_{2a}\rangle$ then we get $$ V_{2a}^{-1}U_{1a}(|\psi_1\rangle+|\psi'_1\rangle)|\phi_{2a}\rangle = |\chi(\psi)_{1a}\rangle|\psi_2\rangle+|\chi(\psi')_{1a}\rangle|\psi'_2\rangle\tag2 $$ where the second qudit is entangled with the composite system of the first qudit and the ancilla. However, after these two gates no more interactions occur between the second qudit and the other systems and the full sequence $U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}$ ends up sending a product state to an entangled state. Therefore, we conclude that $|\chi\rangle$ does not depend on $|\psi\rangle$ and we may rewrite $(1)$ as $$ V_{2a}^{-1}U_{1a}|\psi_1\rangle|\phi_{2a}\rangle=|\chi_{1a}\rangle|\psi_2\rangle.\tag{1'} $$

Exchange subsystem

Now, consider the state $|\mu_{12a}\rangle=U_{1a}|\psi_1\rangle|\phi_{2a}\rangle=V_{2a}|\chi_{1a}\rangle|\psi_2\rangle$ in the middle between $V_{2a}^{-1}$ and $U_{1a}$ in equation $(1')$. The reduced state of the first qudit is $$ \begin{align} \rho_1&=\mathrm{tr}_{2a}(|\mu_{12a}\rangle\langle\mu_{12a}|)\\ &=\mathrm{tr}_{2a}(V_{2a}|\chi_{1a}\rangle|\psi_2\rangle\langle\psi_2|\langle\chi_{1a}|V_{2a}^\dagger)\\ &=\mathrm{tr}_a(|\chi_{1a}\rangle\langle\chi_{1a}|)\tag3 \end{align} $$ and similarly the state of the second qudit is $$ \begin{align} \rho_2&=\mathrm{tr}_{1a}(|\mu_{12a}\rangle\langle\mu_{12a}|)\\ &=\mathrm{tr}_{1a}(U_{1a}|\psi_1\rangle|\phi_{2a}\rangle\langle\phi_{2a}|\langle\psi_1|U_{1a}^\dagger)\\ &=\mathrm{tr}_a(|\phi_{2a}\rangle\langle\phi_{2a}|)\tag4 \end{align} $$ both of which are independent of $|\psi\rangle$. Thus, the state $|\psi\rangle$ has been fully transferred into a subsystem in a subspace of the Hilbert space $\mathcal{H}_a$ of the ancilla. In other words, $$ |\mu_{12a}\rangle=|\upsilon_{12r}\rangle\otimes|\psi_x\rangle\tag5 $$ for some subsystems $r$ and $x$ in a subspace of $\mathcal{H}_a$. See no-hiding theorem for more details about this step in the argument. We can make the subsystems explicit by writing $\mathcal{H}_a$ as the direct sum $$ \mathcal{H}_a=\mathcal{H}_r\otimes\mathcal{H}_x\oplus\mathcal{H}_{pad}\tag6 $$ where $\mathcal{H}_x$ describes the subsystem into which $U_{1a}$ sends the state of the first qudit, $\mathcal{H}_r$ is the subsystem that $U_{1a}$ may entangle with the first qudit and $\mathcal{H}_{pad}$ is a "padding" subspace of dimensions unused by $\mathcal{H}_r\otimes\mathcal{H}_x$. Some dimensions will go unused for example when $d_a$ is not an integer multiple of $m$. Note that by linearity the amplitudes in $\mathcal{H}_{pad}$ are zero, so $(5)$ may be written as $$ |\mu_{12a}\rangle=|\upsilon_{12r}\rangle\otimes|\psi_x\rangle+0_{pad}.\tag{5'} $$

Also note that the tensor product structure in $(6)$ is independent of any pre-existing tensor product structure that the ancilla may have. Instead, the structure in $(6)$ is defined by the action of the gates $U$ and $V$ on a given input. Namely, $\mathcal{H}_x$ is precisely the subsystem into which $U$ sends the state of the first qudit and from which $V$ picks it up before sending it to the second qudit. For this reason, we'll call any such $\mathcal{H}_x$ an exchange subsystem. Note that in general $\mathcal{H}_x$ depends on the input states, but the gates $U$ and $V$ necessarily agree on where the exchange subsystem is within the Hilbert space of the ancilla.

Finally, note that $(6)$ indicates that $U$ and $V$ are not necessarily swap gates or a composition of swap gates with product unitaries. Indeed, the labels on the state $|\upsilon_{12r}\rangle$ indicate that both gates may create entanglement between a qudit and the ancilla. However, the independence argument above shows that no entanglement is created between a qudit and the exchange subsystem.

Backup subsystem

Let us now consider the action of the first and fourth gates. The above arguments have shown that $U_{1a}$ sends the state of the first qudit into an exchange subsystem $\mathcal{H}_x$ and $V_{2a}^{-1}$ sends the state of the exchange subsystem $\mathcal{H}_x$ into the second qudit. Consequently, $V_{2a}$ sends the state of the second qudit into an exchange subsystem $\mathcal{H}_{x'}$ and $U_{1a}^{-1}$ sends the state of the exchange subsystem $\mathcal{H}_{x'}$ into the first qudit.

Thus, to complete the swap, $V_{2a}^{-1}U_{1a}$ must act as identity on $\mathcal{H}_{x'}$. In the very middle of the circuit the exchange subsystem $\mathcal{H}_x$ is in state $|\psi_x\rangle$ which is independent of the initial state $|\omega_2\rangle$ of the second qudit. Since $V_{2a}^{-1}$ doesn't act on the first qudit and $U_{1a}$ doesn't act on the second qudit, $|\omega\rangle$ is transferred into a subsystem within $\mathcal{H}_a$, necessarily different from $\mathcal{H}_x$. Call it the backup subsystem and denote its Hilbert space with $\mathcal{H}_b$. Thus, we can rewrite equation $(6)$ as $$ \mathcal{H}_a=\mathcal{H}_{r'}\otimes\mathcal{H}_b\otimes\mathcal{H}_x\oplus\mathcal{H}_{pad}\tag{6'} $$ where $\mathcal{H}_{r'}$ is the residual subsystem which, like $\mathcal{H}_r$ earlier, may become temporarily entangled with the first and second qudit. As was the case with the exchange subsystem earlier, the backup subsystem is defined by the action of $U$ and $V$ and depends on the input states. Also, we can rewrite $(5')$ as $$ |\mu_{12a}\rangle=|\upsilon_{12r'}\rangle\otimes|\omega_b\rangle\otimes|\psi_x\rangle+0_{pad}\tag{5''} $$ which shows that in the middle of the circuit the states of the first and second qudits are sent unentangled through the exchange and backup subsystems of the ancilla.

$U$ and $V$ gates explicitly

The definitions of the exchange and backup subsystems hide irrelevant details of the action of $U$ and $V$ on the ancilla and enable us to write it down in a simple form. Namely, $$ U_{1a}|\psi_1\rangle|\alpha_b\rangle|\beta_x\rangle = |\alpha_1\rangle|\beta_b\rangle|\psi_x\rangle\\ V_{2a}|\omega_2\rangle|\alpha_b\rangle|\beta_x\rangle = |\alpha_2\rangle|\beta_b\rangle|\omega_x\rangle.\tag8 $$ For clarity, we have omitted the residual subsystem since it doesn't play active role in the computation. The only constraint that the original gate equation $U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}=\Pi_{12}I_a$ imposes on the actions of $U$ and $V$ on the residual subsystem is that these actions must combine to give the identity. Note however that $U$ and $V$ may temporarily entangle the two qudits with the residual subsystem. Thus, the equation $(8)$ must not be interpreted as precluding entanglement formation by $U$ and $V$.

Contradiction

We have seen that the equation $U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}=\Pi_{12}I_a$ implies that $U_{1a}$ acts as an even permutation on product states built from states in $\mathcal{H}_1$, $\mathcal{H}_b$ and $\mathcal{H}_x$ and that $V_{2a}$ acts as an even permutation on product states built from states in $\mathcal{H}_2$, $\mathcal{H}_b$ and $\mathcal{H}_x$ where $\mathcal{H}_1$ and $\mathcal{H}_2$ denote the Hilbert spaces of the first and second qudit, respectively. Therefore, the permutation resulting from the application of all four gates is also even. However, $\Pi_{12}I_a$ acts as odd permutation on such states. The contradiction means that $$ U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}\ne\Pi_{12}I_a\tag9 $$ for all $U$ and $V$.

Answer 2

What if Your $V$ matrix is just a swap gate and Your $U$ is swap gate controlled by the fact that the second bit has value $\neg a$?

Answer 3

I'll give an alternative proof to the one presented by @Adam Zalcman. The final conclusion is that if the auxiliary space dimension $d_a$ is finite, then the equation $U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}=\Pi_{12} I_a$ cannot hold for any invertible matrices $U,V$ (even for non-unitary ones). However, if $d_a$ is allowed to be infinite, then there exist unitary solutions to this equation.

---

Proof that there is no solution for any finite $d_a$

Assume the opposite, that there exists invertible matrices $U,V$ satisfying $U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}=\Pi_{12} I_a$, or equivalently, $U_{1a}V_{2a}=V_{2a}U_{1a}\Pi_{12}$. Denote by $\mathcal{A}\equiv \mathcal{X}\otimes \mathcal{X}\otimes \mathcal{Y}$ the algebra of operators on the product space, where $\mathcal{X}=M_m(\mathbb{C})$, and $\mathcal{Y}=M_{d_{a}}(\mathbb{C})$. Let $u_{1a},v_{2a},\pi_{12}\in\mathrm{Aut}(\mathcal{A})$ denote the automorphisms of the algebra $\mathcal{A}$ defined as $u_{1a}(A)=U_{1a}AU_{1a}^{-1}$, $v_{2a}(A)=V_{2a}AV_{2a}^{-1}$, and $\pi_{12}(A)=\Pi_{12}A \Pi_{12}^{-1},\forall A\in\mathcal{A}$ [note that $\pi_{12}$ just swaps the tensor factors $\pi_{12}(x\otimes x'\otimes y)=x'\otimes x\otimes y$]. Then $U_{1a}V_{2a}=V_{2a}U_{1a}\Pi_{12}$ leads to $$u_{1a}v_{2a}=v_{2a}u_{1a}\pi_{12},\tag{1}$$ both sides regarded as elements of the group $\mathrm{Aut}(\mathcal{A})$.

For any $X\in \mathcal{X}$, we use $X_1$ to denote $X\otimes I\otimes I\in \mathcal{A}$ and similarly for $X_2$. Applying Eq.(1) to $X_1$, we get $u_{1a}(X_1)=v_{2a}(X_2)$. We now use induction to prove that $u_{1a}^n(X_1)=v_{2a}^n(X_2), \forall n\in \mathbb{Z}_{\geq 1}$. Assume that $u_{1a}^k(X_1)=v_{2a}^k(X_2)$ for $k\leq n-1$. The LHS belongs to $\mathcal{X}\otimes I\otimes \mathcal{Y}$ while the RHS belongs to $I\otimes \mathcal{X}\otimes \mathcal{Y}$, so the equality implies that both $u^k_{1a}(X_1)$ and $v^k_{2a}(X_2)$ must belong to their intersection $I\otimes I\otimes \mathcal{Y}$ for all $X\in \mathcal{X}, k\leq n-1$, so both are left invariant by $\pi_{12}$. Then for $k=n$ we have \begin{eqnarray} u_{1a}^n(X_1)&=&u_{1a} v_{2a}^{n-1}(X_2)\\ &=&v_{2a}u_{1a}\pi_{12} v_{2a}^{n-2}(X_2)\\ &=&v_{2a}u_{1a} v_{2a}^{n-2}(X_2)\\ &=&v_{2a}u_{1a}^{n-1}(X_1)\\ &=&v_{2a}^{n}(X_2), \end{eqnarray} where we applied the induction assumption on the first, fourth, and last lines.

Therefore $u^n_{1a}(X_1)\in I\otimes I\otimes \mathcal{Y}$ for all $X\in \mathcal{X}, n\in \mathbb{Z}_{\geq 1}$. Now take any nontrivial (i.e. not proportional to the identity) $X\in\mathcal{X}$ and consider the sequence $\{u_{1a}^n(X_1)\}_{n\in \mathbb{Z}_{\geq 1}}$. Since $\mathcal{Y}=M_{d_{a}}(\mathbb{C})$ is a finite dimensional algebra, the set $\{u_{1a}^n(X_1)| n\in \mathbb{Z}_{\geq 1}\}$ must be linearly dependent. Let $n_0$ be the smallest integer such that $$u_{1a}^{n_0}(X_1)=\sum^{n_0-1}_{k=1}\lambda_k u_{1a}^k(X_1)\tag{2}$$ for some $\lambda_{1},\ldots,\lambda_{n_0-1}$. Applying $u^{-1}_{1a}\in\mathrm{Aut}(\mathcal{A})$ on both sides of Eq.(2), we get $$\mathcal{X}\otimes I\otimes I\ni\lambda_1 X_1=-u_{1a}^{n_0-1}(X_1)+\sum^{n_0-1}_{k=2}\lambda_k u_{1a}^{k-1}(X_1)\in I\otimes I\otimes \mathcal{Y},\tag{3}$$ so $\lambda_1 X_1\in \mathcal{X}\otimes I\otimes I\cap I\otimes I\otimes \mathcal{Y} =\{\lambda I|\lambda\in\mathbb{C}\}$, implying $\lambda_1=0$ since $X$ is assumed to be nontrivial. But then Eq.(3) means that the set $\{u_{1a}^k(X_1)| 1\leq k\leq n_0-1\}$ is linearly dependent, contradicting the minimality of $n_0$.

---

Construction of a unitary solution for infinite $d_a$

As shown in the figure below, we use an open circle to denote a qudit with Hilbert space dimension $m$. Let the auxiliary space $a$ be the Hilbert space of three semi-infinite chains of qudits (the collection of all open circles except $1,2$). Let $U_{1a}$ be the unitary translation operator which translates the states of qudits along the blue arrows while leaving all other qudits invariant, and similarly $V_{1a}$ translates the states of qudits along the red arrows while leaving all other qudits invariant. Then it is straightforward to check that this construction satisfy the equation $U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}=\Pi_{12} I_a$. I'm yet unable to firgure out how this construction avoids the arguments of @Adam Zalcman (I guess that proof must implicitly assume finite-dimensionality somewhere).