publications | Francisca Vasconcelos

preprint

Methods for Reducing Ancilla-Overhead in Block Encodings

Francisca Vasconcelos, and András Gilyén

2025

⭐ Talk at QSim 2025 (New York City)
⭐ Talk at QTML 2024 (Melbourne).

Abs arXiv Bib Slides

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 ways. In Part I, we prove the existence of a "space-time tradeoff" by deriving an algorithm that, for any block encoding, approximately uncomputes all but one of its ancilla (freeing up those ancillae for reuse in later parts of a quantum algorithm). In Part II, we evaluate the minimum number of ancillae required to perform coherent multiplication of block encodings. We prove that logarithmic ancillae is optimal for exact multiplication of block encodings. However, in certain block encoding regimes, we show that approximate multiplication of block encodings can be achieved to high-precision with just one ancilla.
@article{vasconcelos2025methods, title = {Methods for Reducing Ancilla-Overhead in Block Encodings}, author = {Vasconcelos, Francisca and Gilyén, András}, year = {2025}, }

conference

Random Unitaries in Constant (Quantum) Time

Ben Foxman*, Natalie Parham*, Francisca Vasconcelos*, and Henry Yuen*

In 17th Annual Innovations in Theoretical Computer Science (ITCS), 2026

⭐ Talk at QIP 2026 (Riga).

Abs arXiv Bib

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 unitary designs and pseudorandom unitaries (PRUs) using Θ(\log \log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of \emphconstant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit \textttTOFFOLI gates, (b) many-qubit \textttFANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit \textttTOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class \QAC^0. Finally, our results suggest a new approach towards proving that \textttPARITY is not computable in \QAC^0, a long-standing question in quantum complexity theory.
title = {Random Unitaries in Constant (Quantum) Time}, author = {Foxman*, Ben and Parham*, Natalie and Vasconcelos*, Francisca and Yuen*, Henry}, year = {2026}, booktitle = {17th Annual Innovations in Theoretical Computer Science (ITCS)}, organization = {LIPIcs}, }

Learning shallow quantum circuits with many-qubit gates

Francisca Vasconcelos, and Hsin-Yuan Huang

In 38th Annual Conference on Learning Theory (COLT), 2025

⭐ Talk at QTML 2024 (Melbourne).

Abs arXiv Bib HTML Slides

We present the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, we provide a quasi-polynomial time and sample complexity algorithm for learning unknown QAC0 circuits – constant-depth circuits with arbitrary single-qubit gates and polynomially many CZ gates of unbounded width – up to inverse-polynomially small error. Furthermore, we show that the learned unitary can be efficiently synthesized in poly-logarithmic depth. This work expands the family of efficiently learnable quantum circuits, notably since in finite-dimensional circuit geometries, QAC0 circuits require polynomial depth to implement.
title = {Learning shallow quantum circuits with many-qubit gates}, author = {Vasconcelos, Francisca and Huang, Hsin-Yuan}, booktitle = {38th Annual Conference on Learning Theory (COLT)}, organization = {ACM}, year = {2025}, }

On the Pauli Spectrum of QAC⁰

Shivam Nadimpalli*, Natalie Parham*, Francisca Vasconcelos*, and Henry Yuen*

In 56th Annual ACM Symposium on Theory of Computing (STOC), 2024

⭐ Talk at QIP 2024 (Taipei)
I also presented at: Simons Quantum Pod, Berkeley CS Theory Lunch, CWI QuSoft Seminar.

Abs arXiv Bib HTML Slides Talk

The circuit class QAC⁰ was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC⁰ cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC⁰ circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC⁰ circuits. We conjecture that the Pauli spectrum of \mathsfQAC^0 circuits satisfies low-degree concentration, in analogy to the famous Linial, Nisan, Mansour theorem on the low-degree Fourier concentration of AC⁰ circuits. If true, this conjecture immediately implies that polynomial-size QAC⁰ circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC⁰ circuits with at most n^O(1/d) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute: (1) the n-bit parity function on more than (1/2 + 2^(-Ω(n^1/d)))-fraction of inputs, and (2) the n-bit majority function on more than (1 - 1/poly(n))-fraction of inputs. Additionally we show that this class of QAC⁰ circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC⁰ circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.
title = {On the Pauli Spectrum of QAC0}, author = {Nadimpalli*, Shivam and Parham*, Natalie and Vasconcelos*, Francisca and Yuen*, Henry}, booktitle = {56th Annual ACM Symposium on Theory of Computing (STOC)}, organization = {ACM}, year = {2024}, talk = {https://www.youtube.com/watch?v=mpRpJJORAaY}, }

Extending Quantum State Tomography for Superconducting Quantum Processors

Francisca Vasconcelos, Morten Kjaergaard, Tim Menke, Simon Gustavsson, Terry P Orlando, and William D Oliver

In Microsystems Annual Research Conference, 2019

🎓 MIT Undergraduate EECS SuperUROP Thesis
🏆 MARC Conference Top-10 Presentation, Top Student Presentation

Abs Bib HTML PDF Poster Proceedings

Quantum state tomography (QST), or the reconstruction of the density matrix of a quantum state via measurements, is critcal to ensure the proper functionality of qubits and quantum operations in a quantum computer. In this work, we extend existing QST code based on Maximum Likelihood Estimation from two to an arbitrary number of qubits and from one to arbitrarily many energy levels. A 100x algorithmic speedup is achieved over the original implementation. However, the exponential scaling of the density matrix makes this MLE-based algorithm infeasible for analysis over 6-qubits on a standard computer. To mitigate this limitation, we propose a novel deep-learning based approach to QST. Utilizing the CycleGAN architecture from the field of computer vision, we aim to address the issues of scalability and bias that plague current QST implementations.
title = {Extending Quantum State Tomography for Superconducting Quantum Processors}, author = {Vasconcelos, Francisca and Kjaergaard, Morten and Menke, Tim and Gustavsson, Simon and Orlando, Terry P and Oliver, William D}, booktitle = {Microsystems Annual Research Conference}, year = {2019}, organization = {MIT MTL}, url = {https://mtlsites.mit.edu/mtlexpo/marc2019/}, }

Person-Following UAVs

Francisca Vasconcelos, and Nuno Vasconcelos

In IEEE Winter Conference on Applications of Computer Vision (WACV), 2016

🏆 Intel ISEF 2015: “Robotics & Intelligent Machines” 4th Place Grand Award

Abs Bib HTML PDF Talk

We consider the design of vision-based control algorithms for unmanned aerial vehicles (UAVs), so as to enable a UAV to autonomously follow a person. A new vision-based control architecture is proposed with the goals of 1) robustly following the user and 2) implementing following behaviors programmed by manipulation of visual patterns. This is achieved within a detection/tracking paradigm, where the target is a programmable badge worn by the user. This badge contains a visual pattern with two components. The first is fixed and used to locate the user. The second is variable and implements a code used to program the UAV behavior. A biologically inspired tracking/recognition architecture, combining bottom-up and top-down saliency mechanisms, a novel image similarity measure, and an affine validation procedure, is proposed to detect the badge in the scene. The badge location is used by a control algorithm to adjust the UAV flight parameters so as to maintain the user in the center of the field of view. The detected badge is further analyzed to extract the visual code that commands the UAV behavior This is used to control the height and distance of the UAV relative to the user.
title = {Person-Following UAVs}, author = {Vasconcelos, Francisca and Vasconcelos, Nuno}, booktitle = {IEEE Winter Conference on Applications of Computer Vision (WACV)}, pages = {1--9}, year = {2016}, organization = {IEEE}, doi = {10.1109/WACV.2016.7477660}, talk = {https://www.youtube.com/watch?v=fOFrXrRGFOc}, }

journal

A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

Francisca Vasconcelos*, Emmanouil-Vasileios Vlatakis-Gkaragkounis*, Panayotis Mertikopoulos, Giorgios Piliouras, and Michael I. Jordan

Quantum Journal, 2025

⭐ Long talk at QTML 2023 (CERN).
I also presented at: Surfing the Ocean ERC Seminar.

Abs arXiv Bib HTML Code Slides Talk

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, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of O(d/ε²) iterations to ε-Nash equilibria in the 4^d-dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as O(d/ε) iterations to ε-Nash equilibria. This quadratic speed-up relative to Jain and Watrous’ original algorithm sets a new benchmark for computing ε-Nash equilibria in quantum zero-sum games.
@article{vasconcelos2025qzsg, title = {A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games}, author = {Vasconcelos*, Francisca and Vlatakis-Gkaragkounis*, Emmanouil-Vasileios and Mertikopoulos, Panayotis and Piliouras, Giorgios and Jordan, Michael I.}, journal = {Quantum Journal}, year = {2025}, talk = {https://www.youtube.com/watch?v=lw0JTF7ngKk}, }

UncertaINR: Uncertainty Quantification of End-to-End Implicit Neural Representations for Computed Tomography

Francisca Vasconcelos*, Bobby He*, Nalini Singh, and Yee Whye Teh

Transactions on Machine Learning Research (TMLR), 2023

🎓 Oxford MSc in Statistical Sciences Thesis
Early version of work (Abstract) also presented at NeurIPS 2021 workshops:
Med-NeurIPS (Oral - 6.66% Acceptance Rate) & Bayesian Deep Learning (Poster)

Abs arXiv Bib HTML Code Slides Talk

Implicit neural representations (INRs) have achieved impressive results for scene reconstruction and computer graphics, where their performance has primarily been assessed on reconstruction accuracy. As INRs make their way into other domains, where model predictions inform high-stakes decision-making, uncertainty quantification of INR inference is becoming critical. To that end, we study a Bayesian reformulation of INRs, UncertaINR, in the context of computed tomography, and evaluate several Bayesian deep learning implementations in terms of accuracy and calibration. We find that they achieve well-calibrated uncertainty, while retaining accuracy competitive with other classical, INR-based, and CNN-based reconstruction techniques. Contrary to common intuition in the Bayesian deep learning literature, we find that INRs obtain the best calibration with computationally efficient Monte Carlo dropout, outperforming Hamiltonian Monte Carlo and deep ensembles. Moreover, in contrast to the best-performing prior approaches, UncertaINR does not require a large training dataset, but only a handful of validation images.
@article{vasconcelos2023uinr, title = {Uncerta{INR}: Uncertainty Quantification of End-to-End Implicit Neural Representations for Computed Tomography}, author = {Vasconcelos*, Francisca and He*, Bobby and Singh, Nalini and Teh, Yee Whye}, journal = {Transactions on Machine Learning Research (TMLR)}, issn = {2835-8856}, year = {2023}, url = {https://openreview.net/forum?id=jdGMBgYvfX}, volume = {April}, talk = {https://youtu.be/cD7Wx4F_EjQ}, }

Impact of ionizing radiation on superconducting qubit coherence

Antti P Vepsäläinen, Amir H Karamlou, John L Orrell, Akshunna S Dogra, Ben Loer, Francisca Vasconcelos, and 7 more authors

Nature, 2020

⭐ Featured in MIT News

Abs arXiv Bib HTML

Technologies that rely on quantum bits (qubits) require long coherence times and high-fidelity operations. Superconducting qubits are one of the leading platforms for achieving these objectives. However, the coherence of superconducting qubits is affected by the breaking of Cooper pairs of electrons. The experimentally observed density of the broken Cooper pairs, referred to as quasiparticles, is orders of magnitude higher than the value predicted at equilibrium by the Bardeen-Cooper-Schrieffer theory of superconductivity. Previous work has shown that infrared photons considerably increase the quasiparticle density, yet even in the best-isolated systems, it remains much higher than expected, suggesting that another generation mechanism exists. Here we provide evidence that ionizing radiation from environmental radioactive materials and cosmic rays contributes to this observed difference. The effect of ionizing radiation leads to an elevated quasiparticle density, which we predict would ultimately limit the coherence times of superconducting qubits of the type measured here to milliseconds. We further demonstrate that radiation shielding reduces the flux of ionizing radiation and thereby increases the energy-relaxation time. Albeit a small effect for today’s qubits, reducing or mitigating the impact of ionizing radiation will be critical for realizing fault-tolerant superconducting quantum computers.
@article{vepsalainen2020impact, title = {Impact of ionizing radiation on superconducting qubit coherence}, author = {Veps{\"a}l{\"a}inen, Antti P and Karamlou, Amir H and Orrell, John L and Dogra, Akshunna S and Loer, Ben and Vasconcelos, Francisca and Kim, David K and Melville, Alexander J and Niedzielski, Bethany M and Yoder, Jonilyn L and Orlando, Terry P and Gustavsson, Simon and Oliver, William D}, journal = {Nature}, volume = {584}, number = {7822}, pages = {551--556}, year = {2020}, doi = {10.1038/s41586-020-2619-8}, publisher = {Nature Publishing Group UK London}, url = {https://doi.org/10.1038/s41586-020-2619-8}, }
Generating spatially entangled itinerant photons with waveguide quantum electrodynamics

Bharath Kannan, Daniel L Campbell, Francisca Vasconcelos, Roni Winik, David K Kim, Morten Kjaergaard, and 7 more authors

Science Advances, 2020

⭐ Featured in MIT News

Abs arXiv Bib HTML

Realizing a fully connected network of quantum processors requires the ability to distribute quantum entanglement. For distant processing nodes, this can be achieved by generating, routing, and capturing spatially entangled itinerant photons. In this work, we demonstrate the deterministic generation of such photons using superconducting transmon qubits that are directly coupled to a waveguide. In particular, we generate two-photon N00N states and show that the state and spatial entanglement of the emitted photons are tunable via the qubit frequencies. Using quadrature amplitude detection, we reconstruct the moments and correlations of the photonic modes and demonstrate state preparation fidelities of 84%. Our results provide a path toward realizing quantum communication and teleportation protocols using itinerant photons generated by quantum interference within a waveguide quantum electrodynamics architecture.
@article{kannan2020generating, title = {Generating spatially entangled itinerant photons with waveguide quantum electrodynamics}, author = {Kannan, Bharath and Campbell, Daniel L and Vasconcelos, Francisca and Winik, Roni and Kim, David K and Kjaergaard, Morten and Krantz, Philip and Melville, Alexander and Niedzielski, Bethany M and Yoder, Jonilyn L and Orlando, Terry P and Gustavsson, Simon and Oliver, William D}, journal = {Science Advances}, volume = {6}, number = {41}, pages = {eabb8780}, year = {2020}, doi = {10.1126/sciadv.abb8780}, url = {https://www.science.org/doi/10.1126/sciadv.abb8780}, publisher = {American Association for the Advancement of Science}, }

article

Why Quantum Education?

Francisca Vasconcelos

SPIE Photonics Focus, May 2023

Bib HTML PDF

@article{vasconcelos2023qed,
  title = {Why Quantum Education?},
  author = {Vasconcelos, Francisca},
  journal = {SPIE Photonics Focus},
  volume = {4},
  number = {3},
  pages = {6--7},
  month = may,
  year = {2023},
  url = {https://spie.org/news/photonics-focus/mayjune-2023/teaching-about-quantum-science},
  issn = {2706-8110},
}

Quantum Computing @ MIT: The Past, Present, and Future of the Second Revolution in Computing

Francisca Vasconcelos

MIT Undergraduate Research Journal, May 2019

Abs arXiv Bib PDF

This article provides an overview of the history, theoretical basis, and different implementations of quantum computers. In Fall 2018, four MIT faculty – Isaac Chuang, Dirk Englund, Aram Harrow, and William Oliver – at the forefront of quantum computation and information research were interviewed. They provided personal perspectives on the development of the field, as well as insight to its near-term trajectory. There has been a lot of recent media hype surrounding quantum computation, so in this article we present an academic view of the matter, specifically highlighting progress being made at MIT.
@article{vasconcelos2019qmit, title = {Quantum Computing @ MIT: The Past, Present, and Future of the Second Revolution in Computing}, author = {Vasconcelos, Francisca}, journal = {MIT Undergraduate Research Journal}, volume = {38}, number = {Fall 2019}, pages = {13--24}, year = {2019}, url = {https://doi.org/10.48550/arXiv.2002.05559}, doi = {10.48550/arXiv.2002.05559}, }

thesis

Essays in the Philosophy of Physics, Science, Metaphysics, and Epistemology

Francisca Vasconcelos

University of Oxford, Jun 2022

Submitted in completion of an MSt in Philosophy of Physics.

Bib PDF

@mastersthesis{vasconcelos2022thesis,
  author = {Vasconcelos, Francisca},
  title = {Essays in the Philosophy of Physics, Science, Metaphysics, and Epistemology},
  school = {University of Oxford},
  year = {2022},
  month = jun,
}

Uncertainty in Implicit Neural Representations for Medical Imaging

Francisca Vasconcelos

University of Oxford, Sep 2021

Submitted in completion of an MSc in Statistical Sciences.

Bib PDF

@mastersthesis{vasconcelos2021thesis,
  author = {Vasconcelos, Francisca},
  title = {Uncertainty in Implicit Neural Representations for Medical Imaging},
  school = {University of Oxford},
  year = {2021},
  month = sep,
}