Professor, Computer Science
Donald Bren School of Information and Computer Sciences
Ph.D., UC Berkeley, 1991, Computer Science
B.S.E., Princeton Universiy, 1986, Electrical Engineering and Computer Science
Phone: (949) 824-6346
Fax: (949) 824-4056
University of California, Irvine
Mail Code: 3425
Irvine, CA 92697
Quantum Computational Complexity and Algorithms, Online Algorithms
One of the central goals of my research is to understand quantum systems from the standpoint of computational complexity. Physicists have been using computers for decades to understand various aspects of quantum systems, but these methods are typically heuristic and achieve success on only limited classes of systems. I study the properties of quantum systems and seek to understand which systems have inherent computational difficulty and which systems can be simulated efficiently on a classical or quantum computer.
Most of the research in the early part of my career was focused on online algorithms, in which the input to a problem arrives incrementally and decisions about the final output must be made before the full problem specification is known. I focused in particular on applications to computer systems, such as memory management, scheduling, and energy efficient computing.
Electronic Structure in a Fixed Basis is QMA-complete. (with Bryan O’Gorman, James Whitfield, and Bill Fefferman), arXiv: 2103:08215, 2021.
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems. (with Daniel Gottesman), Theory of Computing, 9(2), 31--116, 2013.
Efficient algorithm for approximating one-dimensional ground states. (with Dorit Aharonov and Itai Arad), Physics Review A, 82(1), 2010.
Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems. Journal of Mathematical Physics, 51(2), 2009.
The Power of Quantum Systems on a Line. (with Dorit Aharonov, Daniel Gottesman, and Julia Kempe), Communications on Mathematical Physics, vol. 287, no. 1, pp. 41-65, 2009.