4
$\begingroup$

Considering the following two phenomena:

  • Adiabatic quantum computing in general exhibits a quadratic speedup over classical simulated annealing, though for some Hamiltonians it may be faster (while for others slower). Typically, quantum tunneling is referred to as the reason for this speedup. (Mukherjee, S., Chakrabarti, B. Multivariable optimization: Quantum annealing and computation. Eur. Phys. J. Spec. Top. 224, 17–24 (2015). https://doi.org/10.1140/epjst/e2015-02339-y)

  • Quantum walks on graphs in general exhibit quadratic improved hit time over their classical counterparts, though for some nodes in some graphs this may be exponentially fast while for others it may be slower. In describing the reason behind this, authors usually refer not to tunneling but interference, pointing out that amplitudes on some graph nodes will constructively interfere while others will destructively interfere. (Kempe, J. Discrete Quantum Walks Hit Exponentially Faster. Probab. Theory Relat. Fields 133, 215–235 (2005). https://doi.org/10.1007/s00440-004-0423-2)

Are these separate phenomena, or are they two different statements of the same underlying result? I noticed (through my distinctly non-random sampling of a few papers on each) that quantum walk papers rarely mention adiabatic computation, and vice versa.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Personally, I have always found suspicious the (admittedly very common in the literature) "justification" of the quadratic speedup in AQC by the tunneling time vs thermal escape comparison. It comes from the behaviour of a one-dimensional system driven by a constant Hamiltonian, while real-life AQC has multidimensional tunneling driven by a time-dependent Hamiltonian. Moreover, I would not accept as true the statement that "AQC is believed to generically exhibit a quadratic speedup over SA". I think our understanding of the AQC vs SA asymptotic scaling in realistic problems is still lacking. $\endgroup$
    – Gianni Mossi
    Commented Apr 29, 2021 at 5:46
  • 1
    $\begingroup$ See e.g. (Section VI in particular) arxiv.org/abs/1611.04471 $\endgroup$
    – Gianni Mossi
    Commented Apr 29, 2021 at 5:50

1 Answer 1

Reset to default
2
$\begingroup$

In response to my own question, I'm thinking Aaronson stated somewhere (I can't find the reference) that the quadratic speedup of e.g. Grover search arises from the fact that probability is amplitude squared, hence linear effort spent improving the amplitude of a correct answer equates to quadratic improvement in the probability of measuring it. This underlying mechanism is obviously shared by both quantum walks and quantum annealing.

Additionally, though this is an informal guess, quantum annealing can presumably itself be analysed as a quantum walk on a graph in which we define the reachability of each node from other nodes using a potential/kinetic-energy-based formulation. Such a graph would have nodes which themselves are unreachable (because too much energy is required) but which do not block access to nodes beyond them. Tunneling would therefore be a special case of a quantum walk on a particular definition of graph.

Seen that way, both phenomena share the property that the likely hit time of certain nodes depends heavily on the structure of the graph, hence "some things happen faster, others happen slower".

Improve this answer
$\endgroup$

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.