2 papers
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…
quant-ph2023
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
John Kallaugher, Ojas Parekh, Nadezhda Voronova
While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work…