{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:25:28Z","timestamp":1725701128445},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540929093"},{"type":"electronic","value":"9783540929109"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-540-92910-9_46","type":"book-chapter","created":{"date-parts":[[2012,8,25]],"date-time":"2012-08-25T14:54:06Z","timestamp":1345906446000},"page":"1545-1571","source":"Crossref","is-referenced-by-count":2,"title":["BQP-Complete Problems"],"prefix":"10.1007","author":[{"given":"Shengyu","family":"Zhang","sequence":"first","affiliation":[]}],"member":"297","reference":[{"volume-title":"The BQP-hardness of approximating the Jones polynomial","year":"2006","author":"D Aharonov","key":"46_CR00461","unstructured":"Aharonov D, Arad I (2006) The BQP-hardness of approximating the Jones polynomial. quant-ph\/0605181"},{"key":"46_CR00465","first-page":"20","volume-title":"Proceedings of 35th annual ACM symposium on theory of computing (STOC)","author":"D Aharonov","year":"2003","unstructured":"Aharonov D, Ta-Shma A (2003) Adiabatic quantum state generation and statistical zero knowledge. In: Proceedings of 35th annual ACM symposium on theory of computing (STOC). ACM, New York, pp 20\u201329"},{"key":"46_CR00466","first-page":"42","volume-title":"Proceedings of the 45th annual IEEE symposium on foundations of computer science (FOCS)","author":"D Aharonov","year":"2033","unstructured":"Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S, Regev O (2004) Adiabatic quantum computation is equivalent to standard quantum computation. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Washington, DC, pp 42\u201351"},{"key":"46_CR00464","first-page":"427","volume-title":"Proceedings of the 38th annual ACM symposium on theory of computing (STOC)","author":"D Aharonov","year":"2006","unstructured":"Aharonov D, Jones V, Landau Z (2006) A polynomial quantum algorithm for approximating the Jones polynomial. In: Proceedings of the 38th annual ACM symposium on theory of computing (STOC). ACM, New York, pp 427\u2013436"},{"volume-title":"Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane","year":"2007","author":"D Aharonov","key":"46_CR00462","unstructured":"Aharonov D, Arad I, Eban E, Landau Z (2007a) Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane. arXiv:quant-ph\/0702008"},{"key":"46_CR00463","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1109\/FOCS.2007.46","volume-title":"Proceedings of the 48th annual IEEE symposium on foundations of computer science (FOCS)","author":"D Aharonov","year":"2007","unstructured":"Aharonov D, Gottesman D, Irani S, Kempe J (2007b) The power of quantum systems on a line. In: Proceedings of the 48th annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Washington, DC, pp 373\u2013383"},{"key":"46_CR00467","doi-asserted-by":"crossref","unstructured":"Ambainis A, Childs AM, Reichardt BW, Spalek R, Zhang S (2007) Any and-or formula of size n can be evaluated in time $${n}^{1\/2+o(1)}$$ on a quantum computer. In: Proceedings of the 48th annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Washington, DC, pp 363\u2013372","DOI":"10.1109\/FOCS.2007.57"},{"key":"46_CR00468","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity: a modern approach","author":"S Arora","year":"2009","unstructured":"Arora S, Barak B (2009) Computational complexity: a modern approach. Cambridge University Press, Cambridge, UK"},{"issue":"5","key":"46_CR00469","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E Bernstein","year":"1997","unstructured":"Bernstein E, Vazirani U (1997) Quantum complexity theory. SIAM J Comput 26(5):1411\u20131473","journal-title":"SIAM J Comput"},{"issue":"2","key":"46_CR004610","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00220-006-0150-x","volume":"270","author":"D Berry","year":"2007","unstructured":"Berry D, Ahokas G, Cleve R, Sanders B (2007) Efficient quantum algorithms for simulating sparse Hamiltonians. Commun Math Phys 270(2):359\u2013371","journal-title":"Commun Math Phys"},{"key":"46_CR004611","volume-title":"Algebraic graph theory","author":"N Biggs","year":"1993","unstructured":"Biggs N (1993) Algebraic graph theory, 2nd edn. Cambridge University Press, New York","edition":"2"},{"key":"46_CR004612","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern graph theory","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s B (1998) Modern graph theory. Springer, New York"},{"volume-title":"One-way quantum computation - a tutorial introduction","year":"2006","author":"D Browne","key":"46_CR004613","unstructured":"Browne D, Briegel H (2006) One-way quantum computation - a tutorial introduction. arXiv:quant-ph\/0603226"},{"key":"46_CR004614","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/0022-1236(68)90020-7","volume":"2","author":"P Chernoff","year":"1968","unstructured":"Chernoff P (1968) Note on product formulas for operator semigroups. J Funct Anal 2:238\u2013242","journal-title":"J Funct Anal"},{"key":"46_CR004615","doi-asserted-by":"crossref","first-page":"180501","DOI":"10.1103\/PhysRevLett.102.180501","volume":"102","author":"A Childs","year":"2009","unstructured":"Childs A (2009) Universal computation by quantum walk. Phys Rev Lett 102:180501","journal-title":"Phys Rev Lett"},{"issue":"0380","key":"46_CR004617","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1103\/RevModPhys.82.1","volume":"arXiv","author":"A Childs","year":"2010","unstructured":"Childs A, van Dam W (2010) Quantum algorithms for algebraic problems. Rev Mod Phys arXiv:0812.0380, 82:1\u201352","journal-title":"Rev Mod Phys"},{"key":"46_CR004616","first-page":"59","volume-title":"Exponential algorithmic speedup by a quantum walk","author":"A Childs","year":"2003","unstructured":"Childs A, Cleve R, Deotto E, Farhi E, Gutmann S, Spielman D (2003) Exponential algorithmic speedup by a quantum walk. Proceedings of the 35th annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 59\u201368"},{"key":"46_CR004618","doi-asserted-by":"crossref","unstructured":"Cook S (1971) The complexity of theorem-proving procedures. In: Proceedings of 3rd annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 151\u2013158","DOI":"10.1145\/800157.805047"},{"issue":"1","key":"46_CR004619","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1073\/pnas.95.1.98","volume":"95","author":"M Freedman","year":"1998","unstructured":"Freedman M (1998) P\/NP, and the quantum field computer. Proc Natl Acad Sci 95(1):98\u2013101","journal-title":"Proc Natl Acad Sci"},{"issue":"1","key":"46_CR004620","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1090\/S0273-0979-02-00964-3","volume":"40","author":"M Freedman","year":"2002","unstructured":"Freedman M, Kitaev A, Larsen M, Wang Z (2002a) Topological quantum computation. Bull Amer Math Soc 40(1):31\u201338","journal-title":"Bull Amer Math Soc"},{"issue":"3","key":"46_CR004621","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s002200200635","volume":"227","author":"M Freedman","year":"2002","unstructured":"Freedman M, Kitaev A, Wang Z (2002b) Simulation of topological field theories by quantum computers. Commun Math Phys 227(3):587\u2013603","journal-title":"Commun Math Phys"},{"key":"46_CR004622","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/s002200200645","volume":"227","author":"M Freedman","year":"2002","unstructured":"Freedman M, Larsen M, Wang Z (2002c) A modular functor which is universal for quantum computation. Commun Math Phys 227:605\u2013622","journal-title":"Commun Math Phys"},{"volume-title":"Computers and intractability: a guide to the theory of NP-completeness","year":"1979","author":"M Garey","key":"46_CR004623","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York"},{"key":"46_CR004624","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic graph theory","author":"C Godsil","year":"2001","unstructured":"Godsil C, Royle G (2001) Algebraic graph theory. Springer, New York"},{"key":"46_CR004625","unstructured":"Goldreich O (2005) On promise problems (a survey in memory of Shimon Even [1935\u20132004]). Electronic colloquium on computational complexity (ECCC). TR05\u2013018"},{"key":"46_CR004626","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational complexity: a conceptual perspective","author":"O Goldreich","year":"2008","unstructured":"Goldreich O (2008) Computational complexity: a conceptual perspective. Cambridge University Press, Cambridge, UK"},{"issue":"3","key":"46_CR004627","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/116825.116852","volume":"38","author":"O Goldreich","year":"1991","unstructured":"Goldreich O, Micali S, Wigderson A (1991) Proofs that yield nothing but their validity. J ACM 38(3):690\u2013728","journal-title":"J ACM"},{"issue":"1","key":"46_CR004628","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1206035.1206039","volume":"54","author":"S Hallgren","year":"2007","unstructured":"Hallgren S (2007) Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. J ACM 54(1):1\u201319","journal-title":"J ACM"},{"issue":"1","key":"46_CR004629","doi-asserted-by":"publisher","first-page":"61","DOI":"10.4086\/toc.2007.v003a004","volume":"3","author":"D Janzing","year":"2007","unstructured":"Janzing D, Wocjan P (2007) A simple PromiseBQP-complete matrix problem. Theor Comput 3(1):61\u201379","journal-title":"Theor Comput"},{"key":"46_CR004630","doi-asserted-by":"publisher","first-page":"093004","DOI":"10.1088\/1367-2630\/10\/9\/093004","volume":"10","author":"D Janzing","year":"2008","unstructured":"Janzing D, Wocjan P, Zhang S (2008) Measuring energy of basis states in translationally invariant nearest-neighbor interactions in qudit chains is universal for quantum computing. New J Phys 10:093004","journal-title":"New J Phys"},{"issue":"1","key":"46_CR004631","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1090\/S0273-0979-1985-15304-2","volume":"12","author":"V Jones","year":"1985","unstructured":"Jones V (1985) A polynomial invariant for knots via von Neumann algebras. Bull Amer Math Soc 12(1):103\u2013111","journal-title":"Bull Amer Math Soc"},{"volume-title":"Complexity of computer computations","year":"1972","author":"R Karp","key":"46_CR004632","unstructured":"Karp R (1972) Reducibility among combinatorial problems. In: Thatcher JW, Miller RE (eds) Complexity of computer computations. Plenum Press, New York"},{"issue":"5","key":"46_CR004633","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1137\/S0097539704445226","volume":"35","author":"J Kempe","year":"2006","unstructured":"Kempe J, Kitaev A, Regev O (2006) The complexity of the local Hamiltonian problem. SIAM J Comput 35(5):1070\u20131097","journal-title":"SIAM J Comput"},{"key":"46_CR004634","unstructured":"Kitaev A (1995) Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph\/9511026"},{"volume-title":"Classical and quantum computation","year":"2002","author":"A Kitaev","key":"46_CR004635","unstructured":"Kitaev A, Shen A, Vyalyi M (2002) Classical and quantum computation. American Mathematical Society, Providence, RI"},{"issue":"4","key":"46_CR004636","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0020-0190(00)00222-2","volume":"79","author":"E Knill","year":"2001","unstructured":"Knill E, Laflamme R (2001) Quantum computing and quadratically signed weight enumerators. Infor Process Lett 79(4):173\u2013179","journal-title":"Infor Process Lett"},{"issue":"1","key":"46_CR004637","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0097539703436345","volume":"35","author":"G Kuperberg","year":"2005","unstructured":"Kuperberg G (2005) A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J Comput 35(1):170\u2013188","journal-title":"SIAM J Comput"},{"issue":"3","key":"46_CR004638","first-page":"265","volume":"9","author":"L Levin","year":"1973","unstructured":"Levin L (1973) Universal search problems (in Russian). Problemy Peredachi Informatsii 9(3):265\u2013266","journal-title":"Problemy Peredachi Informatsii"},{"issue":"3","key":"46_CR004639","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"R Lipton","year":"1977","unstructured":"Lipton R, Zalcstein Y (1977) Word problems solvable in logspace. J ACM 24(3):522\u2013526","journal-title":"J ACM"},{"key":"46_CR004640","unstructured":"Lomont C (2004) The hidden subgroup problem \u2013 review and open problems. arXiv:quant-ph\/0411037"},{"key":"46_CR004641","doi-asserted-by":"crossref","unstructured":"Magniez F, Nayak A, Roland J, Santha M (2007) Search via quantum walk. In: Proceedings of the 39th annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 575\u2013584","DOI":"10.1145\/1250790.1250874"},{"volume-title":"Quantum computation and quantum information","year":"2000","author":"M Nielsen","key":"46_CR004642","unstructured":"Nielsen M, Chuang I (2000) Quantum computation and quantum information. Cambridge University Press, Cambridge, UK"},{"key":"46_CR004643","unstructured":"Papadimitriou C (1994) Computational complexity. Addison-Wesley, Reading"},{"key":"46_CR004644","first-page":"2","volume-title":"Proceedings of the 24th international colloquium on automata, languages and programming (ICALP), Lecture notes in computer science","author":"C Papadimitriou","year":"1997","unstructured":"Papadimitriou C (1997) NP-completeness: a retrospective. In: Proceedings of the 24th international colloquium on automata, languages and programming (ICALP), Lecture notes in computer science, vol. 1256. Springer, Berlin, pp 2\u20136"},{"issue":"23","key":"46_CR004645","doi-asserted-by":"publisher","first-page":"12974","DOI":"10.1073\/pnas.96.23.12974","volume":"96","author":"A Podtelezhnikov","year":"1999","unstructured":"Podtelezhnikov A, Cozzarelli N, Vologodskii A (1999) Equilibrium distributions of topological states in circular DNA: interplay of supercoiling and knotting. Proc Natl Acad Sci USA 96(23):12974\u201312979","journal-title":"Proc Natl Acad Sci USA"},{"key":"46_CR004646","doi-asserted-by":"crossref","unstructured":"Reichardt B, Spalek R (2008) Span-program-based quantum algorithm for evaluating formulas. In: Proceedings of 40th annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 103\u2013112","DOI":"10.1145\/1374376.1374394"},{"key":"46_CR004647","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P Shor","year":"1997","unstructured":"Shor P (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26:1484\u20131509","journal-title":"SIAM J Comput"},{"key":"46_CR004648","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s11128-004-3878-2","volume":"3","author":"P Shor","year":"2004","unstructured":"Shor P (2004) Progress in quantum algorithms. Quant Inform Process 3:5\u201313","journal-title":"Quant Inform Process"},{"key":"46_CR004649","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1017\/CBO9780511734885.009","volume-title":"Surveys in combinatorics.","author":"A Sokal","year":"2005","unstructured":"Sokal A (2005) The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Webb BS (ed) Surveys in combinatorics. Cambridge University Press, Cambridge, UK, pp 173\u2013226"},{"key":"46_CR004650","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1090\/S0002-9939-1959-0108732-6","volume":"10","author":"H Trotter","year":"1959","unstructured":"Trotter H (1959) On the product of semigroups of operators. Proc Amer Math Soc 10:545\u2013551","journal-title":"Proc Amer Math Soc"},{"issue":"1&2","key":"46_CR004651","first-page":"147","volume":"8","author":"P Wocjan","year":"2008","unstructured":"Wocjan P, Yard J (2008) The Jones polynomial: quantum algorithms and applications in quantum complexity theory. Quant Inform Comput 8(1&2):147\u2013180","journal-title":"Quant Inform Comput"},{"key":"46_CR004652","unstructured":"Wocjan P, Zhang S (2006) Several natural BQP-complete problems. arXiv:quant-ph\/0606179"},{"key":"46_CR004653","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1103\/RevModPhys.54.235","volume":"54","author":"FY Wu","year":"1982","unstructured":"Wu FY (1982) The Potts model. Rev Mod Phys 54:235\u2013268","journal-title":"Rev Mod Phys"},{"key":"46_CR004654","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1103\/RevModPhys.64.1099","volume":"64","author":"FY Wu","year":"1992","unstructured":"Wu FY (1992) Knot theory and statistical mechanics. Rev Mod Phys 64:1099\u20131131","journal-title":"Rev Mod Phys"},{"key":"46_CR004655","first-page":"352","volume-title":"Proceedings of the 34th annual symposium on foundations of computer science (FOCS).","author":"A Yao","year":"1993","unstructured":"Yao A (1993) Quantum circuit complexity. In: Proceedings of the 34th annual symposium on foundations of computer science (FOCS). IEEE Computer Society, Washington, DC, pp 352\u2013361"}],"container-title":["Handbook of Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92910-9_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T07:53:38Z","timestamp":1674114818000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-92910-9_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783540929093","9783540929109"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92910-9_46","relation":{},"subject":[],"published":{"date-parts":[[2012]]}}}