Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond

J. Mark Keil, Fraser McLeod, Debajyoti Mondal

The classical 3SUM conjecture states that the class of 3SUM-hard problems does not admit a truly subquadratic $O(n^{2-\delta })$-time algorithm, where $\delta >0$, in classical computing. The…