4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ May 25, 2020 at 18:57
  • $\begingroup$ General rulers! Thanks! $\endgroup$ May 25, 2020 at 19:40

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ May 25, 2020 at 21:19
  • $\begingroup$ 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? $\endgroup$ May 25, 2020 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.