The Weirdness of Quantum Random Walks

A lot of questions came to mind when I read this bit of the article,

"If you want to find a particular item in a list with N items classically, you need to check all N items—N evaluations—because the item you are searching for could be the last in the list. (If you are sure that the item is in the list, the correct number of evaluations is N-1, but this does not matter much here.) This means searching through an unsorted database with N entries takes—classically—N steps. However, with Grover’s quantum algorithm—which can be viewed as a quantum random walk—it takes √(N) steps. It allows for the same quadric speedup as the quantum random walk. For large databases—lists with big N— this can mean a lot fewer evaluations."

As odd as quantum computers are, I couldn't figure out how you could evaluate static values in a database that were never evaluated... the answer was, it can't.

From Wikipedia (https://en.wikipedia.org/wiki/Grover%27s_algorithm) "The database is not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index. Reading a full data-base item by item and converting it into such a representation may take a lot longer than Grover's search."

In essence, you need a completely new database with quantum capable representations. Even with this trade-off, I could imagine 'big data' adapting this type of workflow once quantum computers become viable.

The distribution from the symmetric initial condition looks like a bit like a beta(.5,.5), which is the jeffreys prior for a binomial. I doubt it is but it would be interesting to me if it were.

Great essay.

An essay about how to walk in two directions at the same time