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. We have also studied the
properties and robustness of classes closely related to quantum
computing, e.g., LWPP, which Fortnow and Rogers showed to contain EQP,
and , a cousin of which Berthiaume and Brassard showed to
be contained in quantum polynomial time. We defined the class
BPP
, whose quantum analogue, PostBQP, was later very
interestingly defined and studied by Aaronson (in his 2005
Proceedings
of the Royal Society A
article,
“Quantum Computing, Postselection, and Probabilistic Polynomial-Time”).
- 1
-
This is a list of selected papers, from or related to this project,
by University of Rochester authors. Links to essentially all Lane's
conference and journal papers (and also his arXiv.org technical reports) can
be found via the pointers from the related entries within
Lane's entry at the DBLP
project.
Additionally, here is a link to Lane's complete
publication list
(note: that
list does not itself have links to papers).
- 2
-
B. Borchert, L. Hemaspaandra, and J. Rothe.
Restrictive acceptance suffices for equivalence problems.
In Proceedings of the 12th Conference on Fundamentals of
Computation Theory, pages 124–135. Springer-Verlag Lecture Notes in
Computer Science #1684, August/September 1999.
- 3
-
Y. Han, L. Hemaspaandra, and T. Thierauf.
Threshold computation and cryptographic security.
SIAM Journal on Computing, 26(1):59–78, 1997.
- 4
-
E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe.
The robustness of LWPP and WPP, with an application to graph
reconstruction.
In Proceedings of the 43rd International Symposium on
Mathematical Foundations of Computer Science, pages 51:1–51:14. Leibniz
International Proceedings in Informatics (LIPIcs) #117, August 2018.
- 5
-
E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe.
The robustness of LWPP and WPP, with an application to graph
reconstruction.
Computational Complexity, 29(2, Article 7):1–49, 2020.
- 6
-
E. Hemaspaandra, L. Hemaspaandra, and M. Zimand.
Almost-everywhere superiority for quantum polynomial time.
Information and Computation, 175(2):171–181, 2002.
- 7
-
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.
- 8
-
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 16, 2023.)
Lane A. Hemaspaandra
|