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

Recent Advances in Computer Science and Communications

Quantum Algorithms for Graph and Algebra Problems

Sebastian Dörn

Published Jun 1, 2009• 0 citations
Publisher

Abstract

Quantum algorithms have the potential to demonstrate that for some problems quantum computation is more efficient than classical computation. A goal of quantum computing is to determine for which problems quantum computers are faster than classical computers. In our survey we present recent quantum algorithms for basic problems from graph and algebra theory. The quantum algorithms for these problems use a combination of Grovers search algorithms, quantum amplitude amplification and quantum random walks. These quantum algorithms are faster than the best known classical algorithms for the corresponding problems. Keywords: Quantum computing, quantum algorithms, graph theory, algebra, quantum query complexity

DOI
10.2174/2213275910902020124

Related papers

Quantum complexity of graph and algebraic problems

Sebastian Dörn

In this thesis we present new quantum algorithms for graph and algebra problems. Our quantum algorithms for these problems use a combination of Grover search, amplitude amplification and quantum walk search. The quantum algorithms are faster than the best known classical algorithms for the corresponding problems.

Ausgezeichnete Informatikdissertationen•Jan 1, 2007•6 citations

A panoply of quantum algorithms

Bartholomew Furrow

This paper's aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover\cite{grover}. Grover's algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this paper is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover's algorithm or similar techniques, which can be used as subroutines in many quantum algorithms.}{The tools we provide are carefully constructed: they are easy to use, and in many cases they are asymptotically faster than the best tools previously available. The tools we build on include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer.}{After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known deterministic classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible deterministic classical algorithm. These algorithms solve problems from the fields of graph theory and computational geometry, and some employ dynamic programming techniques. We discuss a breadth-first search that is faster than $\Theta(\text{edges})$ (the classical limit) in a dense graph, maximum-points-on-a-line in $O(N^{3/2}\lg N)$ (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

Quantum Information and Computation•Sep 1, 2008•6 citations

Quantum algorithms and the maximum clique problem in graphs

Matheus Augusto Condé Dias

Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.

•Sep 14, 2022•0 citations

A panoply of quantum algorithms

Bartholomew Furrow

This thesis’ aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grover’s algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover’s algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

Quantum Information and Computation•Jan 1, 2010•7 citations

Quantum random walk search on satisfiability problems

Stephan Hoyer

Using numerical simulation, we measured the performance of several potential quantum algorithms, based on quantum random walks, to solve Boolean satisfiability (SAT) problems. We develop the fundamentals of quantum computing and the theory of classical algorithms to indicate how these algorithms could be implemented. We also discuss the development of quantum random walks and the principles that go into creating them, presenting existing work on search algorithms using coined discrete-time quantum random walks. Although our quantum algorithms do not solve SAT problems faster than may be done classically, as a step toward that objective, we present the first example of a quantum walk on a directed graph that has a significant increase in speed over the analogous classical walk.

•Jan 1, 2008•6 citations

Discrete Quantum Walks on Graphs and Digraphs

Chris D. Godsil, Hanmeng Zhan

Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.

Cambridge University Press eBooks•Dec 23, 2022•11 citations
Quantum algorithms have the potential to demonstrate that for some problems quantum computation is more efficient than classical computation. A goal of quantum computing is to determine for which problems quantum computers are faster than classical computers. In our survey we present recent quantum algorithms for basic problems from graph and algebra theory. The quantum algorithms for these problems use a combination of Grovers search algorithms, quantum amplitude amplification and quantum random walks. These quantum algorithms are faster than the best known classical algorithms for the corresponding problems. Keywords: Quantum computing, quantum algorithms, graph theory, algebra, quantum query complexity
This paper's aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover\cite{grover}. Grover's algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this paper is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover's algorithm or similar techniques, which can be used as subroutines in many quantum algorithms.}{The tools we provide are carefully constructed: they are easy to use, and in many cases they are asymptotically faster than the best tools previously available. The tools we build on include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer.}{After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known deterministic classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible deterministic classical algorithm. These algorithms solve problems from the fields of graph theory and computational geometry, and some employ dynamic programming techniques. We discuss a breadth-first search that is faster than Θ(edges)\Theta(\text{edges})Θ(edges) (the classical limit) in a dense graph, maximum-points-on-a-line in O(N3/2lg⁡N)O(N^{3/2}\lg N)O(N3/2lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.
Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.
This thesis’ aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grover’s algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover’s algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.
Using numerical simulation, we measured the performance of several potential quantum algorithms, based on quantum random walks, to solve Boolean satisfiability (SAT) problems. We develop the fundamentals of quantum computing and the theory of classical algorithms to indicate how these algorithms could be implemented. We also discuss the development of quantum random walks and the principles that go into creating them, presenting existing work on search algorithms using coined discrete-time quantum random walks. Although our quantum algorithms do not solve SAT problems faster than may be done classically, as a step toward that objective, we present the first example of a quantum walk on a directed graph that has a significant increase in speed over the analogous classical walk.
Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.