Скачать или смотреть Min element search. Classical/Quantum comparison

Each white square represents an element of a list (some permutation of the integers from 0 to 99 999).
The classical algorithm is simple: every time a new element is checked (gets blue) it is compared to the smallest element seen before (last Green circle). If the new element is smaller then it becomes the new smallest already seen (and is marked with a Green circle). When there isn't any new element to check the smallest already seen is the answer.
Time complexity: O(N)

The Quantum algorithm uses a quantum subroutine, which will be refered as G.
G(list T, int v) returns a position y such that T[ y ] is smaller than v. All positions satisfying this become gradually darker (in shades of blue) to represent a higher presence in the quantum superposition, and all of them have the same quantum amplitude, thus the same chance to be returned as well. The returned becomes a Blue circle.
The idea is simply to apply G successively using its last output to find an element smaller each time. Just repeate many times: y receives G( T , T[ y ] ).
To simplify, consider that when the T [ y ] is the smallest G( T , T[ y ] ) returns y (it becomes the yellow circle).

The Quantum algorithm is described in this paper: https://arxiv.org/abs/quant-ph/9607014 .

G has time complexity: O((N/t)^(1/2)), where t is the number of elements satisfying T[ y ] smaller than v.
Time complexity (mean): O(cN^(1/2)), error probability: (1/2)^c
Music: Libertango - Astor Piazzolla (Arr. Jacob Koller)
   • Recital de Conclusão do Curso Técnico em P...  &t=286