Bill Fefferman

bill-fefferman's picture
Assistant Research Professor (2018-2019)
bfefferman@gmail.com
3100E Atlantic Building
Bill Fefferman was a Research Assistant Professor in QuICS and a Research Scientist at NIST from 2018-2019.  His work focused on quantum computation and computational complexity theory, with an emphasis on understanding the capabilities of near term quantum devices and experiments.  He previously held postdoctoral positions at UC Berkeley advised by Umesh Vazirani, and at the University of Maryland in QuICS.  He received his doctorate from Caltech in 2014, advised by Alexei Kitaev and Chris Umans.  In 2017 he was the recipient of a Young Investigator Award from the Air Force Office of Scientific Research to help support his research on the power of near-term quantum systems.  Bill is an Assistant Professor at the University of Chicago.  

Publications

2023

B. Fefferman, Ghosh, S., Gullans, M., Kuroiwa, K., and Sharma, K., “Effect of non-unital noise on random circuit sampling”, 2023.
B. Ware, Deshpande, A., Hangleiter, D., Niroula, P., Fefferman, B., Gorshkov, A. V., and Gullans, M., “A sharp phase transition in linear cross-entropy benchmarking”, 2023.

2022

A. Deshpande, Gorshkov, A. V., and Fefferman, B., “Importance of the Spectral gap in Estimating Ground-State Energies”, PRX Quantum, vol. 3, 2022.
A. Deshpande, Mehta, A., Vincent, T., Quesada, N., Hinsche, M., Ioannou, M., Madsen, L., Lavoie, J., Qi, H., Eisert, J., Hangleiter, D., Fefferman, B., and Dhand, I., “Quantum computational advantage via high-dimensional Gaussian boson sampling”, Science Advances, vol. 8, p. eabi7894, 2022.

2021

A. Deshpande, Mehta, A., Vincent, T., Quesada, N., Hinsche, M., Ioannou, M., Madsen, L., Lavoie, J., Qi, H., Eisert, J., Hangleiter, D., Fefferman, B., and Dhand, I., “Quantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling”, 2021.
A. Deshpande, Fefferman, B., Gorshkov, A. V., Gullans, M., Niroula, P., and Shtanko, O., “Tight bounds on the convergence of noisy random circuits to uniform”, 2021.

2019

Y. Alexeev, Bacon, D., Brown, K. R., Calderbank, R., Carr, L. D., Chong, F. T., DeMarco, B., Englund, D., Farhi, E., Fefferman, B., Gorshkov, A. V., Houck, A., Kim, J., Kimmel, S., Lange, M., Lloyd, S., Lukin, M. D., Maslov, D., Maunz, P., Monroe, C., Preskill, J., Roetteler, M., Savage, M., Thompson, J., and Vazirani, U., “Quantum Computer Systems for Scientific Discovery”, 2019.
N. Maskara, Deshpande, A., Tran, M. C., Ehrenberg, A., Fefferman, B., and Gorshkov, A. V., “Complexity phase diagram for interacting and long-range bosonic Hamiltonians”, 2019.

2018

A. Bouland, Fefferman, B., Nirkhe, C., and Vazirani, U., “Quantum Supremacy and the Complexity of Random Circuit Sampling”, 2018.
A. Deshpande, Fefferman, B., Tran, M. C., Foss-Feig, M., and Gorshkov, A. V., “Dynamical phase transitions in sampling complexity”, Phys. Rev. Lett., vol. 121, no. 030501, p. 12 pages, 4 figures. v3: published version, 2018.

2017

B. Fefferman, Foss-Feig, M., and Gorshkov, A. V., “Exact sampling hardness of Ising spin models”, Physical Review A, vol. 96, no. 3, p. 032324, 2017.
A. Deshpande, Fefferman, B., Foss-Feig, M., and Gorshkov, A. V., “Complexity of sampling as an order parameter”, 2017.

2016

G. Alagic, Broadbent, A., Fefferman, B., Gagliardoni, T., Schaffner, C., and Jules, M. St., “Computational Security of Quantum Encryption”, in Computational Security of Quantum Encryption. In: Nascimento A., Barreto P. (eds) Information Theoretic Security. , 2016.
B. Fefferman, Kobayashi, H., Lin, C. Yen- Yu, Morimae, T., and Nishimura, H., “Space-Efficient Error Reduction for Unitary Quantum Computations”, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), vol. 55, p. 14:1--14:14, 2016.
B. Fefferman and Lin, C. Yen- Yu, “A Complete Characterization of Unitary Quantum Space”, 2016.
G. Alagic and Fefferman, B., “On Quantum Obfuscation”, 2016.
B. Fefferman and Lin, C. Yen- Yu, “Quantum Merlin Arthur with Exponentially Small Gap”, 2016.

2015

B. Fefferman and Kimmel, S., “Quantum vs Classical Proofs and Subset Verification”, 2015.
B. Fefferman and Umans, C., “The Power of Quantum Fourier Sampling”, 2015.

2012

B. Fefferman, Shaltiel, R., Umans, C., and Viola, E., “On Beating the Hybrid Argument”, Proceedings, ITCS, vol. 9, pp. 809-843, 2012.