Superlinear advantage for exact quantum algorithms

DOI10.1145/2488608.2488721zbMath1293.68124arXiv1211.0721OpenAlexW2159430156WikidataQ130923897 ScholiaQ130923897MaRDI QIDQ5495861

Andris Ambainis

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityquantum algorithmsquantum computingconcrete complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (8)

Time-Space Complexity Advantages for Quantum Computing ⋮ Optimal separation in exact query complexities for Simon's problem ⋮ From Quantum Query Complexity to State Complexity ⋮ Parity decision tree in classical-quantum separations for certain classes of Boolean functions ⋮ Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$ ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ On exact quantum query complexity

This page was built for publication: Superlinear advantage for exact quantum algorithms