Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on Information Technology

A quantum algorithm for minimal spanning tree

Mohammad Reza Soltan Aghaei, Zuriati Ahmad Zukarnain, Ali Mamat, Hishamuddin Zainuddin

Published Aug 1, 2008• 9 citations
Publisher

Abstract

Quantum computing algorithms are considered for several problems in graph theory. Classical algorithms involve searching over some space for finding the minimal spanning tree problem in a graph. We modify classical Primpsilas algorithm and replace quantum search instead of classical search, of which it will lead to more efficient algorithm. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Primpsilas algorithm in the probabilistic quantum-classical algorithm.

DOI
10.1109/itsim.2008.4632038

Related papers

A Hybrid Algorithm for the Shortest-Path Problem in the Graph

Mohammad Reza Soltan Aghaei, Zuriati Ahmad Zukarnain, Ali Mamat +1 more

Quantum algorithms run on quantum computers are qualitatively different from those that run on classical computers. Quantum computing algorithms can be used for several problems in graph theory. Most of the classical algorithms involve searching over some space for finding the shortest-paths problem between two points in a graph and a minimal weight spanning tree. We modified classical Dijkstra's algorithm and implement quantum search instead of classical search, of which it will lead to more efficient algorithm. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Dijkstra's algorithm as the probabilistic quantum-classical algorithm.

International Conference on Advanced Computer Theory and Engineering•Dec 1, 2008•5 citations

A hybrid algorithm for finding shortest path in network routing.

Mohammad Reza Soltan Aghaei, Zuriati Ahmad Zukarnain, Ali Mamat +2 more

Classical algorithms have been used to search over some space for finding the shortest paths problem between two points in a network and a minimal weight spanning tree for routing. Any classical algorithm deterministic or probabilistic will clearly used O(N) steps since on the average it will measure a large fraction of N records. Quantum algorithm is the fastest possible algorithm that can do several operations simultaneously due to their wave like properties. This wave gives an O( N ) steps quantum algorithm for identifying that record, where was used classical Dijkstra’s algorithm for finding shortest path problem in the graph of network and implement quantum search. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Dijkstra's algorithm as the probabilistic quantum-classical algorithm.

•Mar 1, 2009•12 citations

Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs

Mark Heiligman

Quantum algorithms for several problems in graph theory are considered. Classical algorithms for finding the lowest weight path between two points in a graph and for finding a minimal weight spanning tree involve searching over some space. Modification of classical algorithms due to Dijkstra and Prim allows quantum search to replace classical search and leads to more efficient algorithms. In the case of highly asymmetric complete bipartite graphs, simply replacing classical search with quantum search leads to a faster quantum algorithm. A fast quantum algorithm for computing the diameter of a complete graph is also given.

arXiv:quant-ph/0303131•Mar 20, 2003•8 citations

Quantum and classical algorithms for graph classification and search problems

B. L. Douglas

[Truncated abstract] This thesis is split into three parts, each addressing the overarching theme of applying graph theoretic techniques to classi cation and search problems. Part I explores this theme in the context of quantum algorithms, in particular involving quantum walks, coined by Aharonov et al. in 1993 [1]. As a quantum analogue to classical random walks, quantum walks represent a promising candidate for quantum algorithms providing speed-ups over known classical methods. I will discuss two categories of quantum walk algorithms; quantum search and graph isomorphism. In particular, the e ciency of quantum walk based search algorithms on various families of graphs will be investigated, linking both e ciency of quantum circuit implementation and the complexity of the search problem to the symmetry of the underlying graphs. Several families of graphs are presented that are amenable to efficient quantum walk based searching, together with explicit quantum circuit implementations. In the case of the n-cube, I show that O(p2n) steps of a quanum walk are suffcient to nd a marked sub-d-cube (where d

•Jan 1, 2011•0 citations

Time- and Query-optimal Quantum Algorithms Based on Decision Trees

Salman Beigi, Leila Taghavi, Artin Tajdini

It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity O( √ GT where T is the query complexity of the classical algorithm (depth of the decision tree) and G is the maximum number of wrong answers by the guessing algorithm [ 3 , 14 ]. In this article, we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time Õ (√ GT ). Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph-theoretic problems including bipartiteness, cycle detection, and topological sort can be solved in time O(n 3/2 log 2 n ) and with O(n 3/2 ) quantum queries. Moreover, finding a maximal matching can be solved with O(n 3/2 ) quantum queries in time O(n 3/2 log 2 n ), and maximum bipartite matching can be solved in time O(n 2 log 2 n ).

arXiv:2105.08309•ACM Transactions on Quantum Computing•Mar 28, 2022•8 citations

Quantum Speedup for Sampling Random Spanning Trees

Simon Apers, Gao, Minbo, Zhengfeng Ji +1 more

We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.

Leibniz international proceedings in informatics•Jan 1, 2025•0 citations
Quantum computing algorithms are considered for several problems in graph theory. Classical algorithms involve searching over some space for finding the minimal spanning tree problem in a graph. We modify classical Primpsilas algorithm and replace quantum search instead of classical search, of which it will lead to more efficient algorithm. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Primpsilas algorithm in the probabilistic quantum-classical algorithm.
Quantum algorithms run on quantum computers are qualitatively different from those that run on classical computers. Quantum computing algorithms can be used for several problems in graph theory. Most of the classical algorithms involve searching over some space for finding the shortest-paths problem between two points in a graph and a minimal weight spanning tree. We modified classical Dijkstra's algorithm and implement quantum search instead of classical search, of which it will lead to more efficient algorithm. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Dijkstra's algorithm as the probabilistic quantum-classical algorithm.
Classical algorithms have been used to search over some space for finding the shortest paths problem between two points in a network and a minimal weight spanning tree for routing. Any classical algorithm deterministic or probabilistic will clearly used O(N) steps since on the average it will measure a large fraction of N records. Quantum algorithm is the fastest possible algorithm that can do several operations simultaneously due to their wave like properties. This wave gives an O( N ) steps quantum algorithm for identifying that record, where was used classical Dijkstra’s algorithm for finding shortest path problem in the graph of network and implement quantum search. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Dijkstra's algorithm as the probabilistic quantum-classical algorithm.
Quantum algorithms for several problems in graph theory are considered. Classical algorithms for finding the lowest weight path between two points in a graph and for finding a minimal weight spanning tree involve searching over some space. Modification of classical algorithms due to Dijkstra and Prim allows quantum search to replace classical search and leads to more efficient algorithms. In the case of highly asymmetric complete bipartite graphs, simply replacing classical search with quantum search leads to a faster quantum algorithm. A fast quantum algorithm for computing the diameter of a complete graph is also given.
[Truncated abstract] This thesis is split into three parts, each addressing the overarching theme of applying graph theoretic techniques to classi cation and search problems. Part I explores this theme in the context of quantum algorithms, in particular involving quantum walks, coined by Aharonov et al. in 1993 [1]. As a quantum analogue to classical random walks, quantum walks represent a promising candidate for quantum algorithms providing speed-ups over known classical methods. I will discuss two categories of quantum walk algorithms; quantum search and graph isomorphism. In particular, the e ciency of quantum walk based search algorithms on various families of graphs will be investigated, linking both e ciency of quantum circuit implementation and the complexity of the search problem to the symmetry of the underlying graphs. Several families of graphs are presented that are amenable to efficient quantum walk based searching, together with explicit quantum circuit implementations. In the case of the n-cube, I show that O(p2n) steps of a quanum walk are suffcient to nd a marked sub-d-cube (where d
It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity O( √ GT where T is the query complexity of the classical algorithm (depth of the decision tree) and G is the maximum number of wrong answers by the guessing algorithm [ 3 , 14 ]. In this article, we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time Õ (√ GT ). Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph-theoretic problems including bipartiteness, cycle detection, and topological sort can be solved in time O(n 3/2 log 2 n ) and with O(n 3/2 ) quantum queries. Moreover, finding a maximal matching can be solved with O(n 3/2 ) quantum queries in time O(n 3/2 log 2 n ), and maximum bipartite matching can be solved in time O(n 2 log 2 n ).
We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.