Abstract:We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same ... more >>>

It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with nonzero amplitude in a superposition, or whether a ... more >>>

We say an integer polynomial $p$, on Boolean inputs, weakly $m$-represents a Boolean function $f$ if $p$ is non-constant and is zero (mod $m$), whenever $f$ is zero. In this paper we prove that if a polynomial weakly $m$-represents the Mod$_q$ function on $n$ inputs, where $q$ and $m$ are ... more >>>