Sequential measurements, disturbance and property testing

DOI10.1137/1.9781611974782.105MaRDI QIDQ4575848zbMATH OpenOpenAlexFDO

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

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.03236

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

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. First, 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. Second, 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. Third, correcting an error in a result of Aaronson on de-Merlinizing 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.

Recommendations

• New results on quantum property testing
• Testing product states, quantum Merlin-Arthur games and tensor optimization
• Quantum algorithms for testing properties of distributions
• The efficiency of quantum identity testing of multiple states
• Testing Boolean functions properties

Cited in

(9)

• Testing product states, quantum Merlin-Arthur games and tensor optimization
• Improved quantum data analysis
• Shadow tomography of quantum states
• New results on quantum property testing
• Union bound for quantum information processing
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
• The efficiency of quantum identity testing of multiple states
• scientific article; zbMATH DE number 7561520 (Why is no real title available?)
• Nonlinear sequences for annular testing of discrete devices

This page was built for publication: Sequential measurements, disturbance and property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575848)