10 citations · 13 across the 4 of their papers we have counts for
9 papers
Natural proofs for quantum state preparation lower bounds
Christine Li, Natalie Parham
We identify a barrier that helps explain why proving stronger quantum state-preparation lower bounds has been so difficult. In particular, we establish a quantum analogue of the Ra…
New bounds on private simultaneous quantum message passing
Uma Girish, Alex May, Natalie Parham +1
In the private simultaneous message (PSM) setting, players obtain inputs and then each send messages to a referee, who should learn but no ot…
Magic and communication complexity
Uma Girish, Alex May, Natalie Parham +1
We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communicatio…
Random Unitaries in Constant (Quantum) Time
Ben Foxman, Natalie Parham, Francisca Vasconcelos +1
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work ha…
Quantum circuit lower bounds in the magic hierarchy
Natalie Parham
We introduce the magic hierarchy, a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates ($\textsf{QNC}^…
Identity check problem for shallow quantum circuits
Sergey Bravyi, Natalie Parham, Minh Tran
Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circ…
On the Pauli Spectrum of QAC0
Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos +1
The circuit class was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower…
Unconditional Quantum Advantage for Sampling with Shallow Circuits
Adam Bene Watts, Natalie Parham
Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit w…
Quantum Optimization Heuristics with an Application to Knapsack Problems
Wim van Dam, Karim Eldefrawy, Nicholas Genise +1
This paper introduces two techniques that make the standard Quantum Approximate Optimization Algorithm (QAOA) more suitable for constrained optimization problems. The first techniq…