Abstract We present an iterative algorithm based on semidefinite programming (SDP) for computing the quantum smooth max-mutual information $$I^\varepsilon _{\max }(\rho _{AB})$$ I max ε ( ρ AB ) of bipartite quantum states in any dimension. The algorithm is accurate if a rank condition for marginal states within the smoothing environment is satisfied and provides an upper bound otherwise. Central to our method is a novel SDP, for which we establish primal and dual formulations and prove strong duality. With the direct application of bounding the one-shot distillable key of a quantum state, this contribution extends SDP-based techniques in quantum information theory. Thereby it improves the capabilities to compute or estimate information measures with application to various quantum information processing tasks.
Abstract We present an iterative algorithm based on semidefinite programming (SDP) for computing the quantum smooth max-mutual information Imaxε(ρAB) I max ε ( ρ AB ) of bipartite quantum states in any dimension. The algorithm is accurate if a rank condition for marginal states within the smoothing environment is satisfied and provides an upper bound otherwise. Central to our method is a novel SDP, for which we establish primal and dual formulations and prove strong duality. With the direct application of bounding the one-shot distillable key of a quantum state, this contribution extends SDP-based techniques in quantum information theory. Thereby it improves the capabilities to compute or estimate information measures with application to various quantum information processing tasks.
We derive several efficiently computable converse bounds for quantum communication over quantum channels in both the one-shot and asymptotic regime. First, we derive one-shot semidefinite programming (SDP) converse bounds on the amount of quantum information that can be transmitted over a single use of a quantum channel, which improve the previous bound from [Tomamichel/Berta/Renes, Nat. Commun. 7, 2016]. As applications, we study quantum communication over depolarizing channels and amplitude damping channels with finite resources. Second, we find an SDP-strong converse bound for the quantum capacity of an arbitrary quantum channel, which means the fidelity of any sequence of codes with a rate exceeding this bound will vanish exponentially fast as the number of channel uses increases. Furthermore, we prove that the SDP-strong converse bound improves the partial transposition bound introduced by Holevo and Werner. Third, we prove that this SDP strong converse bound is equal to the so-called max-Rains information, which is an analog to the Rains information introduced in [Tomamichel/Wilde/Winter, IEEE Trans. Inf. Theory 63:715, 2017]. Our SDP strong converse bound is weaker than the Rains information, but it is efficiently computable for general quantum channels.
Abstract Finding the minimal relative entropy of two quantum states under semidefinite constraints is a pivotal problem located at the mathematical core of various applications in quantum information theory. An efficient method for providing provable upper and lower bounds is the central result of this work. Our primordial motivation stems from the essential task of estimating secret key rates for QKD from the measurement statistics of a real device. Further applications include the computation of channel capacities, the estimation of entanglement measures and many more. We build on a recently introduced integral representation of quantum relative entropy by [Frenkel, Quantum 7, 1102 (2023)] and provide reliable bounds as a sequence of semidefinite programs (SDPs). Our approach ensures provable sublinear convergence in the discretization, while also maintaining resource efficiency in terms of SDP matrix dimensions. Additionally, we can provide gap estimates to the optimum at each iteration stage.
We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.
An additive and semidefinite programming (SDP) computable entanglement measure is introduced to upper bound the amount of distillable entanglement in bipartite quantum states by operations completely preserving the positivity of partial transpose (PPT). This quantity is always smaller than or equal to the logarithmic negativity, the previously best known SDP bound on distillable entanglement, and the inequality is strict in general. Furthermore, a succinct SDP characterization of the one-copy PPT deterministic distillable entanglement for any given state is also obtained, which provides a simple but useful lower bound on the PPT distillable entanglement. Remarkably, there is a genuinely mixed state of which both bounds coincide with the distillable entanglement, while being strictly less than the logarithmic negativity.
This thesis aims to improve our understanding of the structure of quantum entanglement and the limits of information processing with quantum systems. It presents new results relevant to three threads of quantum information: the theory of quantum entanglement, the communication capabilities of quantum channels, and the quantum zero-error information theory. \nIn the first part, we investigate the fundamental features of quantum entanglement and develop quantitative approaches to better exploit the power of entanglement. First, we introduce a computable and additive entanglement measure to quantify the amount of entanglement, which also plays an important role as the improved semidefinite programming (SDP) upper bound of distillable entanglement. Second, we show that the Rains bound is neither additive nor equal to the asymptotic relative entropy of entanglement. Third, we establish SDP lower bounds for the entanglement cost and demonstrate the irreversibility of asymptotic entanglement manipulation under positive-partial-transpose-preserving quantum operations, resolving a major open problem in quantum information theory. \nIn the second part, we develop a framework of semidefinite programs to evaluate the classical and quantum communication capabilities of quantum channels in both the non-asymptotic and asymptotic regimes. In particular, we establish the first general SDP strong converse bound on the classical capacity of an arbitrary quantum channel and give in particular the best known upper bound on the classical capacity of the amplitude damping channel. We further establish a finite resource analysis of classical communication over quantum erasure channels, including the first second-order expansion of classical capacity beyond entanglement-breaking channels. For quantum communication, we establish the best SDP-computable strong converse bound and refine it as the so-called max-Rains information. \nIn the third part, we investigate the quantum zero-error information theory. In contrast to the conventional Shannon theory, there is a very different-looking information theory when errors are required to be precisely zero, where the communication problem reduces to the analysis of the so-called confusability graph (noncommutative graph) of a classical channel (quantum channel). We develop an activated communication model and explore its novel properties. Notably, we separate the quantum Lovász number and the entanglement-assisted zero-error capacity, resolving an intriguing open problem in the area of zero-error information.
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n21m21s2poly(log(n),log(m),R,r,1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R,r a upper bounds on the size of the optimal primal and dual solutions. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m. We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n21+m21) quantum lower bound for solving semidefinite programs with constant s,R,r and δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.