Solving cluster moment relaxation with hierarchical matrix
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912479991300096 |
|---|---|
| author | Wang, Yi Huang, Rizheng Khoo, Yuehaw |
| author_facet | Wang, Yi Huang, Rizheng Khoo, Yuehaw |
| contents | Convex relaxation methods are powerful tools for studying the lowest energy of many-body problems. By relaxing the representability conditions for marginals to a set of local constraints, along with a global semidefinite constraint, a polynomial-time solvable semidefinite program (SDP) that provides a lower bound for the energy can be derived. In this paper, we propose accelerating the solution of such an SDP relaxation by imposing a hierarchical structure on the positive semidefinite (PSD) primal and dual variables. Furthermore, these matrices can be updated efficiently using the algebra of the compressed representations within an augmented Lagrangian method. We achieve quadratic and even near-linear time per-iteration complexity. Through experimentation on the quantum transverse field Ising model, we showcase the capability of our approach to provide a sufficiently accurate lower bound for the exact ground-state energy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00235 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Solving cluster moment relaxation with hierarchical matrix Wang, Yi Huang, Rizheng Khoo, Yuehaw Optimization and Control Numerical Analysis Convex relaxation methods are powerful tools for studying the lowest energy of many-body problems. By relaxing the representability conditions for marginals to a set of local constraints, along with a global semidefinite constraint, a polynomial-time solvable semidefinite program (SDP) that provides a lower bound for the energy can be derived. In this paper, we propose accelerating the solution of such an SDP relaxation by imposing a hierarchical structure on the positive semidefinite (PSD) primal and dual variables. Furthermore, these matrices can be updated efficiently using the algebra of the compressed representations within an augmented Lagrangian method. We achieve quadratic and even near-linear time per-iteration complexity. Through experimentation on the quantum transverse field Ising model, we showcase the capability of our approach to provide a sufficiently accurate lower bound for the exact ground-state energy. |
| title | Solving cluster moment relaxation with hierarchical matrix |
| topic | Optimization and Control Numerical Analysis |
| url | https://arxiv.org/abs/2408.00235 |