A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit

• URL: http://arxiv.org/abs/2209.14989v3
• Date: Wed, 3 Jul 2024 14:41:37 GMT
• Title: A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
• Authors: Hamza Fawzi, Omar Fawzi, Samuel O. Scalet,
• Abstract summary: We introduce a classical algorithm to approximate the free energy of local, translationin, one-dimensional quantum systems. Our algorithm runs for any fixed temperature $T > 0 in subpolynomial time.
• Score: 10.2138250640885
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a classical algorithm to approximate the free energy of local, translation-invariant, one-dimensional quantum systems in the thermodynamic limit of infinite chain size. While the ground state problem (i.e., the free energy at temperature $T = 0$) for these systems is expected to be computationally hard even for quantum computers, our algorithm runs for any fixed temperature $T > 0$ in subpolynomial time, i.e., in time $O((\frac{1}{\varepsilon})^{c})$ for any constant $c > 0$ where $\varepsilon$ is the additive approximation error. Previously, the best known algorithm had a runtime that is polynomial in $\frac{1}{\varepsilon}$. Our algorithm is also particularly simple as it reduces to the computation of the spectral radius of a linear map. This linear map has an interpretation as a noncommutative transfer matrix and has been studied previously to prove results on the analyticity of the free energy and the decay of correlations. We also show that the corresponding eigenvector of this map gives an approximation of the marginal of the Gibbs state and thereby allows for the computation of various thermodynamic properties of the quantum system.

Related papers

• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations. The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions. The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Efficient Quantum Simulation Algorithms in the Path Integral Formulation [0.5729426778193399]
  We provide two novel quantum algorithms based on Hamiltonian versions of the path integral formulation and another for Lagrangians of the form $fracm2dotx2 - V(x)$. We show that our Lagrangian simulation algorithm requires a number of queries to an oracle that computes the discrete Lagrangian that scales for a system with $eta$ particles in $D+1$ dimensions, in the continuum limit, as $widetildeO(eta D t2/epsilon)$ if $V(x)$ is bounded
  arXiv  Detail & Related papers  (2024-05-11T15:48:04Z)
• An efficient quantum algorithm for generation of ab initio n-th order susceptibilities for non-linear spectroscpies [0.13980986259786224]
  We develop and analyze a fault-tolerant quantum algorithm for computing $n$-th order response properties. We use a semi-classical description in which the electronic degrees of freedom are treated quantum mechanically and the light is treated as a classical field.
  arXiv  Detail & Related papers  (2024-04-01T20:04:49Z)
• Small-time controllability for the nonlinear Schr\"odinger equation on $\mathbb{R}^N$ via bilinear electromagnetic fields [55.2480439325792]
  We address the small-time controllability problem for a nonlinear Schr"odinger equation (NLS) on $mathbbRN$ in the presence of magnetic and electric external fields. In detail, we study when it is possible to control the dynamics of (NLS) as fast as desired via sufficiently large control signals.
  arXiv  Detail & Related papers  (2023-07-28T21:30:44Z)
• Fast quantum algorithm for differential equations [0.5895819801677125]
  We present a quantum algorithm with numerical complexity that is polylogarithmic in $N$ but is independent of $kappa$ for a large class of PDEs. Our algorithm generates a quantum state that enables extracting features of the solution.
  arXiv  Detail & Related papers  (2023-06-20T18:01:07Z)
• Calculating the many-body density of states on a digital quantum computer [58.720142291102135]
  We implement a quantum algorithm to perform an estimation of the density of states on a digital quantum computer. We use our algorithm to estimate the density of states of a non-integrable Hamiltonian on the Quantinuum H1-1 trapped ion chip for a controlled register of 18bits.
  arXiv  Detail & Related papers  (2023-03-23T17:46:28Z)
• On parametric resonance in the laser action [91.3755431537592]
  We consider the selfconsistent semiclassical Maxwell--Schr"odinger system for the solid state laser. We introduce the corresponding Poincar'e map $P$ and consider the differential $DP(Y0)$ at suitable stationary state $Y0$.
  arXiv  Detail & Related papers  (2022-08-22T09:43:57Z)
• On the complexity of quantum partition functions [2.6937287784482313]
  We study the computational complexity of approximating quantities for $n$-qubit local Hamiltonians. A classical algorithm with $mathrmpoly(n)$ approximates the free energy of a given $2$-local Hamiltonian.
  arXiv  Detail & Related papers  (2021-10-29T00:05:25Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states [14.567067583556714]
  We propose a new thermal area law that holds for generic many-body systems on lattices. We improve the temperature dependence from the original $mathcalO(beta)$ to $tildemathcalO(beta2/3)$. We also prove analogous bounds for the R'enyi entanglement of purification and the entanglement of formation.
  arXiv  Detail & Related papers  (2020-07-22T02:55:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.