Talk:Quantum walk search

Classical problem description

In this section, how do we define a "good probability"? Should there be a thecnical definition? Fpeverelli (talk) 13:44, 7 July 2023 (UTC)

maybe "probability close to 1" is more appropriate. Thanks for the suggestion Serie$dollaro (talk) 14:38, 7 July 2023 (UTC)

Overview

The article is well written and well-documented. The topic is very specific and it is aimed at a technical audience, but the intro does a good job of providing an understanding of the algorithm. Fpeverelli (talk) 13:52, 7 July 2023 (UTC)

I have the same opinion as you. It is a very valuable article, since it is about a very trending and notable topic and it provides a strong technical background. TarkusTheTediousTaciturn (talk) 14:00, 7 July 2023 (UTC)

I think the same as well. A comprehensive article, easy to understand and follow even by the layman on the topic! Isawisa (talk) 14:09, 7 July 2023 (UTC)

Observations and suggestions for improvements

The following observations and suggestions for improvements were collected, following an expert review of the article within the Science, Technology, Society and Wikipedia course at the Politecnico di Milano, in July 2023.

"I find the article fairly clear and complete. It is good as an introduction to the subject, which is what a Wikipedia article should be about. I must confess that I am not very familiar with the topic. Nonetheless, I can offer a few suggestions for improvement, aiming at increasing further its rigour and clarity.

• SECTION ""Preable""

""In a classical random walk, the position of the walker can be described using a probability distribution over the different nodes of the graph"". I find this confusing. I believe that the position of a classical walker should correspond to just one node of the graphs. The probability distribution describes a ""swarm"" of walkers, or the same walker over a very long ""time"".

""quantum walk search algorithms offer an asymptotic quadratic speedup similar to that of Grover's algorithm"". What does ""speedup"" mean? Speedup with respect to what? If speedup measures the performance of a quantum versus a classical search algorith (on the same graph), this should be stated here.

• SECTION ""Classical problem description""

The meaning of ""|X|"" (within the equality |X|=n) should be declared. Is it a dimensionality of the search space? Note that, if the symbol is not used anywhere else in the article, it can probably be eliminated and replaced by plain words.

""while the edges represent the conditional probability..."". I suggest writing ""while the edges E represent the conditional probabilities..."" (so as to define the symbol E, that appears one line above). A few lines below, the symbol P is for the stochastic matrix (or its elements). Is this P distinct or the same as E, above? If they are the same, one should use the same symbol.

• SECTION ""Algorithm description""

""The quantum walk search algorithm was first proposed by Magniez et al.[7] , also known as MNRS algorithm, and is based on the quantum walk formulation proposed by Mario Szegedy"". Add the appropriate reference to the work by Szegedy. Also, if possible, explain the relationship between this work and ref. [5] (declared in the preamble as ""one of the first works on the application of quantum walk to search problems"").

In the inline expression for the ""uniform superposition states"", the symbol P_{ij} should be defined (see above).

In the denominator of the definition of the ""bad state"", I believe X should be |X| (so |X| should be defined, see above). Just below, ""where M is the set of marked elements"" is unnecessary, because it has already been defined.

""Since the way the algorithm finds a marked element is based ..."" could be stated more simply as ""Since the search algorithm is based..."". A few lines below, ""god state"" should be ""good state"".

In the subsection on ""Complexity"", the symbols for U, C and S should be the same throughout.

• SECTION ""Hypercube example""

The long sentence at the end (""the shoft operator ... is still an open challenge"") should be split into 2-3 sences, for clarity."

--Aandurro (talk) 12:58, 18 July 2023 (UTC)