  Several linear algebra routines for quantum computing use a basis of tensor
products of identity and Pauli operators to describe linear operators, and
obtaining the coordinates for any given linear operator from its matrix
representation requires a basis transformation, which for an $\mathrm
N\times\mathrm N$ matrix generally involves $\mathcal O(\mathrm N^4)$
arithmetic operations. Herein, we present an efficient algorithm that for our
particular basis transformation only involves $\mathcal O(\mathrm
N^2\log_2\mathrm N)$ operations. Because this algorithm requires fewer than
$\mathcal O(\mathrm N^3)$ operations, for large $\mathrm N$, it could be used
as a preprocessing step for quantum computing algorithms for certain
applications. As a demonstration, we apply our algorithm to a Hamiltonian
describing a system of relativistic interacting spin-zero bosons and calculate
the ground-state energy using the variational quantum eigensolver algorithm on
a quantum computer.
