|
Complexity-theoretic foundations of BosonSampling with a linear number of modes
With Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Felipe Hernández, and Michał Oszmaniec
QIP 2024
[arXiv]
|
|
Sample-Optimal Classical Shadows for Pure States
With Hakop Pashayan and Luke Schaeffer
TQC 2022
[arXiv]
|
|
The Complexity of Bipartite Gaussian Boson Sampling
With Daniel J. Brod, Juan Miguel Arrazola, Marcos Benicio de Andrade Alonso, Nicolás Quesada
QIP 2022 / Quantum 2022
[arXiv, slides, talk]
|
|
Classical Algorithms for Forrelation
With Sergey Bravyi, David Gosset, Luke Schaeffer
QIP 2022
[arXiv, talk]
|
|
Interactive Quantum Advantage with Noisy, Shallow Clifford Circuits
With Nathan Ju, Luke Schaeffer
QIP 2021
[arXiv]
|
|
Fast Simulation of Planar Clifford Circuits
With David Gosset, Alex Kerzner, Luke Schaeffer
QIP 2021 / Quantum 2024
[arXiv, software]
|
|
Depth-2 QAC Circuits Cannot Simulate Quantum Parity
With Daniel Padé, Stephen Fenner, Thomas Thierauf
[arXiv]
|
|
Interactive Shallow Clifford Circuits: Quantum Advantage Against NC^1 and Beyond
With Luke Schaeffer
QIP 2020 / STOC 2020
[arXiv, slides, talk]
|
|
A Quantum Query Complexity Trichotomy for Regular Languages
With Scott Aaronson and Luke Schaeffer
QIP 2019 / FOCS 2019
[arXiv, slides, talk]
|
|
New Hardness Results for the Permanent Using Linear Optics
With Luke Schaeffer
CCC 2018
[arXiv, slides, talk]
|
|
The Classification of Clifford Gates over Qubits
With Luke Schaeffer
QIP 2018 / Quantum 2022
[arXiv, journal]
|
|
The Classification of Reversible Bit Operations
With Scott Aaronson and Luke Schaeffer
ITCS 2017
[arXiv, slides]
|
|
On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems
With Itai Arad, Adam Bouland, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang
MFCS 2016
[arXiv]
|
|
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games
With Stephen A. Fenner, Jochen Messner, Luke Schaeffer, and Thomas Thierauf
ISAAC 2015
[ECCC, slides]
|
|
Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-complete
ICALP 2013
[arXiv, slides]
|
|
On the Cyclic Van der Waerden Numbers
Geombinatorics 2012
[pdf]
|