Showing 2024Show all
2 papers · 1 filter
quant-ph2024
Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
Chaithanya Rayudu
The Independent Set is a well known NP-hard optimization problem. In this work, we define a fermionic generalization of the Independent Set problem and prove that the optimization…
quant-ph2024
Constrained local Hamiltonians: quantum generalizations of Vertex Cover
Ojas Parekh, Chaithanya Rayudu, Kevin Thompson
Recent successes in producing rigorous approximation algorithms for local Hamiltonian problems such as Quantum Max Cut have exploited connections to unconstrained classical discret…