Abstract
Deutsch–Jozsa problem (\(DJ_{n}\)) showed for the first time that quantum computation can achieve exponential advantages over classical computers, which encouraged and laid the foundation for further research on quantum algorithms. A generalization of Deutsch–Jozsa problem (\(DJ^{k}_{n}\), proposed by Phys Rev A 97:062331, 2018) maintains the exponential advantage when the parameter k is a constant. However, these achieved exponential advantages are just in the case that all outputs are required to be accurate. In contrast, this paper studies classical randomized decision tree complexities of \(DJ_{n}\) and \(DJ^{k}_{n}\). It is proved that the first complexity \(R_{2}(DJ_{n})\le 3\) in all cases and the second complexity \(R_{2}(DJ^{k}_{n})\) is constant when \(\frac{k}{n}\) is constant for n being a large even number. As a result, for these cases, optimal bounded-error quantum algorithms of \(DJ_{n}\) and \(DJ^{k}_{n}\) can only slightly accelerate the classical computation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Buhrman, H., De Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288, 21–43 (2002)
Aaronson, S.: Open problems related to quantum query complexity. (2021). arxiv preprint arXiv:2109.06917
Nielson, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Montanaro, A., Nishimura, H., Raymond, R.: Unbounded error quantum query complexity. Theor. Comput. Sci. 412, 35 (2011)
Simon, D.R.: On the power of quantum computation. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, pp. 116–123 (1994)
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on the Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, pp. 124–134 (1994)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, New York, p. 212 (1996)
Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009)
Deutsch, D.: Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. Ser. A 400, 97 (1985)
Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser. A 439, 553 (1992)
Kish, L.B.: Quantum supremacy revisited: Low-complexity, deterministic solutions of the original Deutsch–Jozsa problem in classical physical systems. R. Soc. Open Sci. 10, 221327 (2023)
Liu, Y.: An exact quantum search algorithm with arbitrary database. Int. J. Theor. Phys. 53, 2571–2578 (2014)
Imran M.: An exact quantum order finding algorithm and its applications. (2022). arxiv preprint arXiv:2205.04240
Qiu, D.W., Zheng, S.G.: Revisiting Deutsch–Jozsa Algorithm. Inf. Comput. 275, 104605 (2020)
Qiu, D.W., Xu, G.L.: Partial Boolean functions computed by exact quantum 1-query algorithms. SPIN 11(03), 2140001 (2021)
Cornelissen, A.S., Mande, N., Ozols, M., De Wolf, R.: Exact quantum query complexity of computing Hamming weight modulo powers of two and three. (2021). arXiv preprint arXiv:2112.14682
Qiu, D.W., Zheng, S.G.: Generalized Deutsch–Jozsa problem and the optimal quantum algorithm. Phys. Rev. A 97, 062331 (2018)
Montanaro, A., Jozsa, R., Mitchison, G.: On exact quantum query complexity. Algorithmica 71, 4 (2015)
Qiu, D.W., Zheng, S.G.: Characterizations of promise problems with exact quantum query complexity. (2016). arXiv preprint arXiv:1603.06505
Mukherjee, C.S., Maitra, S.: Classical-quantum separations in certain classes of boolean functions-analysis using the parity decision trees. (2020). arXiv preprint arXiv:2004.12942v1
Xu, G.L., Qiu, D.W.: Partial Boolean functions with exact quantum 1-query complexity. Entropy 23(2), 189 (2021)
Brassard, G., Hyer, P.: An exact quantum polynomial-time algorithm for Simon’s problem. In: Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, IEEE Computer Society Press, pp. 12–23 (1997)
Acknowledgements
This work is supported in part by the National Natural Science Foundation of China (Nos. 62272208, 61572532, 61876195), the Natural Science Foundation of Guangdong Province of China (No. 2017B030311011), the Natural Science Foundation of Henan Province (Nos. 232300420426, 232300421354), Science and Technology Project of Henan Province (No. 222102110366), the Science and Technology Innovation Team of Henan University (No. 22IRTSTHN016), the Key Scientific Research Project of Higher Education of Henan Province (Nos. 23A520013, 22A110014 ), the Research and practice project of school-level higher education teaching reform (No. 2021xjgj022).
Author information
Authors and Affiliations
Contributions
Conceptualization, GX and DQ; formal analysis, GX and DQ; investigation, GX, DQ, BZ, TW and YZ; writing original draft preparation, GX and DQ; visualization, GX, DQ, BZ, TW and YZ; supervision, DQ, TW and YZ; funding acquisition, TW and YZ All authors have read and agreed to the published version of the manuscript.
Corresponding authors
Ethics declarations
Conflict of interest
The authors declare no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Xu, G., Qiu, D., Zhang, B. et al. Randomized decision tree complexity of Deutsch–Jozsa problem and a generalization. Quantum Inf Process 23, 79 (2024). https://doi.org/10.1007/s11128-024-04292-2
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11128-024-04292-2