8 papers · 1 filter
The QAOA on the ring of disagrees
Kunal Marwaha
We study the performance of symmetric local algorithms finding large cuts on the cycle graph. Such algorithms that cannot see the whole graph at depth p cut at most a (2p+1)/(2p+2)…
On the Complexity of Decoded Quantum Interferometry
Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu +1
We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. First, we show that the algorithm resists classical simulation st…
A complexity phase transition at the EPR Hamiltonian
Kunal Marwaha, James Sud
We study the computational complexity of 2-local Hamiltonian problems generated by a positive-weight symmetric interaction term, encompassing many canonical problems in statistical…
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…
Superposition detection and QMA with non-collapsing measurements
Roozbeh Bassirian, Kunal Marwaha
We prove that QMA where the verifier may also make a single non-collapsing measurement is equal to NEXP, resolving an open question of Aaronson. We show this is a corollary to a mo…
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].…