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 >>>

Higman showed that if A is *any* language then SUBSEQ(A)
is regular, where SUBSEQ(A) is the language of all
subsequences of strings in A. (The result we attribute
to Higman is actually an easy consequence of his work.)
Let s_1, s_2, s_3, ... be ... more >>>

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>

We show that the counting classes AWPP and APP [Li 1993] are more robust
than previously thought. Our results identify asufficient condition for
a language to be low for PP, and we show that this condition is at least
as weak as other previously studied criteria. Our results imply that
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 >>>