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. 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 $\rm C_{=}P$, a cousin of which Berthiaume and Brassard showed to be contained in quantum polynomial time. We defined the class BPP $_{\mathrm{path}}$, 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”).

References

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.
$\begin{tabular}{l}
{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\hline
\end{tabular}$

(Last modified: February 16, 2023.)


Lane A. Hemaspaandra