Projects per year

### Abstract

We describe two procedures which, given access to one copy of a quantum state and a sequence of two-outcome 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 Marriott-Watrous 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 one-way quantum communication protocol where two parties are assisted by an all-powerful 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 ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 |

Publisher | Society for Industrial and Applied Mathematics |

Pages | 1598-1611 |

Number of pages | 14 |

ISBN (Electronic) | 9781611974782 |

ISBN (Print) | 9781510836358 |

DOIs | |

Publication status | Published - 31 Mar 2017 |

Event | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 |

### Conference

Conference | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 |
---|---|

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

## Dr Ashley M R Montanaro

- School of Mathematics - Reader in Quantum Computation
- The Bristol Centre for Nanoscience and Quantum Information
- Theory and Algorithms
- Mathematical Physics
- Quantum Information Theory

Person: Academic , Member, Group lead

## Cite this

*28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017*(pp. 1598-1611). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974782.105