Source-linked AI summary
Semidefinite programs for completely bounded norms
John Watrous
TL;DR
The paper addresses how to compute completely bounded trace and spectral norms, whose direct computation was not known to be straightforward. It formulates the trace norm as a polynomial-size semidefinite program, obtaining a deterministic polynomial-time approximation method and analytic consequences.
Problem
Computing completely bounded trace and spectral norms was not known to be straightforward, while prior iterative methods lacked convergence-rate analyses.
Method
The paper expresses the completely bounded trace norm as a semidefinite program, uses duality and polynomial-time semidefinite-programming algorithms, and derives analytic examples from the formulation.
Results
The resulting formulation provides a deterministic polynomial-time method to approximate the norms, with strong duality established for the constructed program.
Takeaways & Limitations
The semidefinite-programming formulation supports both efficient calculation and verification of completely bounded norms, while also giving alternate characterizations and duality results.
Takeaways & Limitations
The computational guarantee is stated for well-bounded semidefinite programs and uses the ellipsoid method for a formal Turing-machine polynomial-time result.
Abstract
from arXiv · showhide
The completely bounded trace and spectral norms in finite dimensions are shown to be expressible by semidefinite programs. This provides an efficient method by which these norms may be both calculated and verified, and gives alternate proofs of some known facts about them.
1 Introduction
Completely bounded trace and spectral norms provide physically meaningful ways to measure distances between quantum channels, but their computation was not straightforward. The paper makes these norms efficiently computable through semidefinite programming and presents analytic applications of the formulation.
- Motivation: Completely bounded trace and spectral norms are motivated as physically meaningful measures for comparing quantum channels and respect tensor-product structure.The completely bounded trace norm is also called the diamond norm, while the spectral variant is commonly called the completely bounded norm.
- Open problem: Prior methods for computing these norms used iterative procedures but did not analyze their convergence rates.This left the existence of potentially efficient computation without a provable polynomial-time guarantee.
- Contribution: The paper expresses the completely bounded trace norm as the optimal value of a semidefinite program whose size is polynomial in the super-operator dimensions.The completely bounded spectral norm follows through its relation to the trace norm formulation.
- Novelty: Known convex-programming and semidefinite-programming approaches provide related or earlier formulations, but this paper makes the formulation explicit and treats it in full generality.A simpler second formulation applies specifically to differences between two quantum channels.
- Analytic applications: The semidefinite-programming formulation also yields alternate characterizations of the completely bounded trace norm and a duality connection between Uhlmann’s and Alberti’s fidelity theorems.These examples illustrate semidefinite programming as an analytic tool, not only a computational one.
2 Background
The background develops finite-dimensional operator and super-operator notation, completely bounded norms, and the semidefinite-programming framework used later. It also states duality principles and the polynomial-time approximation result supporting the paper’s computational claims.
- Operator theory: The paper defines finite-dimensional complex vector spaces, operators, inner products, and trace, Frobenius, and spectral norms as its basic matrix-theoretic language.It also introduces Hermitian, positive semidefinite, positive definite, and density operators.
- Super-operators: A super-operator is a linear map Φ : L(X) → L(Y), with quantum channels defined as completely positive and trace-preserving super-operators.The Choi–Jamiołkowski representation gives a linear bijection between super-operators and operators on Y ⊗ X, while Stinespring representations provide another representation.
- Completely bounded norms: The induced trace norm and its completely bounded trace and spectral variants are defined for super-operators, with the latter commonly called the diamond norm and completely bounded norm.The completely bounded norms are multiplicative under tensor products, and the trace norm variant of Φ equals the spectral norm variant of Φ*.
- Semidefinite programming: A semidefinite program consists of primal and dual positive-semidefinite optimization problems, feasible sets, objective functions, and ε-interior feasible sets.The formulation used here differs from standard form but is equivalent and better suited to the paper’s needs.
- Duality: Weak duality guarantees α ≤ β, while Slater-type conditions can guarantee equality of primal and dual optimal values.Finite optimal values need not always be attained, so supremum and infimum cannot universally be replaced by maximum and minimum.
- Computational efficiency: The stated semidefinite-programming approximation problem is solvable in polynomial time in the dimensions, accuracy and bounding parameters, and input bit-length.The paper applies this result using the ellipsoid method; interior-point methods are typically faster but lack a formal Turing-machine polynomial-time proof in the stated discussion.
3 A semidefinite program for the completely bounded trace norm
This section constructs a semidefinite program whose optimal value equals the completely bounded trace norm, and establishes strong duality and efficient approximation.
- Program construction: The semidefinite program is built from a Stinespring representation Φ(X) = Tr_Z(AXB*) with minimal auxiliary dimension dim(Z) = rank(J(Φ)).The formal program uses a Hermiticity-preserving super-operator Ψ and Hermitian operators C and D.
- Program construction: Its primal feasible operators are characterized through positive semidefinite extensions satisfying trace and partial-trace constraints derived from A and B.The construction relates the feasible set to operators generated from purifications and unitary transformations.
- Optimal value: The optimal primal and dual values are equal, and the common value is the completely bounded trace norm |||Φ|||_1.Strong duality follows from strict dual feasibility; the optimal primal value is achieved.
- Optimal value: The proof identifies the primal feasible set with a set generated by purifications and unitaries, establishing both inclusions Q ⊆ R and R ⊆ Q.This set equality connects the semidefinite program directly to the norm’s variational characterization.
- Computational efficiency: The program has polynomial-size descriptions and can approximate |||Φ|||_1 within ε = 2^-dN in time polynomial in n, m, and the input bit-length.The analysis uses R = 2^cN and permits smaller errors such as ε = 2^-p(N) for polynomial p.
4 A simpler semidefinite program for quantum channel distance
This section specializes the framework to the difference of two quantum channels and gives a simpler semidefinite program for their completely bounded trace distance.
- Significance: This quantum-channel case is simpler than the general construction and is directly relevant to measuring distances between quantum channels.The case had previously been shown to reduce to a convex optimization problem.
- Specialized formulation: For Φ = Φ_0 − Φ_1, where Φ_0 and Φ_1 are quantum channels, the section formulates specialized primal and dual semidefinite programs.The programs are matched to the formal semidefinite-program framework and satisfy strong duality.
- Optimal value: The specialized program’s optimal value is one-half of the completely bounded trace norm, 1/2 |||Φ|||_1.The variational form is expressed using unit vectors and positive semidefinite operators bounded by the identity.
- Feasible sets: The feasible-set description uses Q = {R ∈ Pos(Y ⊗ X) : R ≤ 1_Y ⊗ ρ for some ρ ∈ D(X)} and an equivalent set R parameterized by B and P.The equality Q = R follows by choosing ρ or B so that ρ = B*B.
5 Connections with known results
The semidefinite-program formulation connects completely bounded trace norms to Stinespring representations and fidelity, yielding alternate characterizations and duality-based proofs of known results.
- Completely bounded norms: Theorem 5 gives an alternate characterization of the completely bounded trace norm as an infimum over Stinespring pairs.The characterization is proved using semidefinite programming duality.
- Completely bounded norms: For every Stinespring pair, the completely bounded trace norm is bounded above by the product of the operator norms of its two components.This inequality is the key bound used in the characterization.
- Connection with fidelity: The semidefinite program’s optimal primal value is the squared fidelity between the reduced operators associated with the relevant vectors.The value is expressed as F(TrY(uu∗), TrY(vv∗))2.
- Connection with fidelity: The squared fidelity equals a maximization over positive semidefinite operators constrained by a partial-trace inequality.This is the explicit primal formulation given in Corollary 7.
- Connection with fidelity: Strong duality identifies the optimal dual value with the same fidelity expression as the primal problem.The dual evaluation uses positive definite operators and a proposition about rank-one positive semidefinite operators.
- Connection with fidelity: Uhlmann’s and Alberti’s theorems are established as precise dual statements in finite dimensions, with each implying the other.Uhlmann’s theorem supplies the primal characterization, while Alberti’s theorem supplies the corresponding infimum characterization.