Quantum lower bounds for the collision and the element distinctness problems

DOI10.1145/1008731.1008735zbMath1169.68406OpenAlexW2034038586MaRDI QIDQ3498860

Yaoyun Shi, Scott Aaronson

Publication date: 17 May 2008

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsquantum algorithmcollision problemexistence of cryptographic primitives immune to quantum cryptanalysissecurity of many fundamental cryptographic primitives

Mathematics Subject Classification ID

Related Items (58)

Low-gate quantum golden collision finding ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ The quantum query complexity of the abelian hidden subgroup problem ⋮ On the black-box complexity of Sperner's Lemma ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Grover walks on a line with absorbing boundaries ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Succinct arguments in the quantum random oracle model ⋮ Optimal parallel quantum query algorithms ⋮ Deterministic quantum search with adjustable parameters: implementations and applications ⋮ Quantum Walk Based Search Algorithms ⋮ Finding many collisions via reusable quantum walks. Application to lattice sieving ⋮ On the relationship between continuous- and discrete-time quantum walk ⋮ Redeeming reset indifferentiability and applications to post-quantum security ⋮ Near-optimal quantum algorithms for string problems ⋮ One-dimensional lackadaisical quantum walks ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ On the Power of Statistical Zero Knowledge ⋮ Unnamed Item ⋮ Quantum key-length extension ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Unnamed Item ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Algorithmic Polynomials ⋮ Quantum algorithm design: techniques and applications ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ How low can approximate degree and quantum query complexity be for total Boolean functions? ⋮ On the power of non-adaptive learning graphs ⋮ Quantum vs Classical Proofs and Subset Verification ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ The hardest halfspace ⋮ Element distinctness revisited ⋮ Quantum algorithm for the multicollision problem ⋮ Polynomial degree vs. quantum query complexity ⋮ Adversary lower bounds for nonadaptive quantum algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Random Walks – New Method for Designing Quantum Algorithms ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ Квантовые атаки на итерационные блочные шифры ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets ⋮ TIGHT QUANTUM BOUNDS FOR COMPUTATIONAL GEOMETRY PROBLEMS ⋮ Key establishment à la Merkle in a quantum world ⋮ Claw finding algorithms using quantum walk ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound ⋮ On subset-resilient hash function families ⋮ Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms

This page was built for publication: Quantum lower bounds for the collision and the element distinctness problems