| 0 |
|
В нашем мире нет недостатка в сложных сетях - от клеточных сетей в биологии до сложных веб-сетей в технологиях. Эти сети также составляют основу различных приложений практически во всех областях науки, и для анализа и манипулирования такими сетями требуются специальные «поисковые» алгоритмы. Но обычные алгоритмы поиска работают медленно и при работе с большими сетями требуют длительного вычислительного времени. Недавно были найдены алгоритмы поиска, основанные на принципах квантовой механики, которые значительно превосходят классические подходы. Одним из таких примеров является алгоритм «квантового блуждания», который можно использовать для поиска конкретной точки или «вершины» на заданном графе с N вершинами. Вместо того, чтобы просто проходить через соседние вершины, подход квантового блуждания использует вероятностные оценки, основанные на квантово-механической теории, что резко сокращает количество шагов, необходимых для нахождения цели. Чтобы достичь этого, прежде чем переходить из одной точки в другую, необходимо повторно выполнить операцию, называемую «вызов оракула», чтобы скорректировать значения вероятности в представлении квантовой системы. Одна из основных проблем состоит в том, чтобы понять взаимосвязь между оптимальным временем вычислений вызова оракула и структурой сети, поскольку эта связь хорошо понятна для стандартных форм и тел, но остается сложной для сложных сетей.
В новом исследовании, опубликованном в Physical Review A, группа ученых из Токийского университета науки, возглавляемая профессором Тетсуро Никуни (Tetsuro Nikuni), углубилась в тонкости этих сетей, пытаясь разработать более эффективные квантовые алгоритмы. Проф. Никуни объясняет: «Многие системы реального мира, такие как Всемирная паутина и социальные / биологические сети, демонстрируют сложные структуры. Чтобы полностью изучить потенциал этих сетевых систем, разработка эффективного алгоритма поиска имеет решающее значение».
Для начала ученые изучили «фрактальные свойства» (геометрические свойства фигур, которые, кажется, бесконечно повторяют их общую форму) сетей. Исследователи сосредоточились на некоторых основных фрактальных решетках (структурах с фрактальной сеткой), таких как «треугольник Серпинского», «тетраэдр Серпинского» и «ковер Серпинского», чтобы попытаться выяснить взаимосвязь между числом вершин (узлов сети) и оптимальным временем вычислений в поиске квантового блуждания. С этой целью они выполнили численное моделирование с более чем миллионом вершин и проверили, соответствуют ли результаты предыдущим исследованиям, которые предложили математический закон или «закон масштабирования», чтобы объяснить эту связь.
Исследователи обнаружили, что закон масштабирования для некоторых фрактальных решеток варьируется в зависимости от их спектральной размерности, подтверждая предыдущую гипотезу для других решеток. Удивительно, но они даже обнаружили, что закон масштабирования для другого типа фрактальной решетки зависит от комбинации ее внутренних характеристик, снова показывая, что предыдущая гипотеза об оптимальном числе вызовов оракула могла бы быть точной. Проф. Никуни говорит: «Действительно, может быть фактом, что квантовый пространственный поиск на фрактальных решетках неожиданно подвержен сочетаниям характерных величин геометрии фрактала. Остается открытым вопрос, почему закон масштабирования для числа вызовов оракула дается такими комбинациями». С этим пониманием, команда даже предложила новую гипотезу масштабирования, которая немного отличается от предложенной ранее, чтобы лучше понять различные фрактальные геометрии сетей.
Исследовательская группа надеется, что благодаря своим открытиям квантовый поиск станет легче анализировать экспериментально - особенно с недавними экспериментами, проводящими квантовые блуждания по физическим системам, таким как оптические решетки. Широкое применение квантовых алгоритмов на фрактальных решетках подчеркивает важность этого исследования. Ввиду своих впечатляющих результатов, это исследование было даже выбрано в качестве «предложения редактора» в выпуске «Physical Review A» за февраль 2020 года. Оптимистично оценивая результаты и с учетом будущих направлений исследований, профессор Никуни заключает: «Мы надеемся, что наше исследование будет способствовать дальнейшему междисциплинарное исследование сложных сетей, математики и квантовой механики на фрактальных геометриях».
Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365
| 0 |
|
