{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T20:10:02Z","timestamp":1748463002726,"version":"3.41.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319202969"},{"type":"electronic","value":"9783319202976"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-20297-6_11","type":"book-chapter","created":{"date-parts":[[2015,6,22]],"date-time":"2015-06-22T01:55:05Z","timestamp":1434938105000},"page":"157-172","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Satisfiability of Quantum Circuits of Small Treewidth"],"prefix":"10.1007","author":[{"given":"Mateus","family":"de Oliveira Oliveira","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,23]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Kitaev, A., Nisan, N.: Quantum circuits with mixed states. In: Proceeding of the 30th Symposium on Theory of Computing, pp. 20\u201330 (1998)","DOI":"10.1145\/276698.276708"},{"key":"11_CR2","unstructured":"Aharonov, D., Naveh, T.: Quantum NP - A survey (2002). arXiv preprint quant-ph\/0210077"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.A.: Satisfiability, branch-width and tseitin tautologies. In: Proceeding of the 43rd Symposium on Foundations of Computer Science, pp. 593\u2013603 (2002)","DOI":"10.1109\/SFCS.2002.1181983"},{"issue":"12","key":"11_CR4","doi-asserted-by":"publisher","first-page":"297","DOI":"10.4086\/toc.2014.v010a012","volume":"10","author":"E Allender","year":"2014","unstructured":"Allender, E., Chen, S., Lou, T., Papakonstantinou, P.A., Tang, B.: Width-parametrized SAT: time-space tradeoffs. Theor. Comput. 10(12), 297\u2013339 (2014)","journal-title":"Theor. Comput."},{"issue":"2","key":"11_CR5","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial $$k$$-trees. Discrete Appl. Math. 23(1), 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/0405008","volume":"5","author":"L Babai","year":"1992","unstructured":"Babai, L.: Bounded round interactive proofs in finite groups. SIAM J. Discrete Math. 5(1), 88\u2013111 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"5\u20136","key":"11_CR8","first-page":"361","volume":"14","author":"AD Bookatz","year":"2014","unstructured":"Bookatz, A.D.: QMA-complete problems. Quantum Inf. Comput. 14(5\u20136), 361\u2013383 (2014)","journal-title":"Quantum Inf. Comput."},{"key":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-540-24605-3_13","volume-title":"Theory and Applications of Satisfiability Testing","author":"E Broering","year":"2004","unstructured":"Broering, E., Lokam, S.V.: Width-based algorithms for SAT and CIRCUIT-SAT. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 162\u2013171. Springer, Heidelberg (2004)"},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I. recognizable sets of finite graphs. Inf. comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. comput."},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-540-79719-7_10","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2008","author":"K Georgiou","year":"2008","unstructured":"Georgiou, K., Papakonstantinou, P.A.: Complexity and algorithms for well-structured k-SAT instances. In: Kleine B\u00fcning, H., Zhao, X. (eds.) SAT 2008. LNCS, vol. 4996, pp. 105\u2013118. Springer, Heidelberg (2008)"},{"key":"11_CR12","unstructured":"Gottesman, D.: The Heisenberg representation of quantum computers (1998). arXiv preprint quant-ph\/9807006"},{"issue":"2036","key":"11_CR13","doi-asserted-by":"publisher","first-page":"2011","DOI":"10.1098\/rspa.2002.1097","volume":"459","author":"R Jozsa","year":"2003","unstructured":"Jozsa, R., Linden, N.: On the role of entanglement in quantum-computational speed-up. Proc. Roy. Soc. Lond. Ser. A 459(2036), 2011\u20132032 (2003)","journal-title":"Proc. Roy. Soc. Lond. Ser. A"},{"key":"11_CR14","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/047","volume-title":"Classical and Quantum Computation","author":"A Kitaev","year":"2002","unstructured":"Kitaev, A., Shen, A., Vyalyi, M.: Classical and Quantum Computation. Graduate Studies in Mathematics, vol. 47. AMS, Boston (2002)"},{"issue":"3","key":"11_CR15","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/050644756","volume":"38","author":"IL Markov","year":"2008","unstructured":"Markov, I.L., Shi, Y.: Simulating quantum computation by contracting tensor networks. SIAM J. Comput. 38(3), 963\u2013981 (2008)","journal-title":"SIAM J. Comput."},{"key":"11_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2010)"},{"issue":"1","key":"11_CR17","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors III. Planar tree-width. J. Comb. Theor. Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/3-540-40996-3_17","volume-title":"Algorithms and Computation","author":"DM Thilikos","year":"2000","unstructured":"Thilikos, D.M., Serna, M., Bodlaender, H.L.: Constructive linear time algorithms for small cutwidth and carving-width. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol. 1969, pp. 192\u2013203. Springer, Heidelberg (2000)"},{"issue":"4","key":"11_CR19","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1137\/S0097539700377025","volume":"31","author":"LG Valiant","year":"2002","unstructured":"Valiant, L.G.: Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput. 31(4), 1229\u20131254 (2002)","journal-title":"SIAM J. Comput."},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"147902","DOI":"10.1103\/PhysRevLett.91.147902","volume":"91","author":"G Vidal","year":"2003","unstructured":"Vidal, G.: Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. 91, 147902 (2003)","journal-title":"Phys. Rev. Lett."},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Watrous, J.: Succinct quantum proofs for properties of finite groups. In: Proceeding of the 41st Symposium on Foundations of Computer Science, pp. 537\u2013546 (2000)","DOI":"10.1109\/SFCS.2000.892141"}],"container-title":["Lecture Notes in Computer Science","Computer Science -- Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-20297-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:41:31Z","timestamp":1748461291000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-20297-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319202969","9783319202976"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-20297-6_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"23 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}