The construction of quantum circuits to simulate Hamiltonian evolution is central to many quantum algorithms. State-of-the-art circuits are based on oracles whose implementation is often omitted, and the complexity of the algorithm is estimated by counting oracle queries. However, in practical applications, an oracle implementation contributes a large constant factor to the overall complexity of the algorithm. The key finding of this work is the efficient procedure for representation of a tridiagonal matrix in the Pauli basis, which allows one to construct a Hamiltonian evolution circuit without the use of oracles. The procedure represents a general tridiagonal matrix by systematically determining all Pauli strings present in the decomposition, dividing them into commuting subsets. The efficiency is in the number of commuting subsets . The method is demonstrated using the one-dimensional wave equation, verifying numerically that the gate complexity as a function of the number of qubits is lower than the oracle-based approach for and requires half the number of qubits. This method is applicable to other Hamiltonians based on the tridiagonal matrices.
The simulation of multidimensional wave propagation with variable material parameters is a computationally intensive task, with applications from seismology to electromagnetics. While quantum computers offer a promising path forward, their algorithms are often analyzed in the abstract oracle model, which can mask the high gate-level complexity of implementing those oracles. We present a framework for constructing a quantum algorithm for the multidimensional wave equation with a variable speed profile. The core of our method is a decomposition of the system Hamiltonian into sets of mutually commuting Pauli strings, paired with a dedicated diagonalization procedure that uses Clifford gates to minimize simulation cost. Within this framework, we derive explicit bounds on the number of quantum gates required for Trotter–Suzuki-based simulation. Our analysis reveals significant computational savings for structured block-model speed profiles compared to general cases. Numerical experiments in three dimensions confirm the practical viability and performance of our approach. Beyond providing a concrete, gate-level algorithm for an important class of wave problems, the techniques introduced here for Hamiltonian decomposition and diagonalization enrich the general toolbox of quantum simulation.