Partition Function Estimation: Quantum and Quantum-Inspired Algorithms

• URL: http://arxiv.org/abs/2208.00930v1
• Date: Mon, 1 Aug 2022 15:29:06 GMT
• Title: Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
• Authors: Andrew Jackson, Theodoros Kapourniotis, Animesh Datta
• Abstract summary: We present two algorithms, one quantum and one classical, for estimating partition functions of quantum spin Hamiltonians. The former is a DQC1 (Deterministic quantum computation with one clean qubit) algorithm, and the first such for complex temperatures.
• Score: 1.7510560590853574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present two algorithms, one quantum and one classical, for estimating partition functions of quantum spin Hamiltonians. The former is a DQC1 (Deterministic quantum computation with one clean qubit) algorithm, and the first such for complex temperatures. The latter, for real temperatures, achieves performance comparable to a state-of-the-art DQC1 algorithm [Chowdhury et al. Phys. Rev. A 103, 032422 (2021)]. Both our algorithms take as input the Hamiltonian decomposed as a linear combination Pauli operators. We show this decomposition to be DQC1-hard for a given Hamiltonian, providing new insight into the hardness of estimating partition functions.

Related papers

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• 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)
• Scalable Algorithms for Power Function Calculations of quantum states in NISQ Era [7.2223563491914]
  This article focuses on the development of scalable and quantum bit-efficient algorithms for computing power functions of random quantum states. Two algorithms, based on Hadamard testing and Gate Set Tomography, are proposed.
  arXiv  Detail & Related papers  (2023-08-28T16:08:17Z)
• 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)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  An ideal state preparation protocol can be characterized by being easily generated classically. We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC) We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
  arXiv  Detail & Related papers  (2022-11-18T20:31:10Z)
• 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)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Optimization and Noise Analysis of the Quantum Algorithm for Solving One-Dimensional Poisson Equation [17.65730040410185]
  We propose an efficient quantum algorithm for solving one-dimensional Poisson equation. We further develop this algorithm to make it closer to the real application on the noisy intermediate-scale quantum (NISQ) devices. We analyze the effect of common noise existing in the real quantum devices on our algorithm using the IBM Qiskit toolkit.
  arXiv  Detail & Related papers  (2021-08-27T09:44:41Z)
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions [4.2698418800007865]
  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.
  arXiv  Detail & Related papers  (2020-09-23T17:27:28Z)
• Characterization of exact one-query quantum algorithms (ii): for partial functions [0.2741266294612775]
  The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity.
  arXiv  Detail & Related papers  (2020-08-27T09:06:34Z)
• Quantum algorithmic differentiation [0.0]
  We present an algorithm to perform algorithmic differentiation in the context of quantum computing. We present two versions of the algorithm, one which is fully quantum and one which employees a classical step.
  arXiv  Detail & Related papers  (2020-06-23T22:52:22Z)
• Algorithms for quantum simulation at finite energies [0.7734726150561088]
  We introduce two kinds of quantum algorithms to explore microcanonical and canonical properties of many-body systems. One is a hybrid quantum algorithm that computes expectation values in a finite energy interval around its mean energy. The other is a quantum-assisted Monte Carlo sampling method to compute other quantities.
  arXiv  Detail & Related papers  (2020-06-04T17:40:29Z)
• Simulation of Thermal Relaxation in Spin Chemistry Systems on a Quantum Computer Using Inherent Qubit Decoherence [53.20999552522241]
  We seek to take advantage of qubit decoherence as a resource in simulating the behavior of real world quantum systems. We present three methods for implementing the thermal relaxation. We find excellent agreement between our results, experimental data, and the theoretical prediction.
  arXiv  Detail & Related papers  (2020-01-03T11:48:11Z)

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.