Publications

2024

  • Pseudorandom unitaries with non-adaptive security. Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen. [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). [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

  • A parallel repetition theorem in the quantum commuting operator model. Junqiao Lin, William Slofstra, Henry Yuen. Submitted.

  • 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] [Chinmay’s QIP talk]

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

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

  • 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] [Anand’s FOCS talk]

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] [Zvika’s STOC talk]

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

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

  • MIP* = RE. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen. Submitted. [arxiv].

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

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

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