Projects per year
Abstract
We describe two procedures which, given access to one copy of a quantum state and a sequence of twooutcome measurements, can distinguish between the case that at least one of the measurements accepts the state with high probability, and the case that all of the measurements have low probability of acceptance. The measurements cannot simply be tried in sequence, because early measurements may disturb the state being tested. One procedure is based on a variant of MarriottWatrous amplification. The other procedure is based on the use of a test for this disturbance, which is applied with low probability. We find a number of applications:Quantum query complexity separations in the property testing model for testing isomorphism of functions under group actions. We give quantum algorithms for testing isomorphism, linear isomorphism and affine isomorphism of boolean functions which use exponentially fewer queries than is possible classically, and a quantum algorithm for testing graph isomorphism which uses polynomially fewer queries than the best algorithm known. Testing properties of quantum states and operations. We show that any finite property of quantum states can be tested using a number of copies of the state which is logarithmic in the size of the property, and give a test for genuine multipartite entanglement of states of n qubits that uses O(n) copies of the state. We also show that equivalence of two unitary operations under conjugation by a unitary picked from a fixed set can be tested efficiently. This is a natural quantum generalisation of testing isomorphism of boolean functions. Correcting an error in a result of Aaronson on demerlinizing quantum protocols. This result claimed that, in any oneway quantum communication protocol where two parties are assisted by an allpowerful but untrusted third party, the third party can be removed with only a modest increase in the communication cost. We give a corrected proof of a key technical lemma required for Aaronson's result.
Original language  English 

Title of host publication  28th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2017 
Publisher  Society for Industrial and Applied Mathematics 
Pages  15981611 
Number of pages  14 
ISBN (Electronic)  9781611974782 
ISBN (Print)  9781510836358 
DOIs  
Publication status  Published  31 Mar 2017 
Event  28th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2017  Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 
Conference
Conference  28th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2017 

Country/Territory  Spain 
City  Barcelona 
Period  16/01/17 → 19/01/17 
Structured keywords
 QITG
 Bristol Quantum Information Institute
Fingerprint
Dive into the research topics of 'Sequential measurements, disturbance and property testing'. Together they form a unique fingerprint.Projects
 2 Finished
Profiles

Professor Ashley M R Montanaro
 School of Mathematics  Professor of Quantum Computation
 The Bristol Centre for Nanoscience and Quantum Information
 Algorithms and Complexity
 Mathematical Physics
 Quantum Information Theory
Person: Academic , Member, Group lead