Simulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly(N) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, polylog(N). The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for any classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.

Understanding the structure of quantum correlations in a many-body system is key to its computational treatment. For fermionic systems, correlations can be defined as deviations from Slater determinant states. The link between fermionic correlations and efficient computational physics methods is actively studied but remains ambiguous. We make progress in establishing this connection mathematically. In particular, we find a rigorous classification of states relative to k-fermion correlations, which admits a computational physics interpretation. Correlations are captured by a measure ω_k, a function of k-fermion reduced density matrix that we call twisted purity. A condition ω_k = 0 for a given k puts the state in a class G_k of correlated states. Sets G_k are nested in k, and Slater determinants correspond to k = 1. Classes G_k=O(1) are shown to be physically relevant, as ω_k vanishes or nearly vanishes for truncated configuration-interaction states, perturbation series around Slater determinants, and some nonperturbative eigenstates of the 1D Hubbard model. For each k = O(1), we give an explicit ansatz with a polynomial number of parameters that covers all states in G_k. Potential applications of this ansatz and its connections to the coupled-cluster wavefunction are discussed.

The experimental realization of increasingly complex quantum states underscores the pressing need for new methods of state learning and verification. In one such framework, quantum state tomography, the aim is to learn the full quantum state from data obtained by measurements. Without prior assumptions on the state, this task is prohibitively hard. Here, we present an efficient algorithm for learning states on n fermion modes prepared by any number of Gaussian and at most t non-Gaussian gates. By Jordan-Wigner mapping, this also includes n-qubit states prepared by nearest-neighbor matchgate circuits with at most t swap gates. Our algorithm is based exclusively on single-copy measurements and produces a classical representation of a state, guaranteed to be close in trace distance to the target state. The sample and time complexity of our algorithm is poly(n,2t); thus if t=O(log⁡(n)), it is efficient. We also show that, if t scales slightly more than logarithmically, any learning algorithm to solve the same task must be inefficient, under common cryptographic assumptions. We also provide an efficient property-testing algorithm that, given access to copies of a state, determines whether such a state is far or close to the set of states for which our learning algorithm works. In addition to the outputs of quantum circuits, our tomography algorithm is efficient for some physical target states, such as those arising in time dynamics and low-energy physics of impurity models. Beyond tomography, our work sheds light on the structure of states prepared with few non-Gaussian gates and offers an improved upper bound on their circuit complexity, enabling an efficient circuit-compilation method.

One of the main problems in computational physics is predicting the low-energy behavior of many-body quantum systems. The computational complexity of this problem, however, is relatively poorly understood. A recent major progress in this direction has been the no low-energy trivial states (NLTS) theorem; it gives a family of qubit Hamiltonians whose low-energy states cannot be reached by shallow quantum circuits. In this work we provide a fermionic counterpart to this theorem, constructing local fermionic Hamiltonians with no low-energy trivial states. Distinct from the qubit case, we define trivial states via finite-depth fermionic quantum circuits. We further strengthen the result, allowing free access to (generally, deep) Gaussian fermionic circuits into our notion of a trivial state. The desired fermionic Hamiltonian can be constructed using any qubit Hamiltonian which has the NLTS property via well-spread distributions over bitstrings. We also define a fermionic analog of quantum probabilistically checkable proofs (PCPs) and explore the relation of fermionic PCP class with the qubit version.

The challenge of preparing a system in a designated state spans diverse facets of quantum mechanics. To complete this task of steering quantum states, one can employ quantum control through a sequence of generalized measurements, which direct the system towards the target state. In an active version of this protocol, the obtained measurement readouts are used to adjust the protocol on the go. This enables a sped-up performance relative to the passive version of the protocol, where no active adjustments are included. In this work, we consider such active measurement-driven steering as applied to the challenging case of many-body quantum systems. The target states of highest interest would be those with multipartite entanglement. Such state preparation in a measurement-based protocol is limited by the natural constraints for system-detector couplings. We develop a framework for finding such physically feasible couplings, based on parent Hamiltonian construction. For helpful decision-making strategies, we offer Hilbert-space-orientation techniques, comparable to those used in navigation. The first one is to tie the active-decision protocol to the greedy accumulation of the cost function, such as the target state fidelity. We show the potential of a significant speedup, employing this greedy approach to a broad family of matrix product state targets. For system sizes considered here, an average value of the speedup factor f across this family settles about 20, for some targets even reaching a few thousands. We also identify a subclass of matrix product state targets, including the ground state of the Affleck-Kennedy-Lieb-Tasaki spin chain, for which the value of f increases with system size. In addition to the greedy approach, the second wayfinding technique is to map out the available measurement actions onto a quantum state machine. A decision-making protocol can be based on such a representation, using semiclassical heuristics. This state-machine-based approach can be applied to a more restricted set of targets, where it sometimes offers advantages over the cost-function-based method. We give an example of a W-state preparation, which is accelerated with this method by f≃3.5, outperforming the greedy protocol for this target.

We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q-local sparse fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q-local means that each term involves exactly q fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4-local interactions (sparse SYK-4 model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O(n⁻¹/²) Gaussian approximation ratio for the normal (dense) SYK-4 model extends to SYK-q for even q > 4, with an approximation ratio of O(n¹/^2−q/4). Our results identify non-sparseness as the prime reason that the SYK-4 model can fail to have a constant approximation ratio [1, 2].