Polynomial-time classical sampling of high-temperature quantum Gibbs states

• URL: http://arxiv.org/abs/2305.18514v1
• Date: Mon, 29 May 2023 18:00:00 GMT
• Title: Polynomial-time classical sampling of high-temperature quantum Gibbs states
• Authors: Chao Yin, Andrew Lucas
• Abstract summary: computational complexity of simulating quantum many-body systems scales exponentially with the number of particles. We present a classical algorithm that discovering samples from a high-temperature quantum Gibbs state in a computational (product) basis. Our result implies that measurement-based quantum computation on a Gibbs state can provide exponential speed up only at sufficiently low temperature.
• Score: 0.22843885788439797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The computational complexity of simulating quantum many-body systems generally scales exponentially with the number of particles. This enormous computational cost prohibits first principles simulations of many important problems throughout science, ranging from simulating quantum chemistry to discovering the thermodynamic phase diagram of quantum materials or high-density neutron stars. We present a classical algorithm that samples from a high-temperature quantum Gibbs state in a computational (product state) basis. The runtime grows polynomially with the number of particles, while error vanishes polynomially. This algorithm provides an alternative strategy to existing quantum Monte Carlo methods for overcoming the sign problem. Our result implies that measurement-based quantum computation on a Gibbs state can provide exponential speed up only at sufficiently low temperature, and further constrains what tasks can be exponentially faster on quantum computers.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum data learning for quantum simulations in high-energy physics [55.41644538483948]
  We explore the applicability of quantum-data learning to practical problems in high-energy physics. We make use of ansatz based on quantum convolutional neural networks and numerically show that it is capable of recognizing quantum phases of ground states. The observation of non-trivial learning properties demonstrated in these benchmarks will motivate further exploration of the quantum-data learning architecture in high-energy physics.
  arXiv  Detail & Related papers  (2023-06-29T18:00:01Z)
• 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)
• Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods [0.4215938932388722]
  Quantum algorithms for simulating electronic ground states are slower than popular classical mean-field algorithms such as Hartree-Fock and density functional theory. We show that certain first quantized quantum algorithms enable exact time evolution of electronic systems with exponentially less space and fewer functional operations in basis set size.
  arXiv  Detail & Related papers  (2023-01-03T17:00:40Z)
• Towards Neural Variational Monte Carlo That Scales Linearly with System Size [67.09349921751341]
  Quantum many-body problems are central to demystifying some exotic quantum phenomena, e.g., high-temperature superconductors. The combination of neural networks (NN) for representing quantum states, and the Variational Monte Carlo (VMC) algorithm, has been shown to be a promising method for solving such problems. We propose a NN architecture called Vector-Quantized Neural Quantum States (VQ-NQS) that utilizes vector-quantization techniques to leverage redundancies in the local-energy calculations of the VMC algorithm.
  arXiv  Detail & Related papers  (2022-12-21T19:00:04Z)
• Ab initio Quantum Simulation of Strongly Correlated Materials with Quantum Embedding [0.5872014229110214]
  ab initio simulation of solid-state materials on quantum computers is still in its early stage. We introduce an orbital-based multi-fragment approach on top of the periodic density matrix embedding theory. Our results suggest that quantum embedding combined with a chemically intuitive fragmentation can greatly advance quantum simulation of realistic materials.
  arXiv  Detail & Related papers  (2022-09-07T15:02:01Z)
• Quantum Computing Quantum Monte Carlo [8.69884453265578]
  We propose a hybrid quantum-classical algorithm that integrates quantum computing and quantum Monte Carlo. Our work paves the way to solving practical problems with intermediatescale and early-fault tolerant quantum computers.
  arXiv  Detail & Related papers  (2022-06-21T14:26:24Z)
• Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation [5.188498150496968]
  We present a quantum kernel function (QKFE) algorithm for solving thermodynamic properties of quantum many-body systems. As compared to its classical counterpart, namely the kernel method (KPM), QKFE has an exponential advantage in the cost of both time and memory. We demonstrate its efficiency with applications to one and two-dimensional quantum spin models, and a fermionic lattice.
  arXiv  Detail & Related papers  (2022-02-02T18:00:04Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
  arXiv  Detail & Related papers  (2021-02-24T12:48:00Z)
• Simulating quantum chemistry in the seniority-zero space on qubit-based quantum computers [0.0]
  We combine the so-called seniority-zero, or paired-electron, approximation of computational quantum chemistry with techniques for simulating molecular chemistry on gate-based quantum computers. We show that using the freed-up quantum resources for increasing the basis set can lead to more accurate results and reductions in the necessary number of quantum computing runs.
  arXiv  Detail & Related papers  (2020-01-31T19:44:37Z)

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.