%% Theory of Computing
%% File: v011a020.bib
%% Publication date: December 31, 2015
%% Authors: Andrew M. Childs, David Gosset, and Zak Webb
%
%
%
%

@string{acm      = "ACM Press"}
@string{ieee     = "IEEE Comp. Soc. Press"}
@string{ams      = "Amer. Math. Soc."}
@string{cup      = "Cambridge Univ. Press"}
@string{doklady  = "Doklady Akademii Nauk SSSR, N.S."}
@string{oup      = "Oxford Univ. Press"}
@string{springer = "Springer"}

@string{SIAMJComput="SIAM J. Comput."}
@string{QuantumInfComput="Quantum Inf. Comput."}

@string{stoc00="Proc. 32nd STOC"}
@string{focs13="Proc. 54th FOCS"}
@string{focs14="Proc. 55th FOCS"}



@article{Boo12,
   author = {Bookatz, Adam D.},
    title = {{QMA}-complete problems},
   eprint = {arXiv:1212.6312},
   journal = QuantumInfComput,
   volume = {14},
   number = {5-6},
   pages = {361-383},
   year = {2014},
   note = {\href{http://dl.acm.org/citation.cfm?id=2638662}{ACM DL}}
}

@article{Bra06,
   author = {Bravyi, Sergey},
    title = {Efficient algorithm for a quantum analogue of 2-{SAT}},
  journal = {Contemporary Mathematics},
   volume = {536},
    pages = {33-48},
     year = {2011},
   eprint = {arXiv:quant-ph/0602108},
      doi = {10.1090/conm/536},
}

@ARTICLE{OT05,
   author = {Oliveira, Roberto and Terhal, Barbara M.},
    title = {The complexity of quantum spin systems on a two-dimensional square lattice},
  journal = QuantumInfComput,
   volume = {8},
   number = {10},
    pages = {900-924},
   eprint = {arXiv:quant-ph/0504050},
     year = {2008},
	 note = {\href{http://dl.acm.org/citation.cfm?id=2016987}{ACM DL}},
}

@ARTICLE{KR03,
   author = {Kempe, Julia and Regev, Oded},
    title = {3-{L}ocal {H}amiltonian is {QMA}-complete},
  journal = QuantumInfComput,
   volume = {3},
   number = {3},
    pages = {258-264},
   eprint = {arXiv:quant-ph/0302079},
     year = {2003},
	 note = {\href{http://dl.acm.org/citation.cfm?id=2011541}{ACM DL}},
}

@ARTICLE{SV09,
   author = {Schuch, Norbert and Verstraete, Frank},
    title = {Computational complexity of interacting electrons and fundamental limitations of density functional theory},
  journal = {Nature Physics},
   eprint = {arXiv:0712.0483},
     year = {2009},
   volume = {5},
   number = {10},
    pages = {732-735},
      doi = {10.1038/nphys1370},
}

@article{CGW13,
author = {Childs, Andrew M. and Gosset, David and Webb, Zak}, 
title = {Universal computation by multiparticle quantum walk},
volume = {339}, 
number = {6121}, 
pages = {791-794}, 
year = {2013}, 
doi = {10.1126/science.1229957}, 
eprint = {arXiv:1205.3782}, 
journal = {Science} 
}

@article{JBCGZ98,
  title = {Cold bosonic atoms in optical lattices},
  author = {Jaksch, D. and Bruder, C. and Cirac, J. I. and Gardiner, C. W. and Zoller, P.},
  journal = {Physical Review Letters},
  volume = {81},
  issue = {15},
  pages = {3108-3111},
  year = {1998},
  doi = {10.1103/PhysRevLett.81.3108},
}

@ARTICLE{MM12,
   author = {Motruk, J. and Mielke, A.},
    title = {{B}ose-{H}ubbard model on two-dimensional line graphs},
  journal = {Journal of Physics A},
   eprint = {arXiv:1112.0131},
     year = {2012},
   volume = {45},
   number = {22},
    pages = {225206},
      doi = {10.1088/1751-8113/45/22/225206},
}

@article{FWGF89,
  title = {Boson localization and the superfluid-insulator transition},
  author = {Fisher, Matthew P. A. and Weichman, Peter B. and Grinstein, G. and Fisher, Daniel S.},
  journal = {Physical Review B},
  volume = {40},
  number = {1},
  pages = {546-570},
  year = {1989},
  doi = {10.1103/PhysRevB.40.546},
}

@ARTICLE{LCV07,
   author = {Liu, Yi-Kai and Christandl, Matthias and Verstraete, Frank},
    title = {Quantum computational complexity of the {$N$}-representability problem: {QMA} complete},
  journal = {Physical Review Letters},
   eprint = {arXiv:quant-ph/0609125},
     year = {2007},
   volume = {98},
   number = {11},
    pages = {110503},
      doi = {10.1103/PhysRevLett.98.110503},
}

@ARTICLE{WMN10,
   author = {Wei, Tzu-Chieh and Mosca, Michele and Nayak, Ashwin},
    title = {Interacting boson problems can be {QMA} hard},
  journal = {Physical Review Letters},
   eprint = {arXiv:0905.3413},
     year = {2010},
   volume = {104},
   number = {4},
    pages = {040501},
      doi = {10.1103/PhysRevLett.104.040501},
}

@ARTICLE{GI09,
   author = {Gottesman, Daniel and Irani, Sandy},
    title = {The quantum and classical complexity of translationally invariant tiling and {H}amiltonian problems},
   eprint = {arXiv:0905.2419},
  journal = {Theory of Computing},
   volume = {9},
   number = {2},
    pages = {31-116},
     year = {2013},
	  doi = {10.4086/toc.2013.v009a002},
	 note = {Preliminary version in \href{http://dx.doi.org/10.1109/FOCS.2009.22}{FOCS'09}},
}

@ARTICLE{AGIK09,
   author = {Aharonov, Dorit and Gottesman, Daniel and Irani, Sandy and Kempe, Julia},
    title = {The power of quantum systems on a line},
  journal = {Communications in Mathematical Physics},
   eprint = {arXiv:0705.4077},
     year = {2009},
   volume = {287},
   number = {1},
    pages = {41-65},
      doi = {10.1007/s00220-008-0710-3},
	  note = {Preliminary version in \href{http://dx.doi.org/10.1109/FOCS.2007.46}{FOCS'07}},
}

@ARTICLE{BDOT08,
   author = {Bravyi, Sergey and DiVincenzo, David P. and Oliveira, Roberto I. and Terhal, Barbara M.},
    title = {The complexity of stoquastic local {H}amiltonian problems},
  journal = QuantumInfComput,
   volume = {8},
   number = {5},
    pages = {361-385},
   eprint = {arXiv:quant-ph/0606140},
 keywords = {Quantum Physics},
     year = {2008},
	 note = {\href{http://dl.acm.org/citation.cfm?id=3D2011772.2011773}{ACM DL}}
}

@article{Moh91,
   author = {Mohar, Bojan},
   title = {Eigenvalues, diameter, and mean distance in graphs},
   journal = {Graphs and Combinatorics},
   pages = {53-64},
   volume = {7},
   number = {1},
   doi = {10.1007/BF01789463},
   year = {1991}
}

@ARTICLE{CEMM98,
   author = {Cleve, Richard and Ekert, Artur and Macchiavello, Chiara and Mosca, Michele},
    title = {Quantum algorithms revisited},
  journal = {Proceedings of the Royal Society of London, Series A},
   eprint = {arXiv:quant-ph/9708016},
     year = {1998},
   volume = {454},
   number = {1969},
    pages = {339-354},
      doi = {10.1098/rspa.1998.0164},
}

@inproceedings{GN13,
   author = {Gosset, David and Nagaj, Daniel},
    title = {Quantum 3-{SAT} is {QMA}$_1$-complete},
   eprint = {arXiv:1302.0290},
    note  = {Preprint, 2013. Extended abstract in \href{http://dx.doi.org/10.1109/FOCS.2013.86}{FOCS'13}},
}

@book{NC00,
  author = {Nielsen, Michael A. and Chuang, Isaac L.},
  publisher = cup,
  title = {Quantum Computation and Quantum Information},
  year = 2000
}

@ARTICLE{JF08,
   author = {Jordan, Stephen P. and Farhi, Edward},
    title = {Perturbative gadgets at arbitrary orders},
  journal = {Physical Review A},
   eprint = {arXiv:0802.1874},
     year = {2008},
   volume = {77},
   number = {6},
    pages = {062329},
      doi = {10.1103/PhysRevA.77.062329},
}

@article{MW05,
 author = {Marriott, Chris and Watrous, John},
 title = {Quantum {A}rthur-{M}erlin games},
 journal = {Computational Complexity},
 volume = {14},
 number = {2},
 year = {2005},
 pages = {122-152},
 doi = {10.1007/s00037-005-0194-x},
 note = {Preliminary version in \href{http://dx.doi.org/10.1109/CCC.2004.1313850}{CCC'04}},
 eprint = {arXiv:cs/0506068},
} 

@misc{JW06,
   author = {Dominik Janzing and Pawel Wocjan},
    title = {{BQP}-complete problems concerning mixing properties of classical random walks on sparse graphs},
   eprint = {arXiv:quant-ph/0610235},
   year = {2006},
}

@ARTICLE{KKR04,
   author = {Kempe, Julia and Kitaev, Alexei and Regev, Oded},
    title = {The complexity of the local {H}amiltonian problem},
  journal = SIAMJComput,
   volume = {35},
   number = {5},
    pages = {1070-1097},
   eprint = {arXiv:quant-ph/0406180},
     year = {2006},
	  doi = {10.1137/S0097539704445226},
     note = {Preliminary version in \href{http://dx.doi.org/10.1007/978-3-540-30538-5\_31}{FSTTCS'04}},	  
}

@article{MLM99,
  title = {Simple proof of equivalence between adiabatic quantum computation and the circuit model},
  author = {Mizel, Ari and Lidar, Daniel A. and Mitchell, Morgan},
  journal = {Physical Review Letters},
  volume = {99},
  number = {7},
  pages = {070502},
  numpages = {4},
  year = {2007},
  doi = {10.1103/PhysRevLett.99.070502}
}

@article{AT03,
   author = {Aharonov, Dorit and Ta-Shma, Amnon},
    title = {Adiabatic quantum state generation and statistical zero knowledge},
   eprint = {arXiv:quant-ph/0301023},
     year = {2007},
  journal = SIAMJComput,
   volume = {37},
   number = {1},
    pages = {47-82},
	  doi = {10.1137/060648829},
	 note = {Preliminary version in \href{http://dx.doi.org/10.1145/780542.780546}{STOC'03}}
}

@inproceedings{AT03-conf,
   author = {Aharonov, Dorit and Ta-Shma, Amnon},
    title = {Adiabatic quantum state generation and statistical zero knowledge},
   eprint = {arXiv:quant-ph/0301023},
     year = {2003},
booktitle = {Proceedings of the 35th ACM Symposium on Theory of Computing},
    pages = {20-29}
}

@article{JGL10,
  title = {Quantum-{M}erlin-{A}rthur complete problems for stoquastic {H}amiltonians and {M}arkov matrices},
  author = {Jordan, Stephen P. and Gosset, David and Love, Peter J.},
  journal = {Physical Review A},
  volume = {81},
  number = {3},
  pages = {032331},
  numpages = {10},
  year = {2010},
  doi = {10.1103/PhysRevA.81.032331},
  eprint = {arXiv:0905.4755}
}

@book{LL94,
  title = {Quantum Mechanics: Non-Relativistic Theory},
  publisher = {Pergamon Press},
  author = {Landau, Lev D. and Lifshitz, Evgenii M.},
  year = {1994},
}

@article{Fey85,
   author = {Feynman, Richard P.},
     title = {Quantum mechanical computers},
   journal = {Optics News},
      pages = {11-46},
	  number = {2},
   volume = {11},
    year = {1985},
	doi = {10.1364/ON.11.2.000011},
}

@book{KSV02,
 author = {Kitaev, Alexei Yu. and Shen, Alexander H. and Vyalyi, Mikhail N.},
 title = {Classical and Quantum Computation},
 year = {2002},
 publisher = ams,
 note = {\href{http://dl.acm.org/citation.cfm?id=863284}{ACM DL}}
} 

@article{BT09,
 author = {Bravyi, Sergey and Terhal, Barbara},
 title = {Complexity of stoquastic frustration-free {H}amiltonians},
 journal = SIAMJComput,
 volume = {39},
 number = {4},
 year = {2009},
 pages = {1462-1485},
 doi = {10.1137/08072689X},
 eprint = {arXiv:0806.1746}
}

@article{Chi09,
	Author = {Andrew M. Childs},
	Eprint = {arXiv:0806.1972},
	Journal = {Physical Review Letters},
	Number = {18},
	Pages = {180501},
	Title = {Universal computation by quantum walk},
	Volume = {102},
	Year = {2009}
}

@article{Bar82,
  author={Francisco Barahona},
  title={On the computational complexity of {I}sing spin glass models},
  journal={Journal of Physics A},
  volume={15},
  number={10},
  pages={3241-3253},
  year={1982},
}

@INPROCEEDINGS{Ist00,
  author = {Istrail, Sorin},
  title = {Statistical mechanics, three-dimensionality and {NP}-completeness:
	{I}. {U}niversality of intractability for the partition function of the
	{I}sing model across non-planar lattices},
  crossref = {pstoc00},
  pages = {87-96},
}

@inproceedings{CM13,
   author = {{Cubitt}, Toby S. and {Montanaro}, Ashley},
    title = {Complexity classification of local {H}amiltonian problems},
   eprint = {arXiv:1311.3161},
   note   = {Preprint, 2013-14. Extended abstract in \href{http://dx.doi.org/10.1109/FOCS.2014.21}{FOCS'14}},
}

@ARTICLE{NM07,
   author = {Nagaj, Daniel and Mozes, Shay},
    title = {New construction for a {QMA} complete three-local {H}amiltonian},
  journal = {Journal of Mathematical Physics},
   eprint = {quant-ph/0612113},
     year = 2007,
   volume = 48,
   number = 7,
    pages = {072104},
	  doi = {10.1063/1.2748377}, 
}

@article{BT14,
  author={Nikolas P. Breuckmann and Barbara M. Terhal},
  title={Space-time circuit-to-{H}amiltonian construction and its applications},
  journal={Journal of Physics A},
  volume={47},
  number={19},
  pages={195304},
  year={2014},
  eprint={arXiv:1311.6101},
  note = {\href{http://m.iopscience.iop.org/article/10.1088/1751-8113/47/19/195304}{IOP Science}}}
}

@article{Jan07,
  title = {Spin-{1/2} particles moving on a two-dimensional lattice with nearest-neighbor interactions can realize an autonomous quantum computer},
  author = {Janzing, Dominik},
  journal = {Physical Review A},
  volume = {75},
  number = {1},
  pages = {012307},
  numpages = {16},
  year = {2007},
  eprint = {arXiv:quant-ph/0506270},
  doi = {10.1103/PhysRevA.75.012307},
}





@proceedings{pfocs13,
booktitle = focs13,
publisher = ieee,
year = {2013}
}

@proceedings{pfocs14,
booktitle = focs14,
publisher = ieee,
year = {2014}
}

@proceedings{pstoc00,
booktitle = stoc00,
publisher = acm,
year = {2000}
}