Quantum Complexity Bounds for Independent Set Problems

2005/10/12 by Sebastian Doern, Doern, Sebastian
Computer Science · Mathematics · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computer science #FOS: Physical sciences #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum mechanics #Set (abstract data type) #Theoretical computer science #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0510084

12 pages, 0 figures

openalex publication_date 2005/10/12 · arxiv created 2007/02/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We present quantum complexity lower and upper bounds for independent set problems in graphs. In particular, we give quantum algorithms for computing a maximal and a maximum independent set in a graph. We present applications of these algorithms for some graph problems. Our results improve the best classical complexity bounds for the corresponding problems.

Citations

• An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
• Finding a Maximum Independent Set
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Quantum Complexity of Testing Group Commutativity

Related

• Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors
• Max Independent Set and Quantum Alternating Operator Ansatz
• New Approaches to Complexity via Quantum Graphs
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms
• Quantum Algorithms for Lowest Weight Paths and Spanning Trees in Complete Graphs