  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 $2^n
\times 2^n$ by systematically determining all Pauli strings present in the
decomposition, dividing them into commuting subsets. The efficiency is in the
number of commuting subsets $O(n)$. The method is demonstrated using the
one-dimensional wave equation, verifying numerically that the gate complexity
as function of the number of qubits is lower than the oracle based approach for
$n < 15$ and requires half the number of qubits. This method is applicable to
other Hamiltonians based on the tridiagonal matrices.
