Sparse Hamiltonian

A Hamiltonian H acting on n qubits is called d-sparse if every row of H contains at most d nonzero entries, where d is bounded by a polynomial in the number of qubits. Sparsity is a structural property that allows a quantum algorithm to access matrix entries efficiently through a pair of quantum oracles: one that locates the nonzero entries in a given row, and one that returns their values. With these oracles in hand, the circuit complexity of simulating time evolution under H for time t scales polynomially in d, the norm of H, t, and the inverse of the desired error, achieving an exponential improvement over straightforward classical matrix exponentiation for large system sizes.

The oracle access model is central to why sparse Hamiltonians are efficiently simulable. Classical simulation of arbitrary exponential-dimensional matrices requires exponential space just to store entries, but a quantum algorithm with oracle access only needs to query individual entries on demand. Product formula methods (Trotterization) decompose e^{-iHt} into a product of simpler exponentials corresponding to individual sparse terms, with error controlled by commutator norms. The LCU (linear combination of unitaries) method and qubitization-based approaches achieve even tighter complexity bounds, scaling near-linearly in t rather than polynomially, making them preferable for large simulation times.

In quantum chemistry, Hamiltonians expressed in second quantization become sparse after encoding fermionic modes into qubits. The Jordan-Wigner (JW) transformation maps fermionic operators to Pauli strings, and for molecular Hamiltonians with M spin orbitals, the resulting qubit Hamiltonian typically contains O(M^4) Pauli terms. After a Bravyi-Kitaev (BK) transformation the Pauli weight (locality) of each term is further reduced, and the resulting Hamiltonian is Pauli-sparse: each qubit participates in at most O(log M) terms. This sparsity structure is what makes algorithms like quantum phase estimation tractable for classically intractable molecular systems.

Sparse Hamiltonians are also the regime in which the HHL algorithm for linear systems provides an exponential speedup. HHL requires A to be a sparse, Hermitian, well-conditioned matrix; when these conditions hold, HHL can prepare a quantum state encoding the solution vector with polylogarithmic query complexity in the matrix dimension. The connection is direct: treating A as a Hamiltonian, HHL uses quantum phase estimation to invert eigenvalues, and sparse Hamiltonian simulation subroutines make the phase estimation step efficient. This chain of dependence makes sparse Hamiltonians a foundational concept linking quantum chemistry, linear algebra, and quantum speedup more broadly.