Title | A Complete Characterization of Unitary Quantum Space |

Publication Type | Journal Article |

Year of Publication | 2016 |

Authors | Fefferman, B, Lin, CYen-Yu |

Date Published | 2016/04/05 |

Abstract | We give two complete characterizations of unitary quantum space-bounded classes. The first is based on the Matrix Inversion problem for well-conditioned matrices. We show that given the size-n efficient encoding of a 2O(k(n))×2O(k(n)) well-conditioned matrix H, approximating a particular entry of H−1 is complete for the class of problems solvable by a quantum algorithm that uses O(k(n)) space and performs all quantum measurements at the end of the computation. In particular, the problem of computing entries of H−1 for an explicit well-conditioned n×n matrix H is complete for unitary quantum logspace. |

URL | http://arxiv.org/abs/1604.01384 |