291 citations · 664 across the 28 of their papers we have counts for
34 papers
Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm
Adam Bouland, Victor Shyaka, Chenyi Zhang
The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy in time using any universal gate set. While Solovay a…
Exponential quantum space advantage in random data streams
Adam Bouland, Matthew Ding, Siddhartha Jain
We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa--Zhandry Code Intersection problem admits exponential quantum ad…
A Separation Between Types of Quantum Oracle Separations
Scott Aaronson, Adam Bouland, Jordan Docter +1
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of cer…
Does Not Relativize
Adam Bouland, Andrew Huang, Anand Natarajan +2
We construct an oracle relative to which , resolving a long-standing open question in quantum complexity theory. Together with recent work d…
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…
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 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…
Pseudorandomness from Subset States
Tudor Giurgica-Tiron, Adam Bouland
We show it is possible to obtain quantum pseudorandomness and pseudoentanglement from random subset states -- i.e. quantum states which are equal superpositions over (pseudo)random…
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…
A quantum spectral method for simulating stochastic processes, with applications to Monte Carlo
Adam Bouland, Aditi Dandapani, Anupam Prakash
Stochastic processes play a fundamental role in physics, mathematics, engineering and finance. One potential application of quantum computation is to better approximate properties…
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
Adam Bouland, Yosheb Getachew, Yujia Jin +2
We give a quantum algorithm for computing an -approximate Nash equilibrium of a zero-sum game in a payoff matrix with bounded entries. Given a standard quantum orac…
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…
Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm
Adam Bouland, Tudor Giurgica-Tiron
The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unit…
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…
Noise and the frontier of quantum supremacy
Adam Bouland, Bill Fefferman, Zeph Landau +1
Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step…
Prospects and challenges of quantum finance
Adam Bouland, Wim van Dam, Hamed Joorati +2
Quantum computers are expected to have substantial impact on the finance industry, as they will be able to solve certain problems considerably faster than the best known classical…
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…
Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
Jonas Haferkamp, Dominik Hangleiter, Adam Bouland +3
Demonstrating a quantum computational speedup is a crucial milestone for near-term quantum technology. Recently, quantum simulation architectures have been proposed that have the p…
Classical lower bounds from quantum upper bounds
Shalev Ben-David, Adam Bouland, Ankit Garg +1
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove t…
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…
Trading inverses for an irrep in the Solovay-Kitaev theorem
Adam Bouland, Maris Ozols
The Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with…
Complexity Classification of Conjugated Clifford Circuits
Adam Bouland, Joseph F. Fitzsimons, Dax Enshan Koh
Clifford circuits -- i.e. circuits composed of only CNOT, Hadamard, and phase gates -- play a central role in the study of quantum computation. However, their computational p…