{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:27:29Z","timestamp":1740137249940,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T00:00:00Z","timestamp":1585094400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T00:00:00Z","timestamp":1585094400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","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":[[2020,5]]},"DOI":"10.1007\/s11128-020-02652-2","type":"journal-article","created":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T18:02:42Z","timestamp":1585159362000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantum and classical query complexities for generalized Deutsch\u2013Jozsa problems"],"prefix":"10.1007","volume":"19","author":[{"given":"Zhengwei","family":"Xie","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":[[2020,3,25]]},"reference":[{"key":"2652_CR1","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of 28th ACM Symposium on Theory of Computing, pp. 212-219. ACM, Philadelphia (1996)","DOI":"10.1145\/237814.237866"},{"issue":"1907","key":"2652_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(1907), 553\u2013558 (1992)","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"issue":"2","key":"2652_CR3","doi-asserted-by":"publisher","first-page":"022307","DOI":"10.1103\/PhysRevA.64.022307","volume":"64","author":"GL Long","year":"2001","unstructured":"Long, G.L.: Grover algorithm with zero theoretical failure rate. Phys. Rev. A 64(2), 022307 (2001)","journal-title":"Phys. Rev. A"},{"key":"2652_CR4","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.jcss.2018.05.001","volume":"97","author":"G Cai","year":"2018","unstructured":"Cai, G., Qiu, D.: Optimal separation in exact query complexities for Simon\u2019s problem. J. Comput. Syst. Sci. 97, 83\u201393 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"2652_CR5","unstructured":"Wu, Z., Qiu, D., Cai, G., et al.: Quantum and classical query complexities for generalized Simon\u2019s problem (2019). arXiv:1905.08549"},{"issue":"22\u201323","key":"2652_CR6","doi-asserted-by":"publisher","first-page":"1925","DOI":"10.1016\/j.physleta.2016.04.006","volume":"380","author":"B Perez-Garcia","year":"2016","unstructured":"Perez-Garcia, B., McLaren, M., Goyal, S.K., et al.: Quantum computation with classical light: implementation of the Deutsch\u2013Jozsa algorithm. Phys. Lett. A 380(22\u201323), 1925\u20131931 (2016)","journal-title":"Phys. Lett. A"},{"issue":"3","key":"2652_CR7","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1142\/S021974990700292X","volume":"5","author":"CS Calude","year":"2007","unstructured":"Calude, C.S.: De-quantizing the solution of Deutsch\u2019s problem. Int. J. Quantum Inf. 5(3), 409\u2013415 (2007)","journal-title":"Int. J. Quantum Inf."},{"issue":"7","key":"2652_CR8","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/s11128-018-1932-8","volume":"17","author":"S Gangopadhyay","year":"2018","unstructured":"Gangopadhyay, S., Behera, B.K., Panigrahi, P.K.: Generalization and demonstration of an entanglement-based Deutsch\u2013Jozsa-like algorithm using a 5-qubit quantum computer. Quantum Inf. Process. 17(7), 160 (2018)","journal-title":"Quantum Inf. Process."},{"issue":"6","key":"2652_CR9","doi-asserted-by":"publisher","first-page":"062331","DOI":"10.1103\/PhysRevA.97.062331","volume":"97","author":"D Qiu","year":"2018","unstructured":"Qiu, D., Zheng, S.: Generalized Deutsch\u2013Jozsa problem and the optimal quantum algorithm. Phys. Rev. A 97(6), 062331 (2018)","journal-title":"Phys. Rev. A"},{"key":"2652_CR10","unstructured":"He, X., Sun, X., Yang, G., et al.: Exact quantum query complexity of weight decision problems (2018). arXiv:1801.05717v2"},{"issue":"2","key":"2652_CR11","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1137\/13092770X","volume":"45","author":"D Chakrabarty","year":"2016","unstructured":"Chakrabarty, D., Seshadhri, C.: An $$o(n)$$ monotonicity tester for boolean functions over the hypercube. SIAM J. Comput. 45(2), 461\u2013472 (2016)","journal-title":"SIAM J. Comput."},{"key":"2652_CR12","doi-asserted-by":"crossref","unstructured":"Chen, X., Servedio, R.A., Tan, L.Y.: New algorithms and lower bounds for monotonicity testing. In: Proceedings of 55th Annual Symposium on Foundations of Computer Science, pp. 286-295. IEEE, Philadelphia (2014)","DOI":"10.1109\/FOCS.2014.38"},{"issue":"6","key":"2652_CR13","doi-asserted-by":"publisher","first-page":"2238","DOI":"10.1137\/16M1065872","volume":"47","author":"S Khot","year":"2018","unstructured":"Khot, S., Minzer, D., Safra, M.: On monotonicity testing and boolean isoperimetric-type theorems. SIAM J. Comput. 47(6), 2238\u20132276 (2018)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"2652_CR14","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/3213772","volume":"65","author":"X Chen","year":"2018","unstructured":"Chen, X., Servedio, R.A., Tan, L.Y., et al.: Settling the query complexity of non-adaptive junta testing. J. ACM 65(6), 40 (2018)","journal-title":"J. ACM"},{"issue":"1","key":"2652_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00446-018-0324-8","volume":"32","author":"K Censor-Hillel","year":"2019","unstructured":"Censor-Hillel, K., Fischer, E., Schwartzman, G., et al.: Fast distributed algorithms for testing graph properties. Distrib. Comput. 32(1), 41\u201357 (2019)","journal-title":"Distrib. Comput."},{"issue":"4","key":"2652_CR16","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"issue":"5","key":"2652_CR17","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1137\/S0097539704442416","volume":"37","author":"H Buhrman","year":"2008","unstructured":"Buhrman, H., Fortnow, L., Newman, I., et al.: Quantum property testing. SIAM J. Comput. 37(5), 1387\u20131400 (2008)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"2652_CR18","doi-asserted-by":"publisher","first-page":"062329","DOI":"10.1103\/PhysRevA.84.062329","volume":"84","author":"M Hillery","year":"2011","unstructured":"Hillery, M., Andersson, E.: Quantum tests for the linearity and permutation invariance of Boolean functions. Phys. Rev. A 84(6), 062329 (2011)","journal-title":"Phys. Rev. A"},{"key":"2652_CR19","unstructured":"Montanaro, A., Wolf, R.D.: A survey of quantum property testing (2013). arXiv:1310.2035v4"},{"issue":"3","key":"2652_CR20","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF01201278","volume":"29","author":"JY Cai","year":"1996","unstructured":"Cai, J.Y., Green, F., Thierauf, T.: On the correlation of symmetric functions. Math. Syst. Theory 29(3), 245\u2013258 (1996)","journal-title":"Math. Syst. Theory"},{"issue":"2","key":"2652_CR21","doi-asserted-by":"publisher","first-page":"8","DOI":"10.37236\/2004","volume":"18","author":"FN Castro","year":"2011","unstructured":"Castro, F.N., Medina, L.A.: Linear recurrences and asymptotic behavior of exponential sums of symmetric boolean functions. Electron. J. Comb. 18(2), 8 (2011)","journal-title":"Electron. J. Comb."},{"issue":"3","key":"2652_CR22","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s00026-014-0230-0","volume":"18","author":"FN Castro","year":"2014","unstructured":"Castro, F.N., Medina, L.A.: Asymptotic behavior of perturbations of symmetric functions. Ann. Comb. 18(3), 397\u2013417 (2014)","journal-title":"Ann. Comb."},{"issue":"5","key":"2652_CR23","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s00200-018-0351-5","volume":"29","author":"FN Castro","year":"2018","unstructured":"Castro, F.N., Medina, L.A., St\u0103nic\u0103, P.: Generalized Walsh transforms of symmetric and rotation symmetric Boolean functions are linear recurrent. Appl. Algebra Eng. Commun. Comput. 29(5), 433\u2013453 (2018)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"issue":"6","key":"2652_CR24","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/s11128-019-2303-9","volume":"18","author":"J Cui","year":"2019","unstructured":"Cui, J., Guo, J., Xu, L., et al.: Quantum algorithms for learning Walsh spectra of multi-output Boolean functions. Quantum Inf. Process. 18(6), 180 (2019)","journal-title":"Quantum Inf. Process."},{"key":"2652_CR25","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/conm\/305\/05215","volume":"305","author":"G Brassard","year":"2002","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., et al.: Quantum amplitude amplification and estimation. Contemp. Math. 305, 53\u201374 (2002)","journal-title":"Contemp. Math."},{"key":"2652_CR26","doi-asserted-by":"crossref","unstructured":"Nayak, A., Wu, F.: The quantum query complexity of approximating the median and related statistics (1998). arXiv:quant-ph\/9804066v2","DOI":"10.1145\/301250.301349"},{"issue":"1","key":"2652_CR27","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., Wolf, R.D.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21\u201343 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"2652_CR28","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01111276","volume":"86","author":"H Ehlich","year":"1964","unstructured":"Ehlich, H., Zeller, K.: Schwankung von polynomen zwischen gitterpunkten. Math. Z. 86(1), 41\u201344 (1964)","journal-title":"Math. Z."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02652-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-020-02652-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02652-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T00:23:58Z","timestamp":1616631838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-020-02652-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,25]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["2652"],"URL":"https:\/\/doi.org\/10.1007\/s11128-020-02652-2","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2020,3,25]]},"assertion":[{"value":"4 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"150"}}