{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T04:27:38Z","timestamp":1743827258126,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61572532"],"award-info":[{"award-number":["61572532"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s11128-020-02975-0","type":"journal-article","created":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T02:06:49Z","timestamp":1610503609000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm"],"prefix":"10.1007","volume":"20","author":[{"given":"Guoliang","family":"Xu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1275-7599","authenticated-orcid":false,"given":"Daowen","family":"Qiu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,12]]},"reference":[{"key":"2975_CR1","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D Deutsch","year":"1985","unstructured":"Deutsch, D.: Quantum theory, the Church\u2013Turing principle and the universal quantum computer. Proc. R. Soc. Lond. Ser. A 400, 97 (1985)","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"key":"2975_CR2","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"439","author":"D Deutsch","year":"1992","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser. A 439, 553 (1992)","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"key":"2975_CR3","unstructured":"Shor, P. W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of Annual Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, pp. 124\u2013134 (1994)"},{"key":"2975_CR4","doi-asserted-by":"crossref","unstructured":"Grover, L. K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. ACM, New York, p. 212 (1996)","DOI":"10.1145\/237814.237866"},{"key":"2975_CR5","doi-asserted-by":"publisher","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009)","journal-title":"Phys. Rev. Lett."},{"key":"2975_CR6","unstructured":"Jordan, S.: The quantum algorithm zoo. Available at http:\/\/math.nist.gov\/quantum\/zoo\/"},{"key":"2975_CR7","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semi-definite programming. In: IEEE Conference on Computational Complexity (2003)"},{"key":"2975_CR8","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2018.03.017","volume":"736","author":"SA Grillo","year":"2018","unstructured":"Grillo, S.A., Marquezino, F.L.: Quantum query as a state decomposition. Theor. Comput. Sci. 736, 62\u201375 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"2975_CR9","unstructured":"Arunachalam, S., Bri\u00ebt, J., Palazuelos, C.: Quantum query algorithms are completely bounded forms. (2017). arXiv preprint arXiv:1711.07285"},{"key":"2975_CR10","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielson","year":"2000","unstructured":"Nielson, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"2975_CR11","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288, 21\u201343 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"2975_CR12","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/502090.502097","volume":"48","author":"R Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48, 4 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"2975_CR13","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1006\/jcss.2002.1826","volume":"64","author":"A Ambainis","year":"2002","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci. 64(4), 750\u2013767 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"2975_CR14","unstructured":"Ambainis, A., Iraids, J., Smotrovs, J.: Exact quantum query complexity of EXACT and THRESHOLD (2013). arXiv:1302.1235"},{"key":"2975_CR15","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/s00453-013-9826-8","volume":"71","author":"A Montanaro","year":"2015","unstructured":"Montanaro, A., Jozsa, R., Mitchison, G.: On exact quantum query complexity. Algorithmica 71, 4 (2015)","journal-title":"Algorithmica"},{"key":"2975_CR16","series-title":"Lecture Notes in Computer Science","volume-title":"Exact Quantum Query Complexity of $${\\rm EXACT}^{n}_{k,l}$$","author":"A Ambainis","year":"2017","unstructured":"Ambainis, A., Iraids, J., Nagaj, D.: Exact Quantum Query Complexity of $${\\rm EXACT}^{n}_{k,l}$$. Lecture Notes in Computer Science, vol. 10139. Springer, Cham (2017)"},{"key":"2975_CR17","doi-asserted-by":"publisher","first-page":"062331","DOI":"10.1103\/PhysRevA.97.062331","volume":"97","author":"DW Qiu","year":"2018","unstructured":"Qiu, D.W., Zheng, S.G.: Generalized Deutsch\u2013Jozsa problem and the optimal quantum algorithm. Phys. Rev. A 97, 062331 (2018)","journal-title":"Phys. Rev. A"},{"key":"2975_CR18","unstructured":"He, X. Y., Sun, X. M.,Yang, G., Pei, Y.: Exact quantum query complexity of weight decision problems (2018). arXiv:1801.05717"},{"key":"2975_CR19","doi-asserted-by":"crossref","unstructured":"Gangopadhyay, S., Behera, B. K., Panigrahi, P. K.: Generalization and partial demonstration of an entanglement based Deutsch\u2013Jozsa like algorithm using a 5-Qubit quantum computer (2017). arXiv:1708.06375v1","DOI":"10.1007\/s11128-018-1932-8"},{"key":"2975_CR20","unstructured":"Huang, H.L., Ashutosh, K.G., Bao, W.S., Prasanta, K.P.: Demonstration of the essentiality of entanglement in a Deutsch-like quantum algorithm. arXiv:1706.09489"},{"key":"2975_CR21","doi-asserted-by":"publisher","first-page":"022338","DOI":"10.1103\/PhysRevA.92.022338","volume":"92","author":"TG Wong","year":"2015","unstructured":"Wong, T.G., Ambainis, A.: Quantum search with multiple walk steps per oracle query. Phys. Rev. A 92, 022338 (2015)","journal-title":"Phys. Rev. A"},{"key":"2975_CR22","doi-asserted-by":"publisher","first-page":"022353","DOI":"10.1103\/PhysRevA.92.022353","volume":"92","author":"A Tulsi","year":"2015","unstructured":"Tulsi, A.: Postprocessing can speed up general quantum search algorithms. Phys. Rev. A 92, 022353 (2015)","journal-title":"Phys. Rev. A"},{"key":"2975_CR23","doi-asserted-by":"publisher","first-page":"032335","DOI":"10.1103\/PhysRevA.75.032335","volume":"75","author":"AM Childs","year":"2006","unstructured":"Childs, A.M., Landahl, A.J., Parrilo, P.A.: Quantum algorithms for the ordered search problem via semidefinite programming. Phys. Rev. A 75, 032335 (2006)","journal-title":"Phys. Rev. A"},{"key":"2975_CR24","first-page":"78","volume":"87","author":"P H\u00f8yer","year":"2005","unstructured":"H\u00f8yer, P., S\u0302palek, R.: Lower bounds on quantum query complexity. Bull. Eur. Assoc. Theor. Comput. Sci. 87, 78\u2013103 (2005)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"2975_CR25","series-title":"Lecture Notes in Computer Science","volume-title":"Query Complexity in Expectation","author":"J Kaniewski","year":"2015","unstructured":"Kaniewski, J., Lee, T., de Wolf, R.: Query Complexity in Expectation. Lecture Notes in Computer Science, vol. 9174. Springer, Berlin (2015)"},{"key":"2975_CR26","unstructured":"Lee, T., Prakash, A., de Wolf, R., Yuen, H.: On the sum-of-squares degree of symmetric quadratic functions. In: Conference on Computational Complexity (2016)"},{"key":"2975_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-4049(97)00050-9","volume":"127","author":"P Victoria","year":"1998","unstructured":"Victoria, P., W\u00f6rmann, T.: An algorithm for sums of squares of real polynomials. J. Pure. Appl. Algebra 127, 1 (1998)","journal-title":"J. Pure. Appl. Algebra"},{"key":"2975_CR28","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1137\/04061413X","volume":"16","author":"JB Lasserre","year":"2006","unstructured":"Lasserre, J.B.: A sum of squares approximation of nonnegative polynomials. SIAM J. Optim. 16, 3 (2006)","journal-title":"SIAM J. Optim."},{"key":"2975_CR29","unstructured":"Lasserre, J. B.: Conditions for a real polynomial to be sum of squares. (2006). arXiv:math\/0612358v1"},{"key":"2975_CR30","unstructured":"Papachristodoulou, A., Anderson, J., Valmorbida, G., Prajna, S., Seiler, P., Parrilo, P.: SOSTOOLS version 3.00 sum of squares optimization toolbox for MATLAB. preprint (2013). arXiv:1310.4716"},{"key":"2975_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00209-016-1642-9","volume":"284","author":"B Grigoriy","year":"2016","unstructured":"Grigoriy, B., Jo\u00e3o, G., James, P.: Sums of squares on the hypercube. Math. Z. 284, 1\u20132 (2016)","journal-title":"Math. Z."},{"issue":"3","key":"2975_CR32","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1137\/S0097539702407345","volume":"32","author":"R de Wolf","year":"2003","unstructured":"de Wolf, R.: Nondeterministic quantum query and communication complexitiess. SIAM J. Comput. 32(3), 681\u2013699 (2003)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2975_CR33","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of Boolean functions as real polynomials. Comput. Complex. 4(4), 301\u2013313 (1994)","journal-title":"Comput. Complex."},{"key":"2975_CR34","series-title":"Lecture Notes in Computer Science","volume-title":"A tight omega($$\\log \\log $$ n)-Bound on the Time for Parallel RAMs to Compute nondegenerated Boolean Functions","author":"HU Simon","year":"1983","unstructured":"Simon, H.U.: A tight omega($$\\log \\log $$ n)-Bound on the Time for Parallel RAMs to Compute nondegenerated Boolean Functions. Lecture Notes in Computer Science, vol. 158. Springer, Berlin (1983)"},{"key":"2975_CR35","unstructured":"Aaronson, S., Ambainis, A., Iraids, J., Kokainis, M., Smotrovs, J.: Polynomials, quantum query complexity, and Grothendieck\u2019s inequality. In: Proceedings of 31st Conference on Computational Complexity (CCC), Tokyo, Japan (2016)"},{"key":"2975_CR36","unstructured":"Ambainis, A.: Understanding quantum algorithms via query complexity (2017). arXiv:1712.06349"},{"key":"2975_CR37","unstructured":"Qiu, D.W. , Zheng, S.G.: Characterizations of symmetrically partial Boolean functions with exact quantum query complexity (2016). arXiv:1603.06505"},{"key":"2975_CR38","doi-asserted-by":"publisher","first-page":"104605","DOI":"10.1016\/j.ic.2020.104605","volume":"275","author":"DW Qiu","year":"2020","unstructured":"Qiu, D.W., Zheng, S.G.: Revisiting Deutsch\u2013Jozsa Algorithm. Information and Computation 275, 104605 (2020)","journal-title":"Information and Computation"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02975-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-020-02975-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02975-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T08:44:12Z","timestamp":1612946652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-020-02975-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["2975"],"URL":"https:\/\/doi.org\/10.1007\/s11128-020-02975-0","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"15 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"33"}}