Однако это утверждение предполагает, что частица может напрямую перепрыгивать с любого элемента на любой другой. Любое ограничение на то, к каким элементам может напрямую переходить частица, может замедлить поиск.«Интуиция говорит, что симметричная база данных позволяет частице достаточно свободно перемещаться, чтобы сохранять квантовое ускорение, но наше исследование показало, что эта интуиция ложна», — говорит Том Вонг, физик из Калифорнийского университета в Сан-Диего.
В статье, принятой к публикации Physical Review Letters, исследователи использовали знакомую физикам технику под названием «вырожденная теория возмущений» новым способом, чтобы доказать, что глобальная симметрия не требуется для ускоренного поиска.Ученые-информатики представляют базу данных для поиска в виде графика. В глобально симметричных графах узлы можно менять местами друг с другом, так что связи между ними сохраняются. «Сильно регулярные графы» не обладают этим свойством, но этот анализ показывает, что они также поддерживают быстрый поиск через локальные симметрии.
Их открытие расширяет использование этой теории в области квантовой информатики и расширяет виды структур данных, в которых квантовые вычисления превосходят классические вычисления.