17-03-2014, 05:23 PM
Abstract
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 nonclassical
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.
1. Introduction
Science and engineering have benefited from
advances in algorithms and software. Over the last few
years, several quantum algorithms have emerged.
Some are exponentially faster than their best classical
counterparts [1, 2]; others are polynomially faster
[3,4]. While a polynomial speedup is less than we
would like ideally, quantum search has proven to be
considerably more versatile than the quantum
algorithms exhibiting exponential speedups.
M.R. Soltan Aghaei is faculty member in Dep. of Computer Eng.,
Islamic Azad University of Khorasgan, Isfahan, Iran, and PhD
candidate in Faculty of Computer Science and Information Tech.,
University Putra Malaysia 43400 UPM Serdang, Selangor, Malaysia.
Zuriati A.Z., and Ali Mamat are with Faculty of Computer
Science and Information Technology, University Putra Malaysia
43400 UPM Serdang, Selangor, Malaysia, .
Hishamuddin Z. is with Laboratory of Computational Sciences
and Informatics, Institute for Mathematical Research, Universiti
Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia.
Hence, quantum search is likely to find widespread use
in future quantum computers.
Quantum search solves is known as the
unstructured search problem, which is important for
real world applications, such as searching for
cryptographic keys [5].
In this study, a classical-quantum algorithm is
proposed to find the shortest path in graph. The
Dijkstra's algorithm being used for finding shortest
path in a given graph and also use quantum search in
this algorithm. Simulation results shown that quantum
search algorithm is faster than classical one for finding
the shortest path in graph.
The rest of this paper is organized as follow. First
we have a review on related work on quantum search
algorithm and discuss some of the exciting ways that
can be used in science and engineering. Then, in
section 3, we consider the Dijkstra's algorithm for
finding the shortest path for a given graph. Next, in
section 4, a new framework is proposed to improve the
analyses and design of non-classical algorithm. After
that, in section 5, we did a simulation on a classicalquantum
algorithm. Finally, the analysis of the results
and conclusion are presented.
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 nonclassical
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.
1. Introduction
Science and engineering have benefited from
advances in algorithms and software. Over the last few
years, several quantum algorithms have emerged.
Some are exponentially faster than their best classical
counterparts [1, 2]; others are polynomially faster
[3,4]. While a polynomial speedup is less than we
would like ideally, quantum search has proven to be
considerably more versatile than the quantum
algorithms exhibiting exponential speedups.
M.R. Soltan Aghaei is faculty member in Dep. of Computer Eng.,
Islamic Azad University of Khorasgan, Isfahan, Iran, and PhD
candidate in Faculty of Computer Science and Information Tech.,
University Putra Malaysia 43400 UPM Serdang, Selangor, Malaysia.
Zuriati A.Z., and Ali Mamat are with Faculty of Computer
Science and Information Technology, University Putra Malaysia
43400 UPM Serdang, Selangor, Malaysia, .
Hishamuddin Z. is with Laboratory of Computational Sciences
and Informatics, Institute for Mathematical Research, Universiti
Putra Malaysia, 43400 UPM Serdang, Selangor, Malaysia.
Hence, quantum search is likely to find widespread use
in future quantum computers.
Quantum search solves is known as the
unstructured search problem, which is important for
real world applications, such as searching for
cryptographic keys [5].
In this study, a classical-quantum algorithm is
proposed to find the shortest path in graph. The
Dijkstra's algorithm being used for finding shortest
path in a given graph and also use quantum search in
this algorithm. Simulation results shown that quantum
search algorithm is faster than classical one for finding
the shortest path in graph.
The rest of this paper is organized as follow. First
we have a review on related work on quantum search
algorithm and discuss some of the exciting ways that
can be used in science and engineering. Then, in
section 3, we consider the Dijkstra's algorithm for
finding the shortest path for a given graph. Next, in
section 4, a new framework is proposed to improve the
analyses and design of non-classical algorithm. After
that, in section 5, we did a simulation on a classicalquantum
algorithm. Finally, the analysis of the results
and conclusion are presented.