Search

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_{\rm rel}\mathcal{Z} ))^2$, where $M$ is the dimension of the quantum system, $\mathcal{Z}$ is the partition function, and $\epsilon_{\rm 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., Comment: 15 pages, 2 figures

We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state $\vert x \rangle$ that is proportional to the solution of the system of linear equations $A \vec{x}=\vec{b}$. The time complexities of our algorithms are $O(\kappa^2 \log(\kappa)/\epsilon)$ and $O(\kappa \log(\kappa)/\epsilon)$, where $\kappa$ is the condition number of $A$ and $\epsilon$ is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of $A$, the projector onto the initial state $\vert b \rangle$, and single-qubit Pauli operators. The algorithms are conceptually simple and easy to implement. They are not obtained from equivalences between the gate model and adiabatic quantum computing. They do not use phase estimation or variable-time amplitude amplification, and do not require large ancillary systems. We discuss a gate-based implementation via Hamiltonian simulation and prove that our second algorithm is almost optimal in terms of $\kappa$. Like previous methods, our techniques yield an exponential quantum speedup under some assumptions. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms., Comment: 9 pages, 2 figures. Changes in version 2: - Includes a simpler algorithm for the special case of positive matrices. - Added pseudocode for the algorithms - Overall improved presentation

We present a numerical method based on real-space renormalization that outputs the exact ground space of "frustration-free" Hamiltonians. The complexity of our method is polynomial in the degeneracy of the ground spaces of the Hamiltonians involved in the renormalization steps. We apply the method to obtain the full ground spaces of two spin systems. The first system is a spin-1/2 Heisenberg model with four-spin cyclic-exchange interactions defined on a square lattice. In this case, we study finite lattices of up to 160 spins and find a triplet ground state that differs from the singlet ground states obtained in C.D. Batista and S. Trugman, Phys. Rev. Lett. 93, 217202 (2004). We characterize such a triplet state as consisting of a triplon that propagates in a background of fluctuating singlet dimers. The second system is a family of spin-1/2 Heisenberg chains with uniaxial exchange anisotropy and next-nearest neighbor interactions. In this case, the method finds a ground-space degeneracy that scales quadratically with the system size and outputs the full ground space efficiently. Our method can substantially outperform methods based on exact diagonalization and is more efficient than other renormalization methods when the ground-space degeneracy is large., 10 pages, 8 Figs. Typos corrected

We study the glued-trees problem of Childs et. al. in the adiabatic model of quantum computing and provide an annealing schedule to solve an oracular problem exponentially faster than classically possible. The Hamiltonians involved in the quantum annealing do not suffer from the so-called sign problem. Unlike the typical scenario, our schedule is efficient even though the minimum energy gap of the Hamiltonians is exponentially small in the problem size. We discuss generalizations based on initial-state randomization to avoid some slowdowns in adiabatic quantum computing due to small gaps., 7 pages

A gapped quantum system that is adiabatically perturbed remains approximately in its eigenstate after the evolution. We prove that, for constant gap, general quantum processes that approximately prepare the final eigenstate require a minimum time proportional to the ratio of the length of the eigenstate path to the gap. Thus, no rigorous adiabatic condition can yield a smaller cost. We also give a necessary condition for the adiabatic approximation that depends on local properties of the path, which is appropriate when the gap varies., Comment: 5 pages, 1 figure

We describe a quantum algorithm that solves combinatorial optimization problems by quantum simulation of a classical simulated annealing process. Our algorithm exploits quantum walks and the quantum Zeno effect induced by evolution randomization. It requires order $1/\sqrt{\delta}$ steps to find an optimal solution with bounded error probability, where $\delta$ is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order $1/\delta$ steps required by the latter., Comment: 4 pages - 1 figure. This work differs from arXiv:0712.1008 in that the quantum Zeno effect is implemented via randomization in the evolution

We present a quantum algorithm to estimate parameters at the quantum metrology limit using deterministic quantum computation with one bit. When the interactions occurring in a quantum system are described by a Hamiltonian $H= \theta H_0$, we estimate $\theta$ by zooming in on previous estimations and by implementing an adaptive Bayesian procedure. The final result of the algorithm is an updated estimation of $\theta$ whose variance has been decreased in proportion to the time of evolution under H. For the problem of estimating several parameters, we implement dynamical-decoupling techniques and use the results of single parameter estimation. The cases of discrete-time evolution and reference-frame alignment are also discussed within the adaptive approach., Comment: 12 pages. Improved introduction and technical details moved to Appendix

Characterizing and quantifying quantum correlations in states of many-particle systems is at the core of a full understanding of phase transitions in matter. In this work, we continue our investigation of the notion of generalized entanglement [Barnum et al. Phys. Rev. A 68, 032308 (2003)] by focusing on a simple Lie-algebraic measure of purity of a quantum state relative to an observable set. For the algebra of local observables on multi-qubit systems, the resulting local purity measure is equivalent to a recently introduced global entanglement measure [Meyer and Wallach, J. Math. Phys. 43, 4273 (2002)]. In the condensed-matter setting, the notion of Lie-algebraic purity is exploited to identify and characterize the quantum phase transitions present in two exactly solvable models: the Lipkin-Meshkov-Glick model, and the spin-1/2 anisotropic XY model in a transverse magnetic field. For the latter, we argue that a natural fermionic observable-set arising after the Jordan-Wigner transformation, better characterizes the transition than alternative measures based on qubits. This illustrates the usefulness of going beyond the standard subsystem-based framework while providing a global disorder parameter for this model. Our results show how generalized entanglement leads to useful tools for distinguishing between the ordered and disordered phases in the case of broken symmetry quantum phase transitions. Additional implications and possible extensions of concepts to other systems of interest in condensed matter physics are also discussed., Comment: 48 pages, 14 encapsulated eps color figures, REVTeX4 style. Expanded and clarified discussion of the critical behavior in the isotropic XY model in Section VI; added discussion on valence bond solid states in Appendix B; expanded bibliography

We introduce a generalization of entanglement based on the idea that entanglement is relative to a distinguished subspace of observables rather than a distinguished subsystem decomposition. A pure quantum state is entangled relative to such a subspace if its expectations are a proper mixture of those of other states. Many information-theoretic aspects of entanglement can be extended to the general setting, suggesting new ways of measuring and classifying entanglement in multipartite systems. By going beyond the distinguishable-subsystem framework, generalized entanglement also provides novel tools for probing quantum correlations in interacting many-body systems., 5 pages, 1 encapsulated color figure, REVTeX4 style

We calculate the quantum phase diagram of the {\it XXZ} chain with nearest-neighbor (NN) $J_{1}$ and next-NN exchange $J_{2}$ with anisotropies $\Delta_{1}$ and $\Delta_{2}$ respectively. In particular we consider the case $\Delta_{1}=-\Delta_{2}$ to interpolate between the {\it XX} chain ($% \Delta_{i}=0$) and the isotropic model with ferromagnetic $J_{2}$. For $% \Delta_{1}, Comment: 10 pages, 4 psfigures