Computing partition functions in the one clean qubit model

Abstract

We present a method to approximate partition functions of quantum systems using mixed-state quantum computation. For positive semi-definite Hamiltonians, our method has expected running-time that is almost linear in $(M/({\epsilon }_{\mathrm{rel}}\mathcal{Z}){)}^2$, where $M$ is the dimension of the quantum system, $\mathcal{Z}$ is the partition function, and ${\epsilon }_{\mathrm{rel}}$ is the relative precision. It is based on approximations of the exponential operator as linear combinations of certain operators related to block-encoding of Hamiltonians or Hamiltonian evolutions. The trace of each operator is estimated using a standard algorithm in the one clean qubit model. For large values of $\mathcal{Z}$, our method may run faster than exact classical methods, whose complexities are polynomial in $M$. We also prove that a version of the partition function estimation problem within additive error is complete for the so-called DQC1 complexity class, suggesting that our method provides a super-polynomial speedup for certain parameter values. To attain a desired relative precision, we develop a classical procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.

arXiv comment15 pages, 2 figures

References in corpus (17)

• The Kernel Polynomial Method
• On the Power of One Bit of Quantum Information
• Hamiltonian Simulation by Qubitization
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Simulating Physical Phenomena by Quantum Networks
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect
• Liquid state NMR simulations of quantum many-body problems
• Spectral Gap Amplification
• Parameter Estimation with Mixed-State Quantum Computation
• Introduction to NMR Quantum Information Processing
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Quantum algorithms for classical lattice models
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Computation with Unitaries and One Pure Qubit
• Condensation of Anyons in Frustrated Quantum Magnets

Cited by in corpus (14)

• Quantum algorithm for estimating Renyi entropies of quantum states
• On the complexity of quantum partition functions
• Quantum many-body systems in thermal equilibrium
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• The battle of clean and dirty qubits in the era of partial error correction
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
• Randomized semi-quantum matrix processing
• Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
• Simulating Floquet scrambling circuits on trapped-ion quantum computers
• Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
• Quantum Annealing Algorithms for Estimating Ising Partition Functions