Структуры данных неожиданным образом влияют на скорость квантового поиска

Используя квантовое свойство суперпозиции, квантовые компьютеры способны находить цели среди больших объемов данных намного быстрее, чем обычные компьютеры.

При этом скорость поиска зависит от структуры данных.

Подобный поиск производится, когда квантовая частица прыгает с одного узла связанного набора данных к другому. Как подсказывает интуиция, поиск будет наиболее быстрым в наиболее высоко связанной базе данных.

«Представьте, что нужно найти определенное кафе в городе. Скорость поиска может зависеть от градостроительной схемы и расположения кафе в городе. Можно представить, что чем выше межгородские связи, тем легче по нему перемещаться и проще найти кафе», отметил один из авторов нового анализа скоростного поиска по базам данных с разными структурами и степенями связности Том Вонг.

В работе, опубликованной в издании Physical Review Letters, профессор математики Дэвид Майер из Калифорнийского университета в Сан-Диего показал, что эта логика не подходит для квантовых компьютеров.

«Мы перевернули интуицию с ног на голову», сказал Вонг. „Квантовый мир намного более разнообразен, чем мы можем себе представить. На примере поиска с квантовой частицей мы показали возможность быстрого поиска в городе с низкой связностью и медленного поиска в городе с высокой связностью“.

Ссылка по теме: http://ucsdnews.ucsd.edu/pressrelease/data_structures_influence_speed_of_quantum_search_in_unexpected_ways

18.03.2015