This thesis explores algorithmic applications and limitations of convex relaxation hierarchies for approximating some discrete and continuous optimization problems. - We show a dichotomy of approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations: for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by super-constant levels of the Sherali-Adams hierarchy on instances of size $n$ . - For the problem of approximating the absolute maximum of an n-variate degree-d homogeneous polynomial f with real coefficients over the unit sphere, we analyze the optimum value of the level-t sum-of-squares (SoS) SDP relaxation of the problem. Our results offer a trade-off between the approximation ratio and running time, which can take advantage of additional structure in the polynomial, such as non-negativity or sparsity of the coefficients. - We study the problem of approximating the $p \to q$ -norm of a matrix $A$ , and prove the first NP-hardness result for approximating norms in the hypercontractive case $1< p < q < \infty$ . We also prove almost tight algorithmic results for the case when $p \geq q$ (with $2 \in [q,p]$ ) where constant factor approximations for the matrix norms are possible. A common theme for these results is their connection to geometry. For the discrete optimization problem of CSP, geometry appears as a crucial tool for our lower bound proof. For the problem of polynomial optimization, we show that SDPs capture and extend earlier algorithms based on diameter estimation for convex bodies. For the matrix (operator) norm problem, the definition itself is geometric in nature and embedding theorems play a crucial role in our proofs.This thesis explores algorithmic applications and limitations of convex relaxation hierarchies for approximating some discrete and continuous optimization problems. - We show a dichotomy of approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations: for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by super-constant levels of the Sherali-Adams hierarchy on instances of size $n$. - For the problem of approximating the absolute maximum of an n-variate degree-d homogeneous polynomial f with real coefficients over the unit sphere, we analyze the optimum value of the level-t sum-of-squares (SoS) SDP relaxation of the problem. Our results offer a trade-off between the approximation ratio and running time, which can take advantage of additional structure in the polynomial, such as non-negativity or sparsity of the coefficients. - We study the problem of approximating the $p \to q$-norm of a matrix $A$, and prove the first NP-hardness result for approximating norms in the hypercontractive case $1< p < q < \infty$. We also prove almost tight algorithmic results for the case when $p \geq q$ (with $2 \in [q,p]$) where constant factor approximations for the matrix norms are possible. A common theme for these results is their connection to geometry. For the discrete optimization problem of CSP, geometry appears as a crucial tool for our lower bound proof. For the problem of polynomial optimization, we show that SDPs capture and extend earlier algorithms based on diameter estimation for convex bodies. For the matrix (operator) norm problem, the definition itself is geometric in nature and embedding theorems play a crucial role in our proofs.

arXiv:2508.21327Aug 29, 20250 citations

Quantum Approximation Complexity of Classical Optimization Problems

Stuart Hadfield

Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors. Assuming NP $\nsubseteq$ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors. Assuming NP $\nsubseteq$ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.

quant-pharXiv:2610.09584Oct 8, 20260 citations

Efficient linear reformulations for binary polynomial optimization problems

Sourour Elloumi, Zoé Verchère

Computers & Operations ResearchApr 5, 20235 citations

Discrete Dynamical System Approaches for Boolean Polynomial Optimization

Yi-Shuai Niu, Roland Glowinski

arXiv:1912.10221Journal of Scientific ComputingJun 30, 20228 citations

Approximation Algorithms for Quadratic Programming

Minyue Fu, Zhi-Quan Tom Luo, Yinyu Ye Y

Journal of Combinatorial OptimizationMar 1, 199879 citations

A Quantum Variational Approach to Phase-Only Pattern Synthesis

Sigurd Huber, Michael Epping

Phase-only pattern synthesis is a long-standing and hard to solve problem in antenna engineering. Due to its non-linear nature, this kind of optimization problem is classically approached with iterative algorithms, where the convergence time depends on the problem topology. Often these heuristic solution routines get stuck in local optima and yield sub-optimal results. This paper addresses phase-only pattern synthesis by using a variational quantum algorithm, the quantum approximate optimization algorithm (QAOA). In this context, a mathematical approach is presented, which discretizes the optimization variables and allows representing the original non-linear functional as a higher-order polynomial. In contrast to other series expansion techniques it turns out that this polynomial has finite length without introducing any approximations. This makes phase-only patterns synthesis problems suitable to be solved on quantum computers with standard gate sets. The mathematical treatment of this optimization problem is complemented by a complexity analysis and a performance analysis. Finally, the challenges regarding future deployment of quantum approximate optimization for phase-only pattern synthesis are discussed.Phase-only pattern synthesis is a long-standing and hard to solve problem in antenna engineering. Due to its non-linear nature, this kind of optimization problem is classically approached with iterative algorithms, where the convergence time depends on the problem topology. Often these heuristic solution routines get stuck in local optima and yield sub-optimal results. This paper addresses phase-only pattern synthesis by using a variational quantum algorithm, the quantum approximate optimization algorithm (QAOA). In this context, a mathematical approach is presented, which discretizes the optimization variables and allows representing the original non-linear functional as a higher-order polynomial. In contrast to other series expansion techniques it turns out that this polynomial has finite length without introducing any approximations. This makes phase-only patterns synthesis problems suitable to be solved on quantum computers with standard gate sets. The mathematical treatment of this optimization problem is complemented by a complexity analysis and a performance analysis. Finally, the challenges regarding future deployment of quantum approximate optimization for phase-only pattern synthesis are discussed.

IEEE Transactions on Quantum EngineeringJan 1, 20260 citations

n

. - For the problem of approximating the absolute maximum of an n-variate degree-d homogeneous polynomial f with real coefficients over the unit sphere, we analyze the optimum value of the level-t sum-of-squares (SoS) SDP relaxation of the problem. Our results offer a trade-off between the approximation ratio and running time, which can take advantage of additional structure in the polynomial, such as non-negativity or sparsity of the coefficients. - We study the problem of approximating the

p \to q

-norm of a matrix

A

, and prove the first NP-hardness result for approximating norms in the hypercontractive case

1< p < q < \infty

. We also prove almost tight algorithmic results for the case when

p \geq q

(with

2 \in [q,p]

) where constant factor approximations for the matrix norms are possible. A common theme for these results is their connection to geometry. For the discrete optimization problem of CSP, geometry appears as a crucial tool for our lower bound proof. For the problem of polynomial optimization, we show that SDPs capture and extend earlier algorithms based on diameter estimation for convex bodies. For the matrix (operator) norm problem, the definition itself is geometric in nature and embedding theorems play a crucial role in our proofs.

\nsubseteq

BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.