Tunneling in quantum search: an Emerging Talents Lab Talk with Thomas Wong

By Phil Brown on April 4, 2017

In his recently published Emerging Talents paper in Journal of Physics A: Mathematical and Theoretical Thomas Wong investigates a Quantum walk search through potential barriers. Thomas spoke to JPhys+ to explain more about the world of tunneling in quantum search.

Quantum particles are known to tunnel through energy barriers. Despite this, we show in our recent paper that such barriers can have a devastating affect on a quantum computer’s ability to search an unordered database or all-to-all network, unless the barriers are corrected for. Quantum computers are known to outperform classical computers at several tasks. One example is searching an unordered database of N items, for which a classical computer takes O(N) steps while a quantum computer using Grover’s famous algorithm takes O(√N) steps – a quadratic speedup. One way to understand this is using random walks and their quantum analogues, quantum walks. In this setting, the unordered database corresponds to an all-to-all network, as illustrated below.

An all-to-all network of N = 6 nodes. We are searching for the red node labeled a.

If we randomly jump from node to node, we expect to take O(N) jumps to find the correct node. In contrast, a quantum walk only takes O(√N) steps to have a probability of 1/2 of finding the correct answer, as shown in the next figure.

A plot of the success probability for searching a database of N = 1024 entries as the quantum walk evolves. The
solid black curve is with no barriers, and the dashed red and dotted green curves are with increasing barriers. Figure from Thomas G Wong 2016 J. Phys. A: Math. Theor. 49 484002 © 2016 IOP Publishing Ltd.

Now say there are energy barriers between the nodes. The quantum particle must tunnel through these barriers in order to hop. We show that this has a significant, negative affect on the search. In the above figure, as we increase the strength of the barriers (the red and green curves), the success of the search drops. In particular, we prove that the probability of the particle failing to tunnel must go to zero at least as fast as O(1/N), otherwise it is no better than a classical computer. This means searching larger databases requires increasingly reliable hops. Not to be deterred, in subsequent work with Andris Ambainis, we proved that the errors can be corrected for, allowing the quantum computer to again search in O(√N) steps. This correction is specific to searching problems, however, so the affect of energy barriers in other settings and whether they can be corrected is a topic of future research.

This paper was originally reported in J. Phys. A: Math. Theor. 49, 484002.

Dr. Thomas Wong

About the Author

Tom Wong is a postdoctoral research fellow at the University of Texas at Austin under Scott Aaronson. He was previously a visiting research scientist at the University of Latvia under Andris Ambainis. This summer, he transitions to Creighton University as an Assistant Professor of Physics.

Read More:

This work is licensed under a Creative Commons Attribution 3.0 Unported License.