2020/08/14 by Chandra Sekhar Mukherjee, Subhamoy Maitra, Mukherjee, Chandra Sekhar +1
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.2008.06317
22 pages, modified the presentation
openalex publication_date 2020/08/14 · arxiv created 2021/05/16 · arxiv updated 2021/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In Exact Quantum Query model, almost all of the Boolean functions for which non-trivial query algorithms exist are symmetric in nature. The most well known techniques in this domain exploit parity decision trees, in which the parity of two bits can be obtained by a single query. Thus, exact quantum query algorithms outperforming parity decision trees are rare. In this paper we first obtain optimal exact quantum query algorithms (Qalgo(f)) for a direct sum based class of Ω( 2(√(n))/(2) ) non-symmetric functions. We construct these algorithms by analyzing the algebraic normal form together with a novel untangling strategy. Next we obtain the generalized parity decision tree complexity (D⊕(f)) analysing the Walsh Spectrum. Finally, we show that query complexity of Qalgo is \lceil (3n)/(4) \rceil whereas D⊕(f) varies between n-1 and \lceil (3n)/(4) \rceil+1 for different classes, underlining linear separation between the two measures in many cases. To the best of our knowledge, this is the first family of algorithms beyond generalized parity (and thus parity) for a large class of non-symmetric functions. We also implement these techniques for a larger (doubly exponential in (n)/(4)) class of Maiorana-McFarland type functions, but could only obtain partial results using similar algorithmic techniques.