Research

Jump to:

Algorithms

I primarily study query problems, in which one tries to learn a property of an unknown function, by "querying" values of the function. The goal is to determine the property of the function using as few queries as possible. I try to prove upper and lower bounds on the number of queries needed by a quantum algorithm to solve the problem. This is a rewarding model to work in because it is possible to prove that quantum computers require fewer queries than classical computers.

M. Czekanski, S. Kimmel, R. T. Witter.
Robust and Space-Efficient Dual Adversary Quantum Query Algorithms.
ESA 2023
Proceedings
Arxiv

Bibtex
S. Jeffery, S. Kimmel, A. Piedrafita.
Quantum Algorithm for Path-Edge Sampling.
Proceedings of TQC 2023
Proceedings
Arxiv

Bibtex
N. T. Anderson, J.-U. Chung, S. Kimmel, D.-Y. Koh, X. Ye
Improved Quantum Query Complexity on Easier Inputs.
Manuscript 2023.

Arxiv

Bibtex
S. Kimmel, R. T. Witter.
A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs.
Workshop on Algorithms and Data Structures (WADS) 2021. Springer Lecture Notes in Computer Science: Algorithms and Data Structures, vol 12808, pp 543–555.
Proceedings
Arxiv

Bibtex
K. DeLorenzo, S. Kimmel, R. T. Witter.
Applications of the quantum algorithm for st-connectivity.
Proceedings of Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), vol 135, pp 6:1-14.
Proceedings
Arxiv

Bibtex
M. Jarret, S. Jeffery, S. Kimmel, A. Piedrafita.
Quantum Algorithms for Connectivity and Related Problems.
Proceedings of ESA 2018, pp 49:1-13.
Proceedings
Arxiv
Bibtex
S. Jeffery. S. Kimmel.
Quantum Algorithms for Graph Connectivity and Formula Evaluation.
Quantum vol 1, 26, 2017.
Journal
Arxiv
Bibtex
S. Kimmel, C. Y-Y. Lin, G. H. Low, M. Ozols, T. J. Yoder
Hamiltonian Simulation with Optimal Sample Complexity
Nature Partner Journals Quantum Information, vol 3, no. 13, 2017.
Journal
Arxiv
Bibtex
E. Farhi, S. Kimmel, K. Temme.
A Quantum Version of Schöning's Algorithm Applied to Quantum 2-SAT.
Quantum Information and Computation, vol 16, no. 13-14, 2016.
Journal
Arxiv
Bibtex
S. Kimmel, C. Y. Y. Lin, H. H. Lin.
Oracles with Costs.
Proceedings of Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015), pp 1-26.
Proceedings
Arxiv
Bibtex
A. M. Childs, S. Kimmel, R. Kothari.
The Quantum Query Complexity of Read-Many Formulas.
Proceedings of ESA 2013, pp 337-348.
Proceedings
Arxiv
Bibtex
S. Kimmel
Quantum Adversary (Upper) Bound.
Chicago Journal of Theoretical Computer Science, vol 2013 n 4. And Proceedings of ICALP. 2012 pp 557-568.
Journal
Arxiv
Bibtex
B. Zhan, S. Kimmel, A. Hassidim.
Super-polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure.
Proceedings of ITCS, pp 249-265. 2012
Proceedings
Arxiv
Bibtex

Process Tomography

We don't yet have scalable quantum computers because errors in current systems grow more quickly than we can correct them. The ability to accurately characterize these errors is important for experimentalists as they try to improve their systems. I create tools that provide information about these errors in ways that are accurate, efficient, and make realistic assumptions about experimental resources.

A. E. Russo, W. M. Kirby, K. M. Rudinger, A. D. Baczewski, S. Kimmel.
Consistency testing for robust phase estimation
Physical Review A, vol 103, 042609, 2021.
Journal Arxiv
Bibtex
I. Roth, R. Kueng, S. Kimmel, Y.-K. Liu, D. Gross, J. Eisert, M. Kliesch.
Recovering quantum gates from few average gate fidelities.
Physical Review Letters, vol 121, no 17, pp 170502, 2018, (Editor's Suggestion.)
Journal
Arxiv
Bibtex
K. Rudinger, S. Kimmel, D. Lobser, P. Maunz.
Experimental demonstration of cheap and accurate phase estimation.
Physical Review Letters, vol. 118, no. 19, pp. 190502, 2017
Journal
Arxiv
Bibtex
S. Kimmel, Y.-K. Liu.
Phase retrieval using unitary 2-designs.
Proceedings of the 2017 International Conference on Sampling Theory and Applications (SAMPTA). pp 345-349, 2017.
Proceedings
Arxiv
Bibtex
S. Kimmel, G. H. Low, T. J. Yoder.
Robust calibration of a universal single-qubit gate set via robust phase estimation.
Phys. Rev. A 92 (6), 062315. 2015.
Journal
Arxiv
Bibtex
B. R. Johnson, M. P. da Silva, C. A. Ryan, S. Kimmel, J. M. Chow, T. A. Ohki.
Demonstration of Robust Quantum Gate Tomography via Randomized Benchmarking.
New Journal of Physics 17 (11), 113019. 2015.
Journal
Arxiv
Bibtex
S. Kimmel, M. P. da Silva, C. Ryan, B. Johnson, T, Ohki.
Robust Extraction of Tomographic Information via Randomized Benchmarking.
Physical Review X, 2014, vol 4, n 1, pp 011050, 2014.
Journal
Arxiv
Bibtex

Computational Complexity, Information Theory, and Eclipses

In the area of complexity theory, I am most interested in understanding whether quantum proofs are more powerful than classical proofs. In other words, if someone tries to convince me that a statement is true by giving me a proof, in what cases is it helpful for that proof to be a quantum state rather than a classical bit string? In information theory, I have investigated how entanglement can be used as a resource to perform quantum measurements between separated parties. Finally, as an undergrad, I did some eclipse chasing, studying the solar corona.

S. Kimmel, S. Kolkowitz
No-Go for Quantum Seals.
Phys. Rev. A, vol. 100 pp. 052326, 2019
Journal
Arxiv
Bibtex
B. Fefferman, S. Kimmel
Quantum vs Classical Proofs and Subset Verification.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 2018, vol. 117, pp. 22:1-23.
Proceedings
Arxiv
Bibtex
S. Bandyopadhyay, G. Brassard, S. Kimmel, W. Wootters.
Entanglement Cost of Nonlocal Measurements.
Phys. Rev. A. vol 80, n 1, pp 012313. 2009.
Journal
Arxiv
Bibtex
J. Pasachoff, S. Kimmel, M. Druckmuller, V. Rusin, M. Saniga.
The April 8, 2005 Eclipse White-light Corona.
Solar Physics. vol 238, n 2, pp 261-270, 2006.
Journal
Bibtex

Surveys and Perspectives

Y. Alexeev et al.
Quantum Computer Systems for Scientific Discovery.
PRX Quantum, vol 2, 017001, 2021.
Journal Arxiv
Bibtex
S. Kimmel
Quantum Algorithms: Promise and Perspective.
Frontiers of Engineering: Reports on Leading-Edge Engineering from the 2018 Symposium. National Academy of Engineering. 2019
Journal
Arxiv
Bibtex