Abstract The measured relative entropies of quantum states and channels find operational significance in quantum information theory as achievable error rates in hypothesis testing tasks. They are of interest in the near term, as they correspond to hybrid quantum–classical strategies with technological requirements far less challenging to implement than required by the most general strategies allowed by quantum mechanics. In this paper, we prove that these measured relative entropies can be calculated efficiently by means of semidefinite programming (SDP), by making use of variational formulas for the measured relative entropies of states and semidefinite representations of the weighted geometric mean and the operator connection of the logarithm. Not only do the semidefinite programs provide the optimal values of the measured relative entropies of states and channels, but also the numerical characterizations of optimal strategies for achieving them, which is of significant practical interest for designing hypothesis testing protocols.
Abstract The measured relative entropies of quantum states and channels find operational significance in quantum information theory as achievable error rates in hypothesis testing tasks. They are of interest in the near term, as they correspond to hybrid quantum–classical strategies with technological requirements far less challenging to implement than required by the most general strategies allowed by quantum mechanics. In this paper, we prove that these measured relative entropies can be calculated efficiently by means of semidefinite programming (SDP), by making use of variational formulas for the measured relative entropies of states and semidefinite representations of the weighted geometric mean and the operator connection of the logarithm. Not only do the semidefinite programs provide the optimal values of the measured relative entropies of states and channels, but also the numerical characterizations of optimal strategies for achieving them, which is of significant practical interest for designing hypothesis testing protocols.
The problem of reconstructing a quantum channel from a sample of classical data is considered. When the total fidelity can be represented as a ratio of two quadratic forms (e.g., in the case of mapping a mixed state to a pure state, projective operators, unitary learning, and others), Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix. A remarkable feature of SDP is that the optimization is convex, which allows the problem to be efficiently solved by a variety of numerical algorithms. We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms. A notable feature is that the Kraus rank of the obtained quantum channel typically comprises less than a few percent of its maximal possible value. This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data. The theory was also applied to the problem of reconstructing projective operators from data. Finally, we discuss a classical computational model based on quantum channel transformation, performed and calculated on a classical computer, possibly hardware-optimized.
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.
The measured relative entropy and measured Rényi relative entropy are quantifiers of the distinguishability of two quantum states ρ and σ. They are defined as the maximum classical relative entropy or Rényi relative entropy realizable by performing a measurement on ρ and σ, and they have interpretations in terms of asymptotic quantum hypothesis testing. Crucially, they can be rewritten in terms of variational formulas involving the optimization of a concave or convex objective function over the set of positive definite operators. In this paper, we establish foundational properties of these objective functions by analyzing their matrix gradients and Hessian superoperators; namely, we prove that these objective functions are β-smooth and γ-strongly convex / concave, where β and γ depend on the max-relative entropies of ρ and σ. A practical consequence of these properties is that we can conduct Nesterov accelerated projected gradient descent / ascent, a well known classical optimization technique, to calculate the measured relative entropy and measured Rényi relative entropy to arbitrary precision. These algorithms are generally more memory efficient than our previous algorithms based on semi-definite optimization [Huang and Wilde, arXiv:2406.19060], and for well conditioned states ρ and σ, these algorithms are notably faster.
Many fundamental problems in quantum information theory can be formulated as optimization tasks over quantum states and measurements. While the convex structure of quantum theory often enables powerful semidefinite programming formulations, a major challenge persists: the exponential growth of Hilbert space dimension with system size. This dissertation discusses techniques to address these and related obstacles across several core problems in quantum information. We first study optimization over separable quantum states. Such problems are typically NP-hard and standard semidefinite programming hierarchies suffer from the curse of dimensionality. We introduce a hybrid algorithm that leverages a quantum co-processor to reduce the effective dimension of the problem. While several existing approaches provide only a numerical bound on the optimal value, our method is guaranteed to return an explicit feasible solution: a valid separable state, even in instances where it is not optimal. We apply this framework to approximate the minimum separable energy of many-body Hamiltonians, define an entanglement measure for their ground spaces, and demonstrate numerical scalability to systems of up to 28 qubits. We next consider the general Bayes framework, as introduced by Helstrom, for state discrimination when, instead of a classical description of the candidate states, one has access to their source code: the quantum circuit that prepares them. We show that the typical semidefinite program for the discrimination problem can be reformulated in terms of the Gram matrix of these states, reducing the variable dimensions from dL to NL, where d is the Hilbert space dimension, N is the number of candidate states, and L is the number of possible guesses. Importantly, we further introduce a quantum pre-processing procedure which efficiently constructs the reduced problem from the source code, enabling our method to operate directly on quantum data. We consider two applications. First, we characterize the optimal identifications for quantum changepoint problems under several reward structures whose associated discrimination problems were previously computationally inaccessible. Second, we consider a quantum error classification problem and show how our reduction makes it tractable for systems of hundreds of qubits. We also analyze structural measurement strategies. As a counterpart to the well-known pretty good measurement for minimum-error state discrimination, we introduce the pretty bad measurement for the exclusion variant, in which the goal is to identify a state that was not sent, rather than to identify the one that was, and prove that both are guaranteed to perform at least as well as blind guessing in their respective objectives. Finally, we consider evaluating Boolean functions under severe memory constraints and prove that a simple local "greedy" measurement strategy is globally optimal precisely for affine Boolean functions, while more generally achieving at least the square of the optimal global success probability. Together, these results demonstrate that high-dimensional quantum optimization problems often admit hidden structure enabling dimension reduction, hybrid computation, and provable approximation guarantees.
We study the semidefinite programs (SDPs) of quantum information whose variables are density operators, measurement operators, or unbounded positive semidefinite operators, together with their thermodynamic regularizations by the von Neumann, Fermi-Dirac, and Bose-Einstein entropies, which have been associated with Boltzmann, Fermi-Dirac, and Bose-Einstein statistics, respectively. We find that this correspondence is exact: the Fermi-Dirac and Bose-Einstein regularized SDPs coincide with the constrained free-energy minimization of an ideal Fermi or Bose gas whose Hamiltonian and non-commuting charges are the second quantizations of the SDP data and whose one-body density matrix is the SDP variable, while the Boltzmann framework corresponds to the single-particle case. We show that the three frameworks can be unified under one framework, in which each entropy-regularized dual is, up to a term linear in the chemical potentials, the grand potential of the corresponding system; the duals are unconstrained and concave in the chemical-potential vector, with gradient and Hessian given by thermal expectation values that hybrid quantum-classical algorithms can estimate. We further identify the Fermi-Dirac and Bose-Einstein relative entropies with the Umegaki relative entropy between quasi-free states, which yields their monotonicity under gauge-covariant Gaussian channels. The result places a wide class of SDPs and their solvers within the thermodynamics of ideal quantum gases and points to extensions to interacting gases.
Solving optimization problems is a key task for which quantum computers could possibly provide a speedup over the best known classical algorithms. Particular classes of optimization problems including semidefinite programming (SDP) and linear programming (LP) have wide applicability in many domains of computer science, engineering, mathematics, and physics. Here we focus on semidefinite and linear programs for which the dimensions of the variables involved are exponentially large, so that standard classical SDP and LP solvers are not helpful for such large-scale problems. We propose the QSlack and CSlack methods for estimating their optimal values, respectively, which work by (1) introducing slack variables to transform inequality constraints to equality constraints, (2) transforming a constrained optimization to an unconstrained one via the penalty method, and (3) replacing the optimizations over all possible nonnegative variables by optimizations over parameterized quantum states and parameterized probability distributions. Under the assumption that the SDP and LP inputs are efficiently measurable observables, it follows that all terms in the resulting objective functions are efficiently estimable by either a quantum computer in the SDP case or a quantum or probabilistic computer in the LP case. Furthermore, by making use of SDP and LP duality theory, we prove that these methods provide a theoretical guarantee that, if one could find global optima of the objective functions, then the resulting values sandwich the true optimal values from both above and below. Finally, we showcase the QSlack and CSlack methods on a variety of example optimization problems and discuss details of our implementation, as well as the resulting performance. We find that our implementations of both the primal and dual for these problems approach the ground truth, typically achieving errors of the order 10-2.