1 citations · 1 across the 7 of their papers we have counts for
7 papers
Verifiable quantum advantage in extremely low depth
Alexandru Gheorghiu
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable b…
Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure
Alexandru Gheorghiu
We construct a family of 2D-local constant-depth quantum circuits that output states whose entanglement entropy across a specified cut cannot be estimated in quantum polynomial tim…
Quantum state isomorphism problems for groups
Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban +1
We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the tw…
Improved quantum circuits for division
Priyanka Mukhopadhyay, Alexandru Gheorghiu, Hari Krovi
Arithmetic operations are an important component of many quantum algorithms. Optimizing quantum circuits for these operations therefore leads to more efficient implementations of t…
Learning depth-3 circuits via quantum agnostic boosting
Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu +1
We initiate the study of quantum agnostic learning of phase states with respect to a function class : given copies of an unk…
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…