Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0402076

There, and Back Again: Quantum Theory and Global Optimisation

Koenraad M. R. Audenaert

Published Feb 11, 2004• 7 citations
arXivHTMLPDF

Abstract

We consider a problem in quantum theory that can be formulated as an optimisation problem and present a global optimisation algorithm for solving it, the foundation of which relies in turn on a theorem from quantum theory. To wit, we consider the maximal output purity $ν_q$ of a quantum channel as measured by Schatten $q$-norms, for integer $q$. This quantity is of fundamental importance in the study of quantum channel capacities in quantum information theory. To calculate $ν_q$ one has to solve a non-convex optimisation problem that typically exhibits local optima. We show that this particular problem can be approximated to arbitrary precision by an eigenvalue problem over a larger matrix space, thereby circumventing the problem of local optima. The mathematical proof behind this algorithm relies on the Quantum de Finetti theorem, which is a theorem used in the study of the foundations of quantum theory. We expect that the approach presented here can be generalised and will turn out to be applicable to a larger class of global optimisation problems. We also present some preliminary numerical results, showing that, at least for small problem sizes, the present approach is practically realisable.

DOI
10.48550/arxiv.quant-ph/0402076

Related papers

On some additivity problems in quantum information theory

Grigori Gennadievich Amosov, Alexander Semenovich Holevo, Reinhard F. Werner

A class of problems in quantum information theory, having an elementary formulation but still resisting solution, concerns the additivity properties of various quantities characterizing quantum channels, notably the "classical capacity", and the "maximal output purity". All known results, including extensive numerical work, are consistent with the conjecture that these quantities are indeed additive (resp. multiplicative) with respect to tensor products of channels. A proof of this conjecture would have important consequences in quantum information theory. In particular, according to this conjecture, the classical capacity or the maximal purity of outputs cannot be increased by using entangled inputs of the channel. In this paper we state the additivity/multiplicativity problems, give some relations between them, and prove some new partial results, which also support the conjecture.

arXiv:math-ph/0003002•Mar 4, 2000•125 citations

Notes on multiplicativity of maximal output purity for completely positive qubit maps

K M R Audenaert

A problem in quantum information theory that has received considerable attention in recent years is the question of multiplicativity of the so-called maximal output purity (MOP) of a quantum channel. This quantity is defined as the maximum value of the purity one can get at the output of a channel by varying over all physical input states, when purity is measured by the Schatten $q$-norm, and is denoted by $ν_q$. The multiplicativity problem is the question whether two channels used in parallel have a combined $ν_q$ that is the product of the $ν_q$ of the two channels. A positive answer would imply a number of other additivity results in QIT. Very recently, P. Hayden has found counterexamples for every value of $q>1$. Nevertheless, these counterexamples require that the dimension of these channels increases with $1-q$ and therefore do not rule out multiplicativity for $q$ in intervals $[1,q_0)$ with $q_0$ depending on the channel dimension. I argue that this would be enough to prove additivity of entanglement of formation and of the classical capacity of quantum channels. More importantly, no counterexamples have as yet been found in the important special case where one of the channels is a qubit-channel, i.e. its input states are 2-dimensional. In this paper I focus attention to this qubit case and I rephrase the multiplicativity conjecture in the language of block matrices and prove the conjecture in a number of special cases.

arXiv:0709.0855•Journal of Physics Conference Series•Mar 1, 2008•1 citation

Quantum de finetti theorems under local measurements with applications

Fernando G. S. L. Brandão, Aram W. Harrow

Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling probability distributions. We give the following applications of the results to quantum complexity theory, polynomial optimization, and quantum information theory: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the assumption there is no subexponential-time algorithm for SAT. In the protocol a prover sends to a verifier √n polylog(n) unentangled quantum states, each composed of O(log(n)) qubits, as a proof of the satisfiability of a 3-SAT instance with n variables and O(n) clauses. The quantum verifier checks the validity of the proof by performing local measurements on each of the proofs and classically processing the outcomes. We show that any similar protocol with O(n1/2 - ε) qubits would imply a exp (n1 - 2ε polylog(n))-time algorithm for 3-SAT. We show that the maximum winning probability of free games (in which the questions to each prover are chosen independently) can be estimated by linear programming in time exp(O(log|Q| + log2|A|/ε2) ), with |Q| and |A| the question and answer alphabet sizes, respectively, matching the performance of a previously known algorithm due to Aaronson, Impagliazzo, Moshkovitz, and Shor. This result follows from a new monogamy relation for non-locality, showing that k-extendible non-signaling distributions give at most a O(k-1/2) advantage over classical strategies for free games. We also show that 3-SAT with n variables can be reduced to obtaining a constant error approximation of the maximum winning probability under entangled strategies of O(√n)-player one-round non-local games, in which only two players are selected to send O(√n)-bit messages. We show that the optimization of certain polynomials over the complex hypersphere can be performed in quasipolynomial time in the number of variables $n$ by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. This can be considered an analogue to the hypersphere of a similar known results for the simplex. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a quantum tomography result due to Aaronson -- showing that given an unknown n-qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information. The results constitute improvements and generalizations of a recent de Finetti theorem due to Brandao, Christandl and Yard.

arXiv:1210.6367•ACM Symposium on Theory of Computing (STOC)•May 28, 2013•74 citations

Exponential de Finetti Theorems for Fermionic Gaussian States

Jędrzej Burkat, Michał Studziński, Sergii Strelchuk

We prove an exponential variant of the Gaussian de Finetti theorem: the subsystems of permutation-invariant, free-fermionic Gaussian states are well approximated by convex combinations of almost-i.i.d. states that are Gaussian on subsets of their parts. Our result provides an error bound between the original state and its approximants that decays exponentially in the number of unconstrained parts, becoming super-exponential when the subsystem under consideration is small. The dependence of our bound on the local Hilbert space dimension is polylogarithmic, giving an exponential improvement over the standard de Finetti theorem of [Nat. Phys. 3, 645-649]. Previous works considered Gaussian-symmetric states, which are supported on the trivial irrep of the tensor matchgate representation. We extend these results to the broader class of Gaussian-invariant states, which contains, for example, i.i.d. copies of single-replica mixed Gaussian states. We show that Gaussian-invariant states are precisely the partial traces of Gaussian-symmetric states on locally enlarged replicas and always admit a purification into a larger Gaussian-symmetric state. As an application, we derive explicit convergence bounds for a hierarchy of convex relaxations of polynomial optimisation over fermionic Gaussian states. For variational energy minimisation, the hierarchy gives lower bounds converging to the global Gaussian minimum. Combined with upper bounds from Gaussian trial states, these bounds quantify how far a variational calculation can be from the best energy attainable within the Gaussian family.

quant-pharXiv:2607.25779•Jul 29, 2026•1 citation

Probability Measures on the Set of Quantum States in Optimization Problems for Information Quantities

A. S. Holevo

A number of optimization problems in quantum information theory, such as one-shot classical capacity of a quantum channel, entanglement of formation of a state, classical capacity of a quantum observable, and accessible information of an ensemble of quantum states, can be formulated as the calculation of the convex closure of the output entropy of a certain quantum channel. This general problem can be considered as a convex programming problem for which necessary and sufficient optimality conditions can be established along with a dual problem. These optimality conditions imply some tight lower bounds for entropy, either quantum or classical, which are related to the famous logarithmic Sobolev inequality.

Theory of Probability and Its Applications•Aug 1, 2026•0 citations

Optimal Quantum de Finetti Theorems via Argmax Rounding

Fernando Granha Jeronimo, Pei Wu, Haochen Xu

We prove optimal finite quantum de Finetti upper bounds. Given a bosonic state $ρ_N\in D(\mathrm{Sym}^N(\mathbb C^d))$, there is a probability measure $ν$ on the unit sphere such that \[ \left\| ρ_N^{(2)}-\int |u\rangle\langle u|^{\otimes 2}\,dν(u) \right\|_1 \le \frac{\sqrt{d-1}}{N-1}. \] By purification, the bosonic theorem also gives the optimal $O(d/N)$ upper bound for arbitrary exchangeable states. These results settle the dimension dependence left open by Christandl, König, Mitchison, and Renner (CMP 2007). The proof casts de Finetti approximation as sum-of-squares rounding and applies the argmax method of Jeronimo, Wu, and Xu (manuscript 2026). More generally, $t$-site marginals satisfy $O(t\sqrt d/N)$ bosonic and $O(td/N)$ permutation-invariant bounds. Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program and rounds an optimum by the argmax principle. The sharp bounds have several consequences. For every fixed $\varepsilon\in(0,1)$, we construct a channel with input dimension $D=\exp(O_\varepsilon(\sqrt d\log d))=\exp(o(d))$ whose outputs are $\varepsilon$-close to separable states of local dimension $d$ and whose image contains every such separable state, thereby refuting Watrous's disentangler conjecture. We also obtain deterministic $\exp(\widetilde O(\sqrt d/\varepsilon))$-time algorithms for explicit Best Separable State without perfect completeness and for trace-distance separability testing. Finally, spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance, with the optimal rate $Θ(N^{-1/2})$ when the dimension may grow.

quant-pharXiv:2608.02590•Aug 4, 2026•5 citations
We consider a problem in quantum theory that can be formulated as an optimisation problem and present a global optimisation algorithm for solving it, the foundation of which relies in turn on a theorem from quantum theory. To wit, we consider the maximal output purity νqν_qνq​ of a quantum channel as measured by Schatten qqq-norms, for integer qqq. This quantity is of fundamental importance in the study of quantum channel capacities in quantum information theory. To calculate νqν_qνq​ one has to solve a non-convex optimisation problem that typically exhibits local optima. We show that this particular problem can be approximated to arbitrary precision by an eigenvalue problem over a larger matrix space, thereby circumventing the problem of local optima. The mathematical proof behind this algorithm relies on the Quantum de Finetti theorem, which is a theorem used in the study of the foundations of quantum theory. We expect that the approach presented here can be generalised and will turn out to be applicable to a larger class of global optimisation problems. We also present some preliminary numerical results, showing that, at least for small problem sizes, the present approach is practically realisable.
A class of problems in quantum information theory, having an elementary formulation but still resisting solution, concerns the additivity properties of various quantities characterizing quantum channels, notably the "classical capacity", and the "maximal output purity". All known results, including extensive numerical work, are consistent with the conjecture that these quantities are indeed additive (resp. multiplicative) with respect to tensor products of channels. A proof of this conjecture would have important consequences in quantum information theory. In particular, according to this conjecture, the classical capacity or the maximal purity of outputs cannot be increased by using entangled inputs of the channel. In this paper we state the additivity/multiplicativity problems, give some relations between them, and prove some new partial results, which also support the conjecture.
A problem in quantum information theory that has received considerable attention in recent years is the question of multiplicativity of the so-called maximal output purity (MOP) of a quantum channel. This quantity is defined as the maximum value of the purity one can get at the output of a channel by varying over all physical input states, when purity is measured by the Schatten qqq-norm, and is denoted by νqν_qνq​. The multiplicativity problem is the question whether two channels used in parallel have a combined νqν_qνq​ that is the product of the νqν_qνq​ of the two channels. A positive answer would imply a number of other additivity results in QIT. Very recently, P. Hayden has found counterexamples for every value of q>1q>1q>1. Nevertheless, these counterexamples require that the dimension of these channels increases with 1−q1-q1−q and therefore do not rule out multiplicativity for qqq in intervals [1,q0)[1,q_0)[1,q0​) with q0q_0q0​ depending on the channel dimension. I argue that this would be enough to prove additivity of entanglement of formation and of the classical capacity of quantum channels. More importantly, no counterexamples have as yet been found in the important special case where one of the channels is a qubit-channel, i.e. its input states are 2-dimensional. In this paper I focus attention to this qubit case and I rephrase the multiplicativity conjecture in the language of block matrices and prove the conjecture in a number of special cases.
Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling probability distributions. We give the following applications of the results to quantum complexity theory, polynomial optimization, and quantum information theory: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the assumption there is no subexponential-time algorithm for SAT. In the protocol a prover sends to a verifier √n polylog(n) unentangled quantum states, each composed of O(log(n)) qubits, as a proof of the satisfiability of a 3-SAT instance with n variables and O(n) clauses. The quantum verifier checks the validity of the proof by performing local measurements on each of the proofs and classically processing the outcomes. We show that any similar protocol with O(n1/2 - ε) qubits would imply a exp (n1 - 2ε polylog(n))-time algorithm for 3-SAT. We show that the maximum winning probability of free games (in which the questions to each prover are chosen independently) can be estimated by linear programming in time exp(O(log|Q| + log2|A|/ε2) ), with |Q| and |A| the question and answer alphabet sizes, respectively, matching the performance of a previously known algorithm due to Aaronson, Impagliazzo, Moshkovitz, and Shor. This result follows from a new monogamy relation for non-locality, showing that k-extendible non-signaling distributions give at most a O(k-1/2) advantage over classical strategies for free games. We also show that 3-SAT with n variables can be reduced to obtaining a constant error approximation of the maximum winning probability under entangled strategies of O(√n)-player one-round non-local games, in which only two players are selected to send O(√n)-bit messages. We show that the optimization of certain polynomials over the complex hypersphere can be performed in quasipolynomial time in the number of variables nnn by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. This can be considered an analogue to the hypersphere of a similar known results for the simplex. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a quantum tomography result due to Aaronson -- showing that given an unknown n-qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information. The results constitute improvements and generalizations of a recent de Finetti theorem due to Brandao, Christandl and Yard.
We prove an exponential variant of the Gaussian de Finetti theorem: the subsystems of permutation-invariant, free-fermionic Gaussian states are well approximated by convex combinations of almost-i.i.d. states that are Gaussian on subsets of their parts. Our result provides an error bound between the original state and its approximants that decays exponentially in the number of unconstrained parts, becoming super-exponential when the subsystem under consideration is small. The dependence of our bound on the local Hilbert space dimension is polylogarithmic, giving an exponential improvement over the standard de Finetti theorem of [Nat. Phys. 3, 645-649]. Previous works considered Gaussian-symmetric states, which are supported on the trivial irrep of the tensor matchgate representation. We extend these results to the broader class of Gaussian-invariant states, which contains, for example, i.i.d. copies of single-replica mixed Gaussian states. We show that Gaussian-invariant states are precisely the partial traces of Gaussian-symmetric states on locally enlarged replicas and always admit a purification into a larger Gaussian-symmetric state. As an application, we derive explicit convergence bounds for a hierarchy of convex relaxations of polynomial optimisation over fermionic Gaussian states. For variational energy minimisation, the hierarchy gives lower bounds converging to the global Gaussian minimum. Combined with upper bounds from Gaussian trial states, these bounds quantify how far a variational calculation can be from the best energy attainable within the Gaussian family.
A number of optimization problems in quantum information theory, such as one-shot classical capacity of a quantum channel, entanglement of formation of a state, classical capacity of a quantum observable, and accessible information of an ensemble of quantum states, can be formulated as the calculation of the convex closure of the output entropy of a certain quantum channel. This general problem can be considered as a convex programming problem for which necessary and sufficient optimality conditions can be established along with a dual problem. These optimality conditions imply some tight lower bounds for entropy, either quantum or classical, which are related to the famous logarithmic Sobolev inequality.
We prove optimal finite quantum de Finetti upper bounds. Given a bosonic state ρN∈D(SymN(Cd))ρ_N\in D(\mathrm{Sym}^N(\mathbb C^d))ρN​∈D(SymN(Cd)), there is a probability measure ννν on the unit sphere such that ∥ρN(2)−∫∣u⟩⟨u∣⊗2 dν(u)∥1≤d−1N−1. \left\| ρ_N^{(2)}-\int |u\rangle\langle u|^{\otimes 2}\,dν(u) \right\|_1 \le \frac{\sqrt{d-1}}{N-1}. ​ρN(2)​−∫∣u⟩⟨u∣⊗2dν(u)​1​≤N−1d−1​​. By purification, the bosonic theorem also gives the optimal O(d/N)O(d/N)O(d/N) upper bound for arbitrary exchangeable states. These results settle the dimension dependence left open by Christandl, König, Mitchison, and Renner (CMP 2007). The proof casts de Finetti approximation as sum-of-squares rounding and applies the argmax method of Jeronimo, Wu, and Xu (manuscript 2026). More generally, ttt-site marginals satisfy O(td/N)O(t\sqrt d/N)O(td​/N) bosonic and O(td/N)O(td/N)O(td/N) permutation-invariant bounds. Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program and rounds an optimum by the argmax principle. The sharp bounds have several consequences. For every fixed ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), we construct a channel with input dimension D=exp⁡(Oε(dlog⁡d))=exp⁡(o(d))D=\exp(O_\varepsilon(\sqrt d\log d))=\exp(o(d))D=exp(Oε​(d​logd))=exp(o(d)) whose outputs are ε\varepsilonε-close to separable states of local dimension ddd and whose image contains every such separable state, thereby refuting Watrous's disentangler conjecture. We also obtain deterministic exp⁡(O~(d/ε))\exp(\widetilde O(\sqrt d/\varepsilon))exp(O(d​/ε))-time algorithms for explicit Best Separable State without perfect completeness and for trace-distance separability testing. Finally, spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance, with the optimal rate Θ(N−1/2)Θ(N^{-1/2})Θ(N−1/2) when the dimension may grow.