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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Hybrid and Quantum Graph Algorithms via Quantum Array Search: Applications to Hamiltonian Paths and Path Counting

Ethan Hunt, Hieu Nguyen, Dheeraj Sai Tukkugudam, Dillon Horton, Tu N. Nguyen

Published Aug 30, 2025• 0 citations
Publisher

Abstract

In this paper, we introduce novel hybrid and quantum algorithms for fundamental graph problems, specifically the Hamiltonian Path Problem (HPP) and$\langle s, t\rangle$Path Counting Problem. By leveraging quantum array search techniques, rooted in amplitude amplification and applied in new and effective ways, we achieve significant reductions in time complexity compared to classical methods. We propose a quantum algorithm that solves the HPP on a special class of graphs known as clique trees in$O(\sqrt{n})$time. Additionally, we develop a hybrid quantum-classical algorithm for counting simple$\langle s, t\rangle$paths with a time complexity of$O\left(\binom{m}{n} \sqrt{n}\right)$for large$m$, improving over the classical baseline. Beyond these algorithmic contributions, we present a fixedparameter tractable (FPT) algorithm for identifying clique trees, enabling their structural properties to be efficiently leveraged. We also explore additional algorithmic results related to clique trees, including insights into their treewidth and chromatic number. Overall, our work demonstrates how quantum and hybrid approaches can offer practical advantages for solving challenging graph problems, specifically applications to Hamiltonian paths and path counting problems.

DOI
10.1109/qce65121.2025.00036

Related papers

Quantum Circuit Design for Finding k-Cliques via Quantum Amplitude Amplification Strategies

Simone Perriello

The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations.This work introduces two quantum algorithms for solving the 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs.We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets.Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2 5 to 2 20 .

ACM International Conference on Computing Frontiers (CF)•May 28, 2025•2 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

Quantum Algorithmic Complexity in Graph Theory -Shortest Path Problems and Quantum Acceleration Mechanisms

Jeffrey Quinn Cordova

We provide a rigorous theoretical analysis of quantum algorithms for shortest path problems in weighted graphs, establishing complexity-theoretic foundations for quantum acceleration in this fundamental computational domain. Building upon recent quantum adaptations of classical graph algorithms, we develop a unified framework that characterizes when and why quantum approaches offer computational advantages for single-source and all-pairs shortest path computations. Our analysis encompasses both positive-weight and negative-weight scenarios, deriving conditional speedup theorems that depend on graph structure, weight distribution, and oracle access models. We prove that quantum amplitude amplification and quantum walks can provide polynomial to exponential speedups under specific structural assumptions, while establishing hardness results that identify problem instances where quantum advantage is provably absent. The theoretical framework introduces novel complexity measures that capture graph-theoretic properties relevant to quantum algorithm performance, including quantum diameter, entanglement capacity, and interference efficiency. We extend our analysis to dynamic graph scenarios where edge weights evolve over time, establishing bounds on quantum advantage preservation under graph modifications. This work contributes fundamental insights into quantum algorithmic graph theory, clarifying the boundaries of quantum computational advantage and providing theoretical guidance for algorithm design in network optimization, routing, and graph analytics applications.

•Oct 21, 2025•0 citations

Quantum algorithms for path and cycle containment problems

Arjan Cornelissen, Amin Shiraz Gilani, Subhasree Patro

The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph $H$ is present in an input graph $G$, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length $k$. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly $k$, or at most $k$. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes. When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity $\widetilde{O}(n^{3/2-α_k})$, where $α_k \in Θ(c^{-k})$ and $c = \sqrt{3+\sqrt{17}}/2 \approx 1.33$, beating the previous best upper bound $O(n^{3/2})$ on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an $O(\sqrt{n})$ query algorithm.

quant-pharXiv:2605.09017•Leibniz international proceedings in informatics•May 12, 2026•0 citations

Quantum Walk Algorithms for Graph Partitioning

Jincheng Zhang

Graph partitioning is a crucial problem in computer science with applications in diverse areas like VLSI design, image segmentation, and network analysis. Traditional classical algorithms often face significant challenges when dealing with large and complex graphs, leading to increased computational time and memory requirements. This paper explores the potential of quantum walk algorithms to address this issue. We propose a framework for leveraging quantum walk algorithms to efficiently explore the connectivity structure of a graph and identify optimal partitions. The core idea involves mapping the graph's nodes and edges onto a quantum system and utilizing the inherent parallelism of quantum walks to traverse the graph. We present a theoretical analysis of the algorithm's potential speedup compared to classical approaches, focusing on scenarios where quantum computation offers a significant advantage. Specifically, we formulate the graph partitioning problem as a search problem on a graph represented as a quantum walk, considering the Hamiltonian operator and its eigenstates for efficient traversal. The effectiveness of the algorithm is dependent on the graph's structure and the ability to accurately simulate the quantum walk. The presented methodology provides a novel approach to graph partitioning, potentially leading to substantial performance improvements for large, complex graphs.

•Sep 2, 2026•0 citations

Hybrid Quantum-Classical Steiner Tree Optimization: A Novel Framework Combining Amplitude Amplification, QAOA, and SDP Relaxations

Yalla Jnan Devi Satya Prasad, Sahil Ram Chatrati, Shaik Fathima Masthan

We introduce a novel hybrid quantum-classical algorithm for the Minimum Steiner Tree problem that integrates three key innovations to achieve practical improvements on structured graph families. First, we employ a fast classical preprocessing pipeline, including geometric ranking, connectivity pruning, and a lightweight ML surrogate, to reduce the candidate Steiner vertex set by 60-80% while preserving 95% of optimal solutions. Second, we leverage a custom "Greedy-Mixer" QAOA ansatz tailored to terminal clustering, paired with quantum amplitude amplification, to explore exponentially many subsets with O(2 m/2) oracle complexity. Third, we integrate quantum SDP relaxations to tighten lower bounds, improving threshold selection in amplitude amplification and boosting success rates by 26% over classical bounds. Under structural assumptions (bounded local treewidth), we prove a conditional approximation guarantee α < 1.55 in expected time O(2 θm poly(n)) with θ < 1 2. Extensive experiments on planar, random geometric, and VLSI-like graphs (up to n = 50, m ≤ 20) demonstrate a 4-5× reduction in quantum resources and a 3-8% improvement in approximation ratio versus classical heuristics, with statistically significant advantages (p < 0.01) for gate errors 1%, 200 measurement shots, and mixer depths p ≥ 4. This work establishes a practical pathway toward NISQ-era quantum advantage in combinatorial network design.

•Oct 6, 2025•1 citation
In this paper, we introduce novel hybrid and quantum algorithms for fundamental graph problems, specifically the Hamiltonian Path Problem (HPP) and⟨s,t⟩\langle s, t\rangle⟨s,t⟩Path Counting Problem. By leveraging quantum array search techniques, rooted in amplitude amplification and applied in new and effective ways, we achieve significant reductions in time complexity compared to classical methods. We propose a quantum algorithm that solves the HPP on a special class of graphs known as clique trees inO(n)O(\sqrt{n})O(n​)time. Additionally, we develop a hybrid quantum-classical algorithm for counting simple⟨s,t⟩\langle s, t\rangle⟨s,t⟩paths with a time complexity ofO((mn)n)O\left(\binom{m}{n} \sqrt{n}\right)O((nm​)n​)for largemmm, improving over the classical baseline. Beyond these algorithmic contributions, we present a fixedparameter tractable (FPT) algorithm for identifying clique trees, enabling their structural properties to be efficiently leveraged. We also explore additional algorithmic results related to clique trees, including insights into their treewidth and chromatic number. Overall, our work demonstrates how quantum and hybrid approaches can offer practical advantages for solving challenging graph problems, specifically applications to Hamiltonian paths and path counting problems.
The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations.This work introduces two quantum algorithms for solving the 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs.We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets.Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2 5 to 2 20 .
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.
We provide a rigorous theoretical analysis of quantum algorithms for shortest path problems in weighted graphs, establishing complexity-theoretic foundations for quantum acceleration in this fundamental computational domain. Building upon recent quantum adaptations of classical graph algorithms, we develop a unified framework that characterizes when and why quantum approaches offer computational advantages for single-source and all-pairs shortest path computations. Our analysis encompasses both positive-weight and negative-weight scenarios, deriving conditional speedup theorems that depend on graph structure, weight distribution, and oracle access models. We prove that quantum amplitude amplification and quantum walks can provide polynomial to exponential speedups under specific structural assumptions, while establishing hardness results that identify problem instances where quantum advantage is provably absent. The theoretical framework introduces novel complexity measures that capture graph-theoretic properties relevant to quantum algorithm performance, including quantum diameter, entanglement capacity, and interference efficiency. We extend our analysis to dynamic graph scenarios where edge weights evolve over time, establishing bounds on quantum advantage preservation under graph modifications. This work contributes fundamental insights into quantum algorithmic graph theory, clarifying the boundaries of quantum computational advantage and providing theoretical guidance for algorithm design in network optimization, routing, and graph analytics applications.
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph HHH is present in an input graph GGG, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length kkk. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly kkk, or at most kkk. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes. When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O~(n3/2−αk)\widetilde{O}(n^{3/2-α_k})O(n3/2−αk​), where αk∈Θ(c−k)α_k \in Θ(c^{-k})αk​∈Θ(c−k) and c=3+17/2≈1.33c = \sqrt{3+\sqrt{17}}/2 \approx 1.33c=3+17​​/2≈1.33, beating the previous best upper bound O(n3/2)O(n^{3/2})O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n)O(\sqrt{n})O(n​) query algorithm.
Graph partitioning is a crucial problem in computer science with applications in diverse areas like VLSI design, image segmentation, and network analysis. Traditional classical algorithms often face significant challenges when dealing with large and complex graphs, leading to increased computational time and memory requirements. This paper explores the potential of quantum walk algorithms to address this issue. We propose a framework for leveraging quantum walk algorithms to efficiently explore the connectivity structure of a graph and identify optimal partitions. The core idea involves mapping the graph's nodes and edges onto a quantum system and utilizing the inherent parallelism of quantum walks to traverse the graph. We present a theoretical analysis of the algorithm's potential speedup compared to classical approaches, focusing on scenarios where quantum computation offers a significant advantage. Specifically, we formulate the graph partitioning problem as a search problem on a graph represented as a quantum walk, considering the Hamiltonian operator and its eigenstates for efficient traversal. The effectiveness of the algorithm is dependent on the graph's structure and the ability to accurately simulate the quantum walk. The presented methodology provides a novel approach to graph partitioning, potentially leading to substantial performance improvements for large, complex graphs.
We introduce a novel hybrid quantum-classical algorithm for the Minimum Steiner Tree problem that integrates three key innovations to achieve practical improvements on structured graph families. First, we employ a fast classical preprocessing pipeline, including geometric ranking, connectivity pruning, and a lightweight ML surrogate, to reduce the candidate Steiner vertex set by 60-80% while preserving 95% of optimal solutions. Second, we leverage a custom "Greedy-Mixer" QAOA ansatz tailored to terminal clustering, paired with quantum amplitude amplification, to explore exponentially many subsets with O(2 m/2) oracle complexity. Third, we integrate quantum SDP relaxations to tighten lower bounds, improving threshold selection in amplitude amplification and boosting success rates by 26% over classical bounds. Under structural assumptions (bounded local treewidth), we prove a conditional approximation guarantee α < 1.55 in expected time O(2 θm poly(n)) with θ < 1 2. Extensive experiments on planar, random geometric, and VLSI-like graphs (up to n = 50, m ≤ 20) demonstrate a 4-5× reduction in quantum resources and a 3-8% improvement in approximation ratio versus classical heuristics, with statistically significant advantages (p < 0.01) for gate errors 1%, 200 measurement shots, and mixer depths p ≥ 4. This work establishes a practical pathway toward NISQ-era quantum advantage in combinatorial network design.