Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis

• URL: http://arxiv.org/abs/2211.05325v1
• Date: Thu, 10 Nov 2022 04:12:20 GMT
• Title: Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis
• Authors: Michael J. Bremner, Zhengfeng Ji, Xingjian Li, Luke Mathieson, Mauro E.S. Morales
• Abstract summary: We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem. The relevant quantum states are superpositions of computational basis states of Hamming weight $k$. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy.
• Score: 3.7179456510537694
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight $k$. The Hamming weight constraint can have a physical interpretation as a constraint on the number of excitations allowed or particle number in a system. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy and that it is hard for QM[1], the quantum analogue of M[1]. Our results show that this problem cannot be fixed-parameter quantum tractable (FPQT) unless certain natural quantum analogue of the exponential time hypothesis (ETH) is false.

Related papers

• Rapidly Achieving Chemical Accuracy with Quantum Computing Enforced Language Model [22.163742052849432]
  QiankunNet-VQE is a transformer based language models enforced with quantum computing to learn and generate quantum states. It has been implemented using up to 12 qubits and attaining an accuracy level competitive with state-of-the-art classical methods.
  arXiv  Detail & Related papers  (2024-05-15T07:50:57Z)
• Computational supremacy in quantum simulation [22.596358764113624]
  We show that superconducting quantum annealing processors can generate samples in close agreement with solutions of the Schr"odinger equation. We conclude that no known approach can achieve the same accuracy as the quantum annealer within a reasonable timeframe.
  arXiv  Detail & Related papers  (2024-03-01T19:00:04Z)
• Coherence generation with Hamiltonians [44.99833362998488]
  We explore methods to generate quantum coherence through unitary evolutions. This quantity is defined as the maximum derivative of coherence that can be achieved by a Hamiltonian. We identify the quantum states that lead to the largest coherence derivative induced by the Hamiltonian.
  arXiv  Detail & Related papers  (2024-02-27T15:06:40Z)
• Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
  We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem. These problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We show that guidable local Hamiltonian problems for both classes of guiding states are $mathsfQCMA$-complete in the inverse-polynomial precision setting.
  arXiv  Detail & Related papers  (2023-02-22T19:00:00Z)
• Hamiltonian variational ansatz without barren plateaus [0.0]
  Variational quantum algorithms are one of the most promising applications of a near-term quantum computer. Despite their huge potential, the utility of variational quantum algorithms beyond tens of qubits is still questioned.
  arXiv  Detail & Related papers  (2023-02-16T19:01:26Z)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement. Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
  arXiv  Detail & Related papers  (2023-01-23T19:23:54Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Efficient ground state preparation in variational quantum eigensolver with symmetry-breaking layers [0.0]
  Variational quantum eigensolver (VQE) solves the ground state problem of a given Hamiltonian by finding the parameters of a quantum circuit ansatz. We show that the proposed ansatz finds the ground state in depth significantly shorter than the bare HVA when the target Hamiltonian has symmetry-broken ground states.
  arXiv  Detail & Related papers  (2021-06-04T14:25:48Z)
• Importance of the spectral gap in estimating ground-state energies [0.0]
  The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian.
  arXiv  Detail & Related papers  (2020-07-22T18:00:00Z)
• Unraveling the topology of dissipative quantum systems [58.720142291102135]
  We discuss topology in dissipative quantum systems from the perspective of quantum trajectories. We show for a broad family of translation-invariant collapse models that the set of dark state-inducing Hamiltonians imposes a nontrivial topological structure on the space of Hamiltonians.
  arXiv  Detail & Related papers  (2020-07-12T11:26:02Z)
• Sample-efficient learning of quantum many-body systems [17.396274240172122]
  We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs state. We give the first sample-efficient algorithm for the quantum Hamiltonian learning problem.
  arXiv  Detail & Related papers  (2020-04-15T18:01:59Z)

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.