Quantum Algorithms and Lower Bounds for Independent Set and Subgraph Isomorphism Problem
Sebastian Doern · arXiv (Cornell University) · 2005
The study of the quantum query complexity for some graph problems is an interesting area in quantum computing. Only for a few graph problems there are quantum algorithms and lower bounds known. We present some new quantum query and quantum time algorithms and quantum query complexity bounds for the maximal and maximum independent set problem and the graph and subgraph isomorphism problem.