Papers

2025

  • Magic and communication complexity
    Uma Girish, Alex May, Natalie Parham, Henry Yuen.
    [arxiv]

  • Local transformations of bipartite entanglement are rigid
    John Bostanci, Tony Metger, Henry Yuen.
    QIP 2026. ITCS 2026.
    [arxiv]

  • Random Unitaries in Constant (Quantum) Time
    Ben Foxman, Natalie Parham, Francisca Vasconcelos, Henry Yuen.
    QIP 2026. ITCS 2026.
    [arxiv]

  • A complexity theory for non-local quantum computation
    Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, Henry Yuen.
    [arxiv]

  • The Hardness of Learning Quantum Circuits and its Cryptographic Applications
    Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen.
    QCTiP 2025. ITCS 2026.
    [arxiv]

  • QMA vs. QCMA and Pseudorandomness
    Jiahiu Liu, Saachi Mutreja, Henry Yuen.
    STOC 2025.
    [arxiv]

  • Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography
    Prabhanjan Ananth, Fatih Kaleoglu, Henry Yuen.
    ITCS 2025.
    [arxiv]

2024

  • Simple constructions of linear-depth $t$-designs and pseudorandom unitaries
    Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen.
    FOCS 2024. QIP 2025.
    [arxiv]

  • Pseudorandom Strings from Pseudorandom Quantum States
    Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen.
    ITCS 2024.
    [arxiv]

  • Unitary Complexity and the Uhlmann Transformation Problem
    John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, Henry Yuen.
    QIP 2024 (Plenary talk). ITCS 2026.
    [arxiv]

  • An efficient quantum parallel repetition theorem and applications
    John Bostanci, Luowen Qian, Nick Spooner, Henry Yuen.
    QIP 2024 (Plenary talk), STOC 2024.
    [arxiv]

  • On the Pauli Spectrum of QAC0
    Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen.
    QIP 2024, STOC 2024.
    [arxiv]

2023

  • Efficiently stable presentations from error-correcting codes
    Michael Chapman, Thomas Vidick, Henry Yuen.
    [arxiv]

  • stateQIP = statePSPACE
    Tony Metger, Henry Yuen.
    QIP 2023. FOCS 2023.
    [arxiv]

  • On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions
    Prabhanjan Ananth, Zihan Hu, Henry Yuen.
    AsiaCrypt 2023.
    [arxiv]

2022

  • Unitary property testing lower bounds by polynomials
    Adrian She, Henry Yuen.
    ITCS 2023. QIP 2023.
    [arxiv]

  • Testing and Learning Quantum Juntas Nearly Optimally
    Thomas Chen, Shivam Nadimpalli, Henry Yuen.
    SODA 2023. QIP 2023.
    [arxiv]

  • Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications
    Prabhanjan Ananth, Aditya Gulati, Luowen Qian, Henry Yuen.
    QCRYPT 2022. TCC 2022. QIP 2023 (Short plenary talk).
    [arxiv]

  • An Improved Sample Complexity Lower Bound for Quantum State Tomography
    Henry Yuen.
    Quantum 7, 890 (2023).
    [journal link]

2021

  • Cryptography from Pseudorandom Quantum States
    Prabhanjan Ananth, Luowen Qian, Henry Yuen.
    CRYPTO 2022. QCRYPT 2022.
    [arxiv]

  • Quantum search-to-decision reductions and the state synthesis problem
    Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen.
    QIP 2022. CCC 2022.
    [arxiv]

  • Interactive Proofs for Synthesizing Quantum States and Unitaries
    Gregory Rosenthal and Henry Yuen.
    ITCS 2022. QIP 2022.
    [arxiv]

  • Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
    Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen.
    QIP 2022 (Plenary talk). STOC 2022.
    [arxiv]

  • Quantum soundness of testing tensor codes
    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen.
    Discrete Analysis 2022:17. A preliminary version appeared at FOCS 2021.
    [journal link]

2020

  • Rigidity of superdense coding
    Ashwin Nayak and Henry Yuen.
    ACM Transactions on Quantum Computing.
    [arxiv]

  • Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
    Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, Henry Yuen.
    PRX Quantum Vol. 1, Iss. 2.
    [journal] [arxiv]

  • Quantum Garbled Circuits
    Zvika Brakerski, Henry Yuen.
    QIP 2021. STOC 2022.
    [arxiv]

  • On the complexity of zero gap MIP*
    Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen.
    TQC 2020. ICALP 2020.
    [arxiv]

  • MIP* = RE
    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen.
    Submitted.
    [arxiv].
    Popular press coverage: Communications of the ACM, Quanta Magazine, Science News, Vice. Also see my blog post, and a more technical introduction by Thomas Vidick.

2019

  • Perfect zero knowledge for quantum multiprover interactive proofs
    Alex B. Grilo, William Slofstra, Henry Yuen.
    Quantum Information Processing (QIP) 2020. Foundations of Computer Science (FOCS) 2019.
    [arxiv]

  • Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
    Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, Henry Yuen.
    Quantum Information Processing (QIP) 2019. Symposium on Theory of Computing (STOC) 2019.
    [arxiv]

  • Quantum proof systems for iterated exponential time, and beyond
    Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen.
    Quantum Information Processing (QIP) 2019. Symposium on Theory of Computing (STOC) 2019.
    [arxiv]

2018

  • Approximate low-weight check codes and circuit lower bounds for noisy ground states
    Chinmay Nirkhe, Umesh Vazirani, Henry Yuen.
    International Colloquium of Automata, Languages, and Programming (ICALP) 2018. Theory of Quantum Computation (TQC) 2018.
    [arxiv]

  • Noise-tolerant testing of high entanglement of formation
    Rotem Arnon-Friedman, Henry Yuen.
    International Colloquium of Automata, Languages, and Programming (ICALP) 2018.
    [arxiv]

2017

  • Multiplayer parallel repetition for expander games
    Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen.
    Innovations in Theoretical Computer Science (ITCS) 2017 (Invited talk)
    [ECCC]

  • Parallel repetition via fortification: analytic view and the quantum case
    Mohammad Bavarian, Thomas Vidick, Henry Yuen.
    Theory of Quantum Computing (TQC) 2016. Innovations in Theoretical Computer Science (ITCS) 2017.
    [arxiv]

  • New security notions and feasibility results for authentication of quantum data
    Sumegha Garg, Henry Yuen, Mark Zhandry.
    CRYPTO 2017. International Conference on Quantum Cryptography (QCrypt) 2016.
    [arxiv]

  • Anchored parallel repetition for nonlocal games
    Mohammad Bavarian, Thomas Vidick, Henry Yuen.
    QIP 2016 (Plenary talk) SIAM Journal on Computing Vol. 51, Iss. 2 (2022). A preliminary version appeared in STOC 2017 as Hardness amplification for entangled games via anchoring.
    [arxiv] [journal version]

2016

  • A parallel repetition theorem for all entangled games
    Henry Yuen.
    International Colloquium of Automata, Languages,and Programming (ICALP) 2016. Quantum Information Processing (QIP) 2017.
    [arxiv]

  • Rescuing Complementarity With Little Drama
    Ning Bao, Adam Bouland, Aidan Chatwin-Davies, Jason Pollack, Henry Yuen.
    In Journal of High Energy Physics (JHEP) 2016:26 (2016).
    [arxiv] [JHEP]

  • A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian
    Dana Moshkovitz, Govind Ramnarayan, Henry Yuen.
    RANDOM 2016.
    [arxiv]

  • On the sum-of-squares degree of symmetric quadratic functions
    Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen.
    Computational Complexity Conference (CCC) 2016.
    [arxiv]

2015

  • Parallel repetition for entangled $k$-player games via fast quantum search
    Kai-Min Chung, Xiaodi Wu, Henry Yuen.
    Computational Complexity Conference (CCC) 2015.
    [arxiv] [video]

2014

  • Infinite Randomness Expansion and Amplification with a Constant Number of Devices
    Matt Coudron, Henry Yuen.
    Quantum Information Processing (QIP) 2014. Symposium on the Theory of Computing (STOC) 2014.
    [arxiv]

  • A quantum lower bound for distinguishing random functions from random permutations
    Henry Yuen.
    Quantum Information and Computation, 14(9-10), 2014.
    [arxiv]

2013

  • Robust Randomness Amplifiers: Upper and Lower Bounds
    Matt Coudron, Thomas Vidick, Henry Yuen.
    RANDOM 2013.
    [arxiv]

  • Continuous Time Channels with Interference
    Ioana Ivan, Michael Mitzenmacher, Justin Thaler, Henry Yuen.
    International Symposium on Information Theory (ISIT) 2012.
    [arxiv]

Before 2013

  • DNA Sequencing via Machine Learning and Quantum Mechanics
    F. Shimojo, K. Zhang, A. Nakano, K. Nomura, P. Vashishta, R. Kalia, H. Yuen. 2010

Notes and other manuscripts

  • Quantum soundness of the classical low individual degree test
    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen.
    Manuscript.
    [arxiv].

  • Quantum statistical query learning
    Srinivasan Arunachalam, Alex B. Grilo, Henry Yuen.
    Manuscript.
    [arxiv]

  • Raz-McKenzie simulation with the inner product gadget
    Xiaodi Wu, Penghui Yao, Henry Yuen.
    Manuscript.
    [ECCC]

  • A simple proof of Renner’s exponential de Finetti theorem
    Thomas Vidick, Henry Yuen.
    Manuscript.
    [arxiv]