Parity decision tree in classical–quantum separations for certain classes of Boolean functions

• Published in: Quantum information processing 2021-06, Vol.20 (6), Article 218
• Main Authors: Mukherjee, Chandra Sekhar, Maitra, Subhamoy
• Format: Article
• Language: English
• Subjects: Boolean; Boolean algebra; Boolean functions; Codes; Complexity; Data Structures and Information Theory; Decision analysis; Decision trees; Mathematical analysis; Mathematical Physics; Parity; Physics; Physics and Astronomy; Quantum Computing; Quantum Information Technology; Quantum Physics; Queries; Separation; Spintronics
• ISSN: 1570-0755; 1573-1332
• DOI: 10.1007/s11128-021-03158-1

In this paper, we study the separation between the deterministic (classical) query complexity ( D ) and the exact quantum query complexity ( Q E ) of several Boolean function classes using the parity decision tree method. We first define the query friendly (QF) functions on n variables as the ones with minimum deterministic query complexity D ( f ). We observe that for each n , there exists a non-separable class of QF functions such that D ( f ) = Q E ( f ) . Further, we show that for some values of n , all the QF functions are non-separable. Then, we present QF functions for certain other values of n where separation can be demonstrated, in particular, Q E ( f ) = D ( f ) - 1 . In a related effort, we also study the Maiorana–McFarland (MM)-type Bent functions. We show that while for any MM Bent function f on n variables D ( f ) = n , separation can be achieved as n 2 ≤ Q E ( f ) ≤ ⌈ 3 n 4 ⌉ . Our results highlight how different classes of Boolean functions can be analyzed for classical–quantum separation exploiting the parity decision tree method.