5 papers
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,…
An improved Quantum Max Cut approximation via matching
Eunou Lee, Ojas Parekh
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quan…
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…
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].…