4551
правка
Квантовый алгоритм поиска треугольников: различия между версиями
Материал из WEGA
Квантовый алгоритм поиска треугольников (посмотреть исходный код)
Версия от 23:23, 6 апреля 2016
, 6 апреля 2016→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 82: | Строка 82: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Наиболее очевидный из открытых вопросов касается решения проблемы сложности квантовых запросов при поиске треугольников; на данный момент лучшими верхней и нижней границей являются O( | Наиболее очевидный из открытых вопросов касается решения проблемы сложности квантовых запросов при поиске треугольников; на данный момент лучшими верхней и нижней границей являются '''O(n^{13/10}) \;''' и <math>\Omega(n) \;</math>. Кроме того, остаются нерешенными следующие задачи: | ||
Сложность квантовых запросов при поиске монотонных свойств графов | '''Сложность квантовых запросов при поиске монотонных свойств графов''' | ||
Наилучшая известная нижняя граница сложности квантовых запросов для (нетривиальных) монотонных свойств графов, составляющая | Наилучшая известная нижняя граница сложности квантовых запросов для (нетривиальных) монотонных свойств графов, составляющая <math>\Omega(n^{2/3} \; log^{1/6} \; n)</math> и полученная Эндрю Яо, следует из нижней границы <math>\Omega(n^{4/3} \; log^{1/3} \; n)</math> классического рандомизированного алгоритма Чакрабарти и Хота [8] и техники квантового противопоставления Амбайниса [2]. Возможно ли улучшить границу <math>\Omega(n) \;</math>? Если возможно, она будет достаточно близкой, поскольку для того, чтобы определить при помощи алгоритма Гровера, является ли множество ребер графа непустым, требуется <math>O(n) \;</math> квантовых запросов. | ||
Новые алгоритмы с применением квантового блуждания | '''Новые алгоритмы с применением квантового блуждания''' | ||
Технология квантового блуждания успешно применялась при разработке более эффективных алгоритмов квантового поиска для нескольких задач – таких как различение элементов [3], поиск треугольников [13], верификация матричного произведения [7] и проверка коммутативности групп [11]. Было бы любопытно узнать, как подход на основе квантового блуждания может быть расширен для получения новых и улучшенных квантовых алгоритмов для решения различных вычислительных задач. | |||
== См. также == | == См. также == | ||
