{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:34Z","timestamp":1740109414633,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,11,25]],"date-time":"2016-11-25T00:00:00Z","timestamp":1480032000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["339691"],"award-info":[{"award-number":["339691"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00224-016-9727-8","type":"journal-article","created":{"date-parts":[[2016,11,24]],"date-time":"2016-11-24T21:53:53Z","timestamp":1480024433000},"page":"656-688","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Satisfiability of Quantum Circuits of Small Treewidth"],"prefix":"10.1007","volume":"61","author":[{"given":"Mateus de","family":"Oliveira Oliveira","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,25]]},"reference":[{"key":"9727_CR1","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Kitaev, A., Nisan, N.: Quantum circuits with mixed states. In: Proceedings of the 30th Symposium on Theory of Computing, pp. 20\u201330 (1998)","DOI":"10.1145\/276698.276708"},{"key":"9727_CR2","unstructured":"Aharonov, D., Naveh, T.: Quantum NP - Asurvey. Eprint arXiv: quant-ph\/0210077 (2002)"},{"key":"9727_CR3","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.A.: Satisfiability, branch-width and Tseitin tautologies. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, pp. 593\u2013603 (2002)","DOI":"10.1109\/SFCS.2002.1181983"},{"issue":"12","key":"9727_CR4","doi-asserted-by":"crossref","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\u2013space tradeoffs. Theory Comput. 10(12), 297\u2013339 (2014)","journal-title":"Theory Comput."},{"issue":"2","key":"9727_CR5","doi-asserted-by":"crossref","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":"9727_CR6","doi-asserted-by":"crossref","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":"9727_CR7","doi-asserted-by":"crossref","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. Discret. Math. 5(1), 88\u2013111 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"9727_CR8","first-page":"116","volume":"36","author":"HL Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Classes of graphs with with bounded treewidth. Bull. EATCS 36, 116\u2013126 (1988)","journal-title":"Bull. EATCS"},{"key":"9727_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: NC-algorithms for graphs with small treewidth. In: Proceedings of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science, volume 344 of LNCS, pp. 1\u201310. Springer (1989)","DOI":"10.1007\/3-540-50728-0_32"},{"issue":"1","key":"9727_CR10","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/2390176.2390188","volume":"9","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M., Kratsch, D., Thilikos, D.M.: On exact algorithms for treewidth. ACM Trans. Algorithms 9(1), 12 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"5-6","key":"9727_CR11","first-page":"361","volume":"14","author":"AD Bookatz","year":"2014","unstructured":"Bookatz, A.D: QMA-complete problems. Quan. Inf. Comput. 14(5-6), 361\u2013383 (2014)","journal-title":"Quan. Inf. Comput."},{"key":"9727_CR12","doi-asserted-by":"crossref","unstructured":"Broering, E., Lokam, S.V.: Width-based algorithms for SAT and CIRCUIT-SAT. In: Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing, volume 2919 of LNCS, pp. 162\u2013171. Springer (2004)","DOI":"10.1007\/978-3-540-24605-3_13"},{"issue":"1","key":"9727_CR13","doi-asserted-by":"crossref","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":"9727_CR14","doi-asserted-by":"crossref","unstructured":"de Oliveira Oliveira, M.: On the satisfiability of quantum circuits of small treewidth. In: Proceedings of the 10th International Computer Science Symposium in Russia, volume 9139 of LNCS, pp. 157\u2013172. Springer (2015)","DOI":"10.1007\/978-3-319-20297-6_11"},{"key":"9727_CR15","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Papakonstantinou, P.A.: Complexity and algorithms for well-structured k-SAT instances. In: Proceedings of the 11th International Conference on Theory and Applications of Satisfiability Testing, volume 4996 of LNCS, pp. 105\u2013118. Springer (2008)","DOI":"10.1007\/978-3-540-79719-7_10"},{"key":"9727_CR16","unstructured":"Gottesman, D.: The Heisenberg representation of quantum computers. arXiv: quant-ph\/9807006 (1998)"},{"issue":"2","key":"9727_CR17","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2036","key":"9727_CR18","doi-asserted-by":"crossref","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. R. Soc. London Series A 459(2036), 2011\u20132032 (2003)","journal-title":"Proc. R. Soc. London Series A"},{"key":"9727_CR19","doi-asserted-by":"crossref","unstructured":"Kitaev, A., Shen, A., Vyalyi, M.: Classical and Quantum Computation, Volume 47 of Graduate Studies in Mathematics. AMS (2002)","DOI":"10.1090\/gsm\/047"},{"issue":"3","key":"9727_CR20","doi-asserted-by":"crossref","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":"9727_CR21","doi-asserted-by":"crossref","unstructured":"Nielsen, M.A., Chuang, I.L: Quantum Computation and Quantum Information. Cambridge University Press (2010)","DOI":"10.1017\/CBO9780511976667"},{"issue":"1","key":"9727_CR22","doi-asserted-by":"crossref","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. Theory, Series B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory, Series B"},{"issue":"1","key":"9727_CR23","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XIII. The disjoint paths problem. J. Comb. Theory, Series B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Series B"},{"key":"9727_CR24","doi-asserted-by":"crossref","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Constructive linear time algorithms for small cutwidth and carving-width. In: Proceedings of the 11th International Conference on Algorithms and Computation, volume 1969 of LNCS, pp. 192\u2013203. Springer (2000)","DOI":"10.1007\/3-540-40996-3_17"},{"issue":"4","key":"9727_CR25","doi-asserted-by":"crossref","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":"9727_CR26","doi-asserted-by":"crossref","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":"9727_CR27","doi-asserted-by":"crossref","unstructured":"Watrous, J.: Succinct quantum proofs for properties of finite groups. In: Proceedings of the 41st Symposium on Foundations of Computer Science, pp. 537\u2013546 (2000)","DOI":"10.1109\/SFCS.2000.892141"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9727-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9727-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9727-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T19:30:18Z","timestamp":1568575818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9727-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,25]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["9727"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9727-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,11,25]]}}}