5 papers
2-Fold Forrelation is in QAC
Francisca Vasconcelos
We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC circuits. Unlike the standard oracle-based Fo…
Constant-Depth Unitary Preparation of Dicke States
Malvika Raj Joshi, Francisca Vasconcelos
Dicke states serve as a critical resource in quantum metrology, communication, and computation. However, unitary preparation of Dicke states is limited to logarithmic depth in stan…
Improved Lower Bounds for QAC0
Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos +1
In this work, we prove the strongest known lower bounds for QAC, allowing polynomially many gates and ancillae. Our main results show that: (1) Depth-3 QAC circuits cannot…
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…
Methods for Reducing Ancilla-Overhead in Block Encodings
Francisca Vasconcelos, András Gilyén
Block encodings are a fundamental primitive in quantum algorithms, but can often have large ancilla overhead. In this work, we introduce novel techniques for reducing this overhead…