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

В нашем мире нет недостатка в сложных сетях — от сотовых сетей в биологии до сложных веб-сетей в технологиях. Эти сети также составляют основу различных приложений практически во всех областях науки, и для анализа и управления этими сетями требуются специальные алгоритмы «поиска». Но обычные алгоритмы поиска медленны и при работе с большими сетями требуют длительного времени вычислений. Недавно было обнаружено, что алгоритмы поиска, основанные на принципах квантовой механики, значительно превосходят классические подходы. Одним из таких примеров является алгоритм «квантового обхода», который можно использовать для поиска определенной точки или «вершины» на заданном N-узловом графе. Вместо того, чтобы просто проходить через соседние вершины, подход квантового блуждания использует вероятностные оценки, основанные на квантовой теории, что резко сокращает количество шагов, необходимых для нахождения цели. Для этого перед переходом от одной точки к другой необходимо многократно выполнить операцию, называемую «вызов оракула», чтобы скорректировать значения вероятности в представлении квантовой системы. Одна из основных проблем — понять взаимосвязь между оптимальным временем вычисления вызова оракула и структурой сети, поскольку эта взаимосвязь хорошо понятна для стандартных форм и тел, но остается неясной для сложных сетей.

В новом исследовании, опубликованном в Physical Review A , группа ученых из Токийского научного университета под руководством профессора Тетсуро Никуни глубже вникла в хитросплетения этих сетей, пытаясь разработать больше эффективные квантовые алгоритмы. Профессор Никуни объясняет: «Многие системы реального мира, такие как Всемирная паутина и социальные / биологические сети, обладают сложной структурой. Чтобы полностью изучить потенциал этих сетевых систем, разработка эффективного алгоритма поиска имеет решающее значение».

Для начала ученые изучили «фрактальные свойства» (геометрические свойства фигур, которые, кажется, бесконечно повторяют их общую форму) сетей. Исследователи сосредоточились на некоторых основных фрактальных решетках (структурах с фрактальной сетью), таких как «прокладка Серпинского», «тетраэдр Серпинского» и «ковер Серпинского», чтобы попытаться выяснить взаимосвязь между количеством вершин (узлов сеть) и оптимальное время вычислений при поиске квантового блуждания. С этой целью они выполнили численное моделирование с более чем миллионом вершин и проверили, соответствуют ли результаты предыдущим исследованиям, которые предлагали математический закон или «закон масштабирования» для объяснения этой взаимосвязи.

Исследователи обнаружили, что закон масштабирования для некоторых фрактальных решеток варьируется в зависимости от их спектральной размерности, что подтверждает предыдущую гипотезу для других решеток. Удивительно, но они даже обнаружили, что закон масштабирования для другого типа фрактальной решетки зависит от комбинации ее внутренних характеристик, снова показывая, что предыдущая гипотеза об оптимальном количестве вызовов оракула может быть верной. Профессор Никуни говорит: «Это действительно может быть факт, что квантовый пространственный поиск на фрактальных решетках удивительно зависит от комбинаций характерных величин фрактальной геометрии. Остается открытым вопрос, почему закон масштабирования для количества вызовов оракулов дается такими комбинациями «. Понимая это, команда даже предложила новую гипотезу масштабирования, которая немного отличается от ранее предложенных, чтобы лучше понять различные фрактальные геометрии сетей.

Исследовательская группа надеется, что с их выводами квантовые поиски станет легче анализировать экспериментально, особенно с недавними экспериментами по квантовым блужданиям в физических системах, таких как оптические решетки. Широкая применимость квантовых алгоритмов на фрактальных решетках подчеркивает важность этого исследования. Благодаря своим захватывающим открытиям это исследование было даже выбрано как «предложение редактора» в февральском выпуске журнала Physical Review A за 2020 год. С оптимизмом оценивая результаты и изложенные направления будущих исследований, профессор Никуни заключает: «Мы надеемся, что наше исследование будет способствовать дальнейшему междисциплинарному изучению сложных сетей, математики и квантовой механики на фрактальной геометрии».