Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a d_A-dimensional and d_B-dimensional qudit pair, denoted (d_A×d_B)-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain QMA_1-hard, in that (2×5)-QSAT is QMA_1-complete. (QMA_1 is a quantum analogue of MA with perfect completeness.) In contrast, (2×2)-QSAT (i.e. Quantum 2-SAT on qubits) is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that (3×d)-QSAT on the 1D line with d ∈ O(1) is also QMA_1-hard. Finally, we initiate the study of (2×d)-QSAT on the 1D line by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state.

As implied by our title, our first result uses a direct embedding: We combine a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset and Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from Ω(1/T⁶) to Ω(1/T²), for T the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian H on d'-dimensional qudits, we show how to embed it into an effective 1D (3×d)-QSAT instance, for d ∈ O(1). Our approach may be viewed as a weaker notion of "analog simulation" (à la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based QMA_1-hardness result.

Adiabatic measurements, followed by feedback and erasure protocols, have often been considered as a model to embody Maxwell’s Demon paradox and to study the interplay between thermodynamics and information processing. Such studies have led to the conclusion, now widely accepted in the community, that Maxwell’s Demon and the second law of thermodynamics can peacefully coexist because any gain provided by the demon must be offset by the cost of performing the measurement and resetting the demon’s memory to its initial state. Statements of this kind are collectively referred to as second laws of information thermodynamics and have recently been extended to include quantum theoretical scenarios. However, previous studies in this direction have made several assumptions, particularly about the feedback process and the demon’s memory readout, and thus arrived at statements that are not universally applicable and whose range of validity is not clear. In this work, we fill this gap by precisely characterizing the full range of quantum feedback control and erasure protocols that are overall consistent with the second law of thermodynamics. This leads us to conclude that the second law of information thermodynamics is indeed universal: it must hold for any quantum feedback control and erasure protocol, regardless of the measurement process involved, as long as the protocol is overall compatible with thermodynamics. Our comprehensive analysis not only encompasses new scenarios but also retrieves previous ones, doing so with fewer assumptions. This simplification contributes to a clearer understanding of the theory.

We propose a vertex representation of the tensor network (TN) for classical spin systems on hyperbolic lattices. The tensors form a network of regular p-sided polygons (p > 4) with the coordination number 4. The response to multistate spin systems on the hyperbolic TN is analyzed for their entire parameter space. We show that entanglement entropy is sensitive to distinguish various hyperbolic geometries, whereas other thermodynamic quantities are not. We test the numerical accuracy of vertex TNs in the phase transitions of the first, second, and infinite order at the point of maximal entanglement entropy. The hyperbolic structure of TNs induces noncritical properties in the bulk, although boundary conditions significantly affect the total free energy in the thermodynamic limit. Thus a developed vertex-type TN can be used for the lowest-energy quantum states on the hyperbolic lattices.

In the quest for robust and universal quantum devices, the notion of simulation plays a crucial role, both from a theoretical and from an applied perspective. In this work, we go beyond the simulation of quantum channels and quantum measurements, studying what it means to simulate a collection of measurements, which we call a multimeter. To this end, we first explicitly characterize the completely positive transformations between multimeters. However, not all of these transformations correspond to valid simulations, as otherwise we could create any resource from nothing. For example, the set of transformations includes maps that always prepare the same multimeter regardless of the input, which we call trash-and-prepare. From the perspective of an experimenter with a given multimeter as part of a complicated setup, having to discard the multimeter and using a different one instead is undesirable. We give a new definition of multimeter simulations as transformations that are triviality-preserving, i.e., when given a multimeter consisting of trivial measurements they can only produce another trivial multimeter. In the absence of a quantum ancilla, we then characterize the transformations that are triviality-preserving and the transformations that are trash-and-prepare. Finally, we use these characterizations to compare our new definition of multimeter simulation to three existing ones: classical simulations, compression of multimeters, and compatibility-preserving simulations.