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

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?

• The example you have provided is a perfect Golomb ruler (can measure $n(n-1)$ lengths where $n$ is the number of marks, and in your case is $2\cdot 3=6$). Do you want an algorithm for perfect rulers or for general rulers? Because, if you want the former, then there exist no such rulers with more than 4 marks. May 25 '20 at 18:57
• General rulers! Thanks! May 25 '20 at 19:40

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 and since $$0\le x-y, 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.

• Thanks! I guess I’m looking for the dual problem- given about $n^2$ qubits try to make about $n$ of them $1$, so as to satisfy the Golomb property. May 25 '20 at 21:19
• I am not sure I get you, although I have a vague idea what you mean. Can you provide a couple of examples to demonstrate your idea? Say with 4 and 9 qubits? May 25 '20 at 23:08