English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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)$. Recentprogress by Ta-Shma [Ta13] implies a method to approximate the determinant ofHermitian matrices with condition number $\kappa$ in quantum space $O(\log n +\log \kappa)$. 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 thatthe 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 ofHermitian matrices with condition number $\kappa$ can be approximated toinverse polynomial relative error with classical circuits of depth $\tildeO(\log n \cdot \log \kappa)$, and in particular one can approximate thedeterminant for sufficiently well-conditioned matrices in depth $\tilde{O}(\logn)$. Our algorithm combines Barvinok's recent complex-analytic approach forapproximating combinatorial counting problems [Bar16] with theValiant-Berkowitz-Skyum-Rackoff depth-reduction theorem for low-degreearithmetic circuits [Val83].

Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits