Commuting Local Hamiltonian Problem on 2D beyond qubits

• URL: http://arxiv.org/abs/2309.04910v1
• Date: Sun, 10 Sep 2023 01:43:48 GMT
• Title: Commuting Local Hamiltonian Problem on 2D beyond qubits
• Authors: Sandy Irani, Jiaqing Jiang
• Abstract summary: We study the complexity of local Hamiltonians in which the terms pairwise commute. CLHs provide a way to study the role of non-commutativity in the complexity of quantum systems.
• Score: 0.8333246626497363
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of local Hamiltonians in which the terms pairwise commute. Commuting local Hamiltonians (CLHs) provide a way to study the role of non-commutativity in the complexity of quantum systems and touch on many fundamental aspects of quantum computing and many-body systems, such as the quantum PCP conjecture and the area law. Despite intense research activity since Bravyi and Vyalyi introduced the CLH problem two decades ago [BV03], its complexity remains largely unresolved; it is only known to lie in NP for a few special cases. Much of the recent research has focused on the physically motivated 2D case, where particles are located on vertices of a 2D grid and each term acts non-trivially only on the particles on a single square (or plaquette) in the lattice. In particular, Schuch [Sch11] showed that the CLH problem on 2D with qubits is in NP. Aharonov, Kenneth and Vigdorovich~[AKV18] then gave a constructive version of this result, showing an explicit algorithm to construct a ground state. Resolving the complexity of the 2D CLH problem with higher dimensional particles has been elusive. We prove two results for the CLH problem in 2D: (1) We give a non-constructive proof that the CLH problem in 2D with qutrits is in NP. As far as we know, this is the first result for the commuting local Hamiltonian problem on 2D beyond qubits. Our key lemma works for general qudits and might give new insights for tackling the general case. (2) We consider the factorized case, also studied in [BV03], where each term is a tensor product of single-particle Hermitian operators. We show that a factorized CLH in 2D, even on particles of arbitrary finite dimension, is equivalent to a direct sum of qubit stabilizer Hamiltonians. This implies that the factorized 2D CLH problem is in NP. This class of CLHs contains the Toric code as an example.

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)
• Commuting Local Hamiltonians Beyond 2D [0.09208007322096534]
  We present a new technique to analyze the complexity of commuting local Hamiltonians. We show that a larger family of commuting local Hamiltonians is in NP. This is the first time a family of 3D commuting local Hamiltonians has been contained in NP.
  arXiv  Detail & Related papers  (2024-10-14T13:40:54Z)
• KPZ scaling from the Krylov space [83.88591755871734]
  Recently, a superdiffusion exhibiting the Kardar-Parisi-Zhang scaling in late-time correlators and autocorrelators has been reported. Inspired by these results, we explore the KPZ scaling in correlation functions using their realization in the Krylov operator basis.
  arXiv  Detail & Related papers  (2024-06-04T20:57:59Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Reduced Density Matrices and Moduli of Many-Body Eigenstates [1.261852738790008]
  eigenstate moduli problem is closely related to the $N$-representability conditions for 2-reduced density matrices. Despite its importance, the eigenstate moduli problem remains largely unexplored in the literature.
  arXiv  Detail & Related papers  (2023-01-04T03:14:07Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• A first-principles calculation of electron-phonon interactions for the $\text{C}_2\text{C}_\text{N}$ and $\text{V}_\text{N}\text{N}_\text{B}$ defects in hexagonal boron nitride [52.77024349608834]
  Quantum emitters in two-dimensional hexagonal boron nitride (h-BN) have generated significant interest. Recent observations of Fourier transform (FT) limited photons emitted from h-BN flakes at room temperature.
  arXiv  Detail & Related papers  (2022-07-28T23:31:38Z)
• Improved Hardness Results for the Guided Local Hamiltonian Problem [1.53934570513443]
  Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. We show that the BQP-completeness persists even with 2-local Hamiltonians. We also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians.
  arXiv  Detail & Related papers  (2022-07-21T01:13:32Z)
• Non-NP-Hardness of Translationally-Invariant Spin-Model Problems [0.0]
  We show that finding the ground state energy of the Heisenberg model cannot be an NP-Hard problem unless P=NP. The result hints at the potential tractability of the problem and encourages further research towards a positive complexity result.
  arXiv  Detail & Related papers  (2021-11-19T08:38:52Z)
• Mesoscopic quantum superposition states of weakly-coupled matter-wave solitons [58.720142291102135]
  We establish quantum features of an atomic soliton Josephson junction (SJJ) device. We show that the SJJ-model in quantum domain exhibits unusual features due to its effective nonlinear strength proportional to the square of total particle number. We have shown that the obtained quantum state is more resistant to few particle losses from the condensates if tiny components of entangled Fock states are present.
  arXiv  Detail & Related papers  (2020-11-26T09:26:19Z)
• Einselection from incompatible decoherence channels [62.997667081978825]
  We analyze an open quantum dynamics inspired by CQED experiments with two non-commuting Lindblad operators. We show that Fock states remain the most robust states to decoherence up to a critical coupling.
  arXiv  Detail & Related papers  (2020-01-29T14:15:19Z)

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.