Квантовый алгоритм поиска треугольников: различия между версиями

Перейти к навигации Перейти к поиску
Строка 25: Строка 25:
   
   


Алгоритм с увеличением амплитуды; сложность O(n +   nm)
'''Алгоритм с увеличением амплитуды; сложность <math>O(n + \sqrt{nm} ) \;</math>'''


Поскольку в графе G имеется (") потенциальных треугольников (a, b, c), тривиальное применение алгоритма квантового поиска Гровера [10] решает задачу поиска треугольников при помощи O(n3/2) квантовых запросов. Бурман и коллеги [ ] улучшили эту верхнюю границу для специального случая, когда граф G является разреженным (т.е. m = o (n2)), при помощи следующего рассуждения.
Поскольку в графе G имеется <math>\tbinom{n}{3} \;</math> потенциальных треугольников (a, b, c), тривиальное применение алгоритма квантового поиска Гровера [10] решает задачу поиска треугольников при помощи <math>O(n^{3/2}) \;</math> квантовых запросов. Бурман и коллеги [6] улучшили эту верхнюю границу для специального случая, когда граф G является [[разреженные графы|разреженным]] (т.е. <math>m = o (n^2)) \;</math>, при помощи следующего рассуждения.




Строка 69: Строка 69:


В своей недавней работе Маньез и коллеги [ ], используя разработанную Шегеди [15] технику квантового блуждания, предложили новую процедуру поиска на основе квантового блуждания, обобщая наработки Амбайниса [ ]. Одним из вариантов ее применения стал алгоритм квантового блуждания для поиска треугольников за O(n13/10) квантовых запросов.
В своей недавней работе Маньез и коллеги [ ], используя разработанную Шегеди [15] технику квантового блуждания, предложили новую процедуру поиска на основе квантового блуждания, обобщая наработки Амбайниса [ ]. Одним из вариантов ее применения стал алгоритм квантового блуждания для поиска треугольников за O(n13/10) квантовых запросов.


== Применение ==
== Применение ==
Источник — http://pco.iis.nsk.su/wega/index.php/Квантовый_алгоритм_поиска_треугольников