Sequential measurements, disturbance and property testing

Aram W. Harrow, Cedric Yen Yu Lin, Ashley Montanaro

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

17 Citations (Scopus)
298 Downloads (Pure)


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 languageEnglish
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
PublisherSociety for Industrial and Applied Mathematics
Number of pages14
ISBN (Electronic)9781611974782
ISBN (Print)9781510836358
Publication statusPublished - 31 Mar 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: 16 Jan 201719 Jan 2017


Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Structured keywords

  • QITG
  • Bristol Quantum Information Institute


Dive into the research topics of 'Sequential measurements, disturbance and property testing'. Together they form a unique fingerprint.

Cite this