Computational Aspects of the Trace Norm Contraction Coefficient

The gist The paper shows that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard, which implies that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard.

Hardness Results for Contraction Coefficient

The main focus of this paper is to study the maximal success probability Psucc(Φ, 2) for transmitting a bit over the quantum channel Φ, which is connected to the trace norm contraction coefficient ηtr(Φ) by Psucc(Φ, 2) = 1/2 + 1/2 ηtr(Φ) 0 0. In terms of channel coding, this corresponds to deciding the existence of a perfect, i.e., zero-error, encoding of a bit. This decision is equivalent to determining if the independence number of the corresponding non-commutative confusability graph of Φ is greater or equal to k. Theorem 3 shows that deciding whether a non-commutative graph has independence number at least 2 is NP-hard.

Convergence Hierarchy of Upper Bounds

The final result establishes a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient (Theorem 26). The convergence speed is shown in Theorem 28, which states that 0 ≤ SDPm(Φ, k) − Psucc(Φ, k) ≤ poly(d)/√m. These simulations show that the bounds obtained by their SDP are numerically tight.

How it works

The paper proves these hardness results by reducing problems from classical complexity, specifically the Hermitian non-commutative Little Grothendieck Problem, to the computation of ηtr(Φ). For quantum-classical channels, the proof uses techniques similar to the general case, involving constructing a map Ψ and relating ηtr(Φα) to FRn→ld1(R). The optimal success probability Psucc(Φ, k) is defined using a Positive Operator Valued Measure (POVM) as Psucc(Φ, k) = max POVM, ρi ∈ D(H): 1 ≤ i ≤ k 1/k Σ Xk i=1 tr(MiΦρi).

Conclusion

The work establishes that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard, and it provides a converging hierarchy of semidefinite programming upper bounds that can detect when the contraction coefficient is less than 1.

How it works

The proof of Theorem 3 involves constructing a projector Π from a Graph 2-CSP instance G, and then relating the distance between rank-one matrices and S to the contraction coefficient via Lemma 20. This leads to the final inequality ηtr(Φ) ≤ s1 − Ω(1/n3). The construction of Sb⊥ is shown to be an operator system, which allows for the application of Theorem 14 to relate ηtr(Φ) = 1 to the existence of a rank-one matrix in G⊥Φ.

Key Definitions and Tools

The paper defines the quantum confusability graph GΦ as Span(K∗i Kj: i, j). It is shown that for a self-adjoint subspace S containing the identity, there exists a channel Φ such that GΦ = S. The set of separable states SEP(H ⊗ H′) is defined as conv ρ ⊗ σ ρ ∈ D(H), σ ∈ D(H′).

Conclusion

The paper demonstrates that the problem of deciding whether a non-commutative graph has an independence number of at least 2 is NP-hard. This is achieved by embedding Graph 2-CSP into the confusability graph of a quantum channel, showing that satisfiability maps to ηtr(Φ) = 1 and unsatisfiability maps to ηtr(Φ) < 1. The paper also presents a hierarchy of SDPs that converges to the optimal success probability Psucc(Φ, k). The convergence speed is bounded by poly(d)/√m.

Key Definitions and Tools

The paper defines the quantum Doeblin coefficient α(Φ) as sup XB∈Herm(B) tr[XB]: IA ⊗ XB ⪯ dAJ(Φ).

Conclusion

The paper concludes that for any channel Φ, whenever αI (Φ) ≥ α(Φ) > 0, we have ηtr(Φ) < 1.

How it works

The proof of Theorem 3 uses the Fuchs-van de Graaf inequality to upper-bound the trace distance between Φ(uu∗) and Φ(vv∗). This leads to the final bound ηtr(Φ) ≤ s1 − Ω(1/n3).

Key Definitions and Tools

The paper defines the Schatten 1-norm as · 1, a.k.a. the trace norm. The Schatten ∞-norm is defined as · ∞, a.k.a. the operator norm. The Hilbert space H are finite dimensional and density operators are positive and unit trace operators in B(H).

Conclusion

The paper provides numerical evidence that the hierarchy detects when a channel has a contraction coefficient < 1. The simulations show that the bounds given by their SDP are numerically tight for amplitude damping channels and depolarizing channels.

1. Approximation of Quantum Channel Performance: The system can achieve an optimal success probability for encoding a bit in a quantum system undergoing noise by approximating the trace norm contraction coefficient within a constant factor, as shown by Theorem 2.

2. Decision Problem Hardness for Perfect Encoding: The AI can determine if a non-commutative graph has an independence number of at least 2 is NP-hard, which relates to deciding if the channel can perfectly preserve a bit, as stated in Theorem 3.

3. Bounding Contraction Coefficient via SDP Hierarchy: The system can compute upper bounds on the trace norm contraction coefficient using a converging hierarchy of semidefinite programming (SDP) upper bounds, specifically showing that SDPm(Φ) = 2SDPm(Φ, 2) − 1 converges to Psucc(Φ, k) (Theorem 28).

4. Identifying Channels with Contraction Coefficient Less Than One: The AI can detect if a channel has a contraction coefficient less than one by checking if the induced Doeblin coefficient is positive, as Proposition 24 states: "whenever αI (Φ) ≥ α(Φ) > 0, we have ηtr(Φ) Distinguishing Channel Types for Quantum-Classical Channels**: The system can distinguish between a unital quantum channel and a quantum-classical channel by analyzing the structure of its Kraus operators, noting that as Fe∗(I2kd) = 0, Φ∗α is unital, so that, for α small enough, Φα is a channel (Theorem 2).

We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. We also establish the NP-hardness of deciding if the contraction coefficient is equal to 1, i.e., the channel can perfectly preserve a bit. As a consequence, deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.