Physics – Quantum Physics
Scientific paper
2010-11-05
Proc. Natl. Acad. Sci. USA 109, 754-759 (2012)
Physics
Quantum Physics
7 pages
Scientific paper
10.1073/pnas.1111758109
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.
Aspuru-Guzik Alan
Yung Man-Hong
No associations
LandOfFree
A Quantum-Quantum Metropolis Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Quantum-Quantum Metropolis Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Quantum-Quantum Metropolis Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-455338