# Choi–Jamiołkowski isomorphism

In quantum information theory and operator theory, the Choi–Jamiołkowski isomorphism refers to the correspondence between quantum channels (described by completely positive maps) and quantum states (described by density matrices), this is introduced by Man-Duen Choi and Andrzej Jamiołkowski. It is also called channel-state duality by some authors in the quantum information area, but mathematically, this is a more general correspondence between positive operators and the complete positive superoperators.

## Definition

To study a quantum channel ${\mathcal {E}}$ from system $S$ to $S'$, which is a trace-preserving completely positive map from operator spaces ${\mathcal {L}}({\mathcal {H}}_{S})$ to ${\mathcal {L}}({\mathcal {H}}_{S'})$, we introduce an auxiliary system $A$ with the same dimension as system $S$. Consider the maximally entangled state:
    $|\Phi ^{+}\rangle ={\frac {1}{\sqrt {d}}}\sum _{i=0}^{d-1}|i\rangle \otimes |i\rangle ={\frac {1}{\sqrt {d}}}(|0\rangle \otimes |0\rangle +\cdots +|d-1\rangle \otimes |d-1\rangle )$
in the space of ${\mathcal {H}}_{A}\otimes {\mathcal {H}}_{S}$. Since ${\mathcal {E}}$ is completely positive, $(I_{A}\otimes {\mathcal {E}})(|\Phi ^{+}\rangle \langle \Phi ^{+}|)$ is a nonnegative operator. Conversely, for any nonnegative operator on ${\mathcal {H}}_{A}\otimes {\mathcal {H}}_{S'}$, we can associate a completely positive map from ${\mathcal {L}}({\mathcal {H}}_{S})$to ${\mathcal {L}}({\mathcal {H}}_{S'})$. This kind of correspondence is called Choi-Jamiołkowski isomorphism.

## The composition of Choi states

The Choi-Jamiołkowski isomorphism is a mathematical concept that connects quantum gates or operations to quantum states called Choi states. It allows us to represent a gate's properties and behavior as a Choi state.
In the generalised gate teleportation scheme, we can teleport a quantum gate from one location to another using entangled states and local operations. Here's how it works:
* The sender wants to apply a specific gate to an input quantum state.
* Instead of directly applying the gate, the sender creates an entangled state with the receiver.
* The sender performs measurements on their input state and their part of the entangled state.
* The measurement outcomes are communicated to the receiver through classical communication.
* Based on the measurement results, the receiver performs local operations on their share of the entangled state.
* These local operations reconstruct the gate's effect on the receiver's side.
By combining the powers of entanglement, measurements, and local operations, the gate's effect is effectively transferred to the receiver's location.
This process enables the teleportation of gate information or the application of the gate itself, making it a fascinating method to manipulate quantum gates in a distributed manner.

## Simulating composition of gates using generalized gate teleportation
### Pure Choi state

Let's consider the unitary case first, where the Choi state is pure. Suppose we have two Choi states represented as $\vert \psi _{U}\rangle _{i}$, and $\vert \psi _{V}\rangle _{i}$ and the corresponding systems are labeled as A, B, C, and D. To simulate the composition of gates $UV$ or $VU$, we aim to obtain the state $\vert \psi _{UV}\rangle _{i}$ or $\vert \psi _{VU}\rangle _{i}$.

#### The standard Bell scheme

The standard approach is to use the Bell scheme, where the gate $V$ is teleported from site A to site C using a Bell measurement on sites B and C, resulting in the state $\vert \psi _{VU}\rangle _{i}$ on sites A and D. To obtain $\vert \psi _{UV}\rangle _{i}$, we would apply the Bell scheme on sites A and D. However, this can introduce Pauli byproduct operators, such as $UPV$, between the two unitary gates, which are generally non-correctable, and can affect the desired gate composition.

#### Indirect Bell measurement

To address this issue, an indirect Bell measurement is used instead of the standard Bell scheme. This measurement involves an extra qubit ancilla. The indirect Bell measurement is performed by applying a gate $U_{T}$, which is the Toffoli gate with one-control qubit replaced by a zero-control qubit and the ancilla as the target. This measurement is expressed as $G(\sigma )={\text{tr}}[U_{T}\circ U_{B}^{\dagger }(\sigma \otimes \vert 1\rangle \langle 1\vert )]$, where $U_{B}^{\dagger }$ represents the reverse operation of preparing Bell states.

#### Outcomes and resulting states

The outcome of the indirect Bell measurement corresponds to either the singlet or the triplet state. If the outcome is the singlet on sites B and C, the gate U on site C is teleported to site A, resulting in the state $\vert \psi _{VU}\rangle _{i}$. On the other hand, if the outcome is the triplet, which has the full symmetry of the relevant unitary group, the gate V is modified by applying a rotation T on the triplet state, equivalent to the action of $V^{\dagger }$ on site C. This leads to the state $\vert \psi _{VtU}\rangle _{i}$, where t represents the adjoint operation.

#### Achieving desired states

By applying the generalised gate teleportation scheme, the states $\vert \psi _{VU}\rangle _{i}$ or $\vert \psi _{VtU}\rangle _{i}$ can be realised in a heralded manner, depending on the outcome from the qubit ancilla measurement. By combining this scheme with the POVM (Positive Operator-Valued Measure) scheme on site D, the gates $VU$ or $VtU$ can be simulated, with the output on site A for final readout.

#### Avoiding transposition issue

Although the generalised gate teleportation scheme enables the composition of Choi states and the simulation of desired gates, there is an apparent issue of transposition. However, this issue can be avoided by expressing any unitary operator as a product of two symmetric unitary operators. Therefore, for any unitary U, only two Choi program states, $\vert \psi _{UL}\rangle _{i}$ and $\vert \psi _{UR}\rangle _{i}$, are needed to deterministically teleport U.

### Mixed Choi state

In the case of channels whose Choi states are mixed states, the symmetry condition does not directly generalise as it does for unitary operators. However, a scheme based on direct-sum dilation can be employed to overcome this obstacle.
For a channel E with a set of Kraus operators ${K_{i}}$, each Kraus operator can be dilated to a unitary operator $U_{K}i$. The dilation is given by $U_{K}i=[[K_{i},q],[1-K_{i}^{\dagger }K_{i},-K_{i}]]$, where $U_{K}i$ acts on a space of dimension 2d.

#### Dilation-based scheme

In this scheme, each Kraus operator is expanded to a larger unitary operator, allowing the use of symmetry-based techniques. By considering the larger unitary operators, the issue of dealing with mixed Choi states is circumvented, and the computations can proceed using unitary transformations.

#### Unitary dilation

The channel $E$ can be simulated by using a random-unitary channel, where the controlled-unitary gate U̘ acts on the joint system of the input state ρ and an ancilla qubit. The ancilla qubit, initially prepared in the state |e⟩, is later traced out. The state σ is a combination of ρ and 0, where 0 represents the state of the ancilla on the dilated subspace. The action E(ρ) is obtained by restricting the evolution to the system subspace.

#### Simulation of the channel

In this scheme, the simulation of channel E involves applying the controlled-unitary gate U̘ to the input state ρ and the ancilla qubit prepared in the state |e⟩. The gate U̘ combines the Kraus operators $U_{K}i$ with the ancilla qubit. After tracing out the ancilla qubit, the resulting state σ is a combination of ρ and 0, with 0 representing the state of the ancilla on the dilated subspace. Finally, the action of the channel E on the input state ρ is obtained by considering the evolution restricted to the system subspace.

#### Teleportation of controlled-unitary gates

In comparison to the unitary case, the task here is to teleport controlled-unitary gates instead of unitary gates. This can be achieved by extending the scheme used in the unitary case. For each $U_{K}i$ in U̘, there exists a gate $T_{i}$ that can teleport it. The $T_{i}$ gates are controlled by the same ancilla used for $U_{K}i$. When a singlet is obtained, the channel E is teleported. To avoid the issue of transposition, each $U_{K}i$ is decomposed as the product of two symmetric unitary matrices, $U_{K}i$ = $U_{L}KiU_{R}Ki$. By using the same control wire for $U_{L}Ki$ and $U_{R}Ki$ and employing two program states, the gate U̘ can be teleported, thereby teleporting the channel E.

#### POVM and channel design

To execute the action of the channel on a state, a POVM (Positive Operator-Valued Measure) and a channel based on the state $\rho \oplus 0$ need to be designed. The channel $R_{0}$, an extension of the channel R, contains three Kraus operators: $K_{0}=[p\rho t,0],K_{1}=[p1-\rho t,0]$ and $K_{2}=[0,1]$. This channel requires a qutrit ancilla, and when the outcome is 2, indicating the occurrence of $E^{\dagger }(1)$, which is equal to 1 due to the trace-preserving condition, the simulation has to be restarted.

#### Special cases

For special types of channels, the scheme can be significantly simplified. Random unitary channels, which are a broad class of channels, can be realised using the controlled-unitary scheme mentioned earlier, without the need for direct-sum dilation. Unital channels, which preserve the identity, are random unitary channels for qubits and can be easily simulated. Another type of channel is the entanglement-breaking channel, characterised by bipartite separable Choi states. These channels and program states are trivial since there is no entanglement, and they can be simulated using a measurement-preparation scheme.

## Preparation of program states

Now we study the preparation of program states if they are not given for free.

### Choi states and program state preparation

A Choi state C is not easy to prepare on the first hand, namely, this may require the operation of E on the Bell state $\vert \omega _{i}\rangle$, and realising E itself (e.g., by a dilated unitary) is a nontrivial task. From Stinespring's dilation, we know that it requires the form of Kraus operators, which are not easy to find in general given a Choi state.

### Convexity and extreme channels

The set of qudit channels forms a convex body. This means that a convex sum of channels still leads to a channel, and there are extreme channels that are not convex sums of others. From Choi, a channel is extreme if there exists a Kraus representation ${K_{i}}$ such that the set ${K_{i}^{\dagger }K_{j}}$ is linearly independent. For a qudit, this means the rank of an extreme channel is at most $d$. Channels of rank $r\leq d$ are termed as generalised-extreme channels, here termed as 'gen-extreme channels.'

### Convex-sum decomposition and random bits

It is clear to see that a gen-extreme but not extreme channel is a convex sum of extreme channels of lower ranks. It has been conjectured and numerically supported that an arbitrary channel can be written as a convex sum of at most $d$ gen-extreme channels $E=\sum _{i=1}^{d}p_{i}E_{{\text{g}}_{i}}$. This requires a random dit. For the worst case, the upper bound for such a convex sum is $d{\frac {4-d}{2}}$ from Carathéodory's theorem on convex sets, which merely costs more random dits.

## Quantum circuit complexity reduction
### Simulating composition of gen-extreme channels

To simulate the composition $Q_{i}E_{i}$, with each $E_{i}$ of rank greater than $d$, hence permitting a convex-sum decomposition, one needs to sample the composition of gen-extreme channels. We find that there exists a concise form of Choi states for gen-extreme channels, which can be used to find the circuit and also Kraus operators directly.

### Quantum circuit realization of channels and Choi states for gen-extreme channels

The Choi state $C$ for a gen-extreme channel $E$ is of rank $r\leq d$ and ${\text{tr}}AC=1,{\text{tr}}BC=E(1)$.
It turns out $C=\sum {ij}\vert ii\rangle \langle jj\vert \otimes C{ij}$ for $C_{ij}:=E^{\dagger }(\vert ii\rangle \langle jj\vert )=\sum _{i}C_{i}U_{i}^{\dagger }U_{j}C_{j}$ for $C_{i}\equiv C_{ii}$, and $U_{i},U_{j}\in SU(d)$ .
Observe that $E^{\dagger }(\rho )=\sum _{ij}\rho _{ij}C_{ij}=V^{\dagger }(\rho \otimes 1)V$, for an isometry $V=\sum _{i}\vert ii\rangle U_{i}{\sqrt {C_{i}}}$.
Here $1$ is an ancilla state. Now we show that $V$ can be used to find a quantum circuit to realise $E$. Given $V$, we can find a unitary dilation $U$ such that $U\vert 0\rangle =V$, and it relates to the channel by $E^{\dagger }(\rho )=\langle 0\vert U^{\dagger }(\rho \otimes 1)U\vert 0\rangle$, while the final projection $\vert 0\rangle \langle 0\vert$ is on the system. Define $W={\text{swap}}\cdot U^{\dagger }$ for the swap gate between the system and ancilla, which are of the same dimension.
Then we find $E(\rho )={\text{tr}}_{W}(\rho \otimes \vert 0\rangle \langle 0\vert )$, which means $W$ is the circuit to realise the channel $E$ as in the standard dilation scheme. The Kraus operators can be obtained from it as $K_{i}=\langle i\vert W\vert 0\rangle$.

### Circuit complexity reduction

Compared with the standard (tensor-product) dilation method to simulate a general channel, which requires two qudit ancillas, the method above requires lower circuit cost since it only needs a single qudit ancilla instead of two. While the convex-sum decomposition, which is a sort of generalised eigenvalue decomposition since a gen-extreme Choi state can be mapped to a pure state, is difficult to solve for large-dimensional channels, it shall be comparable with the eigen-decomposition of the Choi state to find the set of Kraus operators. Both of the decompositions are solvable for smaller systems.
It's important to note that this discussion focuses on the primary components of the model and does not address fault tolerance, as it is beyond the scope of this model. We assume fault-tolerant qubits, gates, and measurements, which can be achieved with quantum error-correcting codes. Additionally, we highlight two intriguing issues that establish connections with standard frameworks and results.

## Connections with standard frameworks and results
### Teleportation of universal gate set

A computation is universal if the group $SU(2^{n})$ can be realised for any integer $n$. The common approach to achieving universality is by gate-compiling based on universal gate sets. Our method can be used to teleport unitary universal gate sets. Consider the popular Hadamard gate $H$, phase gate $S$, the so-called $Z^{1/4}$ gate $T$, CNOT, CZ, and Toffoli gate. One immediately notices that these gates are all symmetric matrices. We see above that symmetric unitary operators, for which $U=U^{\dagger }$, can be teleported deterministically, and the byproduct are Pauli operators. Note that a product of symmetric matrices is not symmetric in general.
It is easy to check that the affine forms of $H$, $S$, CNOT, and CZ are (generalised) permutations since they are Clifford gates, which preserve the Pauli group. A generalised permutation is a permutation that also allows entry of modulus 1 besides 1 itself. The $T$ gate and Toffoli gate are not Clifford gates, and their affine forms are not permutations. Instead, the affine forms of them contain a Hadamard-like gate as a sub-matrix, which means, in the Heisenberg picture, they are able to generate superpositions of Pauli operators. This fact also generalises to the qudit case, with Hadamard replaced by Fourier transform operators. This serves as an intriguing fact regarding the origin of the computational power of quantum computing.

### Stored-program quantum computing

In this approach, a modification is introduced to enable the simulation of the operation $U\vert d_{i}\rangle$ using a generalised gate teleportation scheme. This proposed method allows for the unitary simulation of $U\vert d_{i}\rangle$ by utilising a processor $G$ that depends on the input program state.
For symmetric matrices $U$, the program state $\vert \psi _{U}\rangle _{i}$ is sufficient to achieve the desired results. However, in general cases where $U=U_{L}U_{R}$, both program states $\vert \psi _{UL}\rangle _{i}$ and $\vert \psi _{UR}\rangle _{i}$ are required for deterministic teleportation and composition.