{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:47:03Z","timestamp":1760233623779,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T00:00:00Z","timestamp":1612310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572532, 61876195"],"award-info":[{"award-number":["61572532, 61876195"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then F(f) is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.<\/jats:p>","DOI":"10.3390\/e23020189","type":"journal-article","created":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T11:54:31Z","timestamp":1612353271000},"page":"189","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Partial Boolean Functions With Exact Quantum Query Complexity One"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5520-667X","authenticated-orcid":false,"given":"Guoliang","family":"Xu","sequence":"first","affiliation":[{"name":"Institute of Quantum Computing and Computer Theory, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China"},{"name":"Guangdong Key Laboratory of Information Security Technology, Sun Yat-sen University, Guangzhou 510006, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1275-7599","authenticated-orcid":false,"given":"Daowen","family":"Qiu","sequence":"additional","affiliation":[{"name":"Institute of Quantum Computing and Computer Theory, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China"},{"name":"Guangdong Key Laboratory of Information Security Technology, Sun Yat-sen University, Guangzhou 510006, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","article-title":"Complexity measures and decision tree complexity: A survey","volume":"288","author":"Buhrman","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1145\/502090.502097","article-title":"Quantum lower bounds by polynomials","volume":"48","author":"Beals","year":"2001","journal-title":"J. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1006\/jcss.2002.1826","article-title":"Quantum lower bounds by quantum arguments","volume":"64","author":"Ambainis","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"032335","DOI":"10.1103\/PhysRevA.75.032335","article-title":"Quantum algorithms for the ordered search problem via semidefinite programming","volume":"75","author":"Childs","year":"2007","journal-title":"Phys. Rev. A"},{"key":"ref_5","first-page":"78","article-title":"Lower Bounds on Quantum Query Complexity","volume":"87","author":"Hyer","year":"2005","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Nielson, M.A., and Chuang, I.L. (2012). Quantum Computation and Quantum Information, Cambridge University Press. [10th ed.].","key":"ref_6","DOI":"10.1017\/CBO9780511976667"},{"unstructured":"Goldwasser, S. (1994, January 20\u201322). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA.","key":"ref_7"},{"doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 22\u201324). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, USA.","key":"ref_8","DOI":"10.1145\/237814.237866"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1098\/rspa.1985.0070","article-title":"Quantum theory, the Church-Turing Principle and the universal quantum computer","volume":"400","author":"Deutsch","year":"1985","journal-title":"Proc. R. Soc. London Ser. A"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1098\/rspa.1992.0167","article-title":"Rapid solution of problems by quantum computation","volume":"439","author":"Deutsch","year":"1992","journal-title":"Proc. R. Soc. London Ser. A"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","article-title":"Quantum Algorithm for Linear Systems of Equations","volume":"103","author":"Harrow","year":"2009","journal-title":"Phys. Rev. Lett."},{"unstructured":"Ambainis, A., Iraids, J., and Smotrovs, J. (2013, January 21\u201323). Exact quantum query complexity of EXACT and THRESHOLD. Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, Guelph, ON, Canada.","key":"ref_12"},{"doi-asserted-by":"crossref","unstructured":"Ambainis, A. (2013, January 1\u20134). Superlinear advantage for exact quantum algorithms. Proceedings of the 45th Annual ACM Symposium on Theory of Computing, Palo Alto, CA, USA.","key":"ref_13","DOI":"10.1145\/2488608.2488721"},{"key":"ref_14","first-page":"435","article-title":"Exact quantum algorithms have advantage for almost all Boolean functions","volume":"15","author":"Ambainis","year":"2015","journal-title":"Quantum Inf. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1007\/s00453-013-9826-8","article-title":"On exact quantum query complexity","volume":"71","author":"Montanaro","year":"2015","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Steffen, B., and Baier, C. (2017). Exact Quantum Query Complexity of EXACTnk,l. SOFSEM 2017: Theory and Practice of Computer Science, Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, 16\u201320 January 2017, Springer.","key":"ref_16","DOI":"10.1007\/978-3-319-51963-0"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"062331","DOI":"10.1103\/PhysRevA.97.062331","article-title":"Generalized Deutsch-Jozsa problem and the optimal quantum algorithm","volume":"97","author":"Qiu","year":"2018","journal-title":"Phys. Rev. A"},{"unstructured":"He, X.Y., Sun, X.M., Yang, G., and Yuan, P. (2020, December 22). Exact Quantum Query Complexity of Weight Decision Problems via Chebyshev Polynomials. Available online: https:\/\/arxiv.org\/abs\/1801.05717.","key":"ref_18"},{"doi-asserted-by":"crossref","unstructured":"Kaniewski, J., Lee, T., and de Wolf, R. (2015, January 6\u201310). Query Complexity in Expectation. Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan.","key":"ref_19","DOI":"10.1007\/978-3-662-47672-7_62"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"4619","DOI":"10.1016\/j.tcs.2011.04.043","article-title":"Unbounded error quantum query complexity","volume":"412","author":"Montanaro","year":"2011","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Ambainis, A., Balodis, K., Belovs, A., Lee, T., Santha, M., and Smotrovs, J. (2016, January 19\u201321). Separations in query complexity based on pointer functions. Proceedings of the 48th ACM Symposium on Theory of Computing, Cambridge, MA, USA. Available online: https:\/\/arxiv.org\/abs\/1506.04719.","key":"ref_21","DOI":"10.1145\/2897518.2897524"},{"unstructured":"Montanaro, A. (2020, December 22). Structure, Randomness and Complexity in Quantum Computation. Available online: https:\/\/people.maths.bris.ac.uk\/csxam\/papers\/thesis.pdf.","key":"ref_22"},{"unstructured":"Qiu, D.W., and Zheng, S.G. (2020, December 22). Characterizations of Symmetrically Partial Boolean Functions with Exact Quantum Query Complexity. Available online: https:\/\/arxiv.org\/abs\/1603.06505.","key":"ref_23"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"104605","DOI":"10.1016\/j.ic.2020.104605","article-title":"Revisiting Deutsch-Jozsa Algorithm","volume":"275","author":"Qiu","year":"2020","journal-title":"Inform. Comput."},{"unstructured":"Raz, R. (June, January 29). Polynomials, Quantum Query Complexity, and Grothendieck\u2019s Inequality. Proceedings of the 31st Conference on Computational Complexity, Tokyo, Japan.","key":"ref_25"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.tcs.2018.03.017","article-title":"Quantum query as a state decomposition","volume":"736","author":"Grillo","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1137\/18M117563X","article-title":"Quantum Query Algorithms Are Completely Bounded Forms","volume":"48","author":"Arunachalam","year":"2019","journal-title":"SIAM J. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"022325","DOI":"10.1103\/PhysRevA.101.022325","article-title":"Characterization of exact one-query quantum algorithms","volume":"101","author":"Chen","year":"2020","journal-title":"Phys. Rev. A"},{"unstructured":"Mukherjee, C.S., and Maitra, S. (2020, December 22). Classical-Quantum Separations in Certain Classes of Boolean Functions-Analysis Using the Parity Decision Trees. Available online: https:\/\/arxiv.org\/abs\/2004.12942.","key":"ref_29"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1137\/S0097539702407345","article-title":"Nondeterministic quantum query and communication complexities","volume":"32","year":"2003","journal-title":"SIAM J. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/S0019-9958(82)90477-6","article-title":"A tight \u03c9(log log n)-bound on the time for parallel RAM\u2019s to compute non-degenerated boolean functions","volume":"55","author":"Simon","year":"1982","journal-title":"Inf. Control."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01263419","article-title":"On the degree of Boolean functions as real polynomials","volume":"4","author":"Nisan","year":"1994","journal-title":"Comput. Complex."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s11128-020-02975-0","article-title":"From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm","volume":"20","author":"Xu","year":"2021","journal-title":"Quantum Inf. Process"},{"unstructured":"Raz, R. (June, January 29). On the sum-of-squares degree of symmetric quadratic functions. Proceedings of the 31st Conference on Computational Complexity, Tokyo, Japan.","key":"ref_34"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0022-4049(97)83827-3","article-title":"An algorithm for sums of squares of real polynomials","volume":"127","author":"Powers","year":"1998","journal-title":"J. Pure. Appl. Algebra"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1137\/04061413X","article-title":"A sum of squares approximation of nonnegative polynomials","volume":"16","author":"Lasserre","year":"2006","journal-title":"SIAM J. Optimiz."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/s00013-007-2251-y","article-title":"Sufficient conditions for a real polynomial to be a sum of squares","volume":"89","author":"Lasserre","year":"2006","journal-title":"Arch. Math."},{"unstructured":"Papachristodoulou, A., Anderson, J., Valmorbida, G., Prajna, S., Seiler, P., and Parrilo, P. (2020, December 22). SOSTOOLS Version 3.00 Sum of Squares Optimization Toolbox for MATLAB. Available online: https:\/\/arxiv.org\/abs\/1310.4716.","key":"ref_38"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s00209-016-1644-7","article-title":"Sums of squares on the hypercube","volume":"284","author":"Blekherman","year":"2016","journal-title":"Math. Z."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/2\/189\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:19:44Z","timestamp":1760159984000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/2\/189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,3]]},"references-count":39,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["e23020189"],"URL":"https:\/\/doi.org\/10.3390\/e23020189","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,2,3]]}}}