Quantum adversary lower bound for element distinctness with small range

DOI10.4086/CJTCS.2014.004MaRDI QIDQ3191147zbMATH OpenOpenAlexFDO

Authors Ansis Rosmanis

Publication date 24 September 2014

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

quantum query complexityelement distinctnessadversary bound

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Recommendations

• scientific article; zbMATH DE number 5899233
• Quantum lower bound for the collision problem with small range
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum lower bounds by quantum arguments
• Quantum lower bounds by quantum arguments

Cites work

• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• Automata, Languages and Programming
• On the Power of Quantum Computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Walk Algorithm for Element Distinctness
• Quantum lower bounds by quantum arguments
• Reflections for quantum query algorithms

Cited in

(10)

• Element distinctness revisited
• scientific article; zbMATH DE number 7651029 (Why is no real title available?)
• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• Automata, Languages and Programming
• Quantum lower bound for the collision problem with small range
• The decision-tree complexity of element distinctness
• The quantum adversary method and classical formula size power bounds
• Quantum complexity for vector domination problem
• Optimal deterministic quantum algorithm for the promised element distinctness problem
• Adversary lower bound for the k-sum problem

This page was built for publication: Quantum adversary lower bound for element distinctness with small range

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