IC Colloquium: Testing quantum systems in the high-complexity regime
By: Thomas Vidick - California Institute of Technology
Abstract
From carefully crafted quantum algorithms to information-theoretic security in cryptography, a quantum computer can achieve impressive feats with no classical analogue. Can their correct realization be verified? When the power of the device greatly surpasses that of the user, what means of control remain available to the user?
In the talk I will describe my work providing solutions to this question in two different settings. First we will discuss the model of quantum multiprover interactive proof systems, which provides a complexity-theoretic framework for the familiar setting of Bell inequalities from Physics. I will describe how a combination of classical techniques, such as the PCP theorem, and insights unique to quantum computing, such as the uncertainty principle, lead to protocols for testing randomness, entanglement, and quantum computations.
In the second part of the talk I will focus on a more recent model where testing is done under a post-quantum computational assumption. We will show how a hardness assumption can serve as an effective "classical leash" on a powerful quantum system.
The two most relevant publications for the talk are arXiv:2001.04383 and arXiv:1804.00640.
For anyone interested in broader-audience accounts, I can suggest:
* An article I wrote for the notices of the AMS in 2019, which motivates the study of quantum multiprover interactive proofs from a mathematical (operator algebras) angle:
https://www.ams.org/journals/notices/201910/rnoti-p1618.pdf
* An article published in the Bulletin of the AMS on the topic of the second part of the talk, verification under computational assumptions:
http://users.cms.caltech.edu/~vidick/notes/verification_bulletin.pdf.
Thomas Vidick is Professor of Computing and Mathematical Sciences at the California Institute of Technology. He received a B.A.
in pure mathematics from École Normale Supérieure in Paris, a Masters in Computer Science from Université Paris 7 and a Ph.D. from UC Berkeley.
His Ph.D. thesis was awarded the Bernard Friedman memorial prize in applied mathematics. Before joining Caltech he was a postdoctoral associate at the Massachusetts Institute of Technology. His paper “A multi-prover interactive proof for NEXP sound against entangled provers”, with Tsuyoshi Ito, was co-awarded the best paper award at FOCS’12. His is the recipient of a Presidential Early-Career Award (PECASE, 2019), an FSMP research chair (2020) and a Simons Investigator Award (2021-).
Vidick's research is situated at the interface of theoretical computer science, quantum information and cryptography. He is interested in applying techniques from computer science, such as complexity theory, to study problems in quantum computing. He is most well-known for his work on the study of entanglement in interactive proof systems, through the complexity class MIP*. He made multiple contributions to quantum cryptography, including the first proof of security of device-independent quantum key distribution. He is also known for developing the first polynomial-time algorithm for computing ground states of gapped one-dimensional quantum spin systems.
Bio
Thomas Vidick is Professor of Computing and Mathematical Sciences at the California Institute of Technology. He received a B.A.
in pure mathematics from École Normale Supérieure in Paris, a Masters in Computer Science from Université Paris 7 and a Ph.D. from UC Berkeley.
His Ph.D. thesis was awarded the Bernard Friedman memorial prize in applied mathematics. Before joining Caltech he was a postdoctoral associate at the Massachusetts Institute of Technology. His paper “A multi-prover interactive proof for NEXP sound against entangled provers”, with Tsuyoshi Ito, was co-awarded the best paper award at FOCS’12. His is the recipient of a Presidential Early-Career Award (PECASE, 2019), an FSMP research chair (2020) and a Simons Investigator Award (2021-).
Vidick's research is situated at the interface of theoretical computer science, quantum information and cryptography. He is interested in applying techniques from computer science, such as complexity theory, to study problems in quantum computing. He is most well-known for his work on the study of entanglement in interactive proof systems, through the complexity class MIP*. He made multiple contributions to quantum cryptography, including the first proof of security of device-independent quantum key distribution. He is also known for developing the first polynomial-time algorithm for computing ground states of gapped one-dimensional quantum spin systems.
More information
Abstract
From carefully crafted quantum algorithms to information-theoretic security in cryptography, a quantum computer can achieve impressive feats with no classical analogue. Can their correct realization be verified? When the power of the device greatly surpasses that of the user, what means of control remain available to the user?
In the talk I will describe my work providing solutions to this question in two different settings. First we will discuss the model of quantum multiprover interactive proof systems, which provides a complexity-theoretic framework for the familiar setting of Bell inequalities from Physics. I will describe how a combination of classical techniques, such as the PCP theorem, and insights unique to quantum computing, such as the uncertainty principle, lead to protocols for testing randomness, entanglement, and quantum computations.
In the second part of the talk I will focus on a more recent model where testing is done under a post-quantum computational assumption. We will show how a hardness assumption can serve as an effective "classical leash" on a powerful quantum system.
The two most relevant publications for the talk are arXiv:2001.04383 and arXiv:1804.00640.
For anyone interested in broader-audience accounts, I can suggest:
* An article I wrote for the notices of the AMS in 2019, which motivates the study of quantum multiprover interactive proofs from a mathematical (operator algebras) angle:
https://www.ams.org/journals/notices/201910/rnoti-p1618.pdf
* An article published in the Bulletin of the AMS on the topic of the second part of the talk, verification under computational assumptions:
http://users.cms.caltech.edu/~vidick/notes/verification_bulletin.pdf.
Thomas Vidick is Professor of Computing and Mathematical Sciences at the California Institute of Technology. He received a B.A.
in pure mathematics from École Normale Supérieure in Paris, a Masters in Computer Science from Université Paris 7 and a Ph.D. from UC Berkeley.
His Ph.D. thesis was awarded the Bernard Friedman memorial prize in applied mathematics. Before joining Caltech he was a postdoctoral associate at the Massachusetts Institute of Technology. His paper “A multi-prover interactive proof for NEXP sound against entangled provers”, with Tsuyoshi Ito, was co-awarded the best paper award at FOCS’12. His is the recipient of a Presidential Early-Career Award (PECASE, 2019), an FSMP research chair (2020) and a Simons Investigator Award (2021-).
Vidick's research is situated at the interface of theoretical computer science, quantum information and cryptography. He is interested in applying techniques from computer science, such as complexity theory, to study problems in quantum computing. He is most well-known for his work on the study of entanglement in interactive proof systems, through the complexity class MIP*. He made multiple contributions to quantum cryptography, including the first proof of security of device-independent quantum key distribution. He is also known for developing the first polynomial-time algorithm for computing ground states of gapped one-dimensional quantum spin systems.
Bio
Thomas Vidick is Professor of Computing and Mathematical Sciences at the California Institute of Technology. He received a B.A.
in pure mathematics from École Normale Supérieure in Paris, a Masters in Computer Science from Université Paris 7 and a Ph.D. from UC Berkeley.
His Ph.D. thesis was awarded the Bernard Friedman memorial prize in applied mathematics. Before joining Caltech he was a postdoctoral associate at the Massachusetts Institute of Technology. His paper “A multi-prover interactive proof for NEXP sound against entangled provers”, with Tsuyoshi Ito, was co-awarded the best paper award at FOCS’12. His is the recipient of a Presidential Early-Career Award (PECASE, 2019), an FSMP research chair (2020) and a Simons Investigator Award (2021-).
Vidick's research is situated at the interface of theoretical computer science, quantum information and cryptography. He is interested in applying techniques from computer science, such as complexity theory, to study problems in quantum computing. He is most well-known for his work on the study of entanglement in interactive proof systems, through the complexity class MIP*. He made multiple contributions to quantum cryptography, including the first proof of security of device-independent quantum key distribution. He is also known for developing the first polynomial-time algorithm for computing ground states of gapped one-dimensional quantum spin systems.
More information
Practical information
- General public
- Free
Contact
- Host: Rüdiger Urbanke