Publication:4640297: Difference between revisions
From MaRDI portal
Publication:4640297
Created automatically from import240129110113 |
EloiFerrer (talk | contribs) m EloiFerrer moved page Separations in Query Complexity Based on Pointer Functions to Separations in Query Complexity Based on Pointer Functions: Duplicate |
(No difference)
|
Latest revision as of 16:07, 2 May 2024
DOI10.1145/3106234zbMath1426.68109arXiv1506.04719OpenAlexW2752597570MaRDI QIDQ4640297
Troy Lee, Miklos Santha, J. Smotrovs, Kaspars Balodis, Aleksandrs Belovs, Andris Ambainis
Publication date: 17 May 2018
Published in: Journal of the ACM, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.04719
Monte Carloquantum algorithmsdeterministic algorithmsdecision treesrandomized algorithmsLas Vegasquery complexity
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Time-Space Complexity Advantages for Quantum Computing, Deterministic Communication vs. Partition Number, Beyond quadratic speedups in quantum attacks on symmetric schemes, Optimal separation in exact query complexities for Simon's problem, Optimal parallel quantum query algorithms, Around the log-rank conjecture, An exact quantum algorithm for a restricted subtraction game, Lifting query complexity to time-space complexity for two-way finite automata, Parity decision tree in classical-quantum separations for certain classes of Boolean functions, Query-to-Communication Lifting for BPP, A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$, Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$, Unnamed Item, Separation Between Deterministic and Randomized Query Complexity, Revisiting Deutsch-Jozsa algorithm, Quantum Query Algorithms are Completely Bounded Forms., Quantum Query Algorithms Are Completely Bounded Forms, A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function, Quantum algorithms on Walsh transform and Hamming distance for Boolean functions, Unnamed Item, Unnamed Item, Extended learning graphs for triangle finding, Query complexity of generalized Simon's problem, Equality alone does not simulate randomness, Evaluation of exact quantum query complexities by semidefinite programming