Source-linked AI summary
A Quantum-Quantum Metropolis Algorithm
Man-Hong Yung, Alán Aspuru-Guzik
TL;DR
The appendix describes how Q2MA incorporates random spin-flips and handles highly degenerate eigenstates through energy differences. It also gives an accuracy-dependent annealing-step scaling and discusses a quadratic speedup.
Problem
Q2MA must handle random spin-flips and highly degenerate eigenstates without requiring individual eigenvalues.
Method
Q2MA incorporates random spin-flips and resolves energy changes between states before and after the kick.
Results
d = O(β2⟨H2⟩0/ǫ) steps are required in quantum simulated annealing to achieve accuracy ǫ.
Takeaways & Limitations
For the Ising model, resolving energy changes below O(J) is sufficient despite eigenstate degeneracy.
Abstract
from arXiv · showhide
Recently, the idea of classical Metropolis sampling through Markov chains has been generalized for quantum Hamiltonians. However, the underlying Markov chain of this algorithm is still classical in nature. Due to Szegedy's method, the Markov chains of classical Hamiltonians can achieve a quadratic quantum speedup in the eigenvalue gap of the corresponding transition matrix. A natural question to ask is whether Szegedy's quantum speedup is merely a consequence of employing classical Hamiltonians, where the eigenstates simply coincide with the computational basis, making cloning of the classical information possible. We solve this problem by introducing a quantum version of the method of Markov-chain quantization combined with the quantum simulated annealing (QSA) procedure, and describe explicitly a novel quantum Metropolis algorithm, which exhibits a quadratic quantum speedup in the eigenvalue gap of the corresponding Metropolis Markov chain for any quantum Hamiltonian. This result provides a complete generalization of the classical Metropolis method to the quantum domain.
Appendix: Generalization to include random “kicks”
The appendix extends Q2MA with random kicks and analyzes how energy filtering, degeneracy, leakage, and implementation errors affect the procedure. It argues that suitable kicks can suppress leakage while preserving the algorithm’s quadratic speedup, under stated resolution and distribution assumptions.
- Random kicks: Random spin-flips can be incorporated into Q2MA, including for time-reversal-symmetric systems whose eigenstates have real computational-basis coefficients.The appendix identifies spin-flips as the quantum analogue of random moves used in classical Metropolis sampling.
- Degeneracy: Q2MA requires resolving energy differences between states before and after a kick, rather than individual eigenvalues, so degeneracy need not cause breakdown.For the Ising model, the relevant energy change is O(J), making resolution below O(J) sufficient.
- Energy filtering: Energy changes larger than the filter window ∆ acquire exponentially small phase-estimation errors after repeated applications.The remaining issue is leakage from nearly degenerate states with energy differences below ∆.
- Leakage control: Leakage can be made arbitrarily small when the kick-induced energy distribution is smooth over a range much wider than ∆, but the appendix leaves quantitative analysis for future work.The argument relies on decreasing ∆ and assumes a sufficiently spread distribution of kick-induced energies.
- Error analysis: To achieve accuracy ǫ in quantum simulated annealing, the procedure requires at least d = O(β2⟨H2⟩0/ǫ) steps.The inverse-temperature path is divided into uniform intervals, and the total error decreases as d increases.
- Implementation cost: The phase-estimation implementation depends on the minimum eigenvalue gap ∆min of W and yields controlled-W gate costs involving the Metropolis gap δ.The appendix concludes the error analysis after relating the required phase-estimation precision to the annealing-step count.