Public-key pseudoentanglement and the hardness of learning ground state entanglement structure

• URL: http://arxiv.org/abs/2311.12017v1
• Date: Mon, 20 Nov 2023 18:54:48 GMT
• Title: Public-key pseudoentanglement and the hardness of learning ground state entanglement structure
• Authors: Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh Vazirani, Chenyi Zhang, Zixin Zhou
• Abstract summary: Given a local Hamiltonian, how difficult is it to determine the entanglement structure of its ground state? We show that this problem is computationally intractable even if one is only trying to decide if the ground state is volume-law vs near area-law entangled. Our work opens new directions in Hamiltonian complexity, for example whether it is difficult to learn certain phases of matter.
• Score: 2.1808110832567125
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a local Hamiltonian, how difficult is it to determine the entanglement structure of its ground state? We show that this problem is computationally intractable even if one is only trying to decide if the ground state is volume-law vs near area-law entangled. We prove this by constructing strong forms of pseudoentanglement in a public-key setting, where the circuits used to prepare the states are public knowledge. In particular, we construct two families of quantum circuits which produce volume-law vs near area-law entangled states, but nonetheless the classical descriptions of the circuits are indistinguishable under the Learning with Errors (LWE) assumption. Indistinguishability of the circuits then allows us to translate our construction to Hamiltonians. Our work opens new directions in Hamiltonian complexity, for example whether it is difficult to learn certain phases of matter.

Related papers

• On the hardness of learning ground state entanglement of geometrically local Hamiltonians [2.6034750171634107]
  Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our work suggests that the problem of learning so-called "gapless" phases of matter might be intractable.
  arXiv  Detail & Related papers  (2024-11-07T01:16:15Z)
• $W$ state is not the unique ground state of any local Hamiltonian [0.0]
  characterization of ground states among all quantum states is an important problem in quantum many-body physics. We introduce a new class of simple states, including the $W$ state, that can only occur as a ground state alongside an exactly degenerate partner.
  arXiv  Detail & Related papers  (2023-10-16T18:00:01Z)
• Comment on "Can Neural Quantum States Learn Volume-Law Ground States?" [44.99833362998488]
  We show that suitably chosen NQS can learn ground states with volume-law entanglement both for spin and fermionic problems. We argue that the setup utilized in the aforementioned letter reveals the inefficiency of non-fermionic NQS to learn fermionic states.
  arXiv  Detail & Related papers  (2023-09-20T14:44:04Z)
• Local Hamiltonian Problem with succinct ground state is MA-Complete [0.788657961743755]
  Finding the ground energy of a quantum system is a fundamental problem in condensed matter physics and quantum chemistry. Existing classical algorithms for tackling this problem often assume that the ground state has a succinct classical description. We study the complexity of the local Hamiltonian problem with succinct ground state and prove it is MA-Complete.
  arXiv  Detail & Related papers  (2023-09-18T21:08:51Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Schr\"odinger cat states of a 16-microgram mechanical oscillator [54.35850218188371]
  The superposition principle is one of the most fundamental principles of quantum mechanics. Here we demonstrate the preparation of a mechanical resonator with an effective mass of 16.2 micrograms in Schr"odinger cat states of motion. We show control over the size and phase of the superposition and investigate the decoherence dynamics of these states.
  arXiv  Detail & Related papers  (2022-11-01T13:29:44Z)
• Learning entanglement breakdown as a phase transition by confusion [0.0]
  We develop an approach for revealing entanglement breakdown using a machine learning technique, which is known as 'learning by confusion' We show that the developed method provides correct answers for a variety of states, including entangled states with positive partial transpose (PPT) We also present a more practical version of the method, which is suitable for studying entanglement breakdown in noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2022-02-01T11:41:18Z)
• Determining ground-state phase diagrams on quantum computers via a generalized application of adiabatic state preparation [61.49303789929307]
  We use a local adiabatic ramp for state preparation to allow us to directly compute ground-state phase diagrams on a quantum computer via time evolution. We are able to calculate an accurate phase diagram on both two and three site systems using IBM quantum machines.
  arXiv  Detail & Related papers  (2021-12-08T23:59:33Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware. We present an algorithm that compresses the Trotter steps into a single block of quantum gates. This results in a fixed depth time evolution for certain classes of Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T19:38:01Z)
• Operational Resource Theory of Imaginarity [48.7576911714538]
  We show that quantum states are easier to create and manipulate if they only have real elements. As an application, we show that imaginarity plays a crucial role for state discrimination.
  arXiv  Detail & Related papers  (2020-07-29T14:03:38Z)
• From communication complexity to an entanglement spread area law in the ground state of gapped local Hamiltonians [16.951941479979716]
  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. The second problem is on the quantum communication complexity of testing bipartite states with EPR assistance.
  arXiv  Detail & Related papers  (2020-04-30T17:54:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.