Quantum independent set problem and non-abelian adiabatic mixing

Abstract

We present an efficient quantum algorithm for some independent set problems in graph theory, based on non-abelian adiabatic mixing. We illustrate the performance of our algorithm with analysis and numerical calculations for two different types of graphs, with the number of edges proportional to the number of vertices or its square. The theoretical advantages of our quantum algorithm over classical algorithms are discussed. Non-abelian adiabatic mixing can be a general technique to aid exploration in a landscape of near-degenerate ground states.

arXiv comment5 pages, 6 figures

References in corpus (9)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Mechanics helps in searching for a needle in a haystack
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Holonomic Quantum Computation
• Proof of the Ergodic Theorem and the H-Theorem in Quantum Mechanics
• On independent sets in random graphs
• Entropy for Quantum Pure States and Its Dynamical Relaxation
• Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm
• Generalized Wigner-von Neumann entropy and its typicality

Cited by in corpus (7)

• Quantum Algorithm for Approximating Maximum Independent Sets
• Resonant Quantum Search with Monitor Qubits
• Quantum algorithm of a set of quantum 2-sat problem
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Quantum Hamiltonian Algorithms for Maximum Independent Sets
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Theory of thermalization in an isolated Bose-Einstein condensate