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
communication complexityquery complexityFourier analysis of Boolean functionsforrelationFourier weight of decision treesquantum-classical separations
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
