Francisca Vasconcelos

Interestingly, this work achieves arbitrary-weight Dicke states in QAC^0_f, but only constant-weight Dicke states in QAC^0. Thus, a QAC^0 lower-bound against any ω(1)-weight Dicke state would separate QAC^0 and QAC^0_f, resolving a major open question in quantum complexity.

For architectures (e.g. trapped ions) with access to global FAN-OUT gates, we offer poly-ancillae QAC^0_f circuits for exact preparation of arbitrary-weight Dicke states.

For architectures (e.g. neutral atoms) with access to global CZ gates, we offer poly-ancillae QAC^0 circuits for exact preparation of constant-weight Dicke states. We also show that weight-1 Dicke states, i.e. W states, can be approximated to constant-error fidelity, using only *constant* ancillae.

We overcome the log-depth barrier by moving beyond the standard circuit model and leveraging global interactions. In particular, we consider the constant-depth QAC^0 circuit class (arbitrary 1-QB and global CZ gates) and the QAC^0_f circuit class (arbitrary 1-QB and global FAN-OUT gates).

However, in the standard circuit model (restricted to constant-width gates) there are logarithmic-depth lower-bounds for unitary Dicke state preparation. Thus, all previously known constant-depth protocols for exact Dicke state prep rely on measurement and adaptive feed-forward.

There is a large literature on low-depth Dicke state preparation (see table) due to their prevalence in quantum physics, metrology, communication, and computation. For example, Dicke states are a main quantum resource in the recent Decoded Quantum Interferometry (DQI) algorithm.

Constant-Depth Unitary Preparation of Dicke States 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 standard circuit models ...

Very excited to share a new paper with Malvika Joshi (@malvikaraj.bsky.social) on "Constant-Depth Unitary Preparation of Dicke States"! In this work, we offer the first unitary, constant-depth circuits for exact preparation of arbitrary-weight Dicke states.

arXiv: arxiv.org/abs/2601.10693

Has quantum advantage been achieved? Recently, I gave a couple of perspective talks on quantum advantage, one at the annual retreat of the CIQC and one at a recent KITP programme. I started off by polling the audience on who believed …

Dominik Hangleiter weighs in with an informative post about a much debated question: Has quantum advantage been achieved? This is the first post in a three-part series.
quantumfrontiers.com/2026/01/06/h...

Excitingly, the depth-3 proof introduces novel techniques for proving quantum circuit lower-bounds. We introduce a new form of quantum restrictions to simplify the circuit. We also show these QAC^0 circuits are simulable via small AC^0 circuits, enabling application of the classical Switching Lemma!

Additionally, we prove the first depth-3 lower-bounds for QAC^0! Specifically, we show that depth-3 QAC^0 cannot compute exact Parity with unlimited ancillae nor exact Majority with super-polynomial ancillae.

Our work improves upon previously known depth-2 lower bounds against Parity for QAC^0 with unlimited ancillae.

First, we prove a new structural result (via entropy-based and Fourier-analytic arguments) showing that depth-2 QAC^0 circuits with unlimited ancillae have low influence.

Improved Lower Bounds for QAC0 In this work, we establish the strongest known lower bounds against QAC$^0$, while allowing its full power of polynomially many ancillae and gates. Our two main results show that: (1) Depth 3 QAC$^0...

Very excited to share a new paper with Malvika Joshi, Avishay Tal, and John Wright on “Improved Lower Bounds for QAC^0”! In this work, we prove the strongest known lower-bounds to date for QAC^0 with the full power of polynomially many ancillae.

arXiv: arxiv.org/abs/2512.14643

Join us for the first Quantum Cambridge–Oxford–Warwick Colloquium (Quantum COW, if you insist...), 11–12 December 2025 at the University of Oxford.

This meeting focuses on Quantum Low-Depth Complexity, with talks, tutorials, and open discussions.

Details: qcow.cs.ox.ac.uk

Methods for Reducing Ancilla-Overhead in Block Encodings 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 in two distinct way...

The full paper, titled "Methods for Reducing Ancilla-Overhead in Block Encodings", can be found on arxiv: arxiv.org/abs/2507.07900

YouTube video by Institute for Robust Quantum Simulation Francisca Vasconcelos: “Methods for Reducing Ancilla-Overhead in Block Encodings”

I was very excited to present my first research project on quantum algorithms at QSim 2025! This work, joint with András Gilyén, develops new space-time and space-accuracy tradeoffs for manipulation of block encodings, helping reduce ancilla-overhead in quantum algorithms.

youtu.be/7AaZzzoSAic?...

Beyond cryptographic implications, our approach yields novel average‑case learning lower bounds for QAC⁰ and suggests a new path towards proving Parity ∉ QAC⁰, a longstanding open problem in quantum complexity.

Namely, by considering physically motivated models of computation—such as QAC⁰ and constant-depth circuits with mid-circuit measurements—we surpass prior constructions requiring Θ(log log n) depth.

Random Unitaries in Constant (Quantum) Time 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 has constructed unitar...

In exciting new work with Ben Foxman, @nat-parham.bsky.social , and @henryyuen.bsky.social we show that t-designs and pseudorandom unitaries are implementable in constant (quantum) time!

arxiv.org/abs/2508.11487

What better way to celebrate the 100th anniversary of quantum mechanics than a foundations conference in Gdańsk? I especially enjoyed learning about modern work on contextuality, quantum speed limits, & generalized probability + sharing ideas on connections between quantum logic and the QSVT ⚛️

I had a lot of fun giving my first philosophy (lightning) talk and catching up with quantum learning theory friends at Foundations of Quantum Computing 2025, in Edinburgh!

"WE'VE ARRANGED A society based on science and technology, in which nobody understands anything about science technology. And this combustible mixture of ignorance and power, sooner or later, is going to blow up in our faces. Who is running the science and technology in a democracy if the people don't know anything about it?" "Science is more than a body of knowledge, it's a way of thinking. A way of skeptically interrogating the universe with a fine understanding of human fallibility. If we are not able to ask skeptical questions, to interrogate those who tell us that something is true, to be skeptical of those in authority, then we're up for grabs for the next charlatan, political or religious, who comes ambling along."

I think a lot about what Carl Sagan said in one of his final interviews.

YouTube video by Erc Ocean Surfing the OCEAN - Francisca Vasconcelos

Last week, I spoke at the Surfing the Ocean ERC seminar on faster classical algorithms for finding Nash equilibria of quantum zero-sum games. In particular, we achieve an O(1/\eps) convergence rate -- a quadratic speedup over the Jain-Watrous MMWU algorithm (2009).

www.youtube.com/watch?v=lw0J...

On behalf of Qubit x Qubit:

🚀 Calling all Quantum Computing and Cybersecurity Companies in NY!

We're seeking internship hosts in NY state to provide hands-on experience in quantum computing and cybersecurity!

📨 If you’re in NY state and are interested in more details, email us at eqci@the-cs.org.

Thanks Henry 😊

YouTube video by QTML Conference Learning shallow quantum circuits with many-qubit gates - Francisca Vasconcelos

At QTML 2024, I spoke about recent work with Robert Huang on "Learning shallow quantum circuits with many-qubit gates" (a.k.a. efficient learning of QAC^0 unitaries). In this ~15min talk I discuss the project motivation, key results, and high-level proof ideas.

www.youtube.com/watch?v=iRiJ...

Very excited that our work was featured on @tomgur.bsky.social's 2024 advent calendar, alongside many great math/TCS talks from the year! 😊

Day two of #qtml2024 brings another bouquet of exciting talks, e.g, by Maria Schuld and Kristan Temme - and also my plenary talk and a small technical talk have been happening today. I like how the meeting is developing: Lots of solid, rigorous technical work.