Hajim School Logo                                     URCS Mona Logo

Quantum Computing

UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra).

Project Description

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.


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.

E. Hemaspaandra, L. Hemaspaandra, and M. Zimand.
Almost-everywhere superiority for quantum polynomial time.
Information and Computation, 175(2):171-181, 2002.

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.

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: January 22, 2019.)

Lane A. Hemaspaandra