William Kretschmer

activity

20162025

most citedSimulation of Qubit Quantum Circuits via Pauli Propagation

63 citations · 217 across the 21 of their papers we have counts for

collaborators

Showing 2022Show all

3 papers · 1 filter

quant-ph2022

Quantum Mass Production Theorems

William Kretschmer

We prove that for any $n$ -qubit unitary transformation $U$ and for any $r = 2^{o (n / l o g n)}$ , there exists a quantum circuit to implement $U^{\otimes r}$ with at most $O (4^{n})$ ga…

quant-ph2022★ 50 cited

Quantum Cryptography in Algorithmica

William Kretschmer, Luowen Qian, Makrand Sinha +1

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,…

quant-ph2022★ 1 cited

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Sabee Grewal, Vishnu Iyer, William Kretschmer +1

We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an $n$ -qubit pure state $∣ ψ ⟩$ , we give an…