Could finding Golomb rulers be in $\mathrm{BQP}$?

Question

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?

Answer 1

Here's a theorem that gives a nice, elegant (yet not optimal in the ruler sense) algorithm that can run on any computer (classical, quantum, basically any turing complete system):

Theorem : For any $n\in \mathbb N^*$, and for a fixed $c\in\{1,2\}$, the sequence $cnk^2+k,\ k\in[n-1]$ forms a Golomb ruler.

Proof : For $c=2$, we start with $$2n(x^2+y^2)+(x+y)=a.$$ Given that $0\le\frac{x+y}{2n}<1$, we get $$x^2+y^2=\lfloor a/2n\rfloor.$$ Thus $$x+y=a-2n\lfloor a/2n\rfloor=a\ \mathrm{mod}\ 2n$$ and $$xy=\frac12\{(x+y)^2-(x^2+y^2)\}=\frac12\{(a\ \mathrm{mod} \ 2n)^2-\lfloor a/2n\rfloor\}.$$

The last 2 equations show that ${x,y}$ are the two roots of a polynomial of degree 2, hence determined in at most one way.

For $c=1$, we start with $$n(x^2-y^2)+(x-y)=a,\ x<y$$ and since $0\le x-y<n$, it follows that $$x^2-y^2=\lfloor a/n\rfloor.$$ Then $$x-y=a-n\lfloor a/n\rfloor=a\ \mathrm{mod}\ n.$$ Dividing the above two equations, we get $$x+y=\frac{\lfloor a/n\rfloor}{a\ \mathrm{mod}\ n}.$$

The last 2 equations form a system of 2 equations with 2 unknowns and hence uniquely define $\{x,y\}$. This completes the proof.

This algorithm can generate the sequence in $\mathcal O(n)$ time. I believe that a quantum algorithm using this will run on the same time since this is a deterministic algorithm.