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

DOI10.1007/S11128-021-03158-1OpenAlexW3175571597MaRDI QIDQ2690505

Chandra Sekhar Mukherjee, Subhamoy Maitra

Publication date: 17 March 2023

Published in: Quantum Information Processing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11128-021-03158-1

zbMATH Keywords

Boolean functionsbent functionsquery complexityparity decision treeclassical-quantum separationquery friendly functions

Mathematics Subject Classification ID

Quantum computation (81P68) Boolean functions (06E30) Boolean functions (94D10) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity measures and decision tree complexity: a survey.
• On exact quantum query complexity
• Exponential separation of quantum and classical communication complexity
• Forrelation
• Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
• Deterministic Communication vs. Partition Number
• Separations in Query Complexity Based on Pointer Functions
• Quantum lower bounds by polynomials
• Superlinear advantage for exact quantum algorithms

This page was built for publication: Parity decision tree in classical-quantum separations for certain classes of Boolean functions