Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection

Kaspars Balodis, Jānis Iraids

We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quant…