Complexity 4

Abstract: In this work, we present new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarithm of the determinant of sparse, well-conditioned, positive matrices can be approximated to $\varepsilon$-relative accuracy in time polylogarithmic in the dimension~$N$, specifically in time~$\mathrm{poly}(\mathrm{log}(N), s, \kappa, 1/\varepsilon)$, where $s$ is the sparsity and $\kappa$ the condition number of the input matrix. We provide a simple dequantization of these techniques that preserves the polylogarithmic dependence on the dimension, at the cost of worse scaling in the sparsity, condition number, and accuracy. Our classical algorithm runs in time~$\mathrm{poly}\mathrm{log}(N)\cdot s^{O(\sqrt{\kappa}\log \kappa/\varepsilon)}$ which constitutes an exponential improvement over previous classical algorithms in certain parameter regimes. In addition, we prove $\mathsf{DQC}1$-completeness for estimating specific spectral sums such as the trace of the inverse and the trace of matrix powers with analogous parameter scalings as the quantum algorithms for the log-determinant in the case of log-local Hamiltonians. The latter solves a main open problem posed by Cade and Montanaro (TQC 2018) and is closely related to the complexity of Schatten $p$-norm estimation. It further shows that the parameter scalings of known quantum algorithms are not achievable classically, assuming~$\mathsf{BPP}\subsetneq\mathsf{DQC}1$. Further, we also consider a different input model where instead of a classical description of a sparse matrix, we are given a block-encoding of it and analyze the complexity of spectral sum estimation in this model. We obtain $\mathsf{DQC}1$-completeness of estimating $\mathrm{tr}[f(A)]$ in this model in a very general way, in particular whenever $f$ and $f^{-1}$ are Lipschitz continuous with bounded Lipschitz constants. We conclude our work with $\mathsf{BQP}$-hardness and $\mathsf{PP}$-completeness results on the estimation of the log-determinant.

Abstract: We develop classical simulation algorithms for adaptive quantum circuits that produce states with low levels of "magic" (i.e., non-stabilizerness). These algorithms are particularly well-suited to circuits with high rates of Pauli measurements, such as those encountered in quantum error correction and monitored quantum circuits. The measurements serve to limit the buildup of magic induced by non-Clifford operations arising from generic noise processes or unitary gates, respectively. Our algorithms also allow a systematic truncation procedure to achieve approximate simulation. To benchmark our approach, we study the dynamics of all-to-all monitored quantum circuits with a sub-extensive rate of T-gates per unit of circuit depth, where we can simulate previously inaccessible system sizes and depths. We characterize measurement-induced phase transitions in the output wavefunction, including in the entanglement, purification, and magic. We outline the utility of our algorithms to simulate dynamics with low magic and high entanglement, complementary to the leading matrix-product state approaches.

Abstract: Classical simulation of quantum circuits is a critical tool for validating quantum hardware and probing the boundary between classical and quantum computational power. Existing state-of-the-art methods, notably tensor network approaches, have computational costs governed by the treewidth of the underlying circuit graph, making circuits with large treewidth intractable. This work rigorously analyzes FeynmanDD, a decision diagram-based simulation method proposed in CAV 2025 by a subset of the authors, and shows that the size of the multi-terminal decision diagram used in FeynmanDD is exponential in the linear rank-width of the circuit graph. As linear rank-width can be substantially smaller than treewidth and is at most larger than the treewidth by a logarithmic factor, our analysis demonstrates that FeynmanDD outperforms all tensor network-based methods for certain circuit families. We also show that the method remains efficient if we use the Solovay-Kitaev algorithm to expand arbitrary single-qubit gates to sequences of Hadamard and T gates, essentially removing the gate-set restriction posed by the method.