A bisection method is used to compute lower and upper bounds on the distance from a quadratic matrix polynomial to the set of quadratic matrix polynomials having an eigenvalue on the imaginary axis. Each bisection step requires to check whether an even quadratic matrix polynomial has a purely imaginary eigenvalue. First, an upper bound is obtained using Frobenius-type linearizations. It takes into account rounding errors but does not use the even structure. Then, lower and upper bounds are obtained by reducing the quadratic matrix polynomial to a linear palindromic pencil. The bounds obtained this way also take into account rounding errors. Numerical illustrations are presented.