On the exact quantum query complexity of MOD and EXACT functions
Penghui YAO, Zekun YE
On the exact quantum query complexity of MOD and EXACT functions
In this paper, we consider the exact quantum query complexity of two fundamental symmetric functions. 1) , which calculates the Hamming weight of an -bit string modulo ; 2) , which determines if the Hamming weight of an -bit string is exactly or . Although these two symmetric functions have received considerable attention, their exact quantum query complexities have not been fully characterized. Specifically, our results are as follows:
1) We design an optimal quantum query algorithm to compute exactly and thus provide a tight characterization of its exact quantum query complexity, which settles a previous conjecture. Based on this algorithm, we demonstrate that a broad class of symmetric functions is not evasive in the quantum model, i.e., there exist quantum algorithms to compute these functions exactly when the number of queries is less than their input size.
2) By proposing a quantum algorithm that utilizes the minimum number of queries to compute exactly for some specific values of and , we give a tight characterization of its exact quantum query complexity in these scenarios.
quantum computing / query complexity / symmetric functions / exact algorithms / evasiveness
Penghui Yao is currently an associate professor in the Department of Computer Science and Technology at Nanjing University, China. He received his PhD degree from the Centre for Quantum Technologies, National University of Singapore, Singapore in 2013. His research interests include quantum complexity theory, quantum information theory, quantum distributed computing, Fourier analysis in theoretical computer science and quantum computation, and derandomization
Zekun Ye is currently a PhD student in the Department of Computer Science and Technology at Nanjing University, China. His research interests include quantum algorithms, quantum query complexity, and quantum communication complexity
[1] |
Simon D R. On the power of quantum computation. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. 1994, 116−123
|
[2] |
Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science. 1994, 124−134
|
[3] |
Liu Q, Zhandry M. On finding quantum multi-collisions. In: Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2019, 189−218
|
[4] |
Yamakawa T, Zhandry M. Classical vs quantum random oracles. In: Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2021, 568−597
|
[5] |
Gilyén A, Arunachalam S, Wiebe N. Optimizing quantum optimization algorithms via faster quantum gradient computation. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. 2019, 1425−1444
|
[6] |
Chakrabarti S, Childs A M, Li T, Wu X . Quantum algorithms and lower bounds for convex optimization. Quantum, 2020, 4: 221
|
[7] |
Li T, Wu X . Quantum query complexity of entropy estimation. IEEE Transactions on Information Theory, 2019, 65( 5): 2899–2921
|
[8] |
Arunachalam S, Chakraborty S, Lee T, Paraashar M, De Wolf R . Two new results about quantum exact learning. Quantum, 2021, 5: 587
|
[9] |
Buhrman H, De Wolf R . Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 2002, 288( 1): 21–43
|
[10] |
Deutsch D, Jozsa R . Rapid solution of problems by quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1992, 439( 1907): 553–558
|
[11] |
Cleve R, Ekert A, Macchiavello C, Mosca M . Quantum algorithms revisited. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1998, 454( 1969): 339–354
|
[12] |
Høyer P . Arbitrary phases in quantum amplitude amplification. Physical Review A, 2000, 62( 5): 052304
|
[13] |
Long G L . Grover algorithm with zero theoretical failure rate. Physical Review A, 2001, 64( 2): 022307
|
[14] |
Brassard G, Høyer P, Mosca M, Tapp A . Quantum amplitude amplification and estimation. Contemporary Mathematics, 2002, 305: 53–74
|
[15] |
Qiu D, Zheng S. Characterizations of symmetrically partial Boolean functions with exact quantum query complexity. 2016, arXiv preprint arXiv: 1603.06505
|
[16] |
Qiu D, Zheng S . Generalized Deutsch-Jozsa problem and the optimal quantum algorithm. Physical Review A, 2018, 97( 6): 062331
|
[17] |
He X, Sun X, Yang G, Yuan P . Exact quantum query complexity of weight decision problems via chebyshev polynomials. Science China Information Sciences, 2023, 66( 2): 129503
|
[18] |
Qiu D, Zheng S . Revisiting Deutsch-Jozsa algorithm. Information and Computation, 2020, 275: 104605
|
[19] |
Li G, Li L . Deterministic quantum search with adjustable parameters: Implementations and applications. Information and Computation, 2023, 292: 105042
|
[20] |
Li G, Li L. Optimal exact quantum algorithm for the promised element distinctness problem. 2022, arXiv preprint arXiv: 2211.05443
|
[21] |
von zur Gathen J, Roche J R . Polynomials with two values. Combinatorica, 1997, 17( 3): 345–362
|
[22] |
Baker R C, Harman G, Pintz J . The difference between consecutive primes, II. Proceedings of the London Mathematical Society, 2001, 83( 3): 532–562
|
[23] |
Beals R, Buhrman H, Cleve R, Mosca M, De Wolf R . Quantum lower bounds by polynomials. Journal of the ACM, 2001, 48( 4): 778–797
|
[24] |
Montanaro A, Jozsa R, Mitchison G . On exact quantum query complexity. Algorithmica, 2015, 71( 4): 775–796
|
[25] |
Farhi E, Goldstone J, Gutmann S, Sipser M . Limit on the speed of quantum computation in determining parity. Physical Review Letters, 1998, 81( 24): 5442–5444
|
[26] |
Ambainis A, Iraids J, Smotrovs J. Exact quantum query complexity of EXACT and THRESHOLD. In: Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography. 2013, 263−269
|
[27] |
Cornelissen A, Mande N S, 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
|
[28] |
Ambainis A, Iraids J, Nagaj D. Exact quantum query complexity of EXACTk,ln. In: Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Informatics. 2017, 243−255
|
[29] |
Wu Z, Hou S Y, Zhang C, Li L, Zeng B. Variational learning algorithms for quantum query complexity. 2022, arXiv preprint arXiv: 2205.07449
|
[30] |
Kahn J, Saks M, Sturtevant D . A topological approach to evasiveness. Combinatorica, 1984, 4( 4): 297–306
|
[31] |
Lutz F H . Some results related to the evasiveness conjecture. Journal of Combinatorial Theory, Series B, 2001, 81( 1): 110–124
|
[32] |
He X, Huang N, Sun X. On the decision tree complexity of string matching. In: Proceeding of the 26th Annual European Symposium on Algorithms. 2018, 45: 1−45: 13
|
[33] |
Aaronson S . Algorithms for Boolean function query properties. SIAM Journal on Computing, 2003, 32( 5): 1140–1157
|
[34] |
Ambainis A, Gruska J, Zheng S. Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Information & Computation, 2015, 15(5−6): 435−452
|
[35] |
Kulkarni R, Qiao Y, Sun X . Any monotone property of 3-uniform hypergraphs is weakly evasive. Theoretical Computer Science, 2015, 588: 16–23
|
[36] |
Deutsch D . Quantum theory, the church−turing principle and the universal quantum computer. Proceedings of the Royal Society A Mathematical, Physical and Engineering Sciences, 1985, 400( 1818): 97–117
|
[37] |
Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. 10th anniversary ed. Cambridge: Cambridge University Press, 2010
|
[38] |
Jeffrey A, Dai H H. Handbook of Mathematical Formulas and Integrals. 4th ed. Amsterdam: Academic, 2008
|
/
〈 | 〉 |