{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:53:27Z","timestamp":1725576807066},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642180729"},{"type":"electronic","value":"9783642180736"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-18073-6_9","type":"book-chapter","created":{"date-parts":[[2011,1,19]],"date-time":"2011-01-19T06:07:19Z","timestamp":1295417239000},"page":"104-112","source":"Crossref","is-referenced-by-count":2,"title":["The Polynomial Degree of Recursive Fourier Sampling"],"prefix":"10.1007","author":[{"given":"Benjamin","family":"Johnson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/167088.167097","volume-title":"STOC 1993: Proceedings of the Twenty-Fifth Annual ACM symposium on Theory of computing","author":"E. Bernstein","year":"1993","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. In: STOC 1993: Proceedings of the Twenty-Fifth Annual ACM symposium on Theory of computing, pp. 11\u201320. ACM Press, New York (1993)"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput.\u00a026, 1411\u20131473 (1997)","journal-title":"SIAM J. Comput."},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing\u00a026, 1484\u20131509 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. In: IEEE Symposium on Foundations of Computer Science, pp. 352\u2013361 (1998)","DOI":"10.1109\/SFCS.1998.743485"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1145\/509907.509999","volume-title":"STOC 2002: Proceedings of the Thiry-Fourth Annual ACM symposium on Theory of Computing","author":"S. Aaronson","year":"2002","unstructured":"Aaronson, S.: Quantum lower bound for the collision problem. In: STOC 2002: Proceedings of the Thiry-Fourth Annual ACM symposium on Theory of Computing, pp. 635\u2013642. ACM, New York (2002)"},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"2","DOI":"10.26421\/QIC3.2-7","volume":"3","author":"S. Aaronson","year":"2003","unstructured":"Aaronson, S.: Quantum lower bound for recursive fourier sampling. Quantum Information and Computation\u00a03, 2\u201372 (2003)","journal-title":"Quantum Information and Computation"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Bqp and the polynomial hierarchy. Technical Report ECCC TR09-104 (2009)","DOI":"10.1145\/1806689.1806711"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M.L. Furst","year":"1984","unstructured":"Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory\u00a017, 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"9_CR9","unstructured":"Johnson, B.E.: Upper and Lower Bounds for Recursive Fourier Sampling. PhD thesis, University of California at Berkeley, Berkeley, CA, USA, chair - Leo Harrington (2008)"}],"container-title":["Lecture Notes in Computer Science","Theory of Quantum Computation, Communication, and Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-18073-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,4]],"date-time":"2023-06-04T18:35:01Z","timestamp":1685903701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-18073-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642180729","9783642180736"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-18073-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}