William Kretschmer

STOC Conference 2025 Conference Paper

Learning the Closest Product State

• Ainesh Bakshi
• John Bostanci
• William Kretschmer
• Zeph Landau
• Jerry Li 0001
• Allen Liu
• Ryan O'Donnell
• Ewin Tang

STOC Conference 2025 Conference Paper

Quantum-Computable One-Way Functions without One-Way Functions

• William Kretschmer
• Luowen Qian
• Avishay Tal

We construct a classical oracle relative to which P = NP but quantum-computable quantum-secure trapdoor one-way functions exist. This is a substantial strengthening of the result of Kretschmer, Qian, Sinha, and Tal (STOC 2023), which only achieved single-copy pseudorandom quantum states relative to an oracle that collapses NP to P . For example, our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes relative to an oracle on which P = NP . Hence, in our new relativized world, classical computers live in ”Algorithmica” whereas quantum computers live in ”Cryptomania,” using the language of Impagliazzo’s worlds. Our proof relies on a new distributional block-insensitivity lemma for AC 0 circuits, wherein a single block is resampled from an arbitrary distribution.

STOC Conference 2024 Conference Paper

Improved Stabilizer Estimation via Bell Difference Sampling

• Sabee Grewal
• Vishnu Iyer
• William Kretschmer
• Daniel Liang

We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: We prove that Ω( n ) T -gates are necessary for any Clifford+ T circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist. Given an n -qubit pure quantum state |ψ⟩ that has fidelity at least τ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least τ − ε. The algorithm uses O ( n /(ε 2 τ 4 )) samples and exp( O ( n /τ 4 )) / ε 2 time. In the regime of τ constant, this algorithm estimates stabilizer fidelity substantially faster than the naive exp( O ( n 2 ))-time brute-force algorithm over all stabilizer states. In the special case of τ > cos 2 (π/8), we show that a modification of the above algorithm runs in polynomial time. We exhibit a tolerant property testing algorithm for stabilizer states. The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory.

STOC Conference 2023 Conference Paper

Quantum Cryptography in Algorithmica

• William Kretschmer
• Luowen Qian
• Makrand Sinha
• Avishay Tal

We construct a classical oracle relative to which P = NP yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo’s five worlds, this is a construction of pseudorandom states in ”Algorithmica,” and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of P vs. NP in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states. We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an oracle relative to which P = NP but BQP ≠ QCMA , based on hardness of the OR ∘ Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against AC 0 circuits. This variant may be of independent interest.

FOCS Conference 2020 Conference Paper

Symmetries, Graph Properties, and Quantum Speedups

• Shalev Ben-David
• Andrew M. Childs
• András Gilyén
• William Kretschmer
• Supartha Podder
• Daochen Wang

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently-we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).