Complexity

Abstract: We study the problem of approximating the partition function of the transverse-field Ising model (TFIM), a widely studied quantum many-body model with important applications in quantum simulation and quantum annealing. Despite its fundamental importance, the algorithmic landscape for computing the TFIM partition function has remained poorly understood beyond restricted parameter regimes. We provide a precise characterization of the temperature regimes in which efficient approximation is possible, establishing a sharp computational phase transition. Let $J$ denote the symmetric interaction matrix and $\Delta(J) = \lambda_{\max}(J)-\lambda_{\min}(J)$ be its spectral width. We show that for all inverse temperatures $\beta \in [0,1/\Delta(J)]$, there exists an efficient classical randomized algorithm that approximates the partition function $\tr(e^{-\beta H})$ to within an arbitrarily small multiplicative factor. We apply the standard Trotter decomposition to map the quantum model to a classical spin system, then leverage new techniques in Markov chain analysis to show an efficient algorithm that samples from and computes the partition function of the resulting distribution. This temperature threshold is tight: for $\beta > 1/\Delta(J)$, we show that approximating the partition function is NP-hard and thus is unlikely to admit an efficient classical or quantum algorithm.

Abstract: We study the circuit width problem introduced by Montanaro in the polynomial representation of quantum circuits over the gate set ({H,Z,\mathrm{CZ},\mathrm{CCZ}}). In this framework, a circuit corresponds to a low‑degree polynomial over (\mathbb{F}_2), and the circuit width (w(f)) is the minimum number of qubits among circuits realizing a given polynomial (f). This parameter governs the precision with which a quantum computer can approximate the gap of (f), motivating the complexity of minimizing (w(f)). We prove that deciding whether (w(f)\le k) is NP‑complete, and that approximating (w(f)) within any factor better than (49/48-\epsilon) is NP‑hard. This inapproximability persists even for degree‑2 polynomials, showing that the hardness is gate‑set independent for common quadratic gate sets. On the algorithmic side, we give a nondeterministic polynomial‑time search algorithm with witness size (O(k\log(n/k))), yielding an XP algorithm by enumeration, and a fixed‑parameter tractable algorithm running in time (k^{O(k)}\cdot n). These results resolve Montanaro’s open question and place circuit width firmly within classical complexity theory while providing efficient algorithms for small width.