291 citations · 377 across the 15 of their papers we have counts for
23 papers
Distinctness threshold for pseudorandom unitaries
Asad Raza, Jens Eisert, Bill Fefferman
Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in tw…
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…
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…
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…
Quantum Merlin-Arthur with an internally separable proof
Roozbeh Bassirian, Bill Fefferman, Itai Leigh +2
We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP NEXP. This gives a new route to prove…
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…
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…
Public-key pseudoentanglement and the hardness of learning ground state entanglement structure
Adam Bouland, Bill Fefferman, Soumik Ghosh +4
Given a local Hamiltonian, how difficult is it to determine the entanglement structure of its ground state? We show that this problem is computationally intractable even if one is…
Approximate t-designs in generic circuit architectures
Daniel Belkin, James Allen, Soumik Ghosh +6
Unitary t-designs are distributions on the unitary group whose first t moments appear maximally random. Previous work has established several upper bounds on the depths at which ce…
Effect of non-unital noise on random circuit sampling
Bill Fefferman, Soumik Ghosh, Michael Gullans +2
In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sour…
Quantum Merlin-Arthur and proofs without relative phase
Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to…
On the power of nonstandard quantum oracles
Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even…
Quantum Pseudoentanglement
Scott Aaronson, Adam Bouland, Bill Fefferman +4
Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. Inspired by recent work of Gheorghiu and Hoban, we define the notion of "pseudoen…
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…
Electronic Structure in a Fixed Basis is QMA-complete
Bryan O'Gorman, Sandy Irani, James Whitfield +1
Finding the ground state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry. We prove that this electronic-structure prob…
Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
Adam Bouland, Bill Fefferman, Umesh Vazirani
A fundamental issue in the AdS/CFT correspondence is the wormhole growth paradox. Susskind's conjectured resolution of the paradox was to equate the volume of the wormhole with the…
Quantum Supremacy and the Complexity of Random Circuit Sampling
Adam Bouland, Bill Fefferman, Chinmay Nirkhe +1
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A l…
Space-Efficient Error Reduction for Unitary Quantum Computations
Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin +2
This paper develops general space-efficient methods for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness and so…
A Complete Characterization of Unitary Quantum Space
Bill Fefferman, Cedric Yen-Yu Lin
Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. F…
On Quantum Obfuscation
Gorjan Alagic, Bill Fefferman
Encryption of data is fundamental to secure communication in the modern world. Beyond encryption of data lies obfuscation, i.e., encryption of functionality. It is well-known that…
Computational Security of Quantum Encryption
Gorjan Alagic, Anne Broadbent, Bill Fefferman +3
Quantum-mechanical devices have the potential to transform cryptography. Most research in this area has focused either on the information-theoretic advantages of quantum protocols…
Quantum Merlin Arthur with Exponentially Small Gap
Bill Fefferman, Cedric Lin
We study the complexity of QMA proof systems with inverse exponentially small promise gap. We show that this class can be exactly characterized by PSPACE, the class of problems sol…
Quantum vs Classical Proofs and Subset Verification
Bill Fefferman, Shelby Kimmel
We study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness. We develop a general framework…