The Choi-Cholesky algorithm for completely positive maps

This paper establishes a canonical construction of natural dilations for completely positive maps by leveraging the Choi-Jamiołkowski correspondence and developing a Cholesky algorithm for bi-partite systems, thereby recovering the maps' behavior through adjoint actions under specific separability and boundedness conditions.

The Gist

The Big Picture: Unpacking the "Black Box"

Imagine you are a quantum physicist. You have a machine (a Quantum Channel) that takes a delicate state of a particle (like an electron's spin) and transforms it into a new state. In the real world, these machines are often "noisy" or interact with the environment, making the process look messy and unpredictable.

Mathematically, we call these machines Completely Positive (CP) maps. They are the rules that govern how quantum information changes.

For decades, we knew these machines could be explained as a simple, clean process:

1. Take your input.
2. Hook it up to a giant, invisible "helper" system (an auxiliary space).
3. Run a perfect, reversible dance (a Unitary operation) between the input and the helper.
4. Throw away the helper and keep the result.

This is known as Kraus's Second Representation Theorem. It's like saying, "Every messy kitchen cleanup can be explained as a perfect, choreographed dance between the chef and a hidden assistant."

The Problem: While we knew this dance existed, we didn't have a clear, step-by-step recipe to find the specific moves for any given machine. The old methods relied on "magic" (mathematical tools like Zorn's Lemma) that proved the dance existed but didn't tell you how to build it. It was like being told, "There is a key to this lock," without ever seeing the key.

The Paper's Solution: The "Choi-Cholesky" Recipe

Raj Dahya's paper provides that missing recipe. He creates a canonical (standard, non-arbitrary) algorithm to explicitly construct the "dance" (the dilation) for any quantum machine.

Here is how he does it, broken down into three simple steps:

1. The "Choi Snapshot" (The Fingerprint)

First, the author takes a picture of the machine's behavior. In math, this is called the Choi Matrix.

• Analogy: Imagine you want to understand how a blender works. Instead of watching it blend, you put a specific set of ingredients in and take a high-resolution photo of the result. This photo (the Choi Matrix) contains all the information about how the machine treats every possible input.
• The Catch: In the past, to turn this photo back into a recipe, you had to "diagonalize" it. This is like trying to sort a pile of mixed-up puzzle pieces by finding the "perfect" way to group them. The problem is, if you have many identical pieces, there is no single "perfect" way to group them. You have to make an arbitrary choice, which breaks the "canonical" nature of the solution.

2. The "Cholesky" Sort (The New Sorting Hat)

Dahya replaces the messy "diagonalization" with a technique called Cholesky Decomposition.

• Analogy: Imagine you have a stack of papers that are all jumbled. Diagonalization is like trying to sort them by color, but some colors are so similar you can't decide which pile they go in.
• Cholesky Decomposition is like a strict, rule-based sorting algorithm. It says: "Put the first paper in pile A. Put the second paper in pile A if it matches the first; otherwise, start pile B." It forces a specific order based on the sequence of the papers, not on arbitrary choices.
• The Twist: Because these "papers" are actually complex quantum objects living in two different worlds at once (a bi-partite system), Dahya had to invent a new version of this sorting algorithm that works for these double-world objects. He calls this the Choi-Cholesky algorithm.

3. The "Resolution" (The Final Dance)

Once the papers are sorted using the Cholesky method, the author can read off the exact steps of the dance.

• He constructs a specific set of vectors (the "moves") that tell the machine exactly how to interact with the hidden helper system.
• Because the sorting method (Cholesky) was rule-based and not arbitrary, the resulting dance is canonical. If you give the same machine to two different people, they will both derive the exact same dance steps.

Why Does This Matter?

1. It's Constructive: Before this, we could only say, "A solution exists." Now, we can say, "Here is the solution, and here is the code to calculate it."
2. It Works for Infinite Systems: Most previous methods only worked for small, finite quantum systems (like a few qubits). This new method works even for infinite-dimensional systems (like continuous waves of light), provided the system is "separable" (can be counted).
3. It's Measurable: The paper proves that if you tweak the machine slightly, the resulting dance steps change in a predictable, measurable way. This is crucial for engineering and computer science applications.

The Limitations (The Fine Print)

The author is honest about the limits of his magic wand:

• Finite Rank Requirement: The machine must preserve "finite rank" operators. In plain English, the machine shouldn't turn a simple, finite input into an infinitely complex, unmanageable mess.
• Computability: While the steps are explicit, they involve "pseudo-inverses" (a type of mathematical division that can be tricky). In the strictest sense of computer science (Turing computability), some of these steps might be impossible to calculate perfectly on a digital computer for certain infinite systems. However, for all practical engineering purposes, the recipe is usable.

Summary Metaphor

Think of a Completely Positive Map as a Magic Trick.

• Old Way: A magician tells you, "I can make the rabbit disappear, and I know there is a secret trapdoor somewhere in the stage, but I won't tell you where or how to build it."
• Dahya's Way: The magician hands you a blueprint. "Here is the exact location of the trapdoor, here is the lever you pull, and here is the sequence of moves. I built it using a strict, rule-based system so that if you build it, it will work exactly the same way every time."

This paper gives us the blueprint for the quantum trapdoor, turning abstract existence proofs into concrete, buildable engineering.

Technical Summary

1. Problem Statement

The paper addresses a fundamental gap in the mathematical theory of quantum channels (Completely Positive Trace-Preserving or CPTP maps). While Kraus's Representation Theorems (specifically the Second Representation Theorem) establish that any CPTP map $\Phi$ can be dilated to a unitary action on a larger Hilbert space (i.e., $\Phi(s) = \text{tr}_2(\text{ad}_U(s \otimes \omega))$), the standard proofs rely on non-constructive tools:

• Stinespring's Dilation Theorem and Naimark's Representation Theorem, which depend on Zorn's Lemma.
• Choi's constructive approach (for finite dimensions), which relies on matrix diagonalization.

The Core Issues:

1. Non-Constructivity: Standard proofs do not provide an explicit algorithm to compute the dilation operators.
2. Non-Canonicity: Even in finite dimensions, Choi's method involves arbitrary choices (e.g., selecting eigenvectors for repeated eigenvalues during diagonalization), meaning the resulting dilation is not unique or "natural."
3. Dimensionality: Existing constructive methods are largely restricted to finite-dimensional Hilbert spaces.

The Goal: To establish a canonical, explicit, and Borel-measurable construction of dilations for completely positive (CP) maps that works for infinite-dimensional (separable) Hilbert spaces, without relying on arbitrary choices or non-constructive axioms.

2. Methodology

The author develops a new algorithmic framework that replaces the spectral decomposition (diagonalization) used in Choi's approach with a Cholesky decomposition adapted for bi-partite systems.

Key Technical Components:

• Choi–Jamiołkowski Correspondence: The paper utilizes the bijection between CP maps $\Phi: L_1(H_1) \to L_1(H_2)$ and positive operators (Choi matrices) $C_\Phi$ on the tensor product space $H_1 \otimes H_2$.
• Bi-partite Cholesky Decomposition:
  • Standard Cholesky decomposition applies to scalar matrices. The author generalizes this to operators on $H_1 \otimes H_2$, treating them as "operator-valued matrices" indexed by a basis of $H_1$.
  • The decomposition takes the form $C_\Phi = \hat{L} D \hat{L}^*$, where $\hat{L}$ is a lower uni-triangular operator and $D$ is a diagonal positive operator.
  • Crucial Constraint: The algorithm requires the map to be Finite Rank Preserving (FP), meaning it maps finite-rank operators to finite-rank operators. This allows the use of Moore-Penrose pseudo-inverses for the diagonal blocks of the Choi matrix, which is essential for the recursive construction.
• Resolution of CP Maps:
  • By decomposing the Choi matrix, the author derives a family of vectors $\{\zeta_i\}$ in a Hilbert-Schmidt space $H = L_2(H_1 \otimes H_2, H_2)$.
  • These vectors satisfy $\Phi(E_{i,j}) = \zeta_i \zeta_j^*$, where $E_{i,j}$ are basis operators.
• Canonical Construction:
  • The construction relies on a fixed Ordered Orthonormal Basis (ONB) for $H_1$.
  • The algorithm uses only operations from a specific class $\mathcal{O}$ (addition, multiplication, tensor products, square roots of positive operators, and pseudo-inverses).
  • This ensures the construction is Borel-measurable and does not require arbitrary choices (like selecting a specific basis for an eigenspace).

3. Key Contributions

A. The Choi–Cholesky Algorithm

The paper introduces a recursive algorithm (detailed in Appendix B) to compute the Cholesky factors of the Choi matrix for CP maps. Unlike diagonalization, which is ill-defined for repeated eigenvalues without arbitrary selection, the Cholesky decomposition is unique given the ordering of the basis.

B. Canonical Representation Theorem (Theorem 1.1)

The author proves that for a separable Hilbert space $H_1$ and arbitrary $H_2$, any Finite Rank Preserving (FP) CPCB (Completely Positive Completely Bounded) map $\Phi$ can be represented as:
$$\Phi = \Psi_{H_1, H_2} \circ \text{ad}_{V_\Phi}$$
Where:

• $V_\Phi: H_1 \to L_2(H_1 \otimes H_2, H_2)$ is a bounded operator (contraction or isometry).
• $\Psi$ is a specific CPTP map defined via partial trace and adjoint action.
• If $\Phi$ is CPTP, $V_\Phi$ is an isometry.

C. Measurability and Constructibility (Theorem 1.2)

The mapping $\Phi \mapsto V_\Phi$ is shown to be Borel-measurable with respect to the Strong Operator Topology (SOT) on the space of maps and the Weak Operator Topology (WOT) on the space of dilations.

• The components of $V_\Phi$ can be explicitly constructed from the values $\{\Phi(E_{i,j})\}$ using operations in class $\mathcal{O}$.
• This provides a "natural" dilation that is unique relative to the choice of the ONB.

D. Extension to Infinite Dimensions

The results hold for separable infinite-dimensional Hilbert spaces, a significant generalization over previous constructive approaches limited to finite dimensions.

4. Results and Properties

• Uniqueness: The dilation $V_\Phi$ is unique given the fixed ONB of $H_1$. This resolves the non-uniqueness issue inherent in Choi's diagonalization method.
• Unitary Dilation: The paper notes that the isometric dilation $V_\Phi$ can be easily extended to a unitary dilation (recovering Kraus's Second Representation) by standard embedding techniques (Remark 1.3).
• Computability:
  • The construction is effectively computable (implementable in modern programming languages).
  • However, the author notes (Remark 3.3) that due to the reliance on pseudo-inverses and spectral theory, the map may not be Borel-Turing computable in the strict sense for all inputs, unlike Choi's diagonalization approach in finite dimensions.
• Limitations: The requirement that maps be Finite Rank Preserving (FP) is a necessary condition for the current proof, primarily due to the use of pseudo-inverses on the diagonal blocks of the Choi matrix.

5. Significance

1. Bridging Constructive and Abstract Theory: The paper successfully bridges the gap between the abstract existence of dilations (Stinespring) and explicit construction, providing a "canonical" path that avoids the Axiom of Choice.
2. Algorithmic Quantum Information: By providing an explicit algorithm (Choi-Cholesky), the work opens the door for computational implementations of quantum channel dilations in infinite-dimensional settings (e.g., continuous variable quantum systems), provided the FP condition is met.
3. Resolution of Non-Canonicity: It solves the problem of "arbitrary choice" in constructing dilations. In applications like quantum error correction or state discrimination, having a unique, basis-dependent dilation is crucial for reproducibility.
4. Foundational Insight: The work highlights the power of Cholesky decomposition over spectral decomposition in operator theory contexts where uniqueness and constructibility are prioritized over diagonalization.

Conclusion

Raj Dahya's paper establishes a rigorous, constructive, and canonical method for dilating completely positive maps. By replacing matrix diagonalization with a bi-partite Cholesky decomposition, the author provides an explicit algorithm that is Borel-measurable and applicable to infinite-dimensional systems, fundamentally advancing the constructive theory of quantum channels.