THE QUANTUM INTELLIGENCER

A paper deposited on the arXiv takes up the class of redundancy-free Hamiltonians, those for which the trace vanishes for any product of Hamiltonian terms in which at least one term appears an odd number of times. The class includes sums of products of Pauli operators with no relations among them, and it arises naturally in Hamiltonian Decoded Quantum Interferometry, a scheme that separates the hardness of state preparation into a classical decoding step and a step preparing the thermofield double state of such a Hamiltonian. The paper reports that for these Hamiltonians the problem becomes easy at quadratically lower temperature than for a general Hamiltonian, the complexity at inverse temperature β turning on β²d, with d the degree of the anticommutation graph. For small β²d the authors supply an efficient classical algorithm for approximating the partition function; for large β²d they show the approximation is NP-hard, introducing what they call an anticommutation glass, whose frustration arises purely from anticommutation relations. They give a subexponential-time quantum algorithm for the thermofield state at small β²d, results toward a polynomial-time algorithm based on the Feiguin-Klich Hamiltonian, and, as a point of independent interest, a polynomial-time algorithm for preparing thermofield double states of general Hamiltonians on an interaction graph of degree d for β ≲ 1/d. Estimating the ground state energy of redundancy-free Hamiltonians is also shown to be QMA-complete. The paper is a preprint, and the usual reserve applies: it does not establish that Hamiltonian DQI as a whole has become easy, the improvement being confined to the state-preparation step and to the stated conditions. Worth cataloguing for the archives, nonetheless. Nor does the paper establish what a hasty reading might take from it. The efficient regime at small β²d is established only for redundancy-free Hamiltonians, not for the general class, and the threshold is a statement about the mathematics, not about any instrument that has been built. The QMA-completeness of ground-state energy estimation is a hardness classification, not a means of performing the estimation; it tells the engineer that the problem belongs to a difficult family, and it offers no method for the practical case. The polynomial-time result for general Hamiltonians at β ≲ 1/d is a bound on a particular construction, and it is not a claim that any physical thermofield double state can be prepared at those temperatures in a laboratory. The results toward a polynomial-time algorithm based on the Feiguin-Klich Hamiltonian are described by the authors themselves as results toward something, not as the finished algorithm. No experiment is reported in the paper, so nothing follows from these pages about the behaviour of real hardware. What the paper does establish is a redrawn boundary of hardness, and that boundary is drawn on paper. Let the scope be stated plainly. Every positive result in the paper is conditioned on the redundancy-free property: the efficient classical algorithm, the subexponential quantum algorithm, and the results toward a polynomial algorithm all concern Hamiltonians in that class. A Hamiltonian with relations among its terms may behave differently, and to say that no theorem here covers it is not to say that it misbehaves, merely that the paper draws no boundary around it. The degree d enters through the anticommutation graph, so the β²d scaling is a statement about that graph, not a universal thermometer. The anticommutation glass is introduced as a construction for proof, a place where frustration arises because anticommutation forces it to; it is not presented as a catalogue of materials a laboratory should send away for. Narrowness of this kind is a virtue in complexity theory: it tells the engineer precisely which door has been opened, and the rest of the wall stands where it stood. —Ada H. Pemberley Dispatch from The Prepared E0