45 citations · 104 across the 15 of their papers we have counts for
18 papers
Anti-symmetrization is cheap and useful
Adam Bene Watts, John Bostanci, Matthias C. Caro +3
We consider the computational task of anti-symmetrization of an unknown mixed quantum state: Given iid copies of a rank- qudit state $ρ=\sum_{i=1}^r λ_i |φ_i\rangle\!\langleφ_i|…
Streaming quantum state purification for general mixed states
Daniel Grier, Debbie Leung, Zhi Li +2
Given multiple copies of a mixed quantum state with an unknown, nondegenerate principal eigenspace, quantum state purification is the task of recovering a quantum state that is clo…
Principal eigenstate classical shadows
Daniel Grier, Hakop Pashayan, Luke Schaeffer
Given many copies of an unknown quantum state , we consider the task of learning a classical description of its principal eigenstate. Namely, assuming that has an eigenstate…
Improved classical shadows from local symmetries in the Schur basis
Daniel Grier, Sihan Liu, Gaurav Mahajan
We study the sample complexity of the classical shadows task: what is the fewest number of copies of an unknown state you need to measure to predict expected values with respect to…
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…
Sample-optimal classical shadows for pure states
Daniel Grier, Hakop Pashayan, Luke Schaeffer
We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state in…
The Complexity of Bipartite Gaussian Boson Sampling
Daniel Grier, Daniel J. Brod, Juan Miguel Arrazola +2
Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of…
Classical algorithms for Forrelation
Sergey Bravyi, David Gosset, Daniel Grier +1
We study the forrelation problem: given a pair of -bit Boolean functions and , estimate the correlation between and the Fourier transform of . This problem is know…
Interactive quantum advantage with noisy, shallow Clifford circuits
Daniel Grier, Nathan Ju, Luke Schaeffer
Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC) can solve with near certainty (probability ), but that an…
Fast simulation of planar Clifford circuits
David Gosset, Daniel Grier, Alex Kerzner +1
A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runti…
Depth-2 QAC circuits cannot simulate quantum parity
Daniel Padé, Stephen Fenner, Daniel Grier +1
We show that the quantum parity gate on qubits cannot be cleanly simulated by a quantum circuit with two layers of arbitrary C-SIGN gates of any arity and arbitrary 1-qubit…
Interactive shallow Clifford circuits: quantum advantage against NC and beyond
Daniel Grier, Luke Schaeffer
Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which…
A Quantum Query Complexity Trichotomy for Regular Languages
Scott Aaronson, Daniel Grier, Luke Schaeffer
We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity Theta(1), ~Theta(sqrt n), or Theta(n). Th…
New Hardness Results for the Permanent Using Linear Optics
Daniel Grier, Luke Schaeffer
In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally…
On the complexity of probabilistic trials for hidden satisfiability problems
Itai Arad, Adam Bouland, Daniel Grier +3
What is the minimum amount of information and time needed to solve 2SAT? When the instance is known, it can be solved in polynomial time, but is this also possible without knowing…
The Classification of Clifford Gates over Qubits
Daniel Grier, Luke Schaeffer
We examine the following problem: given a collection of Clifford gates, describe the set of unitaries generated by circuits composed of those gates. Specifically, we allow the stan…
The Classification of Reversible Bit Operations
Scott Aaronson, Daniel Grier, Luke Schaeffer
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps a…
Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete
Daniel Grier
A poset game is a two-player game played over a partially ordered set (poset) in which the players alternate choosing an element of the poset, removing it and all elements greater…