.png){kind=icon}
Return
Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives
.png){kind=icon}
PRE
AI
DOI：.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 (vQS-DPs) 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 [1], 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.
Keywords:
APPROXIMATION ALGORITHMS
Journal
IF:
5.4
Papers:
951
Citations:
1.0W
Organization
View more organizations
Cited Papers
No cited papers available