2
$\begingroup$

I am currently having hard times while facing an interesting idea, which could speed up many present quantum algorithms, but I am not sure whether my thought is not misleading, or more precisely, impossible to realize:

Would it be practicable to check in less than $\sqrt{N}$ time whether there is an element which, if evaluated by an oracle, equals some predefined value? I do not need its position as in case of Grover algorithm. Analogous to Deutsch-Josza algorithm, my first thought was to use the Hadamard gate, which would turn the superposition into a messy state in case there is an element with flipped phase (i.e. marked), otherwise put the register into its starting state.

However, after implementing this in QCL, I found out that this method does not seem to be sustainable as the probability of measuring the same state in both cases continuously increases, so the measured value cannot be regarded meaningful. Thus, the Walsh-Hadamard interference transformation is not about to be a solution to this problem, neither QFT is; it makes me ask you: Do you think there is any way to interfere the qubits so one could get considerable results or am I quite a bit mistaken?

Thanks in advance.

$\endgroup$
  • $\begingroup$ Hello, and welcome to Stack Exchange. It's not clear what you're talking about; it might help if you spent a bit of time to flesh out your ideas. $\endgroup$ – Daniel Griscom Jan 1 '16 at 3:48
7
$\begingroup$

If it were possible to identify whether a particular element existed in a list in $O(N^{\alpha})$ time, you could search for that element in $O(N^{\alpha}\log N)$ time. The method is simple. You perform a binary search, checking at each stage whether the element in present in half the list, and this eventually leads you to the element you want.

Since the fastest a quantum search algorithm can run is $O(\sqrt{N})$, there is no algorithm of the type you want that has $\alpha<1/2$.

$\endgroup$
  • $\begingroup$ Love simple proofs like this. $\endgroup$ – CR Drost Dec 31 '15 at 16:56
  • $\begingroup$ I was working on a much more awkward proof involving state vectors, when this simple argument occurred to me. $\endgroup$ – Buzz Dec 31 '15 at 17:02
  • $\begingroup$ Thanks! I had exactly the same idea about binary search where this algorithm would be its intermediate step... I knew about Grover´s optimality, however, I was somehow doubtful whether this could not break it. $\endgroup$ – JBI Dec 31 '15 at 17:11
  • 2
    $\begingroup$ @JBI About Grover's optimality, I remember there is a geometrical interpretation that to show that Grover's algorithm is a minimal length curve, a geodesic, according to a certain metric. So I think it can not be broken if the same goal to be achieved. Please check this paper "Geometric Strategy for the Optimal Quantum Search" $\endgroup$ – XXDD Jan 3 '16 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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