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

Lecture notes in computer science

Polynomial Time Quantum Algorithm for Search Problem and Its Application

Satoshi Iriyama, Masanori Ohya

Published Jan 1, 2014• 0 citations
Publisher
DOI
10.1007/978-3-642-54943-4_15

Related papers

Quantum Search Algorithm and Its Applications

Weng-Long Chang, Athanasios V. Vasilakos

Studies in big data•Dec 21, 2020•0 citations

Exponential-time quantum algorithms for graph coloring problems

Shimizu, Kazuya, Ryuhei Mori

The fastest known classical algorithm deciding the $k$-colorability of $n$-vertex graph requires running time $Ω(2^n)$ for $k\ge 5$. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time $O(1.9140^n)$ using quantum random access memory (QRAM). Our approach is based on Ambainis et al's quantum dynamic programming with applications of Grover's search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph $20$-coloring problem with running time $O(1.9575^n)$. In the polynomial-space quantum algorithm, we essentially show $(4-ε)^n$-time classical algorithms that can be improved quadratically by Grover's search.

arXiv:1907.00529•Jul 1, 2019•0 citations

A review on quantum search algorithms

Pulak Ranjan Giri, V. E. Korepin

arXiv:1602.02730•Quantum Information Processing•Nov 13, 2017•82 citations

Exponential-Time Quantum Algorithms for Graph Coloring Problems

Kazuya Shimizu, Ryuhei Mori

Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time $$\varOmega (2^n)$$ Ω ( 2 n ) for $$k\ge 5$$ k ≥ 5 . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time $$O(1.9140^n)$$ O ( 1 . 9140 n ) using quantum random access memory (QRAM). Our approach is based on Ambainis et al’s quantum dynamic programming with applications of Grover’s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time $$O(1.9575^n)$$ O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop $$(4-\epsilon )^n$$ ( 4 - ϵ ) n -time classical algorithms that can be improved quadratically by Grover’s search.

Algorithmica•Jun 1, 2022•18 citations

Quantum search algorithms

Christoph Dürr, xb b b

•Jan 1, 2005•16 citations

Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs

Kamil Ravilevich Khadiev, Liliya Safina

In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is $O(\sqrt{\hat{n}m}\log \hat{n})$, and the running time of the best known deterministic algorithm is $O(n+m)$, where $n$ is the number of vertices, $\hat{n}$ is the number of vertices with at least one outgoing edge; $m$ is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluating. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.

arXiv:1804.09950•Apr 26, 2018•1 citation
The fastest known classical algorithm deciding the kkk-colorability of nnn-vertex graph requires running time Ω(2n)Ω(2^n)Ω(2n) for k≥5k\ge 5k≥5. In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time O(1.9140n)O(1.9140^n)O(1.9140n) using quantum random access memory (QRAM). Our approach is based on Ambainis et al's quantum dynamic programming with applications of Grover's search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 202020-coloring problem with running time O(1.9575n)O(1.9575^n)O(1.9575n). In the polynomial-space quantum algorithm, we essentially show (4−ε)n(4-ε)^n(4−ε)n-time classical algorithms that can be improved quadratically by Grover's search.
Abstract The fastest known classical algorithm deciding the k-colorability of n-vertex graph requires running time Ω(2n)\varOmega (2^n)Ω(2n) Ω ( 2 n ) for k≥5k\ge 5k≥5 k ≥ 5 . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time O(1.9140n)O(1.9140^n)O(1.9140n) O ( 1 . 9140 n ) using quantum random access memory (QRAM). Our approach is based on Ambainis et al’s quantum dynamic programming with applications of Grover’s search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph 20-coloring problem with running time O(1.9575n)O(1.9575^n)O(1.9575n) O ( 1 . 9575 n ) . For the polynomial-space quantum algorithm, we essentially develop (4−ϵ)n(4-\epsilon )^n(4−ϵ)n ( 4 - ϵ ) n -time classical algorithms that can be improved quadratically by Grover’s search.
In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is O(n^mlog⁡n^)O(\sqrt{\hat{n}m}\log \hat{n})O(n^m​logn^), and the running time of the best known deterministic algorithm is O(n+m)O(n+m)O(n+m), where nnn is the number of vertices, n^\hat{n}n^ is the number of vertices with at least one outgoing edge; mmm is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluating. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.