Хури Паскаль Мишалевич — студент
Санкт-Петербург, 197101
Paskal M. Khuri — Student
Saint Petersburg, 197101
Клишева Алина Дмитриевна — студент
Санкт-Петербург, 197101
Alina D. Klisheva — Student
Saint Petersburg, 197101
Демченко Пётр Сергеевич — кандидат технических наук, директор по научной работе
sc 57194214776
Санкт-Петербург, 191167
Petr S. Demchenko — PhD, Director for Science
Saint Petersburg, 191167
Бебех (Губайдуллина) Ксения Витальевна — преподаватель, ИП
sc 57191412462/57220166837
Санкт-Петербург, 197101
Ksenia V. Bebekh (Gubaidullina) – Lecturer, IE Bebekh A.A.
sc 57191412462/57220166837
Saint Petersburg, 197101
Ходзицкий Михаил Константинович — кандидат физико-математических наук, генеральный директор
sc 16444444600
Санкт-Петербург, 191167
Mikhail K. Khodzitsky — PhD (Physics & Mathematics), Chief Executive Officer
sc 16444444600
Saint Petersburg, 191167
Возианова Анна Викторовна — кандидат физико-математических наук, исполнительный директор
sc 17436111400
Санкт-Петербург, 197101
Санкт-Петербург, 191167
Anna V. Vozianova — PhD (Physics & Mathematics), Ececutive Officer
sc 17436111400
Saint Petersburg, 197101
Saint Petersburg, 191167
Введение. Алгоритмы и структуры данных важны в информационных технологиях (в частности, в терагерцовых беспроводных коммуникациях 6G), логистике, транспорте и планировании маршрутов в медицине. Одним из основополагающих алгоритмов, который находит применение во многих практических задачах, является алгоритм поиска кратчайшего пути на графе. Он используется для нахождения оптимального маршрута между двумя вершинами, минимизируя длину или количество промежуточных узлов. Эта задача относится к 21 NP трудной проблеме, сформулированной Ричардом Карпом в 1972 году. Она по-прежнему представляет собой серьезный вызов для науки, поскольку не существует полиномиального алгоритма, способного обеспечить точное ее решение. Метод. Рассмотрены подходы к решению задачи поиска кратчайшего пути на графе, а также обсуждаются их преимущества и недостатки. Изучены алгоритмы, такие как Беллмана–Форда, Дейкстры и А*; проанализированы их эффективность и применимость в различных ситуациях. Обсуждаются вопросы оптимизации алгоритмов поиска кратчайшего пути, такие как использование эвристик, предварительная обработка графа и другие методы, которые могут улучшить производительность и точность алгоритмов. Основные результаты. Предложена оптимизация алгоритма Дейкстры с квантовым ускорением. Проведена оценка устойчивости квантового алгоритма и величины искажений в схеме с различным количеством кубитов. Показано, что с возрастанием интенсивности искажений вероятность обнаружения искомого элемента уменьшается, а время, затрачиваемое на его поиск, увеличивается. При применении алгоритма Гровера для оптимизации пути в квантовой сети эти помехи становятся причиной увеличения времени поиска оптимального пути и повышения вероятности выбора неверного маршрута. Показано, что увеличение количества кубитов и, соответственно, количества итераций делает алгоритм более устойчивым. Продемонстрировано, что устойчивость алгоритма Гровера для схем с большим количеством кубитов имеет схожий характер. Работы квантовых схем на 9, 10 и 11 кубитах различие в значениях вероятностей верного срабатывания отличается менее, чем на 10–3. Таким образом, из полученных зависимостей можно предсказать характер такого влияния на схемы с еще большим числом кубитов, устойчивость которых не может быть исследована вследствие недостаточной вычислительной мощности классических компьютеров. Обсуждение. Наиболее эффективным способом модификации алгоритма Дейкстры является замена очереди с приоритетом в классической версии алгоритма на некоторую квантовую структуру данных, находящую минимальный элемент для следующей итерации алгоритма. Несмотря на то, что квантовый поиск не дает потенциального прироста в асимптотике, можно использовать иную квантовую модификацию алгоритма Дейкстры. А именно, вместо поддержания и поиска минимума в очереди с приоритетом применить квантовый алгоритм сразу для поиска вершины, которую необходимо добавить в дерево кратчайших путей, что дополнительно даст ускорение обхода графа алгоритмом Дейкстры.
Algorithms and data structures are important in information technology (particularly in 6G terahertz wireless communications), logistics, transportation, and route planning in medicine. One of the fundamental algorithms that find application in many practical problems is the shortest path algorithm. The shortest path algorithm is used to find the optimal route between two vertices while minimizing the length or number of intermediate nodes. This problem is one of the 21 NP-hard problems formulated by Richard Karp in 1972. It still poses a serious challenge to science, since there is no polynomial algorithm that can provide an exact solution to this problem. The article considers approaches to solving the problem of finding the shortest path on a graph, and discusses their advantages and disadvantages. Various algorithms, such as the Bellman-Ford algorithm, Dijkstra, and the A* algorithm, are considered; their efficiency and applicability in various situations are analyzed. Issues of optimization of shortest path algorithms are discussed, such as the use of heuristics, graph preprocessing, and other methods that can improve the performance and accuracy of algorithms. The article proposes an optimization of Dijkstra’s algorithm with quantum acceleration. The stability of the quantum algorithm and the magnitude of distortions in a circuit with a different number of qubits are estimated. It is shown that with an increase in the intensity of distortions, the probability of detecting the desired element decreases, and the time spent on its search increases. When using Grover’s algorithm to optimize a path in a quantum network, these interferences cause an increase in the time it takes to find the optimal path and an increase in the probability of choosing an incorrect route. It is shown that an increase in the number of qubits and, accordingly, the number of iterations makes the algorithm more stable. It is demonstrated that the stability of Grover’s algorithm for circuits with a large number of qubits has a similar nature. The work of quantum circuits on 9, 10 and 11 qubits, the difference in the probabilities of correct operation differs by less than 10–3. Thus, from the obtained dependencies, it is possible to predict the nature of such an influence on circuits with an even larger number of qubits, the stability of which cannot be studied due to the insufficient computing power of classical computers. The most efficient way to modify Dijkstra’s algorithm is to replace the priority queue in the classical version of the algorithm with some quantum data structure that finds the minimum element for the next iteration of the algorithm. Despite the fact that quantum search does not provide a potential gain in asymptotics, another quantum modification of Dijkstra’s algorithm can be used. Namely, instead of maintaining and searching for a minimum in the priority queue, use the quantum algorithm immediately to search for a vertex that needs to be added to the shortest path tree, which will additionally acceleration the graph traversal by Dijkstra’s algorithm.
The authors declare that there are no conflicts of interest present.