We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on $\mathbb{C}^d\otimes\mathbb{C}^d$. We consider semidefinite programs (SDPs) that approximate the maximum acceptance probability of a measurement over separable states, the optimization problem underlying QMA(2). In the extended-formulation model of Harrow, Natarajan, and Wu (HNW), all measurements share a common feasible region and an objective-independent embedding of product states that exactly reproduces their acceptance probabilities. For every $0<θ<2/7$, there are constants $c_θ,a_θ>0$ such that, for sufficiently large $d$, any such SDP with uniform additive error $0<a\le a_θ$ has size at least $d^{c_θ\min\{a^{-1/3},d^θ\}}$. The bound applies at sufficiently small constant error, is superpolynomial in $d$ whenever $a=o(1)$, and becomes $d^{Ω(d^θ)}$ when $a\le d^{-3θ}$, improving HNW's quasipolynomial bound at inverse- square error. The same bound holds for any SDP-representable convex set of states that contains all separable states and lies within trace distance $a$ of them, giving a quantitative counterpart to Fawzi's theorem that the separable set has no exact semidefinite representation. Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra, and Steurer with explicit block-positive operators and Chebyshev amplification. Our main results are supported by Lean proofs.
We prove quantitative lower bounds on the semidefinite extension complexity of the set of separable quantum states on Cd⊗Cd. We consider semidefinite programs (SDPs) that approximate the maximum acceptance probability of a measurement over separable states, the optimization problem underlying QMA(2). In the extended-formulation model of Harrow, Natarajan, and Wu (HNW), all measurements share a common feasible region and an objective-independent embedding of product states that exactly reproduces their acceptance probabilities. For every 0<θ<2/7, there are constants cθ,aθ>0 such that, for sufficiently large d, any such SDP with uniform additive error 0<a≤aθ has size at least dcθmin{a−1/3,dθ}. The bound applies at sufficiently small constant error, is superpolynomial in d whenever a=o(1), and becomes dΩ(dθ) when a≤d−3θ, improving HNW's quasipolynomial bound at inverse- square error. The same bound holds for any SDP-representable convex set of states that contains all separable states and lies within trace distance a of them, giving a quantitative counterpart to Fawzi's theorem that the separable set has no exact semidefinite representation. Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra, and Steurer with explicit block-positive operators and Chebyshev amplification. Our main results are supported by Lean proofs.
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.
It is well known that state-of-the-art linear programming solvers are more efficient than their semidefinite programming counterparts and can scale to much larger problem sizes. This leads us to consider the question, how well can we approximate semidefinite programs with linear programs? In this paper, we prove lower bounds on the size of linear programs that approximate the positive semidefinite cone. Let D be the set of n × n positive semidefinite matrices of trace equal to one. We prove two results on the hardness of approximating D with polytopes. We show that if 0 < ε < 1and A is an arbitrary matrix of trace equal to one, any polytope P such that (1-ε) (D-A) ⊂ P ⊂ D-A must have linear programming extension complexity at least [Formula: see text], where c > 0 is a constant that depends on ε. Second, we show that any polytope P such that D ⊂ P and such that the Gaussian width of P is at most twice the Gaussian width of D must have extension complexity at least [Formula: see text]. Our bounds are both superpolynomial in n and demonstrate that there is no generic way of approximating semidefinite programs with compact linear programs. The main ingredient of our proofs is hypercontractivity of the noise operator on the hypercube.
We prove optimal finite quantum de Finetti upper bounds. Given a bosonic state ρN∈D(SymN(Cd)), there is a probability measure ν on the unit sphere such that ρN(2)−∫∣u⟩⟨u∣⊗2dν(u)1≤N−1d−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(td/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 ε∈(0,1), we construct a channel with input dimension D=exp(Oε(dlogd))=exp(o(d)) whose outputs are ε-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(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) when the dimension may grow.
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 investigate (k_{1},k_{2}) extendibility of fermionic Gaussian states, a property central to quantum correlations and approximations of separability. We show that these states are (k_{1},k_{2})-extendible if and only if they admit a fermionic Gaussian extension, yielding a complete covariance-matrix characterization and a simple semidefinite program (SDP) whose size scales linearly with the number of modes. This provides necessary conditions for arbitrary fermionic states and is sufficient within the Gaussian setting. Our main result is a finite de Finetti-type theorem: we derive trace-norm bounds between (k_{1},k_{2})-extendible fermionic Gaussian states and separable states, improving previous exponential scaling to linear in the number of modes, with complementary relative entropy and squashed entanglement bounds. For two modes, upper and lower bounds match at order 1/sqrt[k_{1}k_{2}]. Extendibility also provides operational support for one of the different notions of separability in fermionic systems. Finally, for fermionic Gaussian channels, we provide a simple semidefinite program criterion for antidegradability and show that entanglement-breaking channels coincide with replacement channels, implying no nontrivial entanglement-breaking fermionic Gaussian channels exist.
We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with m constraint matrices of dimension n, each of rank at most r, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy ϵ by using mlogm⋅poly(logn,r,ϵ−1) quantum gates. The dependence on n provides an exponential improvement over the work of Brand\~ao and Svore and the work of van Apeldoorn et al., and demonstrates an exponential quantum speed-up when m and r are small.
We apply the SDP solver to the problem of learning 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 ρ, we show we can find in time mlogm⋅poly(logn,r,ϵ−1) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ on the m measurements up to error ϵ. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle.
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 with a poly-logarithmic dependence on its dimension based on the techniques developed in quantum principal component analysis, which could be of independent interest.