Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.02578 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929576453603328 |
|---|---|
| author | Basso, Joao Chen, Chi-Fang Dalzell, Alexander M. |
| author_facet | Basso, Joao Chen, Chi-Fang Dalzell, Alexander M. |
| contents | A central challenge in quantum simulation is to prepare low-energy states of strongly interacting many-body systems. In this work, we study the problem of preparing a quantum state that optimizes a random all-to-all, sparse or dense, spin or fermionic $k$-local Hamiltonian. We prove that a simplified quantum Gibbs sampling algorithm achieves a $Ω(\frac{1}{k})$-fraction approximation of the optimum, giving an exponential improvement on the $k$-dependence over the prior best (both classical and quantum) algorithmic guarantees. Combined with the circuit lower bound for such states, our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial. This further indicates that quantum Gibbs sampling may be a suitable metaheuristic for optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02578 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimizing random local Hamiltonians by dissipation Basso, Joao Chen, Chi-Fang Dalzell, Alexander M. Quantum Physics A central challenge in quantum simulation is to prepare low-energy states of strongly interacting many-body systems. In this work, we study the problem of preparing a quantum state that optimizes a random all-to-all, sparse or dense, spin or fermionic $k$-local Hamiltonian. We prove that a simplified quantum Gibbs sampling algorithm achieves a $Ω(\frac{1}{k})$-fraction approximation of the optimum, giving an exponential improvement on the $k$-dependence over the prior best (both classical and quantum) algorithmic guarantees. Combined with the circuit lower bound for such states, our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial. This further indicates that quantum Gibbs sampling may be a suitable metaheuristic for optimization problems. |
| title | Optimizing random local Hamiltonians by dissipation |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2411.02578 |