An Optimal Separation of Randomized and Quantum Query Complexity

DOI10.1137/22M1468943OpenAlexW3168722382MaRDI QIDQ5890036

Pei Wu, Unnamed Author, Alexander A. Sherstov

Publication date: 28 April 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.10223

zbMATH Keywords

communication complexityquery complexityFourier analysis of Boolean functionsforrelationFourier weight of decision treesquantum-classical separations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity measures and decision tree complexity: a survey.
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Exponential separation of quantum and classical communication complexity
• Extremal Combinatorics
• Learning Monotone Decision Trees in Polynomial Time
• Quantum Property Testing
• Rapid solution of problems by quantum computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Power of Quantum Computation
• Quantum Complexity Theory
• Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
• Query-To-Communication Lifting for BPP Using Inner Product
• Entangled Simultaneity Versus Classical Interactivity in Communication Complexity
• Analysis of Boolean Functions
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Separations in query complexity using cheat sheets
• Quantum one-way communication can be exponentially stronger than classical communication
• Quantum lower bounds by polynomials
• Fourier growth of parity decision trees

This page was built for publication: An Optimal Separation of Randomized and Quantum Query Complexity