Algorithms 11

Abstract: Performing large-scale, accurate quantum simulations of many-fermion systems is a central challenge in quantum science, with applications in chemistry, materials, and high-energy physics. Despite significant progress, realizing generic fermionic algorithms with qubit systems incurs significant space-time overhead, scaling as $O(N)$ for $N$ fermionic modes. Here we present a method for faster fermionic simulation with asymptotic space-time overhead of $O(\log(N))$ in the worst case, and $O(1)$ for circuits with additional structure, including important subroutines like the fermionic fast Fourier transform. This exponential reduction is achieved by using reconfigurable quantum systems with non-local connectivity, mid-circuit measurement, and classical feedforward, to generate dynamical fermion-to-qubit mappings. We apply this technique to achieve efficient compilation for key simulation tasks, including Hamiltonian simulation of the sparse Sachdev–Ye–Kitaev model and periodic materials, as well as free-fermion state-preparation. Moreover, we show that the algorithms themselves can be adapted to use only the $O(1)$-overhead structures to further reduce resource overhead. These techniques can lower gate counts by orders of magnitude for practical system sizes and are natively compatible with error corrected computation, making them ideal for early fault-tolerant quantum devices. Our results tightly bound the computational gap between fermionic and qubit models and open new directions in quantum simulation algorithm design and implementation.

Abstract: Quantum phase estimation (QPE) and Lindbladian dynamics are both foundational in quantum information science and central to quantum algorithm design. In this work, we bridge these two concepts: certain simple Lindbladian processes can be adapted to perform QPE-type tasks. However, unlike QPE, which achieves Heisenberg-limit scaling, these Lindbladian evolutions are restricted to standard quantum limit complexity. This indicates that, different from Hamiltonian dynamics, the natural dissipative evolution speed of such Lindbladians does not saturate the fundamental quantum limit, thereby suggesting the potential for quadratic fast-forwarding. We confirm this by presenting a quantum algorithm that simulates these Lindbladians for time $t$ within an error $\varepsilon$ using $\mathcal{O}\left(\sqrt{t\log(\varepsilon^{-1})}\right)$ cost. This, to our knowledge, is the first example of Lindbladian fast forwarding, which shares a fundamentally different mechanism from the fast-forwarding examples of Hamiltonian dynamics. As a bonus, this fast-forwarded simulation naturally serves as a new Heisenberg-limit QPE algorithm. Therefore, our work explicitly bridges the standard quantum limit-Heisenberg limit transition to the fast-forwarding of dissipative dynamics. We also adopt our fast-forwarding algorithm for efficient Gibbs state preparation and demonstrate the counter-intuitive implication: the allowance of a quadratically accelerated decoherence effect under arbitrary Pauli noise.

Abstract: The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low- energy Hamiltonians even when the gap between "high" and "low" energy is large (constant). A natural proof strategy is gap amplification: start from the fact that high- and low-energy Hamiltonians are hard to distinguish if the gap is small (inverse polynomial) [KSV02] and amplify the Hamiltonians to increase the energy gap while preserving hardness. Such a gap amplification procedure is at the heart of Dinur’s proof of the classical PCP theorem [Din07]. In this work, following Dinur’s model, we introduce a new quantum gap amplification procedure for Hamiltonians which uses random walks on expander graphs to derandomise (subsample the terms of) the tensor product amplification of a Hamiltonian. Curiously, our analysis relies on a new technique inspired by quantum de Finetti theorems, which have previously been used to rule out certain approaches to the quantum PCP conjecture [BH13].

Abstract: Given a matrix $A$ of dimension $M\times N$ and a vector $\vec{b}$, the quantum linear system (QLS) problem asks for the preparation of a quantum state $\ket{\vec{y}}$ proportional to the solution of $A\vec{y} = \vec{b}$. Existing QLS algorithms typically have runtimes that scale linearly with the condition number $\kappa(A)$, the sparsity of $A$, and logarithmically with the inverse precision. However, these algorithms often overlook structural properties of the input vector $\vec{b}$, despite the fact that its alignment with the eigenspaces of $A$ can significantly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector $\vec{b}$. Let the sparsity of a matrix be defined as the maximum number of nonzero entries in any row or column. The runtime of our algorithm depends polynomially on the sparsity $\s$ of the augmented matrix $H = [A , -\vec{b}]$, the inverse precision, the $\ell_2$ norm of the solution $\vec{y} = A^+ \vec{b}$, and a new instance-dependent parameter $$ ET = \sum_{i=1}^M p_i^2 \cdot d_i, $$ where $\vec{p} = (AA^{\top})^+ \vec{b}$, and $d_i$ denotes the squared $\ell_2$-norm of the $i$-th row of $H$. To further reduce the runtime for certain applications we introduce a structure-aware rescaling technique tailored to the solution $\vec{y} = A^+ \vec{b}$. Unlike \emph{left} preconditioning methods, which transform the system to $DA\vec{z} = D\vec{b}$, our approach applies a \emph{right} rescaling matrix, reformulating the linear system as $A D \vec{z} = \vec{b}$. This combination of an instance-aware QLS algorithm and a rescaling strategy reopens the possibilities for achieving superpolynomial quantum speedups in various domains, such as nonlinear differential equations and polynomial systems. As a application, we develop a new quantum algorithm for solving multivariate polynomial systems in regimes where previous QLS-based methods fail. Our results yield a new end-to-end algorithmic framework, grounded in our new QLS algorithm, that applies to a broad class of problems. In particular, we apply our approach to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system. Given a graph, the MIS problem asks for finding the largest subset of vertices such that no two vertices in the subset share an edge. We provide a detailed runtime analysis and show that, under certain conditions, our quantum algorithm for the MIS problem runs in polynomial time. While no classical algorithms have been developed under these conditions, a promising feature of our quantum algorithm is that its runtime explicitly depends on the structure of the independent sets in the input graph.