# Research

- Algorithms,
- Process Tomography,
- Computational Complexity, Information Theory, and Eclipses
- Surveys and Perspectives

## 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 |