Source-linked AI summary
Simpler semidefinite programs for completely bounded norms
John Watrous
TL;DR
The paper addresses how to formulate the completely bounded trace and spectral norms as semidefinite programs, building on prior work that showed they can be computed this way. It gives two simpler formulations, including a maximum-output-fidelity characterization and an alternative based on the Choi-Jamiołkowski representation.
Problem
Earlier work showed that the completely bounded trace and spectral norms can be efficiently expressed and computed by semidefinite programming, and this paper seeks simpler formulations.
Source: §1 · p. 1Method
The paper formulates the completely bounded trace norm using maximum output fidelity and, alternatively, the Choi-Jamiołkowski representation.
Source: Optimal value · p. 9, §3 · p. 10Results
The paper presents two semidefinite-program formulations of the completely bounded trace and spectral norms that are simpler than the earlier formulations.
Source: §1 · p. 1Takeaways & Limitations
By trace-spectral norm duality, the trace-norm formulations can be adapted to the completely bounded spectral norm.
Source: Norms and fidelity · p. 3For the fidelity semidefinite program, strict primal feasibility may fail when either input operator is not positive definite.
Source: Strong duality · p. 6
Abstract
from arXiv · showhide
The completely bounded trace and spectral norms, for finite-dimensional spaces, are known to be efficiently expressible by semidefinite programs (J. Watrous, Theory of Computing 5: 11, 2009). This paper presents two new, and arguably much simpler, semidefinite programming formulations of these norms.
1 Introduction and preliminary discussion
This section introduces the finite-dimensional operator setting and the completely bounded trace and spectral norms. It presents the paper as a follow-up offering two simpler semidefinite-program formulations of these norms.
1 Introduction and preliminary discussion
- The paper presents two semidefinite-program formulations of the completely bounded trace and spectral norms, each simpler than the earlier formulations.Source: §1 · p. 1
- Linear maps from operators on X to operators on Y are denoted T(X, Y), while operators from X to Y are identified with m × n complex matrices.Source: Linear algebra basics · p. 2
- The section introduces trace, Frobenius, and spectral norms for operators, along with induced and completely bounded variants for linear mappings.Source: Norms and fidelity · pp. 2–3
- The paper focuses on the completely bounded trace norm; duality between trace and spectral norms lets readers adapt its formulations to the completely bounded spectral norm.The section also notes that trace-norm-bounded operators can be expressed as convex combinations of rank-one operators formed from unit vectors.Source: Norms and fidelity · p. 3
2 A semidefinite program for the maximum output fidelity
The section builds a semidefinite program for the completely bounded trace norm by expressing it as a maximum output fidelity. It first gives an SDP for fidelity itself, then uses that characterization to formulate the norm SDP.
2.1 A semidefinite program for the fidelity function
- The fidelity function has an SDP characterization independently discovered by Nathan Killoran.The section establishes strong duality and primal optimum attainment for this SDP; for positive definite P and Q, strict primal feasibility also guarantees dual attainment.Source: §2.1 · p. 5, Strong duality · pp. 5–6
- Dual attainment can fail for some choices of P and Q, although positive definite P and Q ensure strict primal feasibility and an attained dual optimum.Strict primal feasibility may fail when either operator is not positive definite.Source: Strong duality · p. 6
2.2 Maximum output fidelity characterization of the completely bounded trace norm
- The norm characterization identifies |||Φ|||1 with the maximum output fidelity between positive maps Ψ0 and Ψ1.The maximum output fidelity is defined for the two positive maps Ψ0 and Ψ1.Source: §2.2 · p. 7
2.3 A semidefinite program for the maximum output fidelity
- Combining the fidelity SDP with this characterization yields an SDP for the completely bounded trace norm.The formulation is built from a Stinespring representation of the given mapping; such a representation always exists when the auxiliary dimension k is sufficiently large, with k at least mn in the worst case.Source: §2.3 · p. 8
- The resulting SDP's optimum is Fmax(Ψ0, Ψ1), equal to the completely bounded trace norm.For fixed density operators ρ0 and ρ1, the primal objective gives F(Ψ0(ρ0), Ψ1(ρ1)); maximizing over these inputs yields Fmax(Ψ0, Ψ1).Source: Optimal value · p. 9
3 A semidefinite program for the completely bounded trace norm from a mapping’s Choi-Jamiołkowski representation
This section gives an alternative semidefinite program for the completely bounded trace norm using a mapping’s Choi–Jamiołkowski representation rather than its Stinespring representation. It derives an alternate norm expression and uses it to obtain equivalent primal and dual programs, with strong duality and attained optima.
3 A semidefinite program for the completely bounded trace norm from a mapping’s Choi-Jamiołkowski representation
- The Choi–Jamiołkowski representation yields an alternate semidefinite program for the completely bounded trace norm, distinct from the earlier Stinespring-based formulation.The paper notes that the two formulations are closely related.Source: §3 · p. 10
3.1 Choi-Jamiołkowski representations and the completely bounded trace norm
- Theorem 6 gives an alternate expression for the completely bounded trace norm using the Choi–Jamiołkowski representation.The derivation uses an identity connecting the vec-mapping with that representation.Source: §3.1 · p. 10
3.2 A semidefinite program from Theorem 6
- After simplification of the primal and dual problems associated with (Ξ, C, D), one obtains equivalent primal and dual problems; the primal optimum is given using supremums over K and density operators ρ0, ρ1.The supremums range over K ∈ L(X) with ∥K∥∞ ≤ 1 and ρ0, ρ1 ∈ D(X).Source: §3.2 · p. 11, Optimal value · p. 12
- Strict primal and dual feasibility hold for every mapping Φ, so strong duality holds and both optima are attained.The paper supplies examples of strictly feasible solutions for each side.Source: §3.2 · pp. 11–12
4 Remarks on the complexity of approximating optimal solutions to the semidefinite programs
The section considers whether the programs’ optimal values can be approximated efficiently when their input data are rational and encoded in binary. It gives bounds supporting polynomial-time approximation and discusses ellipsoid and interior-point methods.
4 Remarks on the complexity of approximating optimal solutions to the semidefinite programs
- The complexity question assumes rational real and imaginary input parts whose numerators and denominators are encoded in binary.The question concerns approximating the optimal value of either program.Source: §4 · p. 12
- Interior-point methods are described as a practical approach, and CVX can solve the programs efficiently with minimal coding.The paper specifically mentions CVX for MATLAB.Source: §4 · p. 12
- The ellipsoid method applied to the dual formulations is presented as an attractive route to rigorous polynomial-time solvability statements.The analysis considers an ε-interior of the dual feasible set and seeks a sufficiently large lower bound on ε.Source: §4 · p. 13
- Polynomial-time approximation to accuracy δ follows from the stated bounds ε and R, with running time polynomial in input size and log(1/δ).The conclusion is stated for the semidefinite programs discussed in the paper.Source: §4 · p. 14