# Finding the second smallest number. Is it achievable in QC?

I have a set of numbers in a superposition state (example: 3,8,1,5) in a quantum register (of 3 qubits).

So I try to find the $$n^{\text{th}}$$ smallest number (example the $$2^{\text{nd}}$$ is 3).

I started by exploring the algorithm of Durr-Hoyer for finding the minimum, but I do not really see a way out, because I have to do a measurement to find the 1st minimum and other difficulties such as amplitudes changed by Grover algorithm

Can anyone help by telling me if it's possible to perform this computation in QC? And outline the procedure to follow to achieve it.

N.B: In Qiskit, I initialize the register with the function: initialization with the desired state, setting the amplitudes of other states (0,2,4,7) to 0.

• Would you be interested in approaches where you have multiple identical copies of that same superposition state? – Niel de Beaudrap Mar 8 '19 at 9:15
• Yes, it interests me, I can consider using as many quantum registers in input as the number n for example 3 registers that contain identical copies of the same state to find the 3rd smallest number. – rabah Mar 11 '19 at 15:44

I don't think that's possible: Suppose your initial state is $$\vert \phi\rangle$$. Let $$\vert \psi\rangle$$ be a state with the numbers $$1,4,8,13$$ in superposition. Then $$\langle \psi \vert \phi\rangle\neq 0$$, since the states have $$8$$ and $$13$$ in common. But if we have some sort of $$n$$th minimum circuit $$U_n$$ with $$U_2\vert \phi\rangle\vert 0\rangle=\vert\phi\rangle\vert 3\rangle$$ and $$U_2\vert \psi\rangle\vert 0\rangle=\vert \psi\rangle\vert 4\rangle$$, the outputs are orthogonal. This is impossible if $$U_2$$ is a unitary.

I'm not sure exactly what you had in mind (a circuit, a channel,...?). In the most generality I can think of: Suppose $$\vert \phi\rangle$$ and $$\vert\psi\rangle$$ are uniform superpositions of the numbers $$\{1,3,8,13\}$$ and $$\{1,4,8,13\}$$, respectively. Then the fidelity between them is 0.75. Suppose we have some quantum channel $$\Phi$$ that is supposed to select the 2nd smallest element. We know the fidelity between $$\Phi(\vert \phi\rangle\langle\phi\vert)$$ and $$\Phi(\vert \psi\rangle\langle\psi\vert)$$ is at least 0.75 because channels increase fidelity. (I think) This implies that if the probability of measuring 3 in the first state is $$p$$, then the probability of measuring 3 in the second state is at least $$0.75p$$. So if we have a high probability of measuring 3 in the first state (which we should) then we also have a high probability of measuring 3 in the second state (which we should not).

Note that there is a big difference between what you asked, and the problem of finding the $$n$$th minimum given the state $$\vert a_1\rangle\vert a_2\rangle\cdots \vert a_N\rangle$$. In this case, if any of the numbers $$a_1,\cdots, a_N$$ are different, the states are orthogonal. The paper you linked provides a method to solve the problem in this case.

Sam Jaques' first paragraph is a very good explanation of why what you want to do is impossible.

I just wanted to add that your question seems to be implying that you can start with a state such as $$(|1\rangle+|3\rangle+|5\rangle+|8\rangle)/2$$ and return the minimum using the Durr-Hoyer paper that you cite. This is not the case either, by the same argument. The Durr-Hoyer algorithm simply doesn't apply to your setting. They use what is essentially a database function $$f(n)$$ where, in your case, $$f(0)=3, f(1)=8, f(2)=1, f(3)=5$$. They do not start with the state you're talking about, and they access their database function many times. If you did have their setting, you should be able to adapt it to find the 2nd smallest.

• If you have a unitary preparation scheme of the superposition, then I guess it should be possible to implement Durr-Hoyer. All they seem to require is the ability to implement reflections around the superposition (basically to implement Grover search). – smapers Mar 8 '19 at 10:38
• @smapers But I don't think that having the superposition is sufficient to let you perform reflections about the state! – DaftWullie Mar 8 '19 at 10:45
• 1) I mentioned having a "unitary preparation scheme", rather than just having copies. If $|\psi\rangle = U |0\rangle$ then one can implement the reflection by effectively reflecting around the initial state and implementing $U$ and $U^\dagger$: $2|\psi\rangle\langle\psi|-I = U(2|0\rangle\langle 0|-I)U^\dagger$. 2) However, as I come to think of it, this work by Kimmel et al actually provides an algorithm for reflecting around an unknown state, simply given copies of that state. So maybe it is possible after all :) – smapers Mar 8 '19 at 12:36
• In this paper, page 19, the author uses the Durr-Hoyer algorithm to find the minimum without using the index, I try to adapt it but I don't see how :( – rabah Mar 11 '19 at 15:53
• @rabah First, find the minimum. Then repeat the whole procedure, but instead of marking all states below the threshold value, only mark them if they are also larger than the smallest value. (The determination of threshold values the second time is probably much more efficient because I imagine you have some useful information from the minimum finding run). – DaftWullie Mar 11 '19 at 16:28