Improved approximation algorithms for the EPR Hamiltonian
By: Nathan Ju, Ansh Nagda
Potential Business Impact:
Finds best energy for quantum computers.
The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time $\frac{1+\sqrt{5}}{4}\approx 0.809$-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of $0.72$ (arXiv:2410.15544). As a special case, this also implies a $\frac{1+\sqrt{5}}{4}$-approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of $3/4$ that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).
Similar Papers
A 0.8395-approximation algorithm for the EPR problem
Quantum Physics
Finds better ways to use quantum computers.
Conjectured Bounds for 2-Local Hamiltonians via Token Graphs
Quantum Physics
Finds better ways to solve hard math problems.
3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
quant-ph
Proves quantum computers can't solve some problems faster.