3
$\begingroup$

It has been proven that adiabatic quantum computing is equivalent to "standard", or gate-model quantum computing. Adiabatic computing, however, shows promises for optimisation problems, where the objective is to minimise (or maximise) a function which is in some way related to the problem – that is, finding the instance that minimises (or maximises) this function immediately solves the problem.

Now, it seems to me that Grover's algorithm can essentially do the same: by searching over the solution space, it will find one solution (possibly out of many solutions) that satisfies the oracle criterion, which in this case equates to the optimality condition, in time $O(\sqrt N)$, where $N$ is the size of the solution space.

This algorithm has been shown to be optimal: as Bennett et al. (1997) put it, "the class $\rm NP$ cannot be solved on a quantum Turing machine in time $o(2^{n/2})$". In my understanding, this means there is no way to construct any quantum algorithm that finds a solution by searching through the space faster than $O(\sqrt N)$, where $N$ scales with the problem size.

So my question is: while adiabatic quantum computing is often presented as being superior when it comes to optimisation problems, can it really be faster than $O(\sqrt N)$? If yes, this seems to contradict the optimality of Grover's algorithm, since any adiabatic algorithm can be simulated by a quantum circuit. If not, what is the point of developing adiabatic algorithms, if they are never going to be faster than something we can systematically construct with circuits? Or is there something wrong with my understanding?

$\endgroup$
  • 1
    $\begingroup$ This may be more suitable on quantumcomputing.stackexchange.com $\endgroup$ – user191954 Jun 15 '18 at 2:46
  • 1
    $\begingroup$ Grover's algorithm is optimal for a specific kind of search problems, and adiabatic computing cannot do better for that kind of search problem. But Grover's algorithm isn't known to be optimal for all optimization problems. $\endgroup$ – Peter Shor Jun 16 '18 at 1:47
  • $\begingroup$ Grover's algorithm is the 'most universal' optimization algorithm since it uses the minimal structural information. In fact for general optimization problem, we posses more information, which can be explored to accelerate the optimization. As a kind of universal QC, adiabatic QC can do better on those optimization problems than Grover's algorithm. $\endgroup$ – XXDD Sep 28 '18 at 15:13

Your Answer

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

Browse other questions tagged or ask your own question.