Monte Carlo Quantum Computing
arXiv:2012.14523
Abstract
It is shown that a class of separately frustration-free (SFF) Hamiltonians can be Monte Carlo simulated efficiently on a classical computing machine, because such an SFF Hamiltonian corresponds to a Gibbs wavefunction whose nodal structure is efficiently computable by solving a small subsystem associated with a low-dimensional configuration subspace. It is further demonstrated that SFF Hamiltonians can be designed to implement universal ground state quantum computation. The two results combined have effectively solved the notorious sign problem in Monte Carlo simulations, and proved that all bounded-error quantum polynomial time algorithms admit bounded-error probabilistic polynomial time simulations.
arXiv comment119 pages, 6 figures; broadened the notion of a strongly frustration-free Hamiltonian to a more general concept of separately frustration-free (SFF) Hamiltonian
References in corpus (26)
- Quantum algorithm for solving linear systems of equations
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Basic Properties of Strong Mixing Conditions. A Survey and Some Open Questions
- General state space Markov chains and MCMC algorithms
- Operator Quantum Error Correcting Subsystems for Self-Correcting Quantum Memories
- Positive Wigner functions render classical simulation of quantum computation efficient
- Active stabilisation, quantum computation and quantum state synthesis
- A Unified and Generalized Approach to Quantum Error Correction
- Most quantum states are too entangled to be useful as computational resources
- Fast Algorithm for Finding the Eigenvalue Distribution of Very Large Matrices
- Consistency of the Adiabatic Theorem
- Quantum Simulations of Classical Annealing Processes
- Error correcting codes for adiabatic quantum computation
- Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
- Perturbative Gadgets at Arbitrary Orders
- Sharp regularity results for many-electron wave functions
- Quantum search by measurement
- Structure of fermion nodes and nodal cells
- Analytic structure of many-body Coulombic wave functions
- Algorithmic complexity and entanglement of quantum states
- A 2 rebit gate universal for quantum computing
- Denjoy-Carleman differentiable perturbation of polynomials and unbounded operators
- Fermionic quantum criticality and the fractal nodal surface
- Complexity classification of local Hamiltonian problems
- Reptation Quantum Monte Carlo
- Fermion nodes and nodal cells of noninteracting and interacting fermions