4 papers · 2 filters
A 0.8395-approximation algorithm for the EPR problem
Anuj Apte, Eunou Lee, Kunal Marwaha +3
We give an efficient 0.8395-approximation algorithm for the EPR Hamiltonian. Our improvement comes from a new nonlinear monogamy-of-entanglement bound on star graphs and a refined…
No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
Ojas Parekh
Decoded Quantum Interferometry (DQI) is a framework for approximating special kinds of discrete optimization problems that relies on problem structure in a way that sets it apart f…
Conjectured Bounds for 2-Local Hamiltonians via Token Graphs
Anuj Apte, Ojas Parekh, James Sud
We explain how the maximum energy of the Quantum MaxCut, XY, and EPR Hamiltonians on a graph are related to the spectral radii of the token graphs of . From numerical study,…
Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings
Anuj Apte, Eunou Lee, Kunal Marwaha +2
We introduce a -approximation algorithm for Quantum MaxCut and a -approximation algorithm for the EPR Hamiltonian of [arXiv:2209.02589].…