Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits
share
The determinant can be computed by classical circuits of depth O(log^2 n), and therefore it can also be computed in classical space O(log^2 n). Recent progress by Ta-Shma [Ta13] implies a method to approximate the determinant of Hermitian matrices with condition number κ in quantum space O(log n + logκ). However, it is not known how to perform the task in less than O(log^2 n) space using classical resources only. In this work, we show that the condition number of a matrix implies an upper bound on the depth complexity (and therefore also on the space complexity) for this task: the determinant of Hermitian matrices with condition number κ can be approximated to inverse polynomial relative error with classical circuits of depth Õ(log n ·logκ), and in particular one can approximate the determinant for sufficiently well-conditioned matrices in depth Õ(log n). Our algorithm combines Barvinok's recent complex-analytic approach for approximating combinatorial counting problems [Bar16] with the Valiant-Berkowitz-Skyum-Rackoff depth-reduction theorem for low-degree arithmetic circuits [Val83].
READ FULL TEXT