William Kretschmer

William Kretschmer

About

I am a Quantum Postdoctoral Fellow at the Simons Institute for the Theory of Computing. Previously, I did my PhD at UT Austin, where I was fortunate to have Scott Aaronson as my PhD advisor. Before that, I was an undergrad in Mathematics with Computer Science at MIT.

My research lies broadly in quantum computational complexity theory. Much of my work focuses on (limitations of) quantum algorithms and (in)ability to apply classical algorithmic techniques in quantum computation. Some common topics of study in my research include query complexity, structural complexity, pseudorandom quantum states, learning theory, and the stabilizer formalism, especially as they apply to computational problems involving quantum states and unitary transformations.

Interested in learning more about my work? Check out this Quanta Magazine article about my (and others') research on quantum state complexity.

On the side, I have a large interest in combination puzzles, especially Rubik's-type "twisty puzzles". Some of my non-CS theory papers below grew out of this interest. I have also designed more than a dozen unique 3D-printed twisty puzzles, all of which have been shared on the Twisty Puzzles forum, and most of which can be found in the Twisty Puzzles museum. Many of my designs are also available for download.

Contact

Email: (first 7 letters of last name, all lowercase)@berkeley.edu
Office: 314 Calvin Lab

Google Scholar profile

Publications

  1. Learning the closest product state
    Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, Ewin Tang
    To appear in QIP 2025 (short plenary talk)
    [arXiv]
  2. Quantum-Computable One-Way Functions without One-Way Functions
    William Kretschmer, Luowen Qian, Avishay Tal
    To appear in QIP 2025
    [arXiv]
  3. Agnostic Tomography of Stabilizer Product States
    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
    [arXiv]
  4. Pseudoentanglement Ain't Cheap
    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
    Presented at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)
    [arXiv]
  5. Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
    Presented at the 27th Annual Conference on Quantum Information Processing (QIP 2024)
    [arXiv]
  6. Improved Stabilizer Estimation via Bell Difference Sampling
    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
    Presented at the 27th Annual Conference on Quantum Information Processing (QIP 2024)
    Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pp. 1352–1363 (2024)
    [arXiv] [STOC 2024]
  7. Two-Disk Compound Symmetry Groups
    Robert A. Hearn, William Kretschmer, Tomas Rokicki, Benjamin Streeter, Eric Vergo
    Proceedings of Bridges 2023: Mathematics, Art, Music, Architecture, Culture, pp. 29–36 (2023)
    [arXiv] [Bridges 2023]
  8. A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
    Scott Aaronson, Harry Buhrman, William Kretschmer
    15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Leibniz International Proceedings in Informatics (LIPIcs) 287, pp. 1:1–1:24 (2024)
    [arXiv] [ECCC] [ITCS 2024]
  9. Quantum Mass Production Theorems
    William Kretschmer
    18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), Leibniz International Proceedings in Informatics (LIPIcs) 266, pp. 10:1–10:21 (2023)
    [arXiv] [TQC 2023]
  10. Quantum Cryptography in Algorithmica
    William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
    Presented at the 26th Annual Conference on Quantum Information Processing (QIP 2023)
    Presented at the 13th Annual Conference on Quantum Cryptography (QCrypt 2023) as an invited talk
    Presented at the 5th Conference on Information-Theoretic Cryptography (ITC 2024) as an invited talk
    Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pp. 1589–1602 (2023)
    [arXiv] [STOC 2023]
  11. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
    Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
    14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Leibniz International Proceedings in Informatics (LIPIcs) 251, pp. 64:1–64:20 (2023)
    ITCS 2023 Best Student Paper Award
    [arXiv] [ITCS 2023]
  12. The Acrobatics of BQP
    Scott Aaronson, DeVon Ingram, William Kretschmer
    Presented at the 25th Annual Conference on Quantum Information Processing (QIP 2022) as a short plenary talk
    37th Computational Complexity Conference (CCC 2022), Leibniz International Proceedings in Informatics (LIPIcs) 234, pp. 20:1–20:17 (2022)
    CCC 2022 Best Paper Award
    [arXiv] [ECCC] [CCC 2022]
  13. Quantum Pseudorandomness and Classical Complexity
    William Kretschmer
    16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), Leibniz International Proceedings in Informatics (LIPIcs) 197, pp. 2:1–2:20 (2021)
    [arXiv] [TQC 2021]
  14. The Quantum Supremacy Tsirelson Inequality
    William Kretschmer
    Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021)
    12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Leibniz International Proceedings in Informatics (LIPIcs) 185, pp. 13:1–13:13 (2021)
    Quantum 5, 560 (2021)
    [arXiv] [ITCS 2021] [Journal]
  15. Symmetries, graph properties, and quantum speedups
    Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
    Presented at the 24th Annual Conference on Quantum Information Processing (QIP 2021)
    Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020)
    [arXiv] [FOCS 2020]
  16. Lower Bounding the AND-OR Tree via Symmetrization
    William Kretschmer
    ACM Transactions on Computation Theory 13:1 (2021)
    [arXiv] [Journal]
  17. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
    Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
    Presented at the 23rd Annual Conference on Quantum Information Processing (QIP 2020)
    35th Computational Complexity Conference (CCC 2020), Leibniz International Proceedings in Informatics (LIPIcs) 169, pp. 7:1–7:47 (2020)
    [arXiv] [ECCC] [CCC 2020]
  18. Simulation of Qubit Quantum Circuits via Pauli Propagation
    Patrick Rall, Daniel Liang, Jeremy Cook, William Kretschmer
    Physical Review A 99, 062337 (2019)
    [arXiv] [Journal]
  19. Structured Factored Inference for Probabilistic Programming
    Avi Pfeffer, Brian Ruttenberg, William Kretschmer, Alison O'Connor
    Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018), Proceedings of Machine Learning Research 84, pp. 1224–1232 (2018)
    [PMLR]
  20. Groups in Circle Puzzles
    William Kretschmer
    Game and Puzzle Design 3:2, pp. 15–26 (2017)
    [Journal]
Last updated: December 6, 2024