On the complexity of quantum partition functions
- URL: http://arxiv.org/abs/2110.15466v2
- Date: Wed, 20 Sep 2023 21:23:37 GMT
- Title: On the complexity of quantum partition functions
- Authors: Sergey Bravyi, Anirban Chowdhury, David Gosset, Pawel Wocjan
- Abstract summary: 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.
- Score: 2.6937287784482313
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The partition function and free energy of a quantum many-body system
determine its physical properties in thermal equilibrium. Here we study the
computational complexity of approximating these quantities for $n$-qubit local
Hamiltonians. First, we report a classical algorithm with $\mathrm{poly}(n)$
runtime which approximates the free energy of a given $2$-local Hamiltonian
provided that it satisfies a certain denseness condition. Our algorithm
combines the variational characterization of the free energy and convex
relaxation methods. It contributes to a body of work on efficient approximation
algorithms for dense instances of optimization problems which are hard in the
general case, and can be viewed as simultaneously extending existing algorithms
for (a) the ground energy of dense $2$-local Hamiltonians, and (b) the free
energy of dense classical Ising models. Secondly, we establish polynomial-time
equivalence between the problem of approximating the free energy of local
Hamiltonians and three other natural quantum approximate counting problems,
including the problem of approximating the number of witness states accepted by
a QMA verifier. These results suggest that simulation of quantum many-body
systems in thermal equilibrium may precisely capture the complexity of a broad
family of computational problems that has yet to be defined or characterized in
terms of known complexity classes. Finally, we summarize state-of-the-art
classical and quantum algorithms for approximating the free energy and show how
to improve their runtime and memory footprint.
Related papers
- On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
A feature of constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard.
For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class.
We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_mathrmunsat-N_mathrmsat$, spectrally filtered quantum optimization will return states with $E leq q_m.
arXiv Detail & Related papers (2023-12-11T04:15:55Z) - Dense outputs from quantum simulations [5.295277584890625]
The quantum dense output problem is the process of evaluating time-accumulated observables from time-dependent quantum dynamics.
This problem arises frequently in applications such as quantum control and spectroscopic computation.
We present a range of algorithms designed to operate on both early and fully fault-tolerant quantum platforms.
arXiv Detail & Related papers (2023-07-26T18:16:51Z) - Variational quantum algorithms for scanning the complex spectrum of
non-Hermitian systems [0.0]
We propose a variational method for solving the non-Hermitian Hamiltonian on a quantum computer.
The energy is set as a parameter in the cost function and can be tuned to obtain the whole spectrum.
Our work suggests an avenue for solving non-Hermitian quantum many-body systems with variational quantum algorithms on near-term noisy quantum computers.
arXiv Detail & Related papers (2023-05-31T12:50:22Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions.
The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix.
We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
arXiv Detail & Related papers (2023-04-12T18:10:47Z) - 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) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems.
This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state.
Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
arXiv Detail & Related papers (2023-02-07T10:57:36Z) - Near-term quantum algorithm for computing molecular and materials
properties based on recursive variational series methods [44.99833362998488]
We propose a quantum algorithm to estimate the properties of molecules using near-term quantum devices.
We test our method by computing the one-particle Green's function in the energy domain and the autocorrelation function in the time domain.
arXiv Detail & Related papers (2022-06-20T16:33:23Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - A Hybrid Quantum-Classical Hamiltonian Learning Algorithm [6.90132007891849]
Hamiltonian learning is crucial to the certification of quantum devices and quantum simulators.
We propose a hybrid quantum-classical Hamiltonian learning algorithm to find the coefficients of the Pauli operator of the Hamiltonian.
arXiv Detail & Related papers (2021-03-01T15:15:58Z) - Iterative Quantum Assisted Eigensolver [0.0]
We provide a hybrid quantum-classical algorithm for approximating the ground state of a Hamiltonian.
Our algorithm builds on the powerful Krylov subspace method in a way that is suitable for current quantum computers.
arXiv Detail & Related papers (2020-10-12T12:25:16Z) - Variational Monte Carlo calculations of $\mathbf{A\leq 4}$ nuclei with
an artificial neural-network correlator ansatz [62.997667081978825]
We introduce a neural-network quantum state ansatz to model the ground-state wave function of light nuclei.
We compute the binding energies and point-nucleon densities of $Aleq 4$ nuclei as emerging from a leading-order pionless effective field theory Hamiltonian.
arXiv Detail & Related papers (2020-07-28T14:52:28Z)
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.