6 papers
On the Complexity of Decoded Quantum Interferometry
Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu +1
We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. First, we show that the algorithm resists classical simulation st…
On Certified Randomness from Fourier Sampling or Random Circuit Sampling
Roozbeh Bassirian, Adam Bouland, Bill Fefferman +2
Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson (2018, 2020) proposed a novel public certified randomness protoc…
Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
Bill Fefferman, Soumik Ghosh, Wei Zhan
We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falli…
Exponential improvements to the average-case hardness of BosonSampling
Adam Bouland, Ishaun Datta, Bill Fefferman +1
BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating q…
The Hardness of Learning Quantum Circuits and its Cryptographic Applications
Bill Fefferman, Soumik Ghosh, Makrand Sinha +1
We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In…
Complexity-theoretic foundations of BosonSampling with a linear number of modes
Adam Bouland, Daniel Brod, Ishaun Datta +4
BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstration…