Solving Sharp Bounded-error Quantum Polynomial Time Problem by Evolution methods

Abstract

Counting ground state degeneracy of a $k$-local Hamiltonian is important in many fields of physics. Its complexity belongs to the problem of sharp bounded-error quantum polynomial time (#BQP) class and few methods are known for its solution. Finding ground states of a $k$-local Hamiltonian, on the other hand, is an easier problem of Quantum Merlin Arthur (QMA) class, for which many efficient methods exist. In this work, we propose an algorithm of mapping a #BQP problem into one of finding a special ground state of a $k$-local Hamiltonian. We prove that all traditional methods, which solve the QMA problem by evolution under a function of a Hamiltonian, can be used to find the special ground state from a well-designed initial state, thus can solve the #BQP problem. We combine our algorithm with power method, Lanczos method, and quantum imaginary time evolution method for different systems to illustrate the detection of phase boundaries, competition between frustration and quantum fluctuation, and potential implementations with quantum circuits.

11 pages, 7 figures

References in corpus (44)

• Unpaired Majorana fermions in quantum wires
• A variational eigenvalue solver on a quantum processor
• The density-matrix renormalization group in the age of matrix product states
• Detecting topological order in a ground state wave function
• Quantum Spin Liquid States
• Entanglement spectrum of a topological phase in one dimension
• Majorana Zero Modes and Topological Quantum Computation
• Time-dependent density-matrix renormalization-group using adaptive effective Hilbert spaces
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
• Observation of Majorana fermions with spin selective Andreev reflection in the vortex of topological superconductor
• Variational ansatz-based quantum simulation of imaginary time evolution
• Accurate determination of tensor network state of quantum lattice models in two dimensions
• Topological phases with parafermions: theory and blueprints
• An Introduction to Spontaneous Symmetry Breaking
• Constructing gapless spin liquid state for the spin-1/2 J1-J2 Heisenberg model on a square lattice
• Unifying Projected Entangled Pair States contractions
• Simple universal models capture all classical spin physics
• On entropy growth and the hardness of simulating time evolution
• Quantum Criticality and Spin Liquid Phase in the Shastry-Sutherland model
• Purifications of multipartite states: limitations and constructive methods
• The 1D Ising model and topological order in the Kitaev chain
• Ground State Degeneracy of Topological Phases on Open Surfaces
• Chiral topological spin liquids with projected entangled pair states
• Beyond the swap test: optimal estimation of quantum state overlap
• Gradient optimization of finite projected entangled pair states
• Simplex Z_2 spin liquids on the Kagome lattice with Entangled Pair States: spinon and vison coherence lengths, topological entropy and gapless edge modes
• Tropical Tensor Network for Ground States of Spin Glasses
• SU$(3{)}_1$ Chiral Spin Liquid on the Square Lattice: a View from Symmetric PEPS
• SU(2)${}_1$ chiral edge modes of a critical spin liquid
• Unpaired composite fermion, topological exciton, and zero mode
• Ground-state properties of the one-dimensional transverse Ising model in a longitudinal magnetic field
• Computational Difficulty of Computing the Density of States
• Phases and dynamics of ultracold bosons in a tilted optical lattice
• Topological invariants, zero mode edge states and finite size effect for a generalized non-reciprocal Su-Schrieffer-Heeger model
• Quantum dynamics of topological strings in a frustrated Ising antiferromagnet
• Some remarks on the Lieb-Schultz-Mattis theorem and its extension to higher dimensions
• Degeneracy of the ground-state of antiferromagnetic spin-1/2 Hamiltonians
• Critical entanglement spectrum of one-dimensional symmetry protected topological phases
• Study of the phase diagram of the Kitaev-Hubbard chain
• Exact results for a $Z_3$ clock-type model and some close relatives
• Topological degeneracy (Majorana zero-mode) and 1+1D fermionic topological order in a magnetic chain on superconductor via spontaneous Z2 symmetry breaking
• Topological study of a Bogoliubov-de Gennes system of pseudo spin-$1/2$ bosons with conserved magnetization in a honeycomb lattice