2016 André Aisenstadt Prize in Mathematics Recipient
Anne Broadbent (University of Ottawa)
[ français ]
Anne Boadbent : lecture on September 23, 2016.
Slideshow of the lecture
Centre de recherches mathématiques
Université de Montréal
16:00 - 17:00
Anne Broadbent's presentation will be in French, with slides in English.
How to Verify a Quantum Computation
Experimental implementations of quantum computers are in their infancy, but already we are faced with the following conundrum: if quantum computers are exponentially more powerful than their classical counterparts, how can we verify the outcome of a quantum computation? In this context, the scientific method of "predict and verify" appears to fail dramatically: these computations are so complex that they are impossible to predict! For a solution to this problem, we turn to theoretical computer science, where it is well established that interaction dramatically increases the power of a verification process.
We give a new interactive protocol for the verification of quantum computations in the regime of high computational complexity. Our results are given in the language of quantum interactive proof systems. Specifically, we show that any language in BQP has a quantum interactive proof system with a polynomial-time classical verifier (who can also prepare random single-qubit pure states), and a quantum polynomial-time prover. Here, soundness is unconditional--i.e. it holds even for computationally unbounded provers. Compared to prior work, our technique does not require the encoding of the input or of the computation; instead, we rely on encryption of the input (together with a method to perform computations on encrypted data), and show that the random choice between three types of input (defining a computational run, versus two types of test runs) suffice. Because the overhead is linear, this shows that verification could be achieved at minimal cost. We also present a new soundness analysis, based on a reduction to an entanglement-based protocol.
Coffee will be served before the conference and a reception will follow at Salon Maurice-L'Abbé (Room 6245).
The International Scientific Advisory Committee of the Centre de recherches mathématiques (CRM) is pleased to announce that Anne Broadbent of the University of Ottawa is the 2016 André Aisenstadt Prize recipient.
Dr. Broadbent earned her PhD from the Université de Montréal in 2008, under the joint supervision of Alain Tapp and Gilles Brassard. Her doctoral thesis “Quantum nonlocality, cryptography and complexity” was distinguished by multiple prizes, including an NSERC Doctoral Prize by the Natural Sciences and Engineering Research Council of Canada. She went on to win the prestigious John Charles Polanyi Prize in Physics in 2010. Dr. Broadbent continued her research at the Institute for Quantum Computing of the University of Waterloo, first as an NSERC Postdoctoral Fellow, and then as a CIFAR (Canadian Institute for Advanced Research) Global Scholar (2011-2013). In January 2014, Dr. Broadbent joined the Department of Mathematics and Statistics at the University of Ottawa, where she holds the University Research Chair in Quantum Information.
Dr. Broadbent is a leader in the field of Quantum Information and cryptography. In 2009, she and her co-authors introduced the concept of blind quantum computation – roughly, using quantum properties to permit third parties to perform extensive computations on data without jeopardizing the secrecy of the data. These highly-cited papers launched new important research directions in quantum information processing, including her current ground-breaking work on quantum homomorphic encryption. Other significant contributions she has made to this field include characterizing quantum one-time programs and presenting a novel automated technique for parallelizing quantum circuits.