William Kretschmer

Publication Activity (10 Years)

Years Active: 2016-2024
Publications (10 Years): 35

Top Topics

Quantum Computation

Efficient Learning

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Agnostic Tomography of Stabilizer Product States. CoRR (2024)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS (2024)
Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Improved Stabilizer Estimation via Bell Difference Sampling. STOC (2024)
Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Pseudoentanglement Ain't Cheap. CoRR (2024)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. CoRR (2023)
Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements. CoRR (2023)
Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. ITCS (2023)
Robert A. Hearn, William Kretschmer, Tomas Rokicki, Benjamin Streeter, Eric Vergo
Two-Disk Compound Symmetry Groups. CoRR (2023)
William Kretschmer
Quantum Mass Production Theorems. TQC (2023)
William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
Quantum Cryptography in Algorithmica. STOC (2023)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex. (2023)
Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates. CoRR (2023)
Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Improved Stabilizer Estimation via Bell Difference Sampling. CoRR (2023)
William Kretschmer, Luowen Qian, Makrand Sinha, Avishay Tal
Quantum Cryptography in Algorithmica. CoRR (2022)
William Kretschmer
Quantum Mass Production Theorems. CoRR (2022)
Scott Aaronson, DeVon Ingram, William Kretschmer
The Acrobatics of BQP. CCC (2022)
Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. CoRR (2022)
William Kretschmer
Lower Bounding the AND-OR Tree via Symmetrization. ACM Trans. Comput. Theory 13 (1) (2021)
William Kretschmer
The Quantum Supremacy Tsirelson Inequality. ITCS (2021)
Scott Aaronson, DeVon Ingram, William Kretschmer
The Acrobatics of BQP. Electron. Colloquium Comput. Complex. 28 (2021)
William Kretschmer
The Quantum Supremacy Tsirelson Inequality. Quantum 5 (2021)
William Kretschmer
Quantum Pseudorandomness and Classical Complexity. TQC (2021)
Scott Aaronson, DeVon Ingram, William Kretschmer
The Acrobatics of BQP. CoRR (2021)
William Kretschmer
Quantum Pseudorandomness and Classical Complexity. CoRR (2021)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Computational Complexity Conference (2020)
Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
Symmetries, graph properties, and quantum speedups. CoRR (2020)
William Kretschmer
The Quantum Supremacy Tsirelson Inequality. CoRR (2020)
Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
Symmetries, Graph Properties, and Quantum Speedups. FOCS (2020)
William Kretschmer
$\mathsf{QMA}$ Lower Bounds for Approximate Counting. CoRR (2019)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. 26 (2019)
William Kretschmer
Lower Bounding the AND-OR Tree via Symmetrization. CoRR (2019)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR (2019)
William Kretschmer
QMA Lower Bounds for Approximate Counting. Electron. Colloquium Comput. Complex. 26 (2019)
Avi Pfeffer, Brian E. Ruttenberg, William Kretschmer, Alison O'Connor
Structured Factored Inference for Probabilistic Programming. AISTATS (2018)
Avi Pfeffer, Brian E. Ruttenberg, William Kretschmer
Structured Factored Inference: A Framework for Automated Reasoning in Probabilistic Programming Languages. CoRR (2016)