{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:04:31Z","timestamp":1764781471803,"version":"3.46.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T00:00:00Z","timestamp":1759449600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T00:00:00Z","timestamp":1759449600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00037-025-00277-4","type":"journal-article","created":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T06:17:52Z","timestamp":1759472272000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree"],"prefix":"10.1007","volume":"34","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksandrs","family":"Belovs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,3]]},"reference":[{"key":"277_CR1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson (2002). Quantum lower bound for the collision problem.\nIn Proc. of 34th ACM STOC, 635\u2013642.","DOI":"10.1145\/509907.509999"},{"key":"277_CR2","doi-asserted-by":"crossref","unstructured":"Scott Aaronson (2021). Open problems related to quantum query\ncomplexity. ACM Transactions on Quantum Computing 2(4), 1\u20139.","DOI":"10.1145\/3488559"},{"key":"277_CR3","doi-asserted-by":"crossref","unstructured":"Scott Aaronson, Shalev Ben-David & Robin Kothari (2016).\nSeparations in query complexity using cheat sheets. In Proc. of 48th\nACM STOC, 863\u2013876.","DOI":"10.1145\/2897518.2897644"},{"key":"277_CR4","doi-asserted-by":"crossref","unstructured":"Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas\nRao & Avishay Tal (2021). Degree vs. approximate degree and quantum\nimplications of Huang\u2019s sensitivity theorem. In Proc. of 53rd ACM\nSTOC, 1330\u20131342.","DOI":"10.1145\/3406325.3451047"},{"key":"277_CR5","doi-asserted-by":"crossref","unstructured":"Scott Aaronson & Yaoyun Shi (2004). Quantum Lower Bounds\nfor the Collision and the Element Distinctness Problems. Journal of the\nACM 51(4), 595\u2013605.","DOI":"10.1145\/1008731.1008735"},{"key":"277_CR6","doi-asserted-by":"crossref","unstructured":"Andris Ambainis (2002). Quantum Lower Bounds by Quantum Arguments.\nJournal of Computer and System Sciences 64(4), 750\u2013767.","DOI":"10.1006\/jcss.2002.1826"},{"key":"277_CR7","doi-asserted-by":"crossref","unstructured":"Andris Ambainis (2003). Polynomial degree vs. quantum query complexity.\nIn Proc. of 44th  IEEE FOCS, 230\u2013239.","DOI":"10.1109\/SFCS.2003.1238197"},{"key":"277_CR8","unstructured":"Anurag Anshu, Shalev Ben-David & Srijita Kundu (2021). On\nquery-to-communication lifting for adversary bounds. In Proc. of 36th\nIEEE CCC, volume 200 of LIPIcs, 30:1\u201330:39."},{"key":"277_CR9","doi-asserted-by":"crossref","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele\nMosca & Ronald de Wolf (2001). Quantum lower bounds by polynomials.\nJournal of the ACM 48(4), 778\u2013797.","DOI":"10.1145\/502090.502097"},{"key":"277_CR10","doi-asserted-by":"crossref","unstructured":"Aleksandrs Belovs & Ansis Rosmanis (2014). On the Power of\nNon-Adaptive Learning Graphs. Computational Complexity 23(2), 323\u2013\n354.","DOI":"10.1007\/s00037-014-0084-1"},{"key":"277_CR11","unstructured":"Aleksandrs Belovs & Ansis Rosmanis (2018). Quantum Lower\nBounds for Tripartite Versions of the Hidden Shift and the Set Equality\nProblems. In Proc. of 13th TQC, volume 111 of LIPIcs, 3:1\u20133:15.\nDagstuhl."},{"key":"277_CR12","doi-asserted-by":"crossref","unstructured":"Aleksandrs Belovs & Robert \u0160palek (2013). Adversary Lower\nBound for the k-sum Problem. In Proc. of 4th ACM ITCS, 323\u2013328.","DOI":"10.1145\/2422436.2422474"},{"key":"277_CR13","doi-asserted-by":"crossref","unstructured":"Harry Buhrman & Ronald de Wolf (2002). Complexity measures\nand decision tree complexity: a survey. Theoretical Computer Science\n288, 21\u201343.","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"277_CR14","doi-asserted-by":"crossref","unstructured":"Mark Bun, Robin Kothari & Justin Thaler (2018). The polynomial\nmethod strikes back: Tight quantum query bounds via dual\npolynomials. In Proc. of 50th ACM STOC, 297\u2013310.","DOI":"10.1145\/3188745.3188784"},{"key":"277_CR15","doi-asserted-by":"crossref","unstructured":"Peter H\u00f8yer, Troy Lee & Robert \u0160palek (2007). Negative\nweights make adversaries stronger. In Proc. of 39th ACM STOC, 526\u2013\n535.","DOI":"10.1145\/1250790.1250867"},{"key":"277_CR16","doi-asserted-by":"crossref","unstructured":"Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert \u0160palek\n& Mario Szegedy (2011). Quantum query complexity of state conversion.\nIn Proc. of 52nd IEEE FOCS, 344\u2013353.","DOI":"10.1109\/FOCS.2011.75"},{"key":"277_CR17","unstructured":"Nikhil S. Mande, Justin Thaler & Shuchen Zhu (2020). Improved\nApproximate Degree Bounds for k-Distinctness. In Proc. of 15th TQC,\nvolume 158 of LIPIcs, 2:1\u20132:22."},{"key":"277_CR18","unstructured":"Gatis Midrij\u0101nis (2004). Exact quantum query complexity for total\nBoolean functions. Quant-ph\/0403168."},{"key":"277_CR19","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1991). CREW PRAMs and decision trees. SIAM Journal\non Computing 20(6), 999\u20131007.","DOI":"10.1137\/0220062"},{"key":"277_CR20","doi-asserted-by":"crossref","unstructured":"Noam Nisan & Mario Szegedy (1994). On the degree of Boolean\nfunctions as real polynomials. Computational Complexity 4(4), 301\u2013\n313.","DOI":"10.1007\/BF01263419"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00277-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00277-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00277-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:05Z","timestamp":1764781205000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00277-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,3]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["277"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00277-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,10,3]]},"assertion":[{"value":"28 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"14"}}