{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihb4gikumcw7ocp24aj3g43xh2w5mnga44tgsesqqmurymntlrjiy",
    "uri": "at://did:plc:cx57fsir6oyzywdd4jafsdsw/app.bsky.feed.post/3mk2ql6aoxjl2"
  },
  "path": "/papers/q-2026-04-21-2076/",
  "publishedAt": "2026-04-21T09:40:29.000Z",
  "site": "https://quantum-journal.org",
  "tags": [
    "Paper",
    "https://doi.org/10.22331/q-2026-04-21-2076"
  ],
  "textContent": "Quantum 10, 2076 (2026).\n\nhttps://doi.org/10.22331/q-2026-04-21-2076\n\nMany 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-$k$SAT. 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.",
  "title": "Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives"
}