Quantum proofs of proximity

Preview	PDF WRAP-Quantum-proofs-proximity-22.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1MB) | Preview
	PDF dcs-010922-wrap--2105.03697.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (560kB)

Request Changes to record.

Abstract

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity
(QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property Π and reject inputs that are ε-far from Π, while only probing a minuscule portion of their input.
We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).
Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable. A consequence of this framework is a QMA algorithm to verify the Parity of an n-bit string with
O(n2/3) queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.

Request changes or add full text files to a record

Repository staff actions (login required)

View Item