See also my Google Scholar page.

- 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.

Simpler Proofs of Quantumness

*Zvika Brakerski*,*Venkata Koppula*,*Umesh Vazirani*,*Thomas Vidick*

Proceedings of TQC'20, arXiv:2005.04826.Classical proofs of quantum knowledge

*Thomas Vidick*,*Tina Zhang*

Submitted, arXiv:2005.01691.Self-testing of a single quantum device under computational assumptions

*Tony Metger*,*Thomas Vidick*

Proceedings of TQC'20, arXiv:2001.09161.MIP*=RE

*Zhengfeng Ji*,*Anand Natarajan*,*Thomas Vidick*,*John Wright*,*Henry Yuen*

Manuscript. See the related introductory article, blog post, and recorded overview talk, arXiv:2001.04383.Non-interactive zero-knowledge arguments for QMA, with preprocessing

*Andrea Coladangelo*,*Thomas Vidick*,*Tina Zhang*

Crypto'20, arXiv:1911.07546.From Operator Algebras to Complexity Theory and Back

*Thomas Vidick*

Notices of the AMS, November 2019.Verifying quantum computations at scale A cryptographic leash on quantum devices

*Thomas Vidick*

Bull. Amer. Math. Soc., 2020.Computationally-secure and composable remote state preparation

*Alexandru Gheorghiu*,*Thomas Vidick*

Presented at QCRYPT'19. Proceedings of FOCS'19, arXiv:1904.06320.Classical zero-knowledge arguments for quantum computations

*Thomas Vidick*,*Tina Zhang*

Presented at TQC'19. Published inQuantum, 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*

This paper appeared in the proceedings of FOCS'13 and in SICOMP. Due to a mistake in the proof of the main result,*the paper has been withdrawn*. See the erratum for details.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.