The problem of factoring large numbers may be in the so-called "intermediate" regime. These are problems that are in $\mathrm{NP}$, but are neither likely to be easy enough to be in $\mathrm{P}$ nor hard enough to be complete. Following Shor's algorithm and a general consensus that $\mathrm{NP}\not\subseteq\mathrm{BQP}$, focus quickly turned to such difficult intermediate problems, with modest success. Now, a general consensus is that $\mathrm{BQP}$ and $\mathrm{NP}$ are likely incomparable, and research focus has moved a bit to problems, such as forrelation, that are in $\mathrm{BQP}$ but are not likely even in $\mathrm{NP}$ or even in any point of the polynomial hierarchy.
Nevertheless, one problem that appears to me to be in this "intermediate" area is that of finding small Golomb rulers.
Imagine marking a 6" ruler only at the 1" position and the 4". To measure something one-inch in size, measure between the left edge and the 1" mark; to measure something two-inches in size, measure between the 4" mark and the right edge; to measure something three-inches in size, measure between the 3" mark and the 4" mark; etc. We can measure anything between one inches and six inches, with only two marks on the ruler.
Is there any hope of a quantum computer finding a large Golomb ruler? That is, of finding a string of $0$'s and $1$'s that possess the Golomb property of not having distances measurable more than once?
Here I think of having $n=O(m^2)$ qubits, and preparing them in a uniform superposition having a fixed Hamming weight of $O(m)$ ; using the $i$'th index ($i$'th qubit) of the ruler as a way to perform a controlled rotation by $e^{i/n}$ I think would assign a random phase to all vectors but those corresponding to Golomb rulers... or something
EDIT
Upon consideration, perhaps it's best to ask for a quantum algorithm for the dual problem of generating a string on $n=O(m^2)$ qubits that has the Golomb ruler property, with a Hamming weight of $n$.
For example, a solution with $m=4$ and $n=6$ is the already-described string
$$\vert 1010011\rangle;$$
or equivalently
$$\vert 1100101\rangle;$$
a solution with $m=5$ and $n=11$ is
$$\vert 110010000101\rangle;$$
etc.
For a given length (given number of qubits $n$), what's the largest Hamming weight (largest $m$) that can be created for having the Golomb property?