8 papers
Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén +1
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the c…
Depth-Optimal Quantum Compilation
Francisca Vasconcelos
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catal…
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…
A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games
Francisca Vasconcelos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos +2
Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, sp…