All reports by Author Frederic Green:

__
TR08-078
| 15th April 2008
__

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer#### Universal Quantum Circuits

__
TR99-003
| 18th December 1998
__

Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim#### Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

__
TR95-027
| 30th May 1995
__

Frederic Green#### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer

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

Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

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

Frederic Green

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$

more >>>