Publications

2021

  • Interactive Proofs for Synthesizing Quantum States and Unitaries
    Gregory Rosenthal and Henry Yuen
    Submitted
    [arxiv]

  • Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
    Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen
    [arxiv]

  • Quantum soundness of testing tensor codes
    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
    To appear in Foundations of Computer Science (FOCS) 2021
    This paper supersedes the paper titled Quantum soundness of the classical low individual degree test.

2020

  • Rigidity of superdense coding
    Ashwin Nayak and Henry Yuen
    Submitted
    [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
    Quantum Information Processing (QIP) 2021
    [arxiv]

  • On the complexity of zero gap MIP*
    Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen
    Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC) 2020
    International Colloquium on Automata, Languages, and Programming (ICALP) 2020
    [arxiv]

  • Quantum statistical query learning
    Srinivasan Arunachalam, Alex B. Grilo, Henry Yuen
    Submitted
    [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
    Quantum Information Processing (QIP) 2016 (Plenary talk)
    Symposium on the Theory of Computing (STOC) 2017 (appears as Hardness amplification for entangled games via anchoring)
    [arxiv]

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] [QIP 2017 talk]

  • 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] [blog post] [American Scientist article by Scott Aaronson]

  • 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

  • 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]

  • On the limits of communication with non-local resources
    Xiaodi Wu, Henry Yuen
    Manuscript
    [pdf]