harvard6The DASH digital repository system captures, stores, indexes, preserves, and distributes digital research material.https://dash.harvard.edu:4432024-03-19T07:09:44Z2024-03-19T07:09:44ZBeyond Product State Approximations for a Quantum Analogue of Max CutAnshu, AnuragGosset, DavidMorenz, Karenhttps://nrs.harvard.edu/1/373779902024-03-18T20:48:40Z2020-03-31T04:00:00ZBeyond Product State Approximations for a Quantum Analogue of Max Cut
Anshu, Anurag; Gosset, David; Morenz, Karen
We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem's approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3- or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).
2020-03-31T04:00:00ZEntanglement spread area law in gapped ground statesAnshu, AnuragHarrow, Aram W.Soleimanifar, Mehdihttps://nrs.harvard.edu/1/373779892024-03-18T20:43:30Z2022-09-15T04:00:00ZEntanglement spread area law in gapped ground states
Anshu, Anurag; Harrow, Aram W.; Soleimanifar, Mehdi
In this work, we make a connection between two seemingly different problems. The first problem involves characterizing the properties of entanglement in the ground state of gapped local Hamiltonians, which is a central topic in quantum many-body physics. The second problem is on the quantum communication complexity of testing bipartite states with EPR assistance, a well-known question in quantum information theory. We construct a communication protocol for testing (or measuring) the ground state and use its communication complexity to reveal a new structural property for the ground state entanglement. This property, known as the entanglement spread, roughly measures the ratio between the largest and the smallest Schmidt coefficients across a cut in the ground state. Our main result shows that gapped ground states possess limited entanglement spread across any cut, exhibiting an "area law" behavior. Our result quite generally applies to any interaction graph with an improved bound for the special case of lattices. This entanglement spread area law includes interaction graphs constructed in [Aharonov et al., FOCS'14] that violate a generalized area law for the entanglement entropy. Our construction also provides evidence for a conjecture in physics by Li and Haldane on the entanglement spectrum of lattice Hamiltonians [Li and Haldane, PRL'08]. On the technical side, we use recent advances in Hamiltonian simulation algorithms along with quantum phase estimation to give a new construction for an approximate ground space projector (AGSP) over arbitrary interaction graphs.
2022-09-15T04:00:00ZAn area law for 2d frustration-free spin systemsAnshu, AnuragArad, ItaiGosset, Davidhttps://nrs.harvard.edu/1/373779882024-03-18T20:38:19Z2022-06-09T04:00:00ZAn area law for 2d frustration-free spin systems
Anshu, Anurag; Arad, Itai; Gosset, David
We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the lattice into left and right regions. We first establish that the ground state projector of any locally gapped frustration-free 1D spin system can be approximated to within error ϵ by a degree O(nlog(ϵ−1)‾‾‾‾‾‾‾‾‾√) multivariate polynomial in the interaction terms of the Hamiltonian. This generalizes the optimal bound on the approximate degree of the boolean AND function, which corresponds to the special case of commuting Hamiltonian terms. For 2D spin systems we then construct an approximate ground state projector (AGSP) that employs the optimal 1D approximation in the vicinity of the boundary of the bipartition of interest. This AGSP has sufficiently low entanglement and error to establish the area law using a known technique.
2022-06-09T04:00:00ZCircuit Lower Bounds for Low-Energy States of Quantum Code HamiltoniansAnshu, AnuragNirkhe, Chinmayhttps://nrs.harvard.edu/1/373779872024-03-18T20:32:50Z2021-09-10T04:00:00ZCircuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians
Anshu, Anurag; Nirkhe, Chinmay
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes.
For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.
2021-09-10T04:00:00Z