See also my Google Scholar page.

Expository notes

  • See my teaching page for lecture notes on topics in quantum complexity theory and quantum cryptography.
  • A presentation aimed at a general mathematical audience of Mahadev’s result on Classical Verification of Quantum Computations, to appear in the Bulletin of the AMS: pdf.
  • An expository article on my work with Umesh Vazirani on device-independent quantum key distribution, aimed at a general audience of compuer scientists and published in the Communications of the ACM.
  • A simplified analysis (written in the format of a blog post) of my paper with Anand Natarajan presenting a robust test for n EPR pairs.
  • A short proof of security for a protocol for device-independent quantum key distribution in parallel introduced by Jain, Miller and Shi.
  • A simple proof of Renner’s exponential de Finetti.
  • An expository note, aimed at a general TCS audience, giving an analysis of the Blum-Luby-Rubinfeld linearity test as a game with entangled provers.

All publications

  • Computationally-secure and composable remote state preparation
    Alexandru Gheorghiu, Thomas Vidick
    Submitted, arXiv:1904.06320.
  • Classical zero-knowledge arguments for quantum computations
    Thomas Vidick, Tina Zhang
    Presented at TQC'19. Manuscript, arXiv:1902.05217.
  • Bounds on Dimension Reduction in the Nuclear Norm
    Oded Regev, Thomas Vidick
    GAFA seminar notes, arXiv:1901.09480.
  • Trading locality for time: certifiable randomness from low-depth circuits
    Matthew Coudron, Jalex Stark, Thomas Vidick
    Presented at QIP'19. Manuscript, arXiv:1810.04233.
  • Quantum proof systems for iterated exponential time, and beyond
    Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen
    Presented at QIP'19. Proceedings of STOC'19, arXiv:1805.12166.
  • Certifiable Randomness from a Single Quantum Device
    Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, Thomas Vidick
    Proceedings of FOCS'18. Presented at QIP'19, arXiv:1804.00640.
  • A three-player coherent state embezzlement game
    Zhengfeng Ji, Debbie Leung, Thomas Vidick
    Manuscript, arXiv:1802.04926.
  • Low-degree testing for quantum states
    Anand Natarajan, Thomas Vidick
    Presented at QIP'18. Proceedings of FOCS'18, arXiv:1801.03821.
  • Entanglement in non-local games and the hyperlinear profile of groups
    William Slofstra, Thomas Vidick
    Annales Henri Poincare (2018) (journal link). Presented at QIP'18, arXiv:1711.10676.
  • Practical device-independent quantum cryptography via entropy accumulation
    Rotem Arnon-Friedman, Frederic Dupuis, Omar Fawzi, Renato Renner, Thomas Vidick
    Nature Communications 9:459(2018). Journal version of "Simple and tight device-independent security proofs", arXiv:1607.01797.
  • Two-player entangled games are NP-hard
    Anand Natarajan, Thomas Vidick
    Proceedings of CCC'18, arXiv:1710.03062.
  • A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries
    Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, Thomas Vidick
    Proceedings of EUROCRYPT'19, arXiv:1710.00557.
  • Verifier-on-a-Leash new schemes for verifiable delegated quantum computation with quasilinear resources
    Andrea Coladangelo, Alex Grilo, Stacey Jeffery, Thomas Vidick
    Presented at QIP'18. Proceedings of EUROCRYPT'19, arXiv:1708.07359.
  • Parallel DIQKD from parallel repetition
    Thomas Vidick
    Manuscript, arXiv:1703.08508.
  • Rigorous renormalization group method for ground space and low-energy states of local Hamiltonians
    Brenden Roberts, Olexei I. Motrunich, Thomas Vidick
    Phys. Rev. B 96, 214203 (2017), arXiv:1703.01994.
  • Overlapping Qubits
    Rui Chao, Ben Reichardt, Chris Sutherland, Thomas Vidick
    Proceedings of ITCS'17, arXiv:1701.01062.
  • Focus on device independent quantum information
    Stefano Pironio, Valerio Scarani, Thomas Vidick
    Closing editorial for New Journal of Physics special issue on device independence..
  • Robust self-testing of many-qubit states
    Anand Natarajan, Thomas Vidick
    Proceedings of STOC'17, arXiv:1610.03574.
  • QCMA hardness of ground space connectivity for commuting Hamiltonians
    David Gosset, Jenish Mehta, Thomas Vidick
    Quantum 1, 16 (2017), arXiv:1610.03582.
  • Quantum Proofs
    Thomas Vidick, John Watrous
    NOW Foundations and Trends in Theoretical Computer Science, Vol. 11, No. 1-2 (2015) 1-215 (journal link), arXiv:1610.01664.
  • Test for a large amount of entanglement, using few measurements
    Rui Chao, Ben Reichardt, Chris Sutherland, Thomas Vidick
    Quantum, arXiv:1610.00771.
  • Entanglement of approximate quantum strategies in XOR games
    Dimiter Ostrev, Thomas Vidick
    QIC Vol.18 No.7&8, pp. 0617-0631 (2018), arXiv:1609.01652.
  • A simple proof of Renner's exponential de Finetti theorem
    Thomas Vidick, Henry Yuen
    Manuscript, arXiv:1608.04814.
  • Simple and Tight Device-Independent Security Proofs
    Rotem Arnon-Friedman, Renato Renner, Thomas Vidick
    SICOMP 48(1), 181–225 (link), arXiv:1607.01797.
  • A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem
    Steven Heilman, Thomas Vidick
    Submitted, arXiv:1603.0562.
  • Parallel repetition via fortification analytic view and the quantum case
    Mohammad Bavarian, Thomas Vidick, Henry Yuen
    Proceedings of ITCS'17, arXiv:1603.05349.
  • Rigorous RG algorithms and area laws for low energy eigenstates in 1D
    Itai Arad, Zeph Landau, Umesh Vazirani, Thomas Vidick
    Communications in Mathematical Physics, 2017. Also appeared in the proceedings of ITCS'17, arXiv:1602.08828. (video)
  • A simple proof of the detectability lemma and spectral gap amplification
    Anurag Anshu, Itai Arad, Thomas Vidick
    Phys. Rev. B 93, 205142, arXiv:1602.01210.
  • Constant-Soundness Interactive Proofs for Local Hamiltonians
    Anand Natarajan, Thomas Vidick
    Manuscript, arXiv:1512.02090.
  • Survey on nonlocal games and operator space theory
    Carlos Palazuelos, Thomas Vidick
    , arXiv:1512.00419.
  • Anchoring games for parallel repetition
    Mohammad Bavarian, Thomas Vidick, Henry Yuen
    Proceedings of STOC'17. Also presented at QIP'16, arXiv:1509.07466.
  • Interactive proofs with approximately commuting provers
    Matthew Coudron, Thomas Vidick
    Presented at QIP'16. Proceedings of ICALP'15, arXiv:1510.00102.
  • Non-signalling parallel repetition using de Finetti reductions
    Rotem Arnon-Friedman, Renato Renner, Thomas Vidick
    IEEE Transactions on Information Theory, 2014, arXiv:1411.1582.
  • A multiprover interactive proof system for the local Hamiltonian problem
    Joseph Fitzsimons, Thomas Vidick
    Proceedings of ITCS'15, arXiv:1409.026.
  • Unbounded entanglement can be needed to achieve the optimal success probability
    Laura Mancinska, Thomas Vidick
    Proceedings of ICALP'14. Journal version to appear in QIC., arXiv:1402.4145.
  • A parallel repetition theorem for entangled projection games
    Irit Dinur, David Steurer, Thomas Vidick
    Presented at QIP'14. Proceedings of CCC'14, arXiv:1310.4113.
  • The Quantum PCP Conjecture
    Dorit Aharonov, Itai Arad, Thomas Vidick
    A version of the survey appeared in the complexity column of SIGACT News. See also a related blog post, arXiv:1309.7495.
  • A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
    Zeph Landau, Umesh Vazirani, Thomas Vidick
    Proceedings of ITCS'14. Journal version in Nature Physics 11, 566-569 (2015), arXiv:1307.5143. (video)
  • Robust Randomness Amplifiers, Upper and Lower Bounds
    Matthew Coudron, Thomas Vidick, Henry Yuen
    Proceedings of RANDOM'13, arXiv:1305.6626.
  • Three-player entangled XOR games are NP-hard to approximate
    Thomas Vidick
    Appeared in FOCS'13, arXiv:1302.1242.
  • Efficient rounding for the noncommutative Grothendieck inequality
    Assaf Naor, Oded Regev, Thomas Vidick
    Proceedings of STOC'13., arXiv:1210.7656.
  • Fully device independent quantum key distribution
    Umesh Vazirani, Thomas Vidick
    Plenary talk at QIP'13. Proceedings of ITCS'14. Journal version in Phys. Rev. Lett. 113, 140501 (2014). See the erratum, arXiv:1210.181. (video)
  • Quantum XOR games
    Oded Regev, Thomas Vidick
    Presented at QIP'13. Proceedings of CCC'13, arXiv:1207.4939.
  • A multi-prover interactive proof for NEXP sound against entangled provers
    Tsuyoshi Ito, Thomas Vidick
    Appeared in FOCS'12, co-winner of the FOCS 2012 Best Paper Award. Invited for a plenary talk at QIP'13., arXiv:1207.055. (video)
  • A concentration inequality for the overlap of a vector on a large set, with application to communication complexity
    Thomas Vidick
    Chicago Journal of Theoretical Computer Science, 2012 (link).
  • Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms
    Oded Regev, Thomas Vidick
    Journal of Operator Theory 71(2), pp.491-506, Spring 2014 (link)., arXiv:1206.4025.
  • Optimal counterfeiting attacks and generalizations for Wiesner's quantum money
    Abel Molina, Thomas Vidick, John Watrous
    Proceedings of TQC'12, Lecture Notes in Computer Science Volume 7582 (2013)., arXiv:1202.401.
  • All Schatten spaces endowed with the Schur product are Q-algebras
    Jop Briet, Harry Buhrman, Troy Lee, Thomas Vidick
    Journal of Functional Analysis, 262(1), 2012..
  • Parallel Repetition of Entangled Games
    Julia Kempe, Thomas Vidick
    Appeared in STOC'11 and as a featured talk at QIP'11, arXiv:1012.4728.
  • Certifiable quantum dice - Or, exponential randomness expansion
    Umesh Vazirani, Thomas Vidick
    Appeared in STOC'12. Shorter version published in a special theme issue on The foundations of computation, physics and mentality the Turing legacy of Phil. Trans. R. Soc. A (2012) 370, 3432-3448, arXiv:1111.6054.
  • Explicit lower and upper bounds on the entangled value of multiplayer XOR games
    Jop Briet, Thomas Vidick
    Comm. Math. Phys. 321(1), 2013. Presented as a contributed talk at QIP'12., arXiv:1108.5647.
  • Does ignorance of the whole imply ignorance of the parts? - Large violations of non-contextuality in quantum theory
    Thomas Vidick, Stephanie Wehner
    Phys. Rev. Lett. 107, 030402 (2011)., arXiv:1011.6448.
  • More non-locality with less entanglement
    Thomas Vidick, Stephanie Wehner
    Phys. Rev. A 83, 052310 (2011), arXiv:1011.5206.
  • Trevisan's extractor in the presence of quantum side information
    Anindya De, Christopher Portmann, Renato Renner, Thomas Vidick
    SIAM J. Comput 41(4), 2012, arXiv:912.5514.
  • Better Gap-Hamming Lower Bounds via Better Round Elimination
    Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf
    Proceedings of RANDOM'10, arXiv:912.5276.