Fetching the paper…

Reading the bibliography…

2013

Obstructions To Classically Simulating The Quantum Adiabatic Algorithm

Hastings, M. B., Freedman, M. H.

Original
PDF
Post on X

Understand

We consider the adiabatic quantum algorithm for systems with "no sign problem", such as the transverse field Ising mode, and analyze the equilibration time for quantum Monte Carlo (QMC) on these systems.

We ask: if the spectral gap is only inverse polynomially small, will equilibration methods based on slowly changing the Hamiltonian parameters in the QMC simulation succeed in a polynomial time? We show that this is not true, by constructing counter-examples.
Some examples are Hamiltonians where the space of configurations where the wavefunction has non-negligible amplitude has a nontrivial fundamental group, causing the space of trajectories in imaginary time to break into disconnected components, with only negligible probability outside these components.
For the simplest example we give with an abelian fundamental group, QMC does not equilibrate but still solves the optimization problem.

Obstructions To Classically Simulating The Quantum Adiabatic Algorithm · Around

Built on

S. I. Adjan, “The algorithmic unsolvability of checking certain properties of groups”, Dokl. Akad. Nauk SSSR 103
1955
Earlier work this paper cites.
M. O. Rabin, “Recursive unsolvability of group theoretic problems”, Ann. of Math., 67
1958
Earlier work this paper cites.
A. M. Childs, E. Farhi, and J. Preskill, Phys. Rev. A 65
2001
Earlier work this paper cites.
E. Farhi, et. al., Science 292
2001
Earlier work this paper cites.
A. Yu. Kitaev, A.H. Shen, and M.N. Vyalyi. Classical and Quantum Computation
2002
Earlier work this paper cites.
This is a standard result. See for example corollary 1.28 of Algebraic Topology
2002
Earlier work this paper cites.

Similar

H. G. Evertz, arXiv:cond-mat/9707221, Adv. Phys. 52
2003
Cited alongside, same era.
D. Aharonov et. al., SIAM Journal of Computing, 37
2004
Cited alongside, same era.
N. Kawashima and K. Harada, J. Phys. Soc. Jpn. 73
2004
Cited alongside, same era.
M. B. Hastings, Phys.Rev. B69, 104431 (2004)
2004
Cited alongside, same era.
M. B. Hastings, JSTAT P08024 (2007)
2007
Cited alongside, same era.
F. F. Assaad, H. G. Evertz, Computational Many-Particle Physics (Lect. Notes Phys. 739)
2007
Cited alongside, same era.
E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, arXiv:quant-ph/0001106

Then

S. Bravyi, D. P. DiVincenzo, R. I. Oliveira, and B. M. Terhal, Quant. Inf. Comp. 8
2008
Later among the works it cites.
D. C. Handscomb, Proc. Cambridge Philos. Soc. 58, 594 (1962); 60, 115 (1964); R. G. Melko and R.K.Kaul, Phys. Rev. Lett. 100, 017203 (2008)
2008
Later among the works it cites.
M. B. Hastings, Phys. Rev. Lett. 103
2009
Later among the works it cites.
S. Bravyi and B. Terhal, SIAM J. Comput. 39
2009
Later among the works it cites.
A. P. Young, S. Knysh, and V. N. Smelyanskiy, Phys. Rev. Lett. 104
2011
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Cited in the paper.

S. Boixo, T. Rønnow, S. Isakov, M. Troyer, D. Wecker, and J. Martinis, “Adiabatic quantum annealing with more than one hundred qubits”, unpublished

Cited in the paper.

K. Karimi et. al., arXiv:1006.4147

Cited in the paper.

I. Arad et. al., arXiv:1301.1162

Cited in the paper.

C.-W. Liu, A. Polkovnikov, A. W. Sandvik, arXiv:1212.4815

Cited in the paper.

The Cheeger constant is a lower bound on the surface-to-volume ratio of a region of less than half the volume of the space. A lower bound on the first non-zero eigenvalue of the Laplacian can be obtained from the Cheeger constant

Cited in the paper.