|
Quantum Computing
This project focuses on exploring the power of
quantum computation, and in particular on showing its
superiority relative to classical deterministic and
bounded-error probabilistic computing.
We have shown that there is a black box relative to
which there are problems in polynomial-time on
quantum computers that require exponentially more
time on almost every input on any classical deterministic,
or even bounded-error probabilistic, computer.
- 1
-
This is a list of selected journal (except when the work has not yet
appeared in journal/book form, plus in some cases some conference articles)
papers, from or related to this project, by University of Rochester authors.
Essentially all the papers listed below can be found, in their full technical
report versions, in the UR-CS Technical Report Archive's
theory section. Here is
Lane's complete publication
list
and links to
essentially all his conference and journal papers (and also his arXiv.org
technical reports) can be found via the ``EE'' (electronic edition) links at
Lane's entry at the DBLP
project.
- 2
-
E. Hemaspaandra, L. Hemaspaandra, and M. Zimand.
Almost-everywhere superiority for quantum polynomial time.
Information and Computation, 175(2):171-181, 2002.
- 3
-
E. Hemaspaandra, L. Hemaspaandra, and M. Zimand.
Almost-everywhere superiority for quantum polynomial-time languages.
Technical Report TR-754, Department of Computer Science, University
of Rochester, Rochester, NY, January 2005.
This paper provides an extension to the language case of the work of
our 2002 Information and Computation paper, which was for the
function case; this January 2005 version is our most polished version of the
language-case proof.
- 4
-
H. Spakowski, M. Thakur, and R. Tripathi.
Quantum and classical complexity classes: Separations, collapses,
and closure properties.
Information and Computation, 200(1):1-34, 2005.
(Last modified: February 1, 2012.)
Lane A. Hemaspaandra
|