  Inspired by the quantum computing algorithms for Linear Algebra problems
[HHL,TaShma] we study how the simulation on a classical computer of this type
of "Phase Estimation algorithms" performs when we apply it to solve the
Eigen-Problem of Hermitian matrices. The result is a completely new, efficient
and stable, parallel algorithm to compute an approximate spectral decomposition
of any Hermitian matrix. The algorithm can be implemented by Boolean circuits
in $O(\log^2 n)$ parallel time with a total cost of $O(n^{\omega+1})$ Boolean
operations. This Boolean complexity matches the best known rigorous $O(\log^2
n)$ parallel time algorithms, but unlike those algorithms our algorithm is
(logarithmically) stable, so further improvements may lead to practical
implementations.
  All previous efficient and rigorous approaches to solve the Eigen-Problem use
randomization to avoid bad condition as we do too. Our algorithm makes further
use of randomization in a completely new way, taking random powers of a unitary
matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian
perturbation and a random polynomial power are sufficient to ensure almost
pairwise independence of the phases $(\mod (2\pi))$ is the main technical
contribution of this work. This randomization enables us, given a Hermitian
matrix with well separated eigenvalues, to sample a random eigenvalue and
produce an approximate eigenvector in $O(\log^2 n)$ parallel time and
$O(n^\omega)$ Boolean complexity. We conjecture that further improvements of
our method can provide a stable solution to the full approximate spectral
decomposition problem with complexity similar to the complexity (up to a
logarithmic factor) of sampling a single eigenvector.
