6 papers
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…
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…
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…
Holographic pseudoentanglement and the complexity of the AdS/CFT dictionary
Chris Akers, Adam Bouland, Lijie Chen +3
The `quantum gravity in the lab' paradigm suggests that quantum computers might shed light on quantum gravity by simulating the CFT side of the AdS/CFT correspondence and mapping t…
On the hardness of learning ground state entanglement of geometrically local Hamiltonians
Adam Bouland, Chenyi Zhang, Zixin Zhou
Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In this work we study the computational complexity…
The state hidden subgroup problem and an efficient algorithm for locating unentanglement
Adam Bouland, Tudor Giurgica-Tiron, John Wright
We study a generalization of entanglement testing which we call the "hidden cut problem." Taking as input copies of an -qubit pure state which is product across an unknown bipar…