In handwavy technical detail: arrange that the things you're searching form a basis a1, a2, ..., aN for your state space, with your have-I-found-it test as an operator that negates the state you're looking for and maps the others to themselves. In other words, it's reflection in the hyperplane perpendicular to the state you're looking for. Now let a = a1+...+aN, and define a new operator that reflects in the hyperplane perpendicular to a. And now put your system in state a, and repeatedly apply those two operators, one after the other.
The composition of two reflections is a rotation. The angle of that rotation is known (and quite small); the angle between the two vectors (your desired state and a) is close to a right angle; by doing the rotation an appropriate number of times, you bring the system's state vector close to the desired state. Now you measure the system's state, and with high probability it's the state you're looking for.
A little calculation shows that the number of rotations needed is roughly proportional to sqrt(N), and the probability of getting the wrong state is roughly proportional to 1/N. Now do the process as many times as it takes for 1/N^k to be small enough for your satisfaction. Congratulations: you've now found what you were looking for, taking about sqrt(N) time, with error probability as small as you like.
The physorg article does have one advantage over the Nature one: it has a picture of the solid-state device.