On The Complexity of Redundancy-Free Quantum Hamiltonians

Abstract

We consider a class of redudancy-free Hamiltonians, which are those where the trace vanishes for any product of Hamiltonian terms in which at least one term appears an odd number of times. This includes Hamiltonians which are sums of products of Paulis with no relations between them. These Hamiltonians arise naturally in Hamiltonian Decoded Quantum Interferometry, which separates the hardness of preparing quantum states into two steps: a classical decoding step, and a step preparing the thermofield double state of such a redundancy-free Hamiltonian. We focus on the hardness of these Hamiltonians, both for intrinsic interest and to understand the complexity of the state preparation step in Hamiltonian DQI. We present several results showing that the problem becomes easy at quadratically lower temperature than for a general Hamiltonian, with the complexity at given inverse temperature β depending on β² d, where d is the degree of the anticommutation graph. We give an efficient classical algorithm for small β² d to approximate the partition function, while for large β² d we show that approximating the partition function is NP-hard. To this end, we introduce what we call an anticommutation glass, where frustration arises purely from anticommutation relations. We give a subexponential time quantum algorithm to prepare the thermofield state for small β² d, and present some results toward a polynomial time algorithm based on the Feiguin-Klich Hamiltonian. As a result of possible independent interest, we show that this Hamiltonian leads to a polynomial time algorithm for preparing thermofield double states of general Hamiltonians on an interaction graph of degree d for β≲ 1/d. Finally, we show that estimating the ground state energy of redundancy-free Hamiltonians is QMA-complete.

Quantum Complexity of Ancilla-Free Unitary Embeddings for Nonlinear Dynamics via Generalized State-Dependent Double-Bracket Flows
Yuki Ito, Hideaki Hakoshima, Keisuke Fujii
arXiv29 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
The Complexity of Single-Interaction Hamiltonians
Elad Hecker
arXiv30 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
Dominic Lowe, M. S. Kim, Roberto Bondesan +1
arXiv29 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Algebra of free fermions: Classifying spaces, Hamiltonians, and computation
Tian Yuan, Yang Qi
arXiv3 Sep 2026PreprintarXiv licenceFull textMathematical physics Condensed matterarXiv
Optimal Intermediate Hamiltonians for Non-Equilibrium Free Energy Calculations: A Numerical Study of Markov Models
David Beyer, Helmut Grubmüller
arXiv9 Sep 2026PreprintarXiv licenceFull textCondensed matter Statistical & nonlinear physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{hastings2026complexity,
  title = {{On The Complexity of Redundancy-Free Quantum Hamiltonians}},
  author = {Matthew B. Hastings and Alexander Schmidhuber},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.03697},
  eprint = {2610.03697},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.03697},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - On The Complexity of Redundancy-Free Quantum Hamiltonians
AU  - Matthew B. Hastings
AU  - Alexander Schmidhuber
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2610.03697
UR  - https://arxiv.org/abs/2610.03697
AB  - We consider a class of redudancy-free Hamiltonians, which are those where the trace vanishes for any product of Hamiltonian terms in which at least one term appears an odd number of times. This includes Hamiltonians which are sums of products of Paulis with no relations between them. These Hamiltonians arise naturally in Hamiltonian Decoded Quantum Interferometry, which separates the hardness of preparing quantum states into two steps: a classical decoding step, and a step preparing the thermofield double state of such a redundancy-free Hamiltonian. We focus on the hardness of these Hamiltonians, both for intrinsic interest and to understand the complexity of the state preparation step in Hamiltonian DQI. We present several results showing that the problem becomes easy at quadratically lower temperature than for a general Hamiltonian, with the complexity at given inverse temperature β depending on β^2 d, where d is the degree of the anticommutation graph. We give an efficient classical algorithm for small β^2 d to approximate the partition function, while for large β^2 d we show that approximating the partition function is NP-hard. To this end, we introduce what we call an anticommutation glass, where frustration arises purely from anticommutation relations. We give a subexponential time quantum algorithm to prepare the thermofield state for small β^2 d, and present some results toward a polynomial time algorithm based on the Feiguin-Klich Hamiltonian. As a result of possible independent interest, we show that this Hamiltonian leads to a polynomial time algorithm for preparing thermofield double states of general Hamiltonians on an interaction graph of degree d for β≲ 1/d. Finally, we show that estimating the ground state energy of redundancy-free Hamiltonians is QMA-complete.
ER  -

Abstract

Related

Cite