An optimal separation of randomized and Quantum query complexity

DOI10.1145/3406325.3451019MaRDI QIDQ6065253zbMATH OpenOpenAlexWikidataFDO

Authors Alexander A. Sherstov, Pei Wu

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3406325.3451019

zbMATH Keywords

query complexitycommunication complexityFourier analysis of Boolean functionsforrelationFourier weight of decision treesquantum-classical separations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• An Optimal Separation of Randomized and Quantum Query Complexity
• Optimal separation and strong direct sum for randomized query complexity
• Separations in query complexity using cheat sheets

Cited in

(17)

• On the fine-grained query complexity of symmetric functions
• Lifting query complexity to time-space complexity for two-way finite automata
• Optimality proofs of quantum weight decision algorithms
• The quantum setting with randomized queries for continuous problems
• Algorithms and Computation
• On the fine-grained query complexity of symmetric functions
• An Optimal Separation of Randomized and Quantum Query Complexity
• Beyond quadratic speedups in quantum attacks on symmetric schemes
• Mathematical Foundations of Computer Science 2004
• Sharp quantum versus classical query complexity separations
• The quantum query complexity of approximating the median and related statistics
• Optimal separation in exact query complexities for Simon's problem
• The power of various real-valued quantum queries
• Improved bounds on the randomized and quantum complexity of initial-value problems
• Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms
• Optimal separation and strong direct sum for randomized query complexity
• scientific article; zbMATH DE number 6667586 (Why is no real title available?)

This page was built for publication: An optimal separation of randomized and Quantum query complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065253)