Sparsity can be used to improve digital quantum simulation in multiple ways. A common notion of \(d\) -sparsity concerns the target Hamiltonian itself, where each row and column of the Hamiltonian contains \(d\)  nonzero elements accessed by querying quantum oracles. As aforementioned, this provides an abstract framework for designing efficient simulation algorithms and is versatile for establishing lower bounds [1]}, although it sometimes ignores other important properties of the target system, such as locality, commutativity, and symmetry. Another notion of sparsity, closely related to our paper, considers the interactions between the underlying qubits or modes [2]}, [3]}, [4]}, [5]}. The sparsity of interactions does not in general imply the underlying Hamiltonian is sparse, but it provides a tighter bound on the number of terms in the Hamiltonian and may thus be favorable to digital quantum simulation.
