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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Jan 1, 2016 at 3:48

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Love simple proofs like this. $\endgroup$
    – CR Drost
    Commented Dec 31, 2015 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 ♦
    Commented Dec 31, 2015 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
    Commented Dec 31, 2015 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
    Commented Jan 3, 2016 at 8:51

Your Answer

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

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