Quantum walks: a building block for quantum algorithms

Short answer: A quantum walk is the quantum counterpart of a classical random walk, and surveys describe it as an advanced tool for building quantum algorithms. One survey says its most promising property is that it spreads quadratically faster than a classical walk. A later review says quantum walks have been shown to be a universal model of quantum computation, which is a theoretical result about what they can express, not a statement about hardware.

What defines a quantum walk?

A quantum walk is defined as the quantum mechanical counterpart of a classical random walk. A 2012 review calls it an advanced tool for building quantum algorithms. The field distinguishes between two primary mathematical models: discrete-time and continuous-time quantum walks. The 2012 review covers coined discrete-time walks and continuous-time walks, and the connections between them.

A 2004 survey notes that quantum walks possess properties that distinguish them from their classical analogues. One key property is that a quantum walk spreads quadratically faster than its classical counterpart. The survey calls this a promising avenue for designing fast quantum algorithms.

How do quantum walks accelerate search?

The 2008 survey states that quantum walk based search algorithms are quantum analogues of classical search procedures. These algorithms include the work of Ambainis, Szegedy, and Magniez et al. They are compared to Grover search, which is a standard quantum search method. A 2008 survey describes a somewhat simplified version of the MNRS algorithm, which applies quantum walks to specific search problems.

In the query complexity model, quantum walks have been applied to problems such as Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle, and Group Commutativity. The relevance of finite Markov chains, which are classical random walks in graphs, to searching was recognized early on.

What are the algorithmic applications?

The 2004 survey says algorithms using quantum walks can be classified into two groups. The first group consists of algorithms achieving exponentially faster hitting times. In these scenarios, a known graph is used, and the process starts at one vertex. The survey describes the setting in more detail.

The second group involves quantum walk search. The same survey describes the quadratic spreading property as the most promising for algorithm design.

Is quantum walk computation universal?

The 2012 review says theoretical advances have shown that quantum walks constitute a universal model of quantum computation. This universality applies to both continuous-time and discrete-time quantum walks. The review calls this a most important result.

In principle, that means a quantum walk can express any quantum computation. The review describes the field as solid and full of exciting open problems. This universality is a theoretical result. It does not imply that current hardware can efficiently implement these universal simulations. The distinction between theoretical capability and practical implementation remains a central focus of research.

FAQ

What is a quantum walk?

The quantum mechanical counterpart of a classical random walk, according to a 2012 review. It comes in discrete-time and continuous-time forms.

What makes it useful for algorithms?

A 2004 survey says a quantum walk spreads quadratically faster than its classical counterpart, and calls this the most promising property for designing fast quantum algorithms.

What problems have quantum walks been applied to?

In the query complexity model, a survey lists Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle and Group Commutativity.

How do the algorithms group?

The 2004 survey classifies them into two groups: algorithms achieving exponentially faster hitting times, and quantum walk search.

Is a quantum walk a universal model of computation?

The 2012 review says it has been shown that both continuous-time and discrete-time quantum walks are universal for quantum computation. That is a theoretical result.