About

Andrea Coladangelo joined the University of Washington faculty in January 2023 as an Assistant Professor in the Paul G. Allen School of Computer Science & Engineering. His focus areas include Software & Hardware Systems, and Theory & Models of Computation. He is broadly interested in quantum computation, with recent research centered on understanding the interplay between quantum computation and cryptography. His work has involved studying foundational questions about entanglement and quantum correlations, particularly in the context of certifying quantum devices. Prior to his appointment at UW, Coladangelo was a postdoctoral researcher at UC Berkeley and the Simons Institute, working with Umesh Vazirani. He earned his PhD at Caltech under the supervision of Thomas Vidick. His academic background also includes a B.A. in Mathematics from the University of Oxford and a Master in Mathematics from the University of Cambridge. Additionally, he co-founded qBraid, a cloud-based platform dedicated to learning quantum computing and developing quantum algorithms. He co-leads the Quantum group and is part of the Theory and Crypto groups at the Allen School.

Research topics

• Computer science
• Theoretical computer science
• Mathematics
• Discrete mathematics
• Physics

Selected publications

• The Power of Two Bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements

  ArXiv.org · 2026-02-12

  articleOpen access1st authorCorresponding

  A central task in quantum information science is state certification: testing whether an unknown state is $ε_1$-close to a fixed target state, or $ε_2$-far. Recent work has shown that surprisingly simple measurement protocols--comprising only single-qubit measurements--suffice to certify arbitrary $n$-qubit states [Huang, Preskill, Soleimanifar '25; Gupta, He, O'Donnell '25]. However, these certification protocols are not robust: rather than allowing constant $ε_1$, they can only positively certify states within $ε_1=O(1/n)$ trace distance of the target. In many experimental settings, the appropriate error tolerance is constant as the system size grows, so this lack of robustness renders existing tests inapplicable at scale, no matter how many times the test is repeated. Here we present robust certification protocols based on few-qubit measurements that apply to all but a $O(2^{-n})$-fraction of pure target states. Our first protocol achieves constant robustness, i.e. $ε_1=Θ(1)$, using a single $O(\log n)$-qubit measurement along with single-qubit measurements in the $Z$ or $X$ basis on the other qubits. As a corollary of its robustness, this protocol also achieves constant (in $n$) copy complexity, which is optimal. Our second protocol uses exclusively single-qubit measurements and is nearly robust: $ε_1=Ω(1/\log n)$. Our tests are based on a new uncertainty principle for conditional fidelities, which may be of independent interest.

  PublisherOA PDF

• The Curious Case of "XOR Repetition" of Monogamy-Of-Entanglement Games

  Leibniz-Zentrum für Informatik (Schloss Dagstuhl) · 2026-01-01

  articleOpen access1st authorCorresponding

  In this work, we consider "decision" variants of a well-known monogamy-of-entanglement game by Tomamichel, Fehr, Kaniewski, and Wehner [New Journal of Physics '13]. In its original "search" variant, Alice prepares a (possibly entangled) state on registers ABC; register 𝖠, consisting of n qubits, is sent to a Referee, while 𝖡 and 𝖢 are sent to Bob and Charlie; the Referee then measures each qubit in the standard or Hadamard basis (chosen uniformly at random). The basis choices are sent to Bob and Charlie, whose goal is to simultaneously guess the Referee’s n-bit measurement outcome string x. Tomamichel et al. show that the optimal winning probability is cos^{2n}(π/8), following a perfect parallel repetition theorem. We consider the following "decision" variants of this game: - Variant 1, "XOR repetition": Bob and Charlie’s goal is to guess the XOR of all the bits of x. Ananth et al. [Asiacrypt '24] conjectured that the optimal advantage over random guessing decays exponentially in n. Surprisingly, we show that this conjecture is false, and, in fact, there is no decay at all: there exists a strategy that wins with probability cos²(π/8) ≈ 0.85 for any n. Moreover, this strategy does not involve any entanglement between Alice, Bob, and Charlie! - Variant 2, "Goldreich-Levin": The Referee additionally samples a uniformly random n-bit string r that is sent to Bob and Charlie along with the basis choices. Their goal is to guess the parity of r⋅ x. We show that the optimal advantage over random guessing decays exponentially in n for the restricted class of adversaries that do not share entanglement. A similar result was already shown by Champion et al. and Çakan et al.; we give a more direct proof. Showing that Variant 2 is "secure" (i.e., that the optimal winning probability is exponentially close to 1/2) against general adversaries would imply the existence of an information-theoretically "unclonable bit". We put forward a reasonably concrete conjecture that is equivalent to the general security of Variant 2.

  PublisherOA PDFDOI

• The Power of Two Bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements

  Open MIND · 2026-02-12

  preprint1st authorCorresponding

  A central task in quantum information science is state certification: testing whether an unknown state is $ε_1$-close to a fixed target state, or $ε_2$-far. Recent work has shown that surprisingly simple measurement protocols--comprising only single-qubit measurements--suffice to certify arbitrary $n$-qubit states [Huang, Preskill, Soleimanifar '25; Gupta, He, O'Donnell '25]. However, these certification protocols are not robust: rather than allowing constant $ε_1$, they can only positively certify states within $ε_1=O(1/n)$ trace distance of the target. In many experimental settings, the appropriate error tolerance is constant as the system size grows, so this lack of robustness renders existing tests inapplicable at scale, no matter how many times the test is repeated. Here we present robust certification protocols based on few-qubit measurements that apply to all but a $O(2^{-n})$-fraction of pure target states. Our first protocol achieves constant robustness, i.e. $ε_1=Θ(1)$, using a single $O(\log n)$-qubit measurement along with single-qubit measurements in the $Z$ or $X$ basis on the other qubits. As a corollary of its robustness, this protocol also achieves constant (in $n$) copy complexity, which is optimal. Our second protocol uses exclusively single-qubit measurements and is nearly robust: $ε_1=Ω(1/\log n)$. Our tests are based on a new uncertainty principle for conditional fidelities, which may be of independent interest.

  DOI

• The Power of a Single Haar Random State: Constructing and Separating Quantum Pseudorandomness

  Lecture notes in computer science · 2025-01-01 · 4 citations

  book-chapter
  PublisherDOI

• A Meta-Complexity Characterization of Minimal Quantum Cryptography

  ArXiv.org · 2025-10-09

  preprintOpen access

  We give a meta-complexity characterization of EFI pairs, which are considered the "minimal" primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy. A key technical step in our proof, which may be of independent interest, is to show that the existence of EFI pairs is equivalent to the existence of non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). As a corollary, we get an alternative, arguably simpler, construction of a universal EFI pair.

  PublisherOA PDFDOI

• MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)

  ArXiv.org · 2025-06-28

  preprintOpen access1st authorCorresponding

  The MPC-in-the-head technique (Ishai et al., STOC 2007) is a celebrated method to build zero-knowledge protocols with desirable theoretical properties and high practical efficiency. This technique has generated a large body of research and has influenced the design of real-world post-quantum cryptographic signatures. In this work, we present a generalization of the MPC-in-the-head paradigm to the quantum setting, where the MPC is running a quantum computation. As an application of our framework, we propose a new approach to build zero-knowledge protocols where security holds even against a verifier that can obtain a superposition of transcripts. This notion was pioneered by Damgard et al., who built a zero-knowledge protocol for NP (in the common reference string model) secure against superposition attacks, by relying on perfectly hiding and unconditionally binding dual-mode commitments. Unfortunately, no such commitments are known from standard cryptographic assumptions. In this work we revisit this problem, and present two new three-round protocols in the common reference string model: (i) A zero-knowledge argument for NP, whose security reduces to the standard learning with errors (LWE) problem. (ii) A zero-knowledge argument for QMA from the same assumption.

  PublisherOA PDFDOI

• The curious case of "XOR repetition" of monogamy-of-entanglement games

  ArXiv.org · 2025-09-01

  preprintOpen access1st authorCorresponding

  In this work, we consider "decision" variants of a monogamy-of-entanglement game by Tomamichel, Fehr, Kaniewski, and Wehner [New Journal of Physics '13]. In its original "search" variant, Alice prepares a (possibly entangled) state on registers $\mathsf{ABC}$; register $\mathsf{A}$, consisting of $n$ qubits, is sent to a Referee, while $\mathsf{B}$ and $\mathsf{C}$ are sent to Bob and Charlie; the Referee then measures each qubit in the standard or Hadamard basis (chosen uniformly at random). The basis choices are sent to Bob and Charlie, whose goal is to simultaneously guess the Referee's $n$-bit outcome string $x$. Tomamichel et al. show that the optimal winning probability is $\cos^{2n} {(\fracπ{8})}$, following a perfect parallel repetition theorem. We consider the following "decision" variants of this game: - Variant 1, "XOR repetition": Bob and Charlie's goal is to guess the XOR of all the bits of $x$. Ananth et al. [Asiacrypt '24] conjectured that the optimal advantage over random guessing decays exponentially in $n$. Surprisingly, we show that this conjecture is false, and, in fact, there is no decay at all: there exists a strategy that wins with probability $\cos^2{(\fracπ{8})} \approx 0.85$ for any $n$. - Variant 2, "Goldreich-Levin": The Referee additionally samples a uniformly random $n$-bit string $r$ that is sent to Bob and Charlie along with the basis choices. Their goal is to guess the parity of $r\cdot x$. We show that the optimal advantage over random guessing decays exponentially in $n$ for the restricted class of adversaries that do not share entanglement. A similar result was already shown by Champion et al. and Çakan et al.; we give a more direct proof. Additionally, we put forward a reasonably concrete conjecture that is equivalent to exponential decay for general adversaries.

  PublisherOA PDFDOI

• How to Use Quantum Indistinguishability Obfuscation

  2024-06-10 · 8 citations

  articleOpen access1st authorCorresponding

  Quantum copy protection, introduced by Aaronson, enables giving out a quantum program-description that cannot be meaningfully duplicated. Despite over a decade of study, copy protection is only known to be possible for a very limited class of programs. As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of classical programs. We show that applying qsiO to a program immediately achieves best-possible copy protection. Our second contribution is to show that, assuming injective one-way functions exist, qsiO is concrete copy protection for a large family of puncturable programs --- significantly expanding the class of copy-protectable programs. A key tool in our proof is a new variant of unclonable encryption (UE) that we call coupled unclonable encryption (cUE). While constructing UE in the standard model remains an important open problem, we are able to build cUE from one-way functions. If we additionally assume the existence of UE, then we can further expand the class of puncturable programs for which qsiO is copy protection. Finally, we construct qsiO relative to an efficient quantum oracle.

  PublisherOA PDFDOI

• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model

  Quantum · 2024-05-02 · 16 citations

  articleOpen access1st authorCorresponding

  Copy-protection allows a software distributor to encode a program in such a way that it can be evaluated on any input, yet it cannot be "pirated" – a notion that is impossible to achieve in a classical setting. Aaronson (CCC 2009) initiated the formal study of quantum copy-protection schemes, and speculated that quantum cryptography could offer a solution to the problem thanks to the quantum no-cloning theorem. In this work, we introduce a quantum copy-protection scheme for a large class of evasive functions known as "compute-and-compare programs" – a more expressive generalization of point functions. A compute-and-compare program <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">C</mml:mi><mml:mi mathvariant="sans-serif">C</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>y</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:math> is specified by a function <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi></mml:math> and a string <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>y</mml:mi></mml:math> within its range: on input <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>x</mml:mi></mml:math>, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="sans-serif">C</mml:mi><mml:mi mathvariant="sans-serif">C</mml:mi></mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>f</mml:mi><mml:mo>,</mml:mo><mml:mi>y</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:math> outputs <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>1</mml:mn></mml:math>, if <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>y</mml:mi></mml:math>, and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>0</mml:mn></mml:math> otherwise. We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM), which makes it the first copy-protection scheme to enjoy any level of provable security in a standard cryptographic model. As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing", introduced very recently by Ananth and La Placa (eprint 2020), with a standard security bound in the QROM, i.e. guaranteeing negligible adversarial advantage. Finally, as a third contribution, we elucidate the relationship between unclonable encryption and copy-protection for multi-bit output point functions.

  PublisherOA PDFDOI

• On black-box separations of quantum digital signatures from pseudorandom states

  arXiv (Cornell University) · 2024-02-13

  preprintOpen access1st authorCorresponding

  It is well-known that digital signatures can be constructed from one-way functions in a black-box way. While one-way functions are essentially the minimal assumption in classical cryptography, this is not the case in the quantum setting. A variety of qualitatively weaker and inherently quantum assumptions (e.g. EFI pairs, one-way state generators, and pseudorandom states) are known to be sufficient for non-trivial quantum cryptography. While it is known that commitments, zero-knowledge proofs, and even multiparty computation can be constructed from these assumptions, it has remained an open question whether the same is true for quantum digital signatures schemes (QDS). In this work, we show that there $\textit{does not}$ exist a black-box construction of a QDS scheme with classical signatures from pseudorandom states with linear, or greater, output length. Our result complements that of Morimae and Yamakawa (2022), who described a $\textit{one-time}$ secure QDS scheme with classical signatures, but left open the question of constructing a standard $\textit{multi-time}$ secure one.

  PublisherOA PDFDOI

Frequent coauthors

• James Bartusek

  15 shared

• Fermi Ma

  11 shared

• Dakshita Khurana

  11 shared

• Atul Singh Arora

  Park University

  9 shared

• Stacey Jeffery

  7 shared

• Christian Majenz

  7 shared

• Thomas Vidick

  7 shared

• Alex B. Grilo

  6 shared

Education

• B.A., Mathematics

  University of Oxford

• M.A., Mathematics

  University of Cambridge

• Ph.D.

  California Institute of Technology (Caltech)