Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions

• URL: http://arxiv.org/abs/2009.11270v5
• Date: Wed, 31 Aug 2022 00:38:44 GMT
• Title: Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• Authors: Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, Pawel Wocjan
• Abstract summary: We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. We modify the classical algorithm of vStefankovivc, Vempala and Vigoda to improve its sample complexity. We quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei.
• Score: 4.2698418800007865
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Our work has two main contributions: first, we modify the classical algorithm of \v{S}tefankovi\v{c}, Vempala and Vigoda (\emph{J.~ACM}, 56(3), 2009) to improve its sample complexity; second, we quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei (SODA 2020). The conventional approach to estimating partition functions requires approximating the means of Gibbs distributions at a set of inverse temperatures that form the so-called cooling schedule. The length of the cooling schedule directly affects the complexity of the algorithm. Combining our improved version of the algorithm of \v{S}tefankovi\v{c}, Vempala and Vigoda with the paired-product estimator of Huber (\emph{Ann.\ Appl.\ Probab.}, 25(2),~2015), our new quantum algorithm uses a shorter cooling schedule than previously known. This length matches the optimal length conjectured by \v{S}tefankovi\v{c}, Vempala and Vigoda. The quantum algorithm also achieves a quadratic advantage in the number of required quantum samples compared to the number of random samples drawn by the best classical algorithm, and its computational complexity has quadratically better dependence on the spectral gap of the Markov chains used to produce the quantum samples.

Related papers

• 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)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future. In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
  arXiv  Detail & Related papers  (2024-01-25T17:37:40Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum jet clustering with LHC simulated data [0.0]
  Two new quantum algorithms might speed up classical jet clustering algorithms. In the first two algorithms, an exponential speed up in dimensionality and data length can be achieved. In the $k_T$ algorithm, a quantum version of the same order as FastJet is achieved.
  arXiv  Detail & Related papers  (2022-09-19T10:51:13Z)
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
  We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time. This is the first speed-up of this type to be obtained over the seminal nearly-linear time of vStefankovivc, Vempala and Vigoda.
  arXiv  Detail & Related papers  (2022-07-18T14:41:48Z)
• Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
  We propose an adaptive algorithm for interval estimation of amplitudes. The proposed algorithm uses a similar number of quantum queries to achieve the same level of precision. We rigorously prove that the number of oracle queries achieves $O(1/epsilon)$, i.e., a quadratic speedup over classical Monte Carlo sampling.
  arXiv  Detail & Related papers  (2022-06-16T21:11:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Quantum vs. classical algorithms for solving the heat equation [0.04297070083645048]
  Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially. Here we consider a prototypical PDE - the heat equation in a rectangular region - and compare in detail the complexities of ten classical and quantum algorithms for solving it.
  arXiv  Detail & Related papers  (2020-04-14T13:57:47Z)

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.