An official website of the United States government
We design a quantum algorithm for ground state preparation in the early fault tolerant regime. As a Monte Carlo style quantum algorithm, our method features a Lindbladian where the target state is stationary. The construction of this Lindbladian is algorithmic and should not be seen as a specific approximation to some weakly coupled system-bath dynamics in nature. Our algorithm can be implemented using just one ancilla qubit and efficiently simulated on a quantum computer. It can prepare the ground state even when the initial state has zero overlap with the ground state, bypassing the most significant limitation of methods like quantum phase estimation. As a variant, we also propose a discrete-time algorithm, demonstrating even better efficiency and providing a near-optimal simulation cost depending on the desired evolution time and precision. Numerical simulations using Ising and Hubbard models demonstrate the efficacy and applicability of our method. Published by the American Physical Society2024
more »
« less
Efficient Quantum Gibbs Samplers with Kubo–Martin–Schwinger Detailed Balance Condition
Abstract Lindblad dynamics and other open-system dynamics provide a promising path towards efficient Gibbs sampling on quantum computers. In these proposals, the Lindbladian is obtained via an algorithmic construction akin to designing an artificial thermostat in classical Monte Carlo or molecular dynamics methods, rather than being treated as an approximation to weakly coupled system-bath unitary dynamics. Recently, Chen, Kastoryano, and Gilyén (arXiv:2311.09207) introduced the first efficiently implementable Lindbladian satisfying the Kubo–Martin–Schwinger (KMS) detailed balance condition, which ensures that the Gibbs state is a fixed point of the dynamics and is applicable to non-commuting Hamiltonians. This Gibbs sampler uses a continuously parameterized set of jump operators, and the energy resolution required for implementing each jump operator depends only logarithmically on the precision and the mixing time. In this work, we build upon the structural characterization of KMS detailed balanced Lindbladians by Fagnola and Umanità, and develop a family of efficient quantum Gibbs samplers using a finite set of jump operators (the number can be as few as one), akin to the classical Markov chain-based sampling algorithm. Compared to the existing works, our quantum Gibbs samplers have a comparable quantum simulation cost but with greater design flexibility and a much simpler implementation and error analysis. Moreover, it encompasses the construction of Chen, Kastoryano, and Gilyén as a special instance.
more »
« less
- Award ID(s):
- 2016245
- PAR ID:
- 10574213
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Communications in Mathematical Physics
- Volume:
- 406
- Issue:
- 3
- ISSN:
- 0010-3616
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Megow, Nicole; Smith, Adam (Ed.)We provide a perfect sampling algorithm for the hard-sphere model on subsets of R^d with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.more » « less
-
We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.more » « less
-
null (Ed.)Path integral quantum Monte Carlo (PIMC) is a method for estimating thermal equilibrium properties of stoquastic quantum spin systems by sampling from a classical Gibbs distribution using Markov chain Monte Carlo. The PIMC method has been widely used to study the physics of materials and for simulated quantum annealing, but these successful applications are rarely accompanied by formal proofs that the Markov chains underlying PIMC rapidly converge to the desired equilibrium distribution.In this work we analyze the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered transverse Ising models (TIM) with long-range algebraically decaying interactions as well as disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution we rigorously justify the use of PIMC to approximate partition functions and expectations of observables for these models at inverse temperatures that scale at most logarithmically with the number of qubits.The mixing time analysis is based on the canonical paths method applied to the single-site Metropolis Markov chain for the Gibbs distribution of 2D classical spin models with couplings related to the interactions in the quantum Hamiltonian. Since the system has strongly nonisotropic couplings that grow with system size, it does not fall into the known cases where 2D classical spin models are known to mix rapidly.more » « less
-
null (Ed.)We discuss how the language of wave functions (state vectors) andassociated non-commuting Hermitian operators naturally emerges fromclassical mechanics by applying the inverse Wigner-Weyl transform to thephase space probability distribution and observables. In this language,the Schr"odinger equation follows from the Liouville equation, with \hbar ℏ now a free parameter. Classical stationary distributions can berepresented as sums over stationary states with discrete (quantized)energies, where these states directly correspond to quantum eigenstates.Interestingly, it is now classical mechanics which allows for apparentnegative probabilities to occupy eigenstates, dual to the negativeprobabilities in Wigner’s quasiprobability distribution. These negativeprobabilities are shown to disappear when allowing sufficientuncertainty in the classical distributions. We show that thiscorrespondence is particularly pronounced for canonical Gibbs ensembles,where classical eigenstates satisfy an integral eigenvalue equation thatreduces to the Schr"odinger equation in a saddle-pointapproximation controlled by the inverse temperature. We illustrate thiscorrespondence by showing that some paradigmatic examples such astunneling, band structures, Berry phases, Landau levels, levelstatistics and quantum eigenstates in chaotic potentials can bereproduced to a surprising precision from a classical Gibbs ensemble,without any reference to quantum mechanics and with all parameters(including \hbar ℏ )on the order of unity.more » « less
