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

Quantum testing algorithms for graph properties

R.E.A. van de Hoef

Published Jan 1, 2016• 0 citations
OpenAlex

Related papers

Quantum Algorithms for Graph and Algebra Problems

Sebastian Dörn

Recent Advances in Computer Science and Communications•Jan 9, 2010•1 citation

Quantum Property Testing in Sparse Directed Graphs

Simon Apers, Frédéric Magniez, Sayantan Sen +1 more

We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing $k$-star-freeness, and more generally $k$-source-subgraph-freeness, is almost maximally hard for large $k$. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the $k$-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of $3$-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.

arXiv:2410.05001•Leibniz international proceedings in informatics•Oct 7, 2024•4 citations

Generating Property-Based Tests for Quantum Algorithms

Antonio García de la Barrera, Manuel Serrano, Ignacio García‐Rodríguez de Guzmán +2 more

Lecture notes in computer science•Jul 24, 2025•0 citations

Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness

Chris Cade, Ashley Montanaro, Aleksandrs Belovs

We study space and time-efficient quantum algorithms for two graph problems – deciding whether an n-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in O˜(n 3/2 ) time whilst using O(log n) classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time O˜(n √ dm) and also require O(log n) space, where dm is the maximum degree of any vertex in the input graph.

arXiv:1610.00581•Quantum Information and Computation•Feb 1, 2018•22 citations

Quantum algorithm for testing graph completeness

Sara Giordano, Miguel Angel Martin-Delgado

Testing graph completeness is a critical problem in computer science and network theory. Leveraging quantum computation, we present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE). Our algorithm, which takes the number of nodes and the adjacency matrix as input, constructs a quantum walk operator and applies QPE to estimate its eigenvalues. These eigenvalues reveal the graph’s structural properties, enabling us to determine its completeness. We establish a relationship between the number of nodes in a complete graph and the number of marked nodes, optimizing the success probability and running time. The time complexity of our algorithm is O ( log 2 n ) , where n is the number of nodes of the graph. offering a clear quantum advantage over classical methods. This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessing systems based on pairwise comparisons.

arXiv:2407.20069•Annals of Physics•Nov 25, 2025•1 citation

Graph comparison via nonlinear quantum search

Mitchell Chiew, K. de Lacy, Chao‐Hua Yu +2 more

arXiv:1810.01647•Quantum Information Processing•Aug 20, 2019•10 citations
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing kkk-star-freeness, and more generally kkk-source-subgraph-freeness, is almost maximally hard for large kkk. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the kkk-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of 333-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.
We study space and time-efficient quantum algorithms for two graph problems – deciding whether an n-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in O˜(n 3/2 ) time whilst using O(log n) classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time O˜(n √ dm) and also require O(log n) space, where dm is the maximum degree of any vertex in the input graph.
Testing graph completeness is a critical problem in computer science and network theory. Leveraging quantum computation, we present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE). Our algorithm, which takes the number of nodes and the adjacency matrix as input, constructs a quantum walk operator and applies QPE to estimate its eigenvalues. These eigenvalues reveal the graph’s structural properties, enabling us to determine its completeness. We establish a relationship between the number of nodes in a complete graph and the number of marked nodes, optimizing the success probability and running time. The time complexity of our algorithm is O ( log 2 n ) , where n is the number of nodes of the graph. offering a clear quantum advantage over classical methods. This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessing systems based on pairwise comparisons.