Pith. sign in

REVIEW 4 cited by

Quantum Algorithm for the Collision Problem

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv quant-ph/9705002 v1 pith:HC4ZGZUM submitted 1997-05-01 quant-ph

Gilles Brassard (1) , Peter Hoyer (2) , Alain Tapp (1) ((1) Universite de Montreal , (2) Odense University) This is my paper · ORCID
classification quant-ph
keywords algorithmquantumfunctionfunctionsgiveallowingapproacharbitrary
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

In this note, we give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O((N/r)^(1/3)) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

    quant-ph 2025-10 conditional novelty 6.0 of 10

    Using two-level amplitude amplification over random-product-code center points, 3-tuple lattice sieving runs in quantum time 2^{0.2846d} with memory 2^{0.1887d}, improving the previous 2^{0.3098d}.

  2. Quantum Attacks Targeting Nuclear Power Plants: Threat Analysis, Defense and Mitigation Strategies

    cs.CR 2026-02 reject novelty 5.0 of 10

    A threat analysis claims quantum 'harvest now, decrypt later' attacks on nuclear OT systems succeed 8-78% of the time under current defenses, falling below 1% after full PQC migration.

  3. Future-Proofing Cloud Security Against Quantum Attacks: Risk, Transition, and Mitigation Strategies

    cs.CR 2025-09 unverdicted novelty 4.0 of 10

    This survey analyzes quantum vulnerabilities in cloud computing and provides a structured framework for transitioning to post-quantum cryptography with risk assessments and deployment roadmaps.

  4. Cybersecurity in the Quantum Era: Assessing the Impact of Quantum Computing on Infrastructure

    cs.CR 2024-04 unverdicted novelty 2.0 of 10

    The paper assesses quantum computing threats to cybersecurity across infrastructure layers and proposes a nine-component blueprint for quantum-resistant defenses.

Pith tools