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
- Optimizing random local Hamiltonians by dissipation [44.99833362998488]
We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum.
Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
arXiv Detail & Related papers (2024-11-04T20:21:16Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - 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) - 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)
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.