Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

Many practically important NP-hard optimization problems are inherently higher-order polynomial optimizations, which are typically addressed using approximation algorithms. Classical relaxations express polynomial objectives over a polynomial basis and solve the resulting quadratic objective as a semidefinite program, which can significantly inflate problem size and degrade approximation behavior. Variational quantum analogues to classical semidefinite programs (vQSDPs) are near-term formulations geared towards quadratic objectives. We introduce Product-State Lifting (PSL), a simple product-register encoding that upgrades any vQSDP with basis-state encoding to tackle k-degree polynomial optimization. This upgrade requires only a linear increase in resources with constraints constant in k. As a worked example, we pair PSL with the recently-proposed vQSDP with the Hadamard test and approximate amplitude constraints [Quantum 7, 1057 (2023)], and outline an application to Max-kSAT. PSL maintains the device-friendly structure of vQSDPs while making polynomial degree a linear resource parameter, offering a general path from quadratic to polynomial optimization without the constraint growth typical of classical relaxations.