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:

enter image description here

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.

  • $\begingroup$ @MarkS Thanks for the comment. I edited and clarified (1),(3); answer to (2) is yes, identical means the same dimension; for (4), my premature analysis on the classical version of this problem (where $U,V$ are just classical invertible two bit gates) seems to suggest that $d_a\geq m^2$ and $m$ divides $d_a$: $m|d_a$. Also, taking determinant on both sides gives the restriction that $d_a m(m-1)/2$ must be even. $\endgroup$
    – Lagrenge
    Commented Nov 30, 2022 at 4:12
  • $\begingroup$ Would you also be interested in a solution that leaves a residual unitary transformation on the ancilla? IOW, one where $U_{1a}^{-1}V_{2a}^{-1}U_{1a}V_{2a}=\Pi_{12} W_a$ for some $W_a$ not equal to identity? $\endgroup$ Commented Dec 4, 2022 at 18:01
  • $\begingroup$ @AdamZalcman No, in my application the right-hand side has to be identity on $a$. $\endgroup$
    – Lagrenge
    Commented Dec 4, 2022 at 18:19

3 Answers 3


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.


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$.


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$.

  • $\begingroup$ @Lagrenge There is an issue in this proof that requires clarification and which I've been wondering about on and off, but which I haven't resolved yet. Note that the backup and exchange subsystems aren't fixed since they depend on input and gate. There are just a few points where they have to "line up" to make the swap work. The issue is that we need to show that the movement of the two subsystems as we apply the four gates isn't contributing a "hidden" transposition that could make the overall permutation of the LHS odd. $\endgroup$ Commented Dec 14, 2022 at 6:29
  • $\begingroup$ Also, a minor issue is that there could be additional subsystems that $U$ and $V$ are permuting so the permutation due to any one gate may be actually odd. Still, the permutation due to all four will be even. $\endgroup$ Commented Dec 14, 2022 at 6:30

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).

enter image description here

  • $\begingroup$ This is very nice! I like this proof better than mine (which glosses over an important issue, see my comment there). In any case, my proof does indeed work only in finite dimensions as it relies on the notion of permutation sign which is only defined for permutations over a finite set. $\endgroup$ Commented Dec 14, 2022 at 6:31
  • $\begingroup$ Interestingly, we can identify the backup and exchange subsystems in the action of $U_{1a}$ and $V_{2a}$ also in your infinite-dimensional example. The exchange subsystem is the one into which $U_{1a}$ sends the state of the first qudit and from which $V_{2a}^{-1}$ picks it up, i.e. it is the leftmost dot in the chain to the right of $1$ and $2$ (here we see the exchange subsystems "line up"). Similarly, the backup subsystems are the rightmost dots of the left chain (here we see that the subsystems don't line up (and indeed they don't need to in this case)). $\endgroup$ Commented Dec 14, 2022 at 6:34

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$?

  • $\begingroup$ Thanks for the answer, but both $U,V$ are required to be two bit gates. $\endgroup$
    – Lagrenge
    Commented Dec 3, 2022 at 14:54
  • $\begingroup$ thats impossible, You said $\Psi_1,\Psi_2$ are qudits $\endgroup$
    – Sezzart
    Commented Dec 4, 2022 at 10:08
  • $\begingroup$ Also, in this case, the swap gate controlled by one of the qudits in swap, is probably just a CNOT gate, or? $\endgroup$
    – Sezzart
    Commented Dec 4, 2022 at 10:31
  • $\begingroup$ I mean, both $U,V$ are required to be two qudit gates. So $U_{1a}$ should act only on $\psi_1,\psi_a$, it should not act on $\psi_2$ and should not depend on $\psi_2$. Put it another way, $U_{1a}$ is required to commute with any quantum gates that acts on $\psi_2$. $\endgroup$
    – Lagrenge
    Commented Dec 4, 2022 at 15:07
  • $\begingroup$ If you think I misunderstood what you mean, could you please just explicitly write down the expressions of $U_{1a}, V_{2a}$? $\endgroup$
    – Lagrenge
    Commented Dec 4, 2022 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.