USC Researchers Sharpen The Quantum Limit For Collision Search

A team of computer scientists has established a far stronger limit on how efficiently quantum computers can solve collision finding, one of the workhorse problems behind cryptography and large-scale data analysis. In a paper posted to arXiv on 9 July 2026, they prove a one-way quantum communication lower bound of N to the power of one-fourth, sharpening the previous best bound of N to the power of one-twelfth. The jump closes the gap between what had been demonstrated and what theory said should be possible.

A Sharper Limit On Collision Finding

Collision finding asks how much communication or memory a protocol needs to locate two inputs that map to the same value, the same question that sits underneath hash functions and the birthday attack in cryptography. The earlier record, an N to the power of one-twelfth bound proved by Göös and Jain at RANDOM 2022, left a wide margin between the proven hardness of the problem and what researchers believed to be true. No stronger bound was known even when the protocol was restricted to a single one-way message.

The new N to the power of one-fourth bound is tight in the relevant regime, meaning it matches the birthday-paradox upper bound rather than simply improving on the previous figure. Because the exponent climbs from one-twelfth to one-fourth, the guaranteed hardness of the problem rises steeply, and for the first time the quantum limit lines up with the classical intuition the birthday paradox already supplies. A lower bound of this kind is a promise that no cleverer quantum protocol can do better, which makes it a firmer benchmark for anyone reasoning about hash-based security or measuring real quantum search routines against the ideal.

Why Search Problems Resisted The Usual Tools

Standard techniques for proving quantum lower bounds, such as norm and rank methods, work well for decision problems that have a single correct answer. Search problems break that assumption, because a valid solution can be any one of a large set of outputs, and that multiplicity had stalled progress for years. The central contribution here is a method built on matrix discrepancy that bounds the output measurements of a quantum protocol jointly rather than one at a time.

In practice the authors recast the receiver’s success condition as packing constraints on positive semidefinite operators, then analyse the receiver’s quantum strategy directly through positive operator-valued measures. The discrepancy bounds themselves come from noncommutative Khintchine inequalities and matrix concentration estimates, tools more at home in random matrix theory than in communication complexity. Crucially the approach sidesteps the Boolean-Hidden-Matching reduction that earlier work leaned on, a shortcut that falls apart once the protocol is quantum.

A Second Result In Graph Streaming

The same machinery yields a separate bound for triangle finding, the task of spotting three mutually connected vertices in a graph that arrives as a stream of edges. For graphs with m edges and roughly m triangles, the team proves a one-pass quantum streaming space lower bound of the square root of Δ_V, where Δ_V is the largest number of triangles meeting at any single vertex and the condition 1 ≤ Δ_V ≤ m to the power of two-thirds holds. This is the first nontrivial quantum space lower bound in that regime, and it matches the classical upper bound of Jayaram and Kallaugher from RANDOM 2021 up to logarithmic factors.

As a byproduct the method reproduces an earlier classical lower bound due to Kallaugher and Price from SODA 2017, arriving at it by an entirely different route. Triangle counting underpins a range of network-analysis and data-mining workloads, so a firm limit on the memory a streaming algorithm needs carries weight well beyond the theory. Taken together, the two results hint that matrix discrepancy could become a general instrument for pinning down the cost of quantum search rather than a one-off trick.

The work was supported by an NSF CAREER award, number 2141536, and the paper is credited to Minbo Gao, Chenghua Liu, Guangxu Yang of the University of Southern California, and Tianyi Zhang. Whether the technique extends cleanly to other search problems with many valid outputs is left open, but the authors frame it as a reusable toolkit. For a field that has long found search harder to analyse than decision, that is the more consequential claim.