Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917426289967104 |
|---|---|
| author | Wang, Iria W. Brown, Robin Patti, Taylor L. Anandkumar, Anima Pavone, Marco Yelin, Susanne F. |
| author_facet | Wang, Iria W. Brown, Robin Patti, Taylor L. Anandkumar, Anima Pavone, Marco Yelin, Susanne F. |
| contents | 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-$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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07774 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives Wang, Iria W. Brown, Robin Patti, Taylor L. Anandkumar, Anima Pavone, Marco Yelin, Susanne F. Quantum Physics 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-$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 |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.07774 |